Indexing for efficient main memory processing

Abstract

Database management systems (DBMS) have become a standard tool for manipulating large volumes of data on secondary storage. The index structures are used to enable fast data access according to its content. Traditionally, data is stored on storage devices such as disks. As random access memory gets cheaper and larger, it becomes increasingly possible to keep the whole database memory resident. To efficiently process data in memory, we have to address the problem of optimizing L2 cache utilization and minimizing computation cost. In this thesis, we present our solutions on main memory indexing. To speed up the searching process, two novel indexing methods are proposed to deal with single/high-dimensional data respectively. Concurrency control is crucial for running the real-world main memory database applications, and we proposed a main memory concurrency control algorithm to support concurrent operations involving index updates. Extensive experimental studies demonstrate the superiority of the proposed methods.