The optimization of queries in relational databases
Robert Philip Kooi · 1980
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.