Chapter 15: Query Processing

Topic: Query Processing (Page 689)
- Subtopic: Overview (Page 689)
  - Mini-topic: Steps in Query Processing (Page 689)
    - Micro-topic: Parsing and translation (Page 689)
    - Micro-topic: Optimization (Page 689)
    - Micro-topic: Evaluation (Page 689)
  - Mini-topic: Figure 15.1 Steps in query processing. (Page 690)
  - Mini-topic: Relational-Algebra Expressions (Page 690)
  - Mini-topic: Query Evaluation Plan (Page 691)
  - Mini-topic: Query Optimization (Page 691)
  - Mini-topic: Figure 15.2 A query-evaluation plan. (Page 691)
- Subtopic: Measures of Query Cost (Page 692)
  - Mini-topic: Disk Access Costs (Page 692)
  - Mini-topic: SSDs vs. Magnetic Disks (Page 692)
  - Mini-topic: CPU Costs (Page 692)
  - Mini-topic: Block Transfer Time (tT) and Seek Time (tS) (Page 692)
  - Mini-topic: Buffer size (Page 694)
  - Mini-topic: Response Time vs. Resource Consumption (Page 694)
- Subtopic: Selection Operation (Page 695)
  - Mini-topic: File Scan (Page 695)
  - Mini-topic: Index Scan (Page 695)
  - Mini-topic: Algorithms for Selection (Page 695)
    Title
    
    Micro-topic: A1 (linear search) (Page 695)
    
    Micro-topic: A2 (clustering index, equality on key) (Page 697)
    
    Micro-topic: A3 (clustering index, equality on non-key) (Page 697)
    
    Micro-topic: A4 (secondary index, equality) (Page 697)
    
    Micro-topic: A5 (clustering index, comparison) (Page 698)
    
    Micro-topic: A6 (secondary index, comparison) (Page 698)
    Link to original
  - Mini-topic: Figure 15.3 Cost estimates for selection algorithms. (Page 696)
  - Mini-topic: Bitmap Index Scan (Page 698)
- Subtopic: Selections Involving Comparisons (Page 698)
- Subtopic: Implementation of Complex Selections (Page 699)
  - Mini-topic: Conjunction (Page 699)
  - Mini-topic: Disjunction (Page 699)
  - Mini-topic: Negation (Page 699)
  - Mini-topic: Algorithms (Page 699)
    - Micro-topic: A7 (conjunctive selection using one index) (Page 699)
    - Micro-topic: A8 (conjunctive selection using composite index) (Page 700)
    - Micro-topic: A9 (conjunctive selection by intersection of identifiers) (Page 700)
    - Micro-topic: A10 (disjunctive selection by union of identifiers) (Page 700)
- Subtopic: Sorting (Page 701)
  Title
  Mini-topic: External Sort-Merge Algorithm (Page 701)
  
  Micro-topic: Figure 15.4 External sorting using sort-merge. (Page 703)
  
  Mini-topic: Cost Analysis of External Sort-Merge (Page 702)
  Link to original
- Subtopic: Join Operation (Page 704)
  - Mini-topic: Nested-Loop Join (Page 704)
    - Micro-topic: Figure 15.5 Nested-loop join. (Page 705)
  - Mini-topic: Block Nested-Loop Join (Page 705)
    - Micro-topic: Figure 15.6 Block nested-loop join. (Page 706)
  - Mini-topic: Indexed Nested-Loop Join (Page 707)
  - Mini-topic: Merge Join (Page 708)
    - Micro-topic: Merge-Join Algorithm (Page 708)
      - Micro-topic: Figure 15.7 Merge join. (Page 709)
      - Micro-topic: Figure 15.8 Sorted relations for merge join. (Page 710)
    - Micro-topic: Cost Analysis (Page 710)
  - Mini-topic: Hybrid Merge Join (Page 712)
  - Mini-topic: Hash Join (Page 712)
    Hash Join
    
    Micro-topic: Basics (Page 712)
    
    Micro-topic: Figure 15.9 Hash partitioning of relations. (Page 713)
    
    Micro-topic: Figure 15.10 Hash join. (Page 714)
    
    Micro-topic: Recursive Partitioning (Page 714)
    
    Micro-topic: Handling of Overflows (Page 715)
    
    Micro-topic: Cost of Hash Join (Page 715)
    Link to original
  - Mini-topic: Hybrid Hash Join (Page 717)
  - Mini-topic: Complex Joins (Page 718)
- Subtopic: Joins over Spatial Data (Page 719)
- Subtopic: Other Operations (Page 719)
  - Mini-topic: Duplicate Elimination (Page 719)
  - Mini-topic: Projection (Page 720)
  - Mini-topic: Set Operations (Page 720)
  - Mini-topic: Outer Join (Page 722)
  - Mini-topic: Aggregation (Page 723)
- Subtopic: Evaluation of Expressions (Page 724) *
  Evaluation of Expressions
  Mini-topic: Materialization (Page 724)
  
  Micro-topic: Figure 15.11 Pictorial representation of an expression. (Page 724)
  
  Mini-topic: Pipelining (Page 725)
  
  Micro-topic: Implementation of Pipelining (Page 726)
  
  Micro-topic: Evaluation Algorithms for Pipelining (Page 728)
  
  Micro-topic: Figure 15.12 Query plan with pipelining. (Page 729)
  
  Micro-topic: Figure 15.13 Double-pipelined join algorithm. (Page 730)
  
  Mini-topic: Pipelines for Continuous-Stream Data (Page 731)
  Link to original
- Subtopic: Query Processing in Memory (Page 731)
  - Mini-topic: Cache-Conscious Algorithms (Page 732)
  - Mini-topic: Query Compilation (Page 733)
  - Mini-topic: Column-Oriented Storage (Page 734)
Topic: Summary (Page 734)
Topic: Review Terms (Page 735)
Topic: Practice Exercises (Page 736)
Topic: Further Reading (Page 740)
Topic: Bibliography (Page 740)
Topic: Credits (Page 741)

Chapter 16: Query Optimization

Topic: Query Optimization (Page 743)
- Subtopic: Overview (Page 743)
  - Mini-topic: Figure 16.1 Equivalent expressions. (Page 744)
  - Mini-topic: Figure 16.2 An evaluation plan. (Page 745)
- Subtopic: Transformation of Relational Expressions (Page 747)
  - Mini-topic: Equivalence Rules (Page 747)
    - Micro-topic: Figure 16.3 Pictorial representation of equivalences. (Page 748)
  - Mini-topic: Examples of Transformations (Page 752)
    - Micro-topic: Figure 16.4 Multiple transformations. (Page 753)
  - Mini-topic: Join Ordering (Page 754)
  - Mini-topic: Enumeration of Equivalent Expressions (Page 755)
    - Micro-topic: Figure 16.5 Procedure to generate all equivalent expressions. (Page 756)
- Subtopic: Estimating Statistics of Expression Results (Page 757)
  - Mini-topic: Catalog Information (Page 758)
    - Micro-topic: Figure 16.6 Example of histogram. (Page 759)
  - Mini-topic: Selection Size Estimation (Page 760)
  - Mini-topic: Join Size Estimation (Page 762)
  - Mini-topic: Size Estimation for Other Operations (Page 764)
  - Mini-topic: Estimation of Number of Distinct Values (Page 765)
- Subtopic: Choice of Evaluation Plans (Page 766)
  - Mini-topic: Cost-Based Join-Order Selection (Page 767)
    - Micro-topic: Figure 16.7 Dynamic-programming algorithm for join-order optimization. (Page 768)
  - Mini-topic: Cost-Based Optimization with Equivalence Rules (Page 771)
  - Mini-topic: Heuristics in Optimization (Page 772)
    - Micro-topic: Figure 16.8 Left-deep join trees. (Page 773)
  - Mini-topic: Optimizing Nested Subqueries (Page 774)
- Subtopic: Materialized Views (Page 778)
  - Mini-topic: View Maintenance (Page 779)
  - Mini-topic: Incremental View Maintenance (Page 779)
    - Micro-topic: Join Operation (Page 780)
    - Micro-topic: Selection and Projection Operations (Page 780)
    - Micro-topic: Aggregation Operations (Page 781)
    - Micro-topic: Other Operations (Page 782)
    - Micro-topic: Handling Expressions (Page 782)
  - Mini-topic: Query Optimization and Materialized Views (Page 782)
  - Mini-topic: Materialized View and Index Selection (Page 783)
- Subtopic: Advanced Topics in Query Optimization (Page 783)
  - Mini-topic: Top-K Optimization (Page 784)
  - Mini-topic: Join Minimization (Page 784)
  - Mini-topic: Optimization of Updates (Page 784)
  - Mini-topic: Multiquery Optimization and Shared Scans (Page 785)
  - Mini-topic: Parametric Query Optimization (Page 786)
  - Mini-topic: Adaptive Query Processing (Page 786)
Topic: Summary (Page 787)
Topic: Review Terms (Page 788)
Topic: Practice Exercises (Page 789)
Topic: Further Reading (Page 794)
Topic: Bibliography (Page 794)
Topic: Credits (Page 795)

I hope this detailed breakdown is helpful! Let me know if you have any other questions.

2ndSem

Explorer

Query Processing table

Chapter 15: Query Processing

Chapter 16: Query Optimization

Graph View

Table of Contents

Backlinks