A comparative survey of locking in ordered indexes
Event details
| Date | 23.09.2016 |
| Hour | 12:00 › 13:30 |
| Speaker | Goetz Graefe, Google |
| Location | |
| Category | Conferences - Seminars |
For decades, b-tree data structures have been ubiquitous in databases, file systems, and information retrieval; and over the past 25 years, record-level locking has become ubiquitous for ordered indexes such as b-trees. There are multiple designs for fine-granularity locking in b- tree indexes, each a different tradeoff between (i) a fine granularity of locking for high concurrency during updates, (ii) coarse locks for equality queries and range queries, (iii) run-time efficiency with the fewest possible invocations of the lock manager, and (iv) conceptual simplicity for efficient development, maintenance, and testing. Using specific examples such as insertions, deletions, equality queries, and phantom protection, this case study compares five alternative designs for fine-granularity locking in b-tree indexes. For queries, one design dominates all prior other including all designs in industrial use today. For updates, the same design is practically equal to the most recent prior design, which dominates all other ones. These results, together with experiments reported in the past, suggest that new b-tree implementations as well as existing ones ought to adopt a new locking technique.For decades, b-tree data structures have been ubiquitous in databases, file systems, and information retrieval; and over the past 25 years, record-level locking has become ubiquitous for ordered indexes such as b-trees. There are multiple designs for fine-granularity locking in b- tree indexes, each a different tradeoff between (i) a fine granularity of locking for high concurrency during updates, (ii) coarse locks for equality queries and range queries, (iii) run-time efficiency with the fewest possible invocations of the lock manager, and (iv) conceptual simplicity for efficient development, maintenance, and testing. Using specific examples such as insertions, deletions, equality queries, and phantom protection, this case study compares five alternative designs for fine-granularity locking in b-tree indexes. For queries, one design dominates all prior other including all designs in industrial use today. For updates, the same design is practically equal to the most recent prior design, which dominates all other ones. These results, together with experiments reported in the past, suggest that new b-tree implementations as well as existing ones ought to adopt a new locking technique.
Practical information
- General public
- Free
Organizer
- Prof. Anastasia Ailamaki
Contact
- Dimitra Tsaoussis-Melissargos