Abstract

In DBMSs, auxiliary index structures sitting on top of the actual database exist in various forms to speed up query processing. They are carefully handcrafted data structures which typically materialize one or multiple levels of explicit indirections (aka pointers) to allow for a quick navigation to the data of interest. Unfortunately, dereferencing a pointer to traverse from one level to the other is costly as additionally to following the address, it involves two address translations from virtual memory to physical memory under the hood. In the worst case, such an address translation is resolved by an index access itself, namely by a lookup into the page table, a central hardware-accelerated index structure of the OS. However, if the page table is anyways constantly queried, it raises the question whether we can actively incorporate it into our database indexes and make it work for us. Precisely, instead of explicitly materializing indirections in form of traditional pointers, we propose to express equivalent implicit indirections directly in the page table wherever possible. By introducing such shortcuts, we (a) effectively reduce the height of traversal during lookups and (b) exploit the hardware-acceleration of lookups in the page table. To showcase the effectiveness of this approach, we actively incorporate the page table into a database index, namely a resizable hash table, which follows the concept of extendible hashing. Our “cut short” hash table resizes as gracefully as traditional extendible hashing, but offers lookup times comparable to a single flat hash table. Besides evaluating the strengths of the approach, we also list the pitfalls one has to circumvent in order to efficiently exploit the page table in database indexes in general.