Contents 12.9 Points to review 13 INTRODUCTION TO QUERY OPTIMIZATION 359 3.1 Overview of Relational Query Optimization 13.1.1 Query Evaluation Plans 13.1.2 Pipelined Evaluation 13.1.3 The Iterator Interface for Operators and Access Methods 13.1.4 The System R Optimizer 3.2 System Catalog in a Relational DBMS 365 3.2.1 Information Stored in the System Catalog 3.3 Alternative Plans: A Motivating Example 13.3.1 Pushing selections 13.3.2 Using Indexes 13.4 Points to review 14 A TYPICAL RELATIONAL QUERY OPTIMIZER 37 14.1 Translating SQL Queries into Algebra 14.1.1 Decomposition of a Query into Blocks 375 14.1.2 A Query Block as a Relational Algebra Expression 14.2 Estimating the Cost of a Plan 378 14.3 Relational Algebra Equivalences 383 14.3.1 Selections 14.3.2 Projections 14.3.3 Cross-Products and joins 384 14.3.4 Selects, Projects, and Joins 14.3.5 Other Equivalences 387 14.4 Enumeration of Alternative plans 14.4.1 Single-Relation Queries 14.4.2 Multiple-Relation Queries 14.5 Nested Subqueries 14.6 Other Approaches to Query Optimization 14.7 Points to review Part V DATABASE DESIGN 415 15 SCHEMA REFINEMENT AND NORMAL FORMS 417 15.1.1 Problems Caused by Redundancy 418 15.1.2 Use of Decompositions 5.1.3 Problems Related to Decomposition 15.2 Functional Dependencies 15.3 Examples Motivating Schema RefinementContents xiii 12.9 Points to Review 353 13 INTRODUCTION TO QUERY OPTIMIZATION 359 13.1 Overview of Relational Query Optimization 360 13.1.1 Query Evaluation Plans 361 13.1.2 Pipelined Evaluation 362 13.1.3 The Iterator Interface for Operators and Access Methods 363 13.1.4 The System R Optimizer 364 13.2 System Catalog in a Relational DBMS 365 13.2.1 Information Stored in the System Catalog 365 13.3 Alternative Plans: A Motivating Example 368 13.3.1 Pushing Selections 368 13.3.2 Using Indexes 370 13.4 Points to Review 373 14 A TYPICAL RELATIONAL QUERY OPTIMIZER 374 14.1 Translating SQL Queries into Algebra 375 14.1.1 Decomposition of a Query into Blocks 375 14.1.2 A Query Block as a Relational Algebra Expression 376 14.2 Estimating the Cost of a Plan 378 14.2.1 Estimating Result Sizes 378 14.3 Relational Algebra Equivalences 383 14.3.1 Selections 383 14.3.2 Projections 384 14.3.3 Cross-Products and Joins 384 14.3.4 Selects, Projects, and Joins 385 14.3.5 Other Equivalences 387 14.4 Enumeration of Alternative Plans 387 14.4.1 Single-Relation Queries 387 14.4.2 Multiple-Relation Queries 392 14.5 Nested Subqueries 399 14.6 Other Approaches to Query Optimization 402 14.7 Points to Review 403 Part V DATABASE DESIGN 415 15 SCHEMA REFINEMENT AND NORMAL FORMS 417 15.1 Introduction to Schema Refinement 418 15.1.1 Problems Caused by Redundancy 418 15.1.2 Use of Decompositions 420 15.1.3 Problems Related to Decomposition 421 15.2 Functional Dependencies 422 15.3 Examples Motivating Schema Refinement 423