Selections Using Indices A4(secondary index,equality on key/non-key). Retrieve a single record if the search-key is a candidate key Cost=(hi+1)*(tr+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)*(fr+ts) ·Can be very expensive！ Database System Concepts-7th Edition 15.12 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.12 ©Silberschatz, Korth and Sudarshan th Edition Selections Using Indices ▪ A4 (secondary index, equality on key/non-key). • 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 oAsv(r)or oA=vr)by using ·a linear file scan, or by using indices in the following ways: A5(clustering index,comparison).(Relation is sorted on A) 。For CA≥)use index to find first tuple≥and scan relation sequentially from there For Asv(r)just scan relation sequentially till first tuple v;do not use index A6(clustering 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 per record;Linear file scan may be cheaper! Database System Concepts-7th Edition 15.13 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 15.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 (clustering 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 (clustering 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 per record; Linear file scan may be cheaper!
Implementation of Complex Selections ■Conjunction:oa1A2A.·.9n() 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-7th Edition 15.14 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 15.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:oe1V02 V..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()） 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-7th Edition 15.15 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.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
Bitmap Index Scan The bitmap index scan algorithm of PostgreSQL Bridges gap between secondary index scan and linear file scan when number of matching records is not known before execution Bitmap with 1 bit per page in relation ·Steps: Index scan used to find record ids,and set bit of corresponding page in bitmap Linear file scan fetching only pages with bit set to 1 ·Performance Similar to index scan when only a few bits are set Similar to linear file scan when most bits are set Never behaves very badly compared to best alternative Database System Concepts-7th Edition 15.16 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.16 ©Silberschatz, Korth and Sudarshan th Edition Bitmap Index Scan ▪ The bitmap index scan algorithm of PostgreSQL • Bridges gap between secondary index scan and linear file scan when number of matching records is not known before execution • Bitmap with 1 bit per page in relation • Steps: ▪ Index scan used to find record ids, and set bit of corresponding page in bitmap ▪ Linear file scan fetching only pages with bit set to 1 • Performance ▪ Similar to index scan when only a few bits are set ▪ Similar to linear file scan when most bits are set ▪ Never behaves very badly compared to best alternative