System-R Optimizer: Query Optimization and Cost Estimation

This lecture covers the System-R Optimizer, a seminal project from the 70s with a significant influence on subsequent database systems. It explains the high-level idea of iterating over possible plans, estimating costs, and returning the cheapest to the user. The lecture details the steps involved in breaking queries into blocks, generating logical operators, and selecting the best access paths for tables. It also delves into join orderings, cost estimation, and the principle of optimality in query optimization. The instructor emphasizes the importance of interesting orders, selectivity estimates, and the challenges in cardinality estimation. The lecture concludes with a summary of the System R optimizer, highlighting its reliance on heuristics and cost-based optimization.