Technical Reports
HPL-2010-23
Adaptive indexing for relational keys
Graefe, Goetz; Kuno, Harumi
HP Laboratories
HPL-2010-23
Keyword(s): databases, indexes, storage systems, B-trees, adaptive merging, database cracking
Abstract: Adaptive indexing schemes such as database cracking and adaptive merging have been investigated to-date only in the context of range queries. These are typical for non-key columns in relational databases. For complete self-managing indexing, adaptive indexing must also apply to key columns. The present paper proposes a design and offers a first performance evaluation in the context of keys. Adaptive merging for keys also enables further improvements in B-tree indexes. First, partitions can be matched to levels in the memory hierarchy such as a CPU cache and an in- memory buffer pool. Second, adaptive merging in merged B-trees enables automatic master-detail clustering.
6 Pages
Additional Publication Information: To be published and presented at SMDB 2010, Long Beach, CA, March 1, 2010
External Posting Date: February 6, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: February 6, 2010 [Fulltext]