Tabular: Efficiently Building Efficient Indexes

Download PDF

Abstract

Concurrent indexes are hard to build by requiring complex, careful yet error-prone processes of design and implementation. As prior work has observed, modeling indexes as transactional tables can largely ease programming. The developer only needs to write singlethreaded logic without worrying about concurrency or persistence, which are transparently supported by ACID table operations. However, this was deemed infeasible due to high overheads caused by the underlying OLTP engine. In this paper, we argue that by adapting recent OLTP techniques which have been shown to deliver unprecedented performance, this idea is now feasible. We propose Tabular, a new library for building efficient indexes by modeling indexes as ACID tables which provide concurrency and persistence transparently. We elaborate the design of Tabular and its use cases. Our evaluation shows that compared to hand-crafted ones, indexes built using Tabular provide competitive performance with improved programming efficiency.