DATABASE MANAGEMENT SYSTEMS Part Iv QUERY EVALUATION 11 EXTERNAL SORTING 01 11.1 A Simple Two-Way Merge Sort 11.2 External Merge Sort 11.2.1 Minimizing the Number of runs 11.3 Minimizing I/O Cost versus Number of I/Os 11.3.1 Blocked I/O 310 11.3.2 Double Buffering 1.4 Using B+ Trees for Sorting 312 11.4.1 Clustered Index 312 11.4.2 Unclustered index 11.5 Points to review 315 12 EVALUATION OF RELATIONAL OPERATORS 319 12.1 Introduction to Query Processing 2.1.1 Access paths 12.1.2 Preliminaries: Examples and Cost Calculations 12.2 The Selection Operation 12.2.1 No Index. Unsorted Data 12.2.2 No Index Sorted Data 12.2.3 B+ Tree Index 12.2.4 Hash Index, Equality Selection 12.3 General Selection Conditions 12.3.1 CNF and Index Matching 325 12.3.2 Evaluating Selections without Disjunction 12.3.3 Selections with Disjunction 12.4 The Projection Operation 12.4.1 Projection Based on Sorting 7990 12.4.2 Projection Based on Hashing 12.4.3 Sorting versus Hashing for Projections 12.4.4 Use of Indexes for Projection 12.5 The Join Operation 12.5.1 Nested Loops join 12.5.2 Sort-Merge Join 12.5.3 Hash Join 12. 5. 4 General Join Conditions 12.6 The Set Operations 12.6.1 Sorting for Union and Difference 38990 12.6.2 Hashing for Union and Difference Aggregate Operations 12.7.1 Implementing Aggregation by Using an Index The Impact of Buffering 352xii Database Management Systems Part IV QUERY EVALUATION 299 11 EXTERNAL SORTING 301 11.1 A Simple Two-Way Merge Sort 302 11.2 External Merge Sort 305 11.2.1 Minimizing the Number of Runs * 308 11.3 Minimizing I/O Cost versus Number of I/Os 309 11.3.1 Blocked I/O 310 11.3.2 Double Buffering 311 11.4 Using B+ Trees for Sorting 312 11.4.1 Clustered Index 312 11.4.2 Unclustered Index 313 11.5 Points to Review 315 12 EVALUATION OF RELATIONAL OPERATORS 319 12.1 Introduction to Query Processing 320 12.1.1 Access Paths 320 12.1.2 Preliminaries: Examples and Cost Calculations 321 12.2 The Selection Operation 321 12.2.1 No Index, Unsorted Data 322 12.2.2 No Index, Sorted Data 322 12.2.3 B+ Tree Index 323 12.2.4 Hash Index, Equality Selection 324 12.3 General Selection Conditions * 325 12.3.1 CNF and Index Matching 325 12.3.2 Evaluating Selections without Disjunction 326 12.3.3 Selections with Disjunction 327 12.4 The Projection Operation 329 12.4.1 Projection Based on Sorting 329 12.4.2 Projection Based on Hashing * 330 12.4.3 Sorting versus Hashing for Projections * 332 12.4.4 Use of Indexes for Projections * 333 12.5 The Join Operation 333 12.5.1 Nested Loops Join 334 12.5.2 Sort-Merge Join * 339 12.5.3 Hash Join * 343 12.5.4 General Join Conditions * 348 12.6 The Set Operations * 349 12.6.1 Sorting for Union and Difference 349 12.6.2 Hashing for Union and Difference 350 12.7 Aggregate Operations * 350 12.7.1 Implementing Aggregation by Using an Index 351 12.8 The Impact of Buffering * 352