chapter15: Query Processing

Abstract

1 Basic Steps in Query Processing

经过语法分析、语义检查翻译成关系表达式，经过查询优化转化成执行计划（目标代码），由求值引擎得到输出。

Example

2 Measures Of Query Cost

3 Selection Operation

3.1 file scan

3.2 index scan

3.3 Bitmap Index Scan

4 Sorting

• We may build an index on the relation, and then use the index to read the relation in sorted order. May lead to one disk block access for each tuple.
• For relations that fit in memory, techniques like quicksort can be used.
• For relations that don’t fit in memory,external sort-merge is a good choice.

Example

4.1 Procedure

4.2 Cost Analysis

4.3 New Version

5 Join Operation

5.1 Nested-Loop Join

5.2 Block Nested-Loop Join

5.3 Indexed Nested-Loop Join

Example

5.4 Merge-Join

5.5 Hash-Join

Cost

Example

5.5.1 Recursive partitioning

5.5.2 Cost Of Hash-Join