Trang 2
Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ 10 M tuples ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob”
Trang 3
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
Trang 5
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
Trang 6
Solution #2: Issues ◼ Filters on different attributes: SELECT * FROM Employee WHERE Dept = “Sales” ◼ Inserts and Deletes 6
Trang 7
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
Trang 8
Indexes ◼ Disk resident ◼ Large to fit in memory ◼ Persistent ◼ Updated when indexed relation updated ◼ Relation updates costlier ◼ Query cheaper 8
Trang 9
Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob” Single-Attribute Index on Name that supports equality predicates
Trang 10
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
Trang 12
Single Attribute Index: General Construction A B a a b 1 1 1 a a b 2 2 2 A = val A > low a a b A < high i i i an an bn
Trang 13
Exceptions ◼ Sparse Indexes ◼ Require specific physical layout of relation ◼ Example: Relation sorted on indexed attribute ◼ More efficient 13
Trang 14
Single Attribute Index: General Construction Textbook: Dense Index A B a a b 1 1 1 a a b 2 2 2 A = val A > low a a b A < high i i i an an bn 14
Trang 15
Single Attribute Index: General Construction How do we organize a (attribute, pointer) pairs? 1 a 2 A = val Idea: Use dictionary A > low a data structures A < high i Issue: Disk resident? an
Trang 16
Roadmap ◼ Motivation ◼ Single-Attribute Indexes: Overview ◼ Order-based Indexes ◼ B-Trees ◼ Hash-based Indexes ◼ Extensible Hashing ◼ Linear Hashing ◼ Multi-Attribute Indexes 16
Trang 17
B-Trees ◼ Adaptation of search tree data structure ◼ 2-3 trees ◼ Supports range predicates (and equality) 17
Trang 19
Use Binary Search Tree Directly? ◼ Store records of type <key, left-ptr, right-ptr, data-ptr> ◼ Remember position of root ◼ Question: will this work? ◼ Yes ◼ But we can do better! 19
Trang 20
Use Binary Search Tree Directly? ◼ Number of keys: 1 M ◼ Number of levels: log (2^20) = 20 ◼ Total cost index lookup: 20 random disk I/O ◼ 20 x 20 ms = 400 ms B-Tree: less than 3 random disk I/O 20
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!