SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units

The availability of huge system memory, even on standard servers, generated a lot of interest in main memory database engines. In data warehouse systems, highly compressed columnoriented data structures are quite prominent. In order to scale with the data volume and the system load, many of these systems are highly distributed with a shared-nothing approach. The fundamental principle of all systems is a full table scan over one or multiple compressed columns. Recent research proposed different techniques to speedup table scans like intelligent compression or using an additional hardware such as graphic cards or FPGAs. In this paper, we show that utilizing the embedded Vector Processing Units (VPUs) found in standard superscalar processors can speed up the performance of mainmemory full table scan by factors. This is achieved without changing the hardware architecture and thereby without additional power consumption. Moreover, as on-chip VPUs directly access the system’s RAM, no additional costly copy operations are needed for using the new SIMD-scan approach in standard main memory database engines. Therefore, we propose this scan approach to be used as the standard scan operator for compressed column-oriented main memory storage. We then discuss how well our solution scales with the number of processor cores; consequently, to what degree it can be applied in multi-threaded environments. To verify the feasibility of our approach, we implemented the proposed techniques on a modern Intel multicore processor using Intel® Streaming SIMD Extensions (Intel® SSE). In addition, we integrated the new SIMD-scan approach into SAP® Netweaver® Business Warehouse Accelerator. We conclude with describing the performance benefits of using our approach for processing and scanning compressed data using VPUs in column-oriented main memory database systems. 1. I TRODUCTIO Computer technology is continually developing, with abiding rapid improvement in processor architecture, disk storage, and main memory capacity. At the same time, the massive increase in data volumes has created a demand for high performance data management capabilities. This is reflected by the data-intensive query processing tasks like OLAP, data mining, and scientific data analysis. These tasks rely on powerful hardware resources and require optimized software solutions for processing the huge amount of data with high performance. As the system memory gets larger and cheaper, database systems started therefore to evolve from disk-based to memorybased operation (and storage). As a result, main memory is becoming a critical resource. As in disk-based database engines, data compression techniques are considered as one way to handle this new main memory bottleneck. Previous research showed that the performance of relational disk-based database system can be increased by extending the storage manager, the query execution engine, and the query optimizer to handle compressed data . In main memory column-store database systems like SAP® Netweaver® Business Warehouse Accelerator (BWA), relational tables are completely loaded into memory and are stored columnwise. In order to save RAM and to improve access rates, the inmemory data structures are highly compressed. This is achieved by using different variants of Light Weight Compression (LWC) techniques like run-length encoding or multiple version of fixedlength encoding. In SAP® Netweaver® BWA, the default compression mechanism is dictionary compression with bitwise encoding of columns. Here, all distinct values of a column are extracted, sorted, and inserted into a dictionary. The column itself keeps only references to the dictionary, where each reference value is stored using as many bits as needed for fixed-length encoding. While most access functions work directly on compressed data by implicit decompression, operations like projection have to materialize the data, and therefore, explicitly decompress it. Here, high performance is achieved by making optimal use of the CPU local cache. This is accomplished by processing small data chunks in one execution step. Hence, data decompression is becoming a significant part of the query execution. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Database Endowment. To copy otherwise, or to republish, to post on servers or to redistribute to lists, requires a fee and/or special permissions from the publisher, ACM. VLDB ’09, August 24-28, 2009, Lyon, France.  In database engines similar to SAP® Netweaver® BWA, the central low-level access function is the main memory full table scan over highly compressed data (table columns). This operation requires lots of calculations and is CPU-intensive. The need for decompression increases the CPU-bound behavior, whereas a scan over uncompressed data is more memory-bus-bound. With the arrival of multi-core processors, operating on compressed data is continuously becoming cheaper as CPU processing rates are increasing faster than data-access bandwidth rates . As a result, more sophisticated compression algorithms are being used while full table scan operations are shifting from being IO-bound to CPU-bound. In addition, the data in the system’s memory is being compressed as much as possible. This created a new exciting research field focusing on optimizing table scan operations for multi-core processors using different parallelization techniques. However, even though multi-core processors offer rich Simultaneous Multi-Processing (SMP) experience, their fast Vector Processing Units (VPUs) have not been fully exploited to vectorize and streamline table scan operations. In this paper, we introduce a novel SIMD approach for inmemory fast table scan operations working on compressed table columns. We utilize the latest SIMD capabilities of each core in superscalar multi-core processors to efficiently decompress inmemory table columns and search for a scan value with a considerably lower latency. With this approach, we extend the parallelization of table scan operations that has been limited to multithreading on the task and data level. SIMD, firstly classified by Flynn [3][4], represents a vector processing model providing instruction level parallelism. SIMD forms an important extension to modern processors architectures and provides the ability for a single instruction stream to process multiple data streams simultaneously.  1 shows the SIMD execution model.  SIMD execution model: In (a) scalar mode: one operation produces one result. In (b) SIMD mode: one operation produces multiple results