Data-intensive Computing Systems Operators for Data Access Shivnath Babu 1 Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ 10 M tuples ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob” Solution #1: Full Table Scan ◼ Storage: ◼ Employee relation stored in contiguous blocks ◼ Query plan: ◼ Scan the entire relation, output tuples with Name = “Bob” ◼ Cost: ◼ Size of each record = 100 bytes ◼ Size of relation = 10 M x 100 = 1 GB ◼ Time @ 20 MB/s ≈ 1 Minute 3 Solution #2 ◼ Storage: ◼ Employee relation sorted on Name attribute ◼ Query plan: ◼ Binary search 4 Solution #2 ◼ Cost: ◼ Size of a block: 1024 bytes ◼ Number of records per block: 1024 / 100 = 10 ◼ Total number of blocks: 10 M / 10 = 1 M ◼ Blocks accessed by binary search: 20 ◼ Total time: 20 ms x 20 = 400 ms 5 Solution #2: Issues ◼ Filters on different attributes: SELECT * FROM Employee WHERE Dept = “Sales” ◼ Inserts and Deletes 6 Indexes ◼ Data structures that efficiently evaluate a class of filter predicates over a relation ◼ Class of filter predicates: ◼ Single or multi-attributes (index-key attributes) ◼ Range and/or equality predicates ◼ (Usually) independent of physical storage of relation: ◼ Multiple indexes per relation 7 Indexes ◼ Disk resident ◼ Large to fit in memory ◼ Persistent ◼ Updated when indexed relation updated ◼ Relation updates costlier ◼ Query cheaper 8 Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob” Single-Attribute Index on Name that supports equality predicates Roadmap ◼ Motivation ◼ Single-Attribute Indexes: Overview ◼ Order-based Indexes ◼ B-Trees ◼ Hash-based Indexes (May cover in future) ◼ Extensible Hashing ◼ Linear Hashing ◼ Multi-Attribute Indexes (Chapter 14 GMUW, May cover in future) 10 Single Attribute Index: General Construction A B a1 b1 a2 b2 ai bi an bn Single Attribute Index: General Construction A B a1 a1 b1 a2 a2 b2 ai ai bi an an bn