Constant-Time Query Processing
Vijayshankar Raman, Garret Swart, Lin Qiao et al. · Proceedings - International Conference on Data Engineering · 2008
Query performance in current systems depends significantly on tuning: how well the query matches the available indexes, materialized views etc. Even in a well tuned system, there are always some queries that take much longer than others. This frustrates users who increasingly want consistent response times to ad hoc queries. We argue that query processors should instead aim for constant response times for all queries, with no assumption about tuning. We present Blink, our first attempt at this goal, that runs every query as a table scan over a fully denormalized database, with hash group-by done along the way. To make this scan efficient, Blink uses a novel compression scheme that horizontally partitions tuples by frequency, thereby compressing skewed data almost down to entropy, even while producing long runs of fixed-length, easily-parseable values. We also present a scheme for evaluating a conjunction of range and equality predicates in SIMD fashion over compressed tuples, and different schemes for efficient hash-based aggregation within the L2 cache. A experimental study with a suite of arbitrary single block SQL queries over a TPCH-like schema suggests that constant-time queries can be efficient.
Cited by 121 works. doi:10.1109/icde.2008.4497414
Authors
- Vijayshankar Raman
- Garret Swart
- Lin Qiao
- Frederick R. Reiss
- Vijay Dialani
- Donald Kossmann
- Inderpal S. Narang
- Richard Sidle
References
- A Method for the Construction of Minimum-Redundancy Codes
- Cuckoo hashing
- Super-Scalar RAM-CPU Cache Compression
- SYSTEM/U: a database system based on the universal relation assumption
- The implementation and performance of compressed databases
- An optimal algorithm for generating minimal perfect hash functions
- Sybase IQ Multiplex—Designed For Analytics
- How to barter bits for chronons
- Efficient Hash Probes on Modern Processors
- How to wring a table dry: entropy compression of relations and querying of compressed relations