Database Management Systems: Chapter 3 - Algorithms for Query Processing and Optimization Introduction to Query Processing; Translating SQL Queries into Relational Algebra; Algorithms for External Sorting; Algorithms for SELECT and JOIN Operations;. | Chapter 3 Algorithms for Query Processing and Optimization Chapter Outline Introduction to Query Processing Translating SQL Queries into Relational Algebra Algorithms for External Sorting Algorithms for SELECT and JOIN Operations Algorithms for PROJECT and SET Operations Implementing Aggregate Operations and Outer Joins Combining Operations using Pipelining Using Heuristics in Query Optimization Using Selectivity and Cost Estimates in Query Optimization Overview of Query Optimization in Oracle Semantic Query Optimization Introduction to Query Processing Query optimization: the process of choosing a suitable execution strategy for processing a query. Two internal representations of a query – Query Tree – Query Graph Typical steps when processing a high-level query Translating SQL Queries into Relational Algebra (1) Query block: the basic unit that can be translated into the algebraic operators and optimized. A query block contains a single SELECT-FROM-WHERE expression, as | Chapter 3 Algorithms for Query Processing and Optimization Chapter Outline Introduction to Query Processing Translating SQL Queries into Relational Algebra Algorithms for External Sorting Algorithms for SELECT and JOIN Operations Algorithms for PROJECT and SET Operations Implementing Aggregate Operations and Outer Joins Combining Operations using Pipelining Using Heuristics in Query Optimization Using Selectivity and Cost Estimates in Query Optimization Overview of Query Optimization in Oracle Semantic Query Optimization Introduction to Query Processing Query optimization: the process of choosing a suitable execution strategy for processing a query. Two internal representations of a query – Query Tree – Query Graph Typical steps when processing a high-level query Translating SQL Queries into Relational Algebra (1) Query block: the basic unit that can be translated into the algebraic operators and optimized. A query block contains a single SELECT-FROM-WHERE expression, as well as GROUP BY and HAVING clause if these are part of the block. Nested queries within a query are identified as separate query blocks. Aggregate operators in SQL must be included in the extended algebra. Algorithms for External Sorting (1) External sorting : refers to sorting algorithms that are suitable for large files of records stored on disk that do not fit entirely in main memory, such as most database files. Sort-Merge strategy : starts by sorting small subfiles (runs ) of the main file and then merges the sorted runs, creating larger sorted subfiles that are merged in turn. – Sorting phase: nR = (b/nB) – Merging phase: dM = Min(nB-1, nR); nP= (logdM(nR)) nR: number of initial runs; b: number of file blocks; nB: available buffer space; dM: degree of merging; nP: number of passes. a 19 d 31 a 19 g 24 g 24 b 14 a 14 a 19 c 33 a 19 d 31 b 14 d 31 b 14 c 33 c 33 e 16 c 33 b 14 e 16 g 24 d 7 e 16 d 21 r 16 d 31 a 14 d 31 d 21 m 3 d 7 e 16 m 3 r 16 d 21 g 24 p 2 m 3
