Multi-dimensional clustering: a new data layout scheme in DB2

ABSTRACT

We describe the design and implementation of a new data layout scheme, called multi-dimensional clustering, in DB2 Universal Database Version 8. Many applications, e.g., OLAP and data warehousing, process a table or tables in a database using a multi-dimensional access paradigm. Currently, most database systems can only support organization of a table using a primary clustering index. Secondary indexes are created to access the tables when the primary key index is not applicable. Unfortunately, secondary indexes perform many random I/O accesses against the table for a simple operation such as a range query. Our work in multi-dimensional clustering addresses this important deficiency in database systems. Multi-Dimensional Clustering is based on the definition of one or more orthogonal clustering attributes (or expressions) of a table. The table is organized physically by associating records with similar values for the dimension attributes in a cluster. We describe novel techniques for maintaining this physical layout efficiently and methods of processing database operations that provide significant performance improvements. We show results from experiments using a star-schema database to validate our claims of performance with minimal overhead.

REFERENCES

• 1: Method and System for Multi-Dimensional Clustering in a Relational Database System, 2002. Patent Filed, IBM Corp.
• 2: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 3: http://www.ibm.com/software/data/db2/library.
• 4: http://www.informix.com.
• 5: http://www.oracle.com.
• 6: Ralph Kimball, The data warehouse toolkit: practical techniques for building dimensional data warehouses, John Wiley & Sons, Inc., New York, NY, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Algorithms, Design, Experimentation, Performance