Cortex: Harnessing Correlations to Boost Query Performance
This work addresses the problem of efficiently speeding up database queries on non-indexed attributes for database systems, offering an incremental improvement over existing indexing techniques.
The paper introduces Cortex, a novel approach that leverages correlations to extend the benefits of primary indexes to more attributes. Cortex achieves this by adapting to existing primary indexes and harnessing various types of correlations, resulting in 2-8x faster performance than existing correlation indexing methods and using 5x less space than traditional secondary indexes.
Databases employ indexes to filter out irrelevant records, which reduces scan overhead and speeds up query execution. However, this optimization is only available to queries that filter on the indexed attribute. To extend these speedups to queries on other attributes, database systems have turned to secondary and multi-dimensional indexes. Unfortunately, these approaches are restrictive: secondary indexes have a large memory footprint and can only speed up queries that access a small number of records, and multi-dimensional indexes cannot scale to more than a handful of columns. We present Cortex, an approach that takes advantage of correlations to extend the reach of primary indexes to more attributes. Unlike prior work, Cortex can adapt itself to any existing primary index, whether single or multi-dimensional, to harness a broad variety of correlations, such as those that exist between more than two attributes or have a large number of outliers. We demonstrate that on real datasets exhibiting these diverse types of correlations, Cortex matches or outperforms traditional secondary indexes with $5\times$ less space, and it is $2-8\times$ faster than existing approaches to indexing correlations.