Selections Using Indices A4(secondary index,equality on nonkey). Retrieve a single record if the search-key is a candidate key Cost=(h;+1)*(t+ts) Retrieve multiple records if search-key is not a candidate key each of n matching records may be on a different block Cost=(h;+n)*(t+ts) Can be very expensive！ Database System Concepts-6th Edition 12.12 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.12 ©Silberschatz, Korth and Sudarshan th Edition Selections Using Indices A4 (secondary index, equality on nonkey). Retrieve a single record if the search-key is a candidate key Cost = (hi + 1) * (tT + tS) Retrieve multiple records if search-key is not a candidate key each of n matching records may be on a different block Cost = (hi + n) * (tT + tS) – Can be very expensive!
Selections Involving Comparisons Can implement selections of the form cAsv(r)or cA=r)by using a linear file scan, or by using indices in the following ways: A5(primary index,comparison).(Relation is sorted on A) For cAr)use index to find first tuple >v and scan relation sequentially from there For cAsv(r)just scan relation sequentially till first tuple>v;do not use index A6(secondary index,comparison). For cA=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 1/O for each record Linear file scan may be cheaper Database System Concepts-6th Edition 12.13 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.13 ©Silberschatz, Korth and Sudarshan th Edition Selections Involving Comparisons Can implement selections of the form AV (r) or A V (r) by using a linear file scan, or by using indices in the following ways: A5 (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 A6 (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:e 02A...en(r) A7(conjunctive selection using one index). Select a combination of 0;and algorithms A1 through A7 that results in the least cost for ooi(r). Test other conditions on tuple after fetching it into memory buffer. A8(conjunctive selection using composite index). Use appropriate composite(multiple-key)index if available. A9(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-6th Edition 12.14 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.14 ©Silberschatz, Korth and Sudarshan th Edition Implementation of Complex Selections Conjunction: 1 2. . . n (r) A7 (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. A8 (conjunctive selection using composite index). Use appropriate composite (multiple-key) index if available. A9 (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:001V02V...en(r). A10(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_o(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-6th Edition 12.15 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.15 ©Silberschatz, Korth and Sudarshan th Edition Algorithms for Complex Selections Disjunction:1 2 . . . n (r). A10 (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-6th Edition 12.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 12.16 ©Silberschatz, Korth and Sudarshan th Edition 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