Row-wise parallel predicate evaluation
Ryan Johnson, Vijayshankar Raman, Richard Sidle et al. · Proceedings of the VLDB Endowment · 2008
Table scans have become more interesting recently due to greater use of ad-hoc queries and greater availability of multi-core, vector-enabled hardware. Table scan performance is limited by value representation, table layout, and processing techniques. In this paper we propose a new layout and processing technique for efficient one-pass predicate evaluation. Starting with a set of rows with a fixed number of bits per column, we append columns to form a set of banks and then pad each bank to a supported machine word length, typically 16, 32, or 64 bits. We then evaluate partial predicates on the columns of each bank, using a novel evaluation strategy that evaluates column level equality, range tests, IN-list predicates, and conjuncts of these predicates, simultaneously on multiple columns within a bank, and on multiple rows within a machine register. This approach outperforms pure column stores, which must evaluate the partial predicates one column at a time. We evaluate and compare the performance and representation overhead of this new approach and several proposed alternatives.
Cited by 73 works. doi:10.14778/1453856.1453925
Authors
References
- Integrating compression and execution in column-oriented database systems
- MonetDB/X100: Hyper-Pipelining Query Execution
- Database Architecture Optimized for the New Bottleneck: Memory Access
- Super-Scalar RAM-CPU Cache Compression
- Implementing database operations using SIMD instructions
- Block oriented processing of relational database operations in modern computer architectures
- Sybase IQ Multiplex—Designed For Analytics
- Constant-Time Query Processing
- Data page layouts for relational databases on deep memory hierarchies
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9