GCASR 2016‎ > ‎Presentations‎ > ‎

Orthogonal key-value locking

Orthogonal key-value locking
Goetz Graefe

B-tree data structures have been ubiquitous for decades 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 locking in b-tree indexes, each a different tradeoff between (i) high concurrency and a fine granularity of locking during updates, (ii) efficient coarse locks during equality 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.
A new design introduced here is simple and efficient yet supports both fine and coarse granularities of locking. A lock request may cover (i) a gap (open interval) between two (actual) key values, (ii) a key value with its entire list of (actual and possible) row identifiers (in a non-unique index), (iii) a specific pair of distinct key value and row identifier, or (iv) a distinct key value and a fraction of all (actual and possible) row identifiers. Using specific examples such as insertions, deletions, equality queries, and phantom protection, case studies compare the new design for locks in b-tree indexes with four prior ones. For queries, the new design dominates all prior ones including all designs in industrial use today. For updates, the new design is practically equal to the most recent prior design, which dominates all earlier ones. Experiments demonstrate that the new technique reduces the number of lock requests yet increases transactional concurrency, improving transaction throughput for both read-only queries and read-write transactions. Results of both the case studies and the experiments suggest that new b-tree implementations as well as existing ones ought to adopt the new locking techniques.

Goetz is currently a HP fellow. Goetz Graefe's contributions to database research and product development include query optimization in the Exodus research effort and in the Tandem SQL/MX product, query execution in the Volcano research prototype, and query processing in Microsoft's SQL Server product. In addition to query processing, his work has covered indexing, in particular novel techniques for b-trees, robust performance in query processing, for example a new integrated join algorithm, and transaction support, for example a new schemes for key-range locking and key-value locking. One of his current work streams focuses on database utilities, for example faster backup, restore, and recovery.

Before joining HP, Graefe spent 12 years at Microsoft, where he was instrumental in the development, testing and release of the SQL Server product. SQL Server changed the focus in the database market from performance, scalability and specific features to ease-of-use, automation and total cost of ownership.

Two of the top three database conferences have recognized his contributions. In 2000, Graefe received the “ten-year test of time award” at the ACM Special Interest Group on Management Of Data ( SIGMOD) International Conference for his 1990 paper on parallel query execution.

In 2005, he received the inaugural “influential paper award” at the IEEE International Conference on Data Engineering (ICDE) for a 1993 paper on extensible query optimization.