Selections Involving Comparisons Can implement selections of the form Asv(r)or A=r)by using a linear file scan or binary search, or by using indices in the following ways: A6(primary index,comparison).(Relation is sorted on A) For cAv(r)use index to find first tuple>v and scan relation sequentially from there For Asv(r)just scan relation sequentially till first tuple v;do not use index A7 (secondary index,comparison). For cAv(r)use index to find first index entry >v and scan index sequentially from there,to find pointers to records. For oAsv(r)just scan leaf pages of index finding pointers to records, till first entry >v In either case,retrieve records that are pointed to requires an l/O for each record Linear file scan may be cheaper Database System Concepts-5th Edition,Aug 27,2005. 13.12 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 13.12 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. Selections Involving Comparisons Can implement selections of the form AV (r) or A V(r) by using a linear file scan or binary search, or by using indices in the following ways: A6 (primary index, comparison). (Relation is sorted on A) For A V(r) use index to find first tuple v and scan relation sequentially from there For AV (r) just scan relation sequentially till first tuple > v; do not use index A7 (secondary index, comparison). For A V(r) use index to find first index entry v and scan index sequentially from there, to find pointers to records. For AV (r) just scan leaf pages of index finding pointers to records, till first entry > v In either case, retrieve records that are pointed to – requires an I/O for each record – Linear file scan may be cheaper
Implementation of Complex Selections Conjunction:oa1A2Λ.·9n() A8 (conjunctive selection using one index). Select a combination of 0;and algorithms A1 through A7 that results in the least cost for oei(r). Test other conditions on tuple after fetching it into memory buffer. A9(conjunctive selection using multiple-key index). Use appropriate composite(multiple-key)index if available. A10(conjunctive selection by intersection of identifiers). Requires indices with record pointers. Use corresponding index for each condition,and take intersection of all the obtained sets of record pointers. Then fetch records from file If some conditions do not have appropriate indices,apply test in memory. Database System Concepts-5th Edition,Aug 27,2005. 13.13 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 13.13 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. Implementation of Complex Selections Conjunction: 1 2. . . n (r) A8 (conjunctive selection using one index). Select a combination of i and algorithms A1 through A7 that results in the least cost for i (r). Test other conditions on tuple after fetching it into memory buffer. A9 (conjunctive selection using multiple-key index). Use appropriate composite (multiple-key) index if available. A10 (conjunctive selection by intersection of identifiers). Requires indices with record pointers. Use corresponding index for each condition, and take intersection of all the obtained sets of record pointers. Then fetch records from file If some conditions do not have appropriate indices, apply test in memory
Algorithms for Complex Selections Disjunction:coV02 V...en (r). A11(disjunctive selection by union of identifiers). Applicable if all conditions have available indices. Otherwise use linear scan. Use corresponding index for each condition,and take union of all the obtained sets of record pointers. Then fetch records from file Negation:o_e(r) Use linear scan on file If very few records satisfy-0,and an index is applicable to 0 Find satisfying records using index and fetch from file Database System Concepts-5th Edition,Aug 27,2005. 13.14 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 13.14 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. Algorithms for Complex Selections Disjunction:1 2 . . . n (r). A11 (disjunctive selection by union of identifiers). Applicable if all conditions have available indices. Otherwise use linear scan. Use corresponding index for each condition, and take union of all the obtained sets of record pointers. Then fetch records from file Negation: (r) Use linear scan on file If very few records satisfy , and an index is applicable to Find satisfying records using index and fetch from file
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. Database System Concepts-5th Edition,Aug 27,2005. 13.15 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 13.15 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. 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
External Sort-Merge Let M denote memory size (in pages). 1.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 N 2.Merge the runs (next slide)..... Database System Concepts-5th Edition,Aug 27,2005. 13.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 13.16 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. External Sort-Merge 1. 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 N 2. Merge the runs (next slide)….. Let M denote memory size (in pages)