On estimation of the cost of relational query evaluation plans (optimization, dbms)
Mohammad Dadashzadeh · 1985
The problem of relational query optimization is to select the least expensive program to evaluate a query expressed in logical terms from among the alternative ways it can be carried out in the physical database. This thesis addresses the subproblem of estimating the cost (i.e., number of page accesses) of relational query evaluation programs. The approach chosen is based on a framework consisting of three pieces. The first part develops an intermediate level language acting as a target language for the query optimizer. This language, the Stream Processor Network representation, is conceived as an abstract machine consisting of a collection of independent processors with private workspace that operate on streams of records in a data-driven fashion. The second part is concerned with cost analysis for the various stream processors of the SPN model in light of the size of the available workspace. The third part deals with estimation of the statistical parameters associated with the cost equations. The SPN model goes farther than the previous work in modeling of relational query evaluation programs by accomodating arbitrary relational queries, capturing complex evaluation strategies, and facilitating the iterative nature of the query optimizer's task through its additive cost property. This thesis also introduces the Grouped Generalized Division relational operation and gives an algorithm for converting an arbitrary SQL query into relational algebra.