DATA3404 Lecture Notes - Lecture 7: Relational Algebra, Plans, European Cooperation In Science And Technology
22 Jun 2020
School
Department
Course
Professor
Document Summary
Two main issues: for a given query, what plans are considered, algorithm to search plan space for cheapest (estimated) plan, how is the cost of a plan estimated, alternative: rule-based optimization. Two relational algebra expressions are said to be equivalent if on every legal database instance, the two expressions generate the same set of tuples: note: order of tuples is irrelevant. Joins are associative: r (s t) (s r) t: filtering and projections before and after join is equivalent; pushing down. Join optimization: a join over n+1 relations r1,,rn+1 requires n binary joins. Its root-level operator joins sub-plans of k and n k 1 join operators (0 k n 1) Let ck be the number of possibilities to construct a binary tree of i inner nodes (join operators): the resulting search space is enormous: Left-deep join plan s: to master this search space, fundamental decision in system r (the father of all query optimizers): only left-deep join trees are considered.
