Please enable JavaScript.
Coggle requires JavaScript to display documents.
Query Optimization - Coggle Diagram
Query Optimization
Optimizer
Input: parsed query = relational algebra (RA)
Plan/RA Trees generator + Plan cost estimator => System Catalog
Output: query plan, may not the best (
annotated RA tree
)
Annotated RA Tree
: sort merge join? hash join?
Query Plan Cost Estimation
Process
Estimate cost of each operation on (input size + algorithm)
Estimate size of intermediate results on (input relations)
System catalog
number of tuples (cardinality);
size in pages;
number of distinct keys;
range
histograms
materialize
: write intermediate result to disk
pipeline
pipeline result to next operator without writing to disk
no read/write to disk for temporary relation
overlap execution of operators (JOIN + SELECT)
left-deep join
: BNLJ, left child = outer relation
Generate Query Plans
Many possibilities
RA has rules to get equivalent expressions
Push down selections
through projections, joins, other selections
make sure the right branch
sometimes, cannot push up, lose projection attributes
can always push through selection
may not push joins, when selection over joined attributes
Push down projections
through selection and joins
to throw out useless attributes and have less data
most cases: want selection and projections early
=> fewer tuples in intermediate steps
Reorder join
commutativity
associativity
intermediate result as small as possible
=> equi join / common attribute
left-deep join
selections and joins can be evaluated in any order
Get many alternative query plans