Database System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db- for conditions on re-use Chapter 12: Query ProcessingSilberschatz, Korth and Sudarshan12.2Database System Concepts - 6th EditionChapter 12: Query ProcessingnOverview nMeasures of Query CostnSelection Operation nSorting nJoin Operation nOther OperationsnEvaluation of ExpressionsSilberschatz, Korth and Sudarshan12.3Database System Concepts - 6th EditionBasic Steps in Query Processing1. Parsing and translation2. Optimization3. EvaluationSilberschatz, Korth and Sudarshan12.4Database System Concepts - 6th EditionBasic Steps in Query Processing (Cont.)nParsing and translationltranslate the query into its internal form. This is then translated into relational algebra.lParser checks syntax, verifies relationsnEvaluationlThe query-execution engine takes a query-evaluation plan, executes that plan, and returns the answers to the query.Silberschatz, Korth and Sudarshan12.5Database System Concepts - 6th EditionBasic Steps in Query Processing : OptimizationnA relational algebra expression may have many equivalent expressionslE.g., salary75000(salary(instructor) is equivalent to salary(salary75000(instructor)nEach relational algebra operation can be evaluated using one of several different algorithmslCorrespondingly, a relational-algebra expression can be evaluated in many ways. nAnnotated expression specifying detailed evaluation strategy is called an evaluation-plan.lE.g., can use an index on salary to find instructors with salary v; do not use indexnA6 (secondary index, comparison). 4For A V(r) use index to find first index entry v and scan index sequentially from there, to find pointers to records.4For AV (r) just scan leaf pages of index finding pointers to records, till first entry v4In either case, retrieve records that are pointed torequires an I/O for each record Linear file scan may be cheaperSilberschatz, Korth and Sudarshan12.14Database System Concepts - 6th EditionImplementation of Complex SelectionsnConjunction: 1 2. . . n(r) nA7 (conjunctive selection using one index). lSelect a combination of i and algorithms A1 through A7 that results in the least cost for i (r).l Test other conditions on tuple after fetching it into memory buffer.nA8 (conjunctive selection using composite index). lUse appropriate composite (multiple-key) index if available.nA9 (conjunctive selection by intersection of identifiers). lRequires indices with record pointers. lUse corresponding index for each condition, and take intersection of all the obtained sets of record pointers. lThen fetch records from filelIf some conditions do not have appropriate indices, apply test in memory.Silberschatz, Korth and Sudarshan12.15Database System Concepts - 6th EditionAlgorithms for Complex SelectionsnDisjunction:1 2 . . . n (r). nA10 (disjunctive selection by union of identifiers). lApplicable if all conditions have available indices. 4Otherwise use linear scan.lUse corresponding index for each condition, and take union of all the obtained sets of record pointers. lThen fetch records from filenNegation: (r)lUse linear scan on filelIf very few records satisfy , and an index is applicable to 4 Find satisfying records using index and fetch from fileSilberschatz, Korth and Sudarshan12.16Database System Concepts - 6th EditionSortingnWe 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.nFor relations that fit in memory, techniques like quicksort can be used. For relations that dont fit in memory, external sort-merge is a good choice. Silberschatz, Korth and Sudarshan12.17Database System Concepts - 6th EditionExternal Sort-Merge1.Create sorted runs. Let i be 0 initially. Repeatedly do the following till the end of the relation: (a) Read M blocks of relation into memory (b) Sort the in-memory blocks (c) Write sorted data to run Ri; increment i.Let the final value of i be N2.Merge the runs (next slide).Let M denote memory size (in pages). Silberschatz, Korth and Sudarshan12.18Database System Concepts - 6th EditionExternal Sort-Merge (Cont.)2.Merge the runs (N-way merge). We assume (for now) that N M. 1.Use N blocks of memory to buffer input runs, and 1 block to buffer output. Read the first block of each run into its buffer page2.repeat1.Select the first record (in sort order) among all buffer pages2.Write the record to the output buffer. If the output buffer is full write it to disk.3.Delete the record from its input buffer page.If the buffer page becomes empty then read the next block (if any) of the run into the buffer. 2.until all input buffer pages are empty:Silberschatz, Korth and Sudarshan12.19Database System Concepts - 6th EditionExternal Sort-Merge (Cont.)nIf N M, several merge passes are required.lIn each pass, contiguous groups of M - 1 runs are merged. lA pass reduces the number of runs by a factor of M -1, and creates runs longer by the same factor. 4E.g. If M=11, and ther