ByteSlice : pushing the envelop of main memory data processing with a new storage layout

Abstract

Scan and lookup are two core operations in main memory column stores. A scan operation scans a column and returns a result bit vector that indicates which records satisfy a filter. Once a column scan is completed, the result bit vector is converted into a list of record numbers, which is then used to look up values from other columns of interest for a query. Recently there are several in-memory data layout proposals that aim to improve the performance of in-memory data processing. However, these solutions all stand at either end of a trade-off each is either good in lookup performance or good in scan performance, but not both. This thesis presents ByteSlice, a new main memory storage layout that supports both highly efficient scans and lookups. ByteSlice is a byte-level columnar layout that fully leverages SIMD data-parallelism. Micro-benchmark experiments show that ByteSlice achieves a data scan speed at less than 0.5 processor cycle per column value a new limit of main memory data scan, without sacrificing lookup performance. Experiments on TPC-H data and real data show that ByteSlice offers significant performance improvement over all state-of-the-art approaches.