Access path selection in a relational database management system

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. Access path selection in a relational database management system. SIGMOD, 1979.

Databases are one of the backbones of our applications, we use them daily but probably we didn't stop to analyze how things works under the hood. We take for granted that given some declarative query (i.e with SQL), the RDBMS will try to be as efficient as possible. This enables data-independent query processing, back in the day with systems like IMS queries were done using low level information, so knowledge about the underlying data structures was needed to be able to perform efficient queries. The presented paper is the foundation for query optimization field, it decomposes the problem into three distinct subproblems:

• Cost estimation
• Relational equivalences
• Cost-based search

We'll explore how solving those sub-problems databases are able to calculate "good-enough" query plans.