Access Path Selection In Modern Data Systems

Access path selection has always been a key component of database systems. Having the choice between a secondary index scan and a scan of the base data allows systems to utilize the best possible access path by taking into account run-time characteristics at optimization time. A scan over the base data has to scan everything while a secondary index scan only has to access an auxiliary copy of the data which is smaller and has more structure. Secondary indexes, typically in the form of B+-Trees, have been extensively used in row-oriented systems to access the desired values, with neither the overhead of reading the unneeded values nor their associated neighboring attributes. The decision of access path selection is typically based on a fixed selectivity threshold which accounts for the idiosyncrasies of the specific database system, its access path design, and its hardware properties.

This project seeks to understand the trade offs between access paths in modern systems. In particular, the way the choice between access paths changes as software is optimized and new hardware is introduced.

RUM Aware Data Structures

The database research community has been building methods to store, access, and update data for more than four decades. Throughout the evolution of the structures and techniques used to access data, access methods adapt to the ever changing hardware and workload requirements. Today, even small changes in the workload or the hardware lead to redesigning access methods. This phenomenon has reached its peak as data generation and workload diversification grow exponentially, and hardware advances introduce increased complexity. New workload requirements are introduced by the emergence of new applications, and data is managed by large systems composed of more and more complex and heterogeneous hardware. As a result, it is increasingly important to develop application-aware and hardware-aware access methods.

2018

Hentschel B, Kester MS, and Idreos S. "Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation", Proceedings of the International Conference on Management of Data (SIGMOD 18). Houston, TX.
pdf bibtex

Idreos S, Zoumpatianos K, Hentschel B, Kester MS, and Guo D. "The Data Calculator: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models", Proceedings of the International Conference on Management of Data (SIGMOD 18). Houston, TX.
pdf bibtex

Idreos S, Zoumpatianos K, Athanassoulis M, Dayan N, Hentschel B, Kester MS, Guo D, Maas L, Qin W, Wasay A, Sun Y. "The Periodic Table of Data Structures", IEEE Data Engineering Bulletin.
pdf bibtex

2017

Kester MS, Athanassoulis M, Idreos S. "Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?", Proceedings of the International Conference on Management of Data (SIGMOD 17). Chicago, IL.
pdf bibtex

2016

Athanassoulis M, Kester MS, Maas L, Idreos S. "Designing Access Methods: The RUM Conjecture", Proceedings of the 19th International Conference on Extending Database Technology (EDBT 16). Bordeaux, France.
pdf bibtex

2014

Kate B, Kohler E, Kester MS, Narula N, Mao Y, Morris R. "Easy Freshness with Pequod Cache Joins", in 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14). Seattle, WA.
pdf bibtex

2011

Lee JW, Kester MS, Schulzrinne H. "Follow the River and You Will Find the C", in Proceedings of the 42Nd ACM Technical Symposium on Computer Science Education (SIGCSE 11). New York, NY.
pdf bibtex