More and more modern computer applications, from business decision support to scientific data analysis, utilize visualization techniques to support exploratory activities. Various tools have been proposed in the past decade to help users better interpret data using such display techniques. However, most do not scale well with regard to the size of the dataset upon which they operate. In particular, the level of cluttering on the screen is typically unacceptable and the performance is poor. To solve the problem of cluttering at the interface level, visualization tools have recently been extended to support hierarchical views of the data, with support for focusing and drilling-down using interactive brushes. To solve the scalability problem, we now investigate how best to couple such a visualization tool with a database management system without losing the real-time characteristics. This integration must be done carefully, since visual user interactions implemented as main memory operations do not map directly into efficient database operations. The main efficiency issue when doing this integration is to avoid the recursive processing required for hierarchical data retrieval. For this problem, we have develop a tree labeling method, called MinMax tree, that allows the movement of the on-line recursive processing into an off-line precomputation step. Thus, at run time, the recursive processing operations translate into linear cost range queries. Secondly, we employ a main memory access strategy to support incremental loading of data into the main memory. The techniques have been incorporated into XmdvTool, a multidimensional visual exploration tool, in order to achieve scalability. The tool now successfully scales up to datasets of the order 10^5-10^7 records. Lastly, we report experimental results that illustrate the impact of the proposed techniques on the system's overall performance.