Query Processing PDF

Chapter 15: Query Processing Database System Concepts, 7th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use 1...

Chapter 15: Query Processing Database System Concepts, 7th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use 1 Chapter 15: Query Processing What is query processing? ▪ Overview ▪ Measures of Query Cost ▪ Selection Operation ▪ Join Operation ▪ Evaluation of Expressions Database System Concepts - 7th Edition 15.2 ©Silberschatz, Korth and Sudarshan 2 1  Basic Steps in Query Processing-Revisit 1. Parsing and translation 2. Optimization 3. Evaluation Database System Concepts - 7th Edition 15.3 ©Silberschatz, Korth and Sudarshan 3 Basic Steps in Query Processing (Cont.) ▪ Parsing and translation Translate the query into its internal form (similar to a parser to a compiler). Parser checks syntax, verifies relation names (same as in database) etc. The system constructs a parse-tree representation of the query, which it then translates into a relational-algebra expression. If the query was expressed in terms of a view, the translation phase also replaces all uses of the view by the relational-algebra expression that defines the view Database System Concepts - 7th Edition 15.4 ©Silberschatz, Korth and Sudarshan 4 2  Basic Steps in Query Processing (Cont.) ▪ Or the following expression: ▪ Consider the following query: 2. salary(salary75000(instructor)) Select all records (including all attributes) with salary less than 75,000 and project salary.Parser Tree Representation 2 ▪ The query can be translated into the following relational-algebra expressions: 1. salary75000(salary(instructor)) At the leaf node, we have relation Instructor we are projecting only salary and select those less than 75,000 Parser Tree Representation 1 ▪ Both representations will give the same output but the cost will be different. ▪ In relational algebra 𝝅 (pi) is a projection operation that choose specific columns (attributes), hence reduce the table size. While σ (sigma) filters specific rows (tuples) from a table based on a condition. Database System Concepts - 7th Edition 15.5 ©Silberschatz, Korth and Sudarshan 5 Basic Steps in Query Processing (Cont.) ▪ To specify fully how to evaluate a query, apart from providing the relational algebra expression, we need to annotate it with instructions specifying how to evaluate each operation. ▪ Annotations may state the algorithm to be used for a specific operation or the particular index or indices to use. Figure 15.2 illustrates an evaluation plan for example query, “index 1” is specified for the selection operation. ▪ A relational-algebra operation annotated with instructions on how to evaluate it is called an evaluation primitive. ▪ A sequence of primitive operations that can be used to evaluate a query is a query- execution plan or query-evaluation plan. Database System Concepts - 7th Edition 15.6 ©Silberschatz, Korth and Sudarshan 6 3  Basic Steps: Optimization ▪ For a given query, we can have different evaluation plans with different costs ▪ Query Optimization: Amongst all equivalent evaluation plans choose the one with lowest cost. Cost is estimated using statistical information from the database catalog ▪ e.g. number of tuples in each relation, size of tuples, etc. ▪ Once the query plan is chosen, the query-execution engine takes the query-evaluation plan, executes that plan, and returns the answers to the query. Database System Concepts - 7th Edition 15.7 ©Silberschatz, Korth and Sudarshan 7 Measures of Query Cost ▪ In order to optimize a query, a query optimizer must know the cost of each operation. ▪ We must estimate the cost of individual operations and combine them to get the cost of a query evaluation plan ▪ Cost of query evaluation can be measured in terms of : disk access, CPU time to execute query, and cost of communication ▪ Note, we do not include CPU costs neither communication in our model. ▪ Disk cost can be estimated as: Number of seeks (average-seek-cost) Number of blocks read (average-block-read-cost) Number of blocks written (average-block-write-cost) Database System Concepts - 7th Edition 15.8 ©Silberschatz, Korth and Sudarshan 8 4  Measures of Query Cost ▪ For simplicity we just use the number of block transfers from disk and the number of seeks as the cost measures tT – time to transfer one block of data ▪ Assuming for simplicity that write cost is same as read cost tS – time for one seek ▪ Cost for b block transfers plus S seeks b * tT + S * t S ▪ tS and tT depend on where data is stored ▪ For 4 KB blocks and a transfer rate of 40 megabytes per second: High end magnetic disk: tS = 4 msec and tT =0.1 msec SSD: tS = 20-90 microsec and tT = 2-10 microsec The above measures are as of 2018. SSD do not have seek operation. tS refers to overhead in initiating I/O Database System Concepts - 7th Edition 15.9 ©Silberschatz, Korth and Sudarshan 9 Measures of Query Cost (Cont.) ▪ Required data may be buffer resident already, avoiding disk I/O But hard to take into account for cost estimation ▪ Several algorithms can reduce disk IO by using extra buffer space Amount of real memory available to buffer depends on other concurrent queries and OS processes, known only during execution ▪ Worst case estimates assume that no data is initially in buffer and only the minimum amount of memory needed for the operation is available But more optimistic estimates are used in practice Database System Concepts - 7th Edition 15.10 ©Silberschatz, Korth and Sudarshan 10 5  Selection Operation ▪ File scan In query processing, the file scan is the lowest level operator to access data File scans are search algorithms that locate and retrieve records that fulfill a selection condition It allows an entire relation to be read in those cases where the relation is stored in a single, dedicated file. An attribute or set of attributes used to look up records in a file is called a search key. Database System Concepts - 7th Edition 15.11 ©Silberschatz, Korth and Sudarshan 11 Selection Operation: A1 (Linear Search) ▪ In a linear search, the system scans each file block (assume a block consists of 3 tuples) and test all records to see whether they satisfy the selection condition. ▪ Although linear search may be slower than other algorithms, it can be applied regardless of Block 1 ▪ selection condition or ▪ ordering of records in the file, or Block 2 ▪ availability of indices Block 3 ▪ An initial seek is required to access the first block of the file. If blocks are not stored contiguously, extra seeks may be required. Block 4 Cost estimate = br block transfers + 1 seek = b r * tT + tS br denotes number of blocks containing records from relation r Database System Concepts - 7th Edition 15.12 ©Silberschatz, Korth and Sudarshan 12 6  Selection Operation: A1 (Linear Search, Equality on Key) ▪ If selection is on a key attribute, search stops on finding record. Block 1 Block 2 ▪ Average cost : (br /2)* tT + tS ▪ Worst case cost : br * tT + tS Block 3 Block 4 Database System Concepts - 7th Edition 15.13 ©Silberschatz, Korth and Sudarshan 13 We only cover the First two algorithms. Database System Concepts - 7th Edition 15.14 ©Silberschatz, Korth and Sudarshan 14 7  Join Operation ▪ Several different algorithms to implement joins Nested-loop join Block nested-loop join Indexed nested-loop join Merge-join Hash-join ▪ Choice based on cost estimate Database System Concepts - 7th Edition 15.15 ©Silberschatz, Korth and Sudarshan 15 Nested-Loop Join ▪ To compute the theta join r⨝s for each tuple tr in r do begin for each tuple ts in s do begin test pair (tr,ts) to see if they satisfy the join condition  if they do, add tr ts to the result. end end ▪ r is called the outer relation and s the inner relation of the join. ▪ tr. ts - the tuple constructed by concatenating the attribute values of tuples tr and ts Database System Concepts - 7th Edition 15.16 ©Silberschatz, Korth and Sudarshan 16 8  Nested-Loop Join (cont.) ▪ Nested loop join requires no indices and can be used with any kind of join condition. ▪ Expensive since it examines every pair of tuples in the two relations. ▪ The cost of the nested-loop join algorithm: The number of pairs of tuples to be considered is : nr x ns where nr denotes the number of tuples in r and ns denotes the number of tuples in s. In the example below; course=13 and prereq=7; 13 x 7 = 91 For each record in r, a complete scan on s is performed. course prereq Database System Concepts - 7th Edition 15.17 ©Silberschatz, Korth and Sudarshan 17 Nested-Loop Join – Worst case Worst case ▪ If there is enough memory only to hold one block of each relation, ▪ The estimated cost of total block transfers = nr  bs + br where br and bs denote the number of blocks containing tuples of r and s, respectively. ▪ We need only one seek for each scan on the inner relation s since it is read sequentially, and a total of br seeks to read r ▪ Leading to a total seeks of: nr + br Database System Concepts - 7th Edition 15.18 ©Silberschatz, Korth and Sudarshan 18 9  Nested-Loop Join – Best case Best case ▪ Enough space for both relations to fit simultaneously in memory, so each block would have to be read only once; ▪ Hence, only br + bs block transfers would be required, along with two seeks. ▪ If one of the relations fits entirely in main memory, it is beneficial to use that relation as the inner relation, since the inner relation would then be read only once. ▪ Therefore, if s is small enough to fit in main memory, we requires only a total br + bs block transfers and two seeks —the same cost as that for the case where both relations fit in memory. Database System Concepts - 7th Edition 15.19 ©Silberschatz, Korth and Sudarshan 19 Nested-Loop Join - Example ▪ Consider the natural join of student and takes. ▪ Assume for now that we have no indices whatsoever on either relation, and that we are not willing to create any index. ▪ We can use the nested loops to compute the join; assume that student is the outer relation and takes is the inner relation in the join. student (ID, name, dept_name, tot_credit) takes (ID, course_id, sec_id, semester, year, grade) Database System Concepts - 7th Edition 15.20 ©Silberschatz, Korth and Sudarshan 20 10  Nested-Loop Join – Example (Cont.) ▪ Outer relation : r = Student (br = 100) ▪ Inner relation : s = Takes (bs = 400) ▪ Total pairs = nr x ns = 5000 x 10000 = 5 x 107 Database System Concepts - 7th Edition 15.21 ©Silberschatz, Korth and Sudarshan 21 Nested-Loop Join – Example (Cont.) Worst case: ▪ Block transfers : nr  bs + br ▪ = 5000 x 400 + 100 = 2,000,100 ▪ Seeks: nr + br = 5000+100=5100 Best case : ▪ Block transfers : br + bs = 100 + 400 =500 ▪ Seeks : 2 Database System Concepts - 7th Edition 15.22 ©Silberschatz, Korth and Sudarshan 22 11  Nested-Loop Join – Example (Cont.) Now, reverse : ▪ Outer relation : r = Takes (br = 400) ▪ Inner relation : s = Student (bs = 100) Worst case: ▪ Block transfer: nr  bs + br = 10000 x 100 + 400 = 1,000,400 ▪ Seeks: nr + br = 10,000 + 400 = 10,400 Database System Concepts - 7th Edition 15.23 ©Silberschatz, Korth and Sudarshan 23 Comparison: Reverse of Outer & Inner Relation Worst case Best case Outer = r Block transfers: nr  bs + br Block transfers: br + bs (student) = 5000 x 400 + 100 = 100 + 400 Inner = s = 2,000,100 = 500 (takes) Seeks: nr + br Seeks: 2 = 5000+100 =5100 Outer = s Block transfer: nr  bs + br The same. (takes) = 10000 x 100 + 400 Inner = r = 1,000,400 (student) Seeks: nr + br = 10,000 + 400 = 10,400 The number of block transfers is significantly less, and although the number of seeks is higher the overall cost is reduced. Assuming tS = 4 milliseconds and tT = 0.1 milliseconds, the total cost is 220,410 msec for the first, and 141,640 msec for the second. Database System Concepts - 7th Edition 15.24 ©Silberschatz, Korth and Sudarshan 24 12  Evaluation of Expressions ▪ So far, we have studied how individual relational operations are carried out. Now we consider how to evaluate an expression containing multiple operations. ▪ Two approaches: Materialisation Pipelining Database System Concepts - 7th Edition 15.25 ©Silberschatz, Korth and Sudarshan 25 Materialization ▪ Materialized evaluation: evaluate one operation at a time, starting at the lowest-level. Use intermediate results materialized into temporary relations to evaluate next-level operations. ▪ In the example, we start with the selection operation on department (which is the lowest- level operations in the expression-at the bottom of the tree). ▪ Execute these operations using the algorithms that were studied earlier, and store the results in temporary relations. ▪ The inputs to the join are the instructor relation and the temporary relation created by the selection on department. ▪ The join can now be evaluated, creating another temporary relation, and finally compute the projection on name. Database System Concepts - 7th Edition 15.26 ©Silberschatz, Korth and Sudarshan 26 13  Materialization (Cont.) ▪ Materialized evaluation is always applicable ▪ However, the Cost of writing results to disk and reading them back can be quite high Our cost formulas for operations ignore cost of writing results to disk, so ▪ Overall cost = Sum of costs of individual operations + cost of writing intermediate results to disk ▪ Double buffering: use two output buffers for each operation, when one is full, write it to disk while the other is getting filled Allows overlap of disk writes with computation and reduces execution time Database System Concepts - 7th Edition 15.27 ©Silberschatz, Korth and Sudarshan 27 Pipelining ▪ Pipelined evaluation: evaluate several operations simultaneously, passing the results of one operation on to the next. ▪ E.g., in previous expression tree, don’t store result of  building="Watson " (department) instead, pass tuples directly to the join. Similarly, don’t store result of join, pass tuples directly to projection. ▪ Much cheaper than materialization: no need to store a temporary relation to disk. ▪ Pipelining may not always be possible – e.g., sort, hash-join. ▪ For pipelining to be effective, use evaluation algorithms that generate output tuples even as tuples are received for inputs to the operation. ▪ Pipelines can be executed in two ways: demand driven and producer driven Database System Concepts - 7th Edition 15.28 ©Silberschatz, Korth and Sudarshan 28 14  Pipelining (Cont.) ▪ In demand driven or lazy evaluation system repeatedly requests next tuple from top level operation Each operation requests next tuple from children operations as required, in order to output its next tuple In between calls, operation has to maintain “state” so it knows what to return next ▪ In producer-driven or eager pipelining Operators produce tuples eagerly and pass them up to their parents ▪ Buffer is maintained between operators, child puts tuples in buffer, parent removes tuples from buffer ▪ if buffer is full, child waits till there is space in the buffer, and then generates more tuples System schedules operations that have space in output buffer and can process more input tuples ▪ Alternative name: pull and push models of pipelining Database System Concepts - 7th Edition 15.29 ©Silberschatz, Korth and Sudarshan 29 End of Chapter 15 Resources Query Processing https://www.youtube.com/watch?v=zhBydN5l7oo Lecture 11 Part 5 Nested Loops Join https://www.youtube.com/watch?v=RcEW0P8iVTc Database System Concepts - 7th Edition 15.30 ©Silberschatz, Korth and Sudarshan 30 15