The optimization of queries in relational databases

TLDR

The paper presents a fully implemented system for optimizing and executing queries in relational databases. The system optimizes n‑table equi‑join QUEL queries for INGRES by modeling execution plans as binary trees of four operator types and using attribute‑distribution histograms to estimate costs, with extensive performance measurements. The system achieves at least tenfold speedups over INGRES, with accurate histogram‑based cost estimates yielding roughly 30% faster queries than uniform assumptions, and the model subsumes many existing algorithms.

Abstract

A fully implemented system for optimizing and executing queries for relational databases is described. The system optimizes n-table, equi-join queries written in QUEL, the query language supported by the INGRES relational database management system (DBMS). Tenfold and greater improvements in response time to complex queries have been achieved compared to INGRES. The system models query execution plans as binary trees where each node can be one of four operator types: join, restrict-project, reformat and disk-resident-scan. This model is shown to include many previously published algorithms in addition to many new ones. The system also uses histograms to represent information about attribute's distributions. This information is used to accurately determine query execution cost and results in queries which run approximately thirty percent faster than when the distributional information is not used (i.e., uniform distributions are assumed). Measurements are given comparing execution times for the new system and INGRES, comparing estimated and actual disk I/O with actual query execution time, and comparing the use of accurate distributional information stored in histograms with the use of uniform distributions.