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

Thomas Willhalm ; Nicolae Popovici ; Yazan Boshmaf ; Hasso Plattner ; Alexander Zeier ; Jan Schaffner

01 August 2009

Abstract: 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 column-oriented 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 multi-core 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.

Keyword(s): Full table-scan ; in-Memory Databases ; Table (De)compression ; Vectorization ; SAP Netweaver BWA

Published in: Willhalm, T., Popovici, N., Boshmaf, Y., Plattner, H., Zeier, A., and Schaffner, J. 2009. SIMD-scan: ultra fast in-memory table scan using on-chip vector processing units. Proc. VLDB Endow. 2, 1 (Aug. 2009), 385-394. :

The record appears in these collections:
Refereed Conference Papers

 Record created 2010-03-03, last modified 2013-05-22

Transfer from CDS 0.99.7:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)