Paper Info
Title
Correlation maps: a compressed access method for exploiting soft functional dependencies
Abstract
In relational query processing, there are generally two choices for access paths when performing a predicate lookup for which no clustered index is available. One option is to use an unclustered index. Another is to perform a complete sequential scan of the table. Many analytical workloads do not benefit from the availability of unclustered indexes; the cost of random disk I/O becomes prohibitive for all but the most selective queries. It has been observed that a secondary index on an unclustered attribute can perform well under certain conditions if the unclustered attribute is correlated with a clustered index attribute [4]. The clustered index will co-locate values and the correlation will localize access through the unclustered attribute to a subset of the pages. In this paper, we show that in a real application (SDSS) and widely used benchmark (TPC-H), there exist many cases of attribute correlation that can be exploited to accelerate queries. We also discuss a tool that can automatically suggest useful pairs of correlated attributes. It does so using an analytical cost model that we developed, which is novel in its awareness of the effects of clustering and correlation. Furthermore, we propose a data structure called a Correlation Map (CM) that expresses the mapping between the correlated attributes, acting much like a secondary index. The paper also discusses how bucketing on the domains of both attributes in the correlated attribute pair can dramatically reduce the size of the CM to be potentially orders of magnitude smaller than that of a secondary B+Tree index. This reduction in size allows us to create a large number of CMs that improve performance for a wide range of queries. The small size also reduces maintenance costs as we demonstrate experimentally.
Year
DOI
Venue
2009
10.14778/1687627.1687765
PVLDB
Keywords
Field
DocType
secondary b,index attribute,unclustered index,access method,correlation map,small size,correlated attribute,unclustered attribute,attribute correlation,secondary index,tree index,correlated attribute pair,soft functional dependency,data structure,indexation,functional dependency
Data structure,Data mining,Access method,Computer science,Full table scan,Functional dependency,Correlation,Cluster analysis,Database index,Database
Journal
Volume
Issue
ISSN
2
1
2150-8097
Citations 
PageRank 
References 
17
0.76
14
Authors
5
Name
Order
Citations
PageRank
Hideaki Kimura157337.97
George Huo2613.12
Alexander Rasin32950209.48
Samuel Madden4161011176.38
Stanley B. Zdonik591861660.15