X100

Beyond cache-conscious query processing..

Development Wiki (restricted access)

Motivation

Database architecture involves finding good trade-offs of interacting design desicions in many dimensions (e.g. query language, optimization, query processing algorithms and data structures) and their interaction with the hardware environment. As hardware keeps evolving, this implies that database architecture should be subject to constant re-evaluation.

A good example of such balancing is reflected by the "5-minute rule" of Jim Gray, and the various re-formulations in later years to adjust it to ever more recent hardware developments. As a more concrete example, our own work in MonetDB has shown that from the late 1990s it has become important to optimize data structures and e.g. join algorithms to make optimal use of the caches found in modern CPUs, a complication that was nonexistant when most current RDBMS products where architected.

Goal

The X100 project aims at investigating opportunities for improvement in database architecture provided by evolution in computer architecture. We target so-called query-intensive domains, where our prime domains are OLAP and (multi-media) Information Retrieval and XML processing. Hence, an additional requirement of this new high-performance database kernel is that it can be usefully adapted to non-standard database application domains.

Research Questions

We will be evaluating new data structures, indexing structures, query execution and query optimization techniques that try to exploit efficiency opportunities in modern computer hardware regarding:

optimizing CPU cache usage: this involves adapting data structures and query processing algorithms to minimize the number of cache misses. This is where the focus of our work so far has been.
creating high IPC: the observation here is that hyperpipelined CPUs need a continuous pool of independent instructions in order to exploit their wide-issue capabilities. In contrast to scientific computing, DBMS query processing algorithms are notorious for their instruction dependencies (many hard-to-predict branches and loops, late-binding method calls and linked list pointer chasing), making the DBMS profit less than other domains from developments in CPU power.
optimizing I/O bandwidth, as sequential bandwidth is becoming a scarce resource (each year it takes longer to fully scan a new disk). Past DBMS research has focused mostly on optimizing random access block I/O. We will be looking at novel lightweight compression methods to boost sequential bandwidth, even of already powerful RAID systems from the hundreds of MB/s to more the GB/s range at negligable CPU cost (a query processor at X100 speed implies such a bandwidth need). Also, a query optimizer should optimize precious full table scans such that as many queries as possible reuse each of ongoing table scans.
exploiting new parallel architectures, specifically, SMT (symmetrical multi-threading: one CPU executing instructions for 2 or more threads at the same time), CMT (chips containing multiple independent CPUs but sharing a cache as ultra-high speed communication channel) and ccNUMA larger-scale systems (such as SGI Altix or Opteron) with a strong distinction between local and remote memory.

About The Name 'Times-Hundred'...

We want to provide a DBMS kernel that is truely efficient in the sense that:

it executes complex expressions using a minimal number of CPU instructions
and those instructions are executed efficiently by the CPU, in general with an IPC (Instructions Per Cycle) ratio of more than 2.

Now, when we compare this with the state-of-the-art of DBMS kernels, we see that:

the DBMS is often I/O-bound instead of CPU-bound.
and when CPU-bound, we see that when evaluating expressions, a RDBMS only spends a small percent of its effort on the actual work (see this profile of MySQL on TPC-H query 1).
and also when CPU-bound, the IPC of the CPU tends to be low (close to or below 1), because of either memory cache misses, or branch mispredictions.

In all, X100 will need to fight bottlenecks on all levels, from sequential I/O to good use of the caches in the memory hierarchy, up to the level of tuing the instruction mix in the CPU.

So, if eventually we do that succesfully and get to our goal of CPU-boundedness on minimal instructions with a high IPC, then indeed we might arrive at the situation that X100 achieves a performance that is two orders of magnitude better than that of commercial RDBMS systems on the benchmarks of our choice (primarily OLAP such as TPC-H, but also content-based information access in huge multimedia databases like TREC Video).

Prototyping

X100 will be used initially as an extension module inside MonetDB.

Project Members

Peter Boncz.
Marcin Zukowski (CWI Ph.D. student).
Sandor Heman (CWI Ph.D. student).
Niels Nes.
Stefan Manegold.

Publications

MonetDB/X100: Hyper-Pipelining Query Execution. P. A. Boncz, M. Zukowski, N. Nes. Proc. CIDR conference, Asilomar (CA), Januari 2005.
MonetDB/X100 - A DBMS In The CPU Cache. M. Zukowski, P. A. Boncz, N. Nes, S. Heman. IEEE Data Engineering Bulletin, 28(2):17-22, June 2005.
Improving I/O Bandwidth for Data-Intensive Applications. M. Zukowski. Proc. British National Conference on Databases (BNCOD), Sunderland, England, UK, PhD Workshop, July 2005.
Hardware-Conscious DBMS Architecture for Data-Intensive Applications. M. Zukowski. Proc. International Conference on Very Large Data Bases (VLDB), Trondheim, Norway, PhD Workshop, August 2005.
Super-Scalar RAM-CPU Cache Compression. M. Zukowski, S. Heman, N. Nes, P. A. Boncz. Proc. International Conference on Data Engineering (ICDE) Atlanta, GA, USA, April 2006.
Architecture-Conscious Hashing. M. Zukowski, S. Heman, P. A. Boncz. Proc. Intl Workshop for Data Management on New Hardware (DaMoN), Chicago, IL, USA, June 2006.

Our previous work on on cache- and CPU-efficiency inside MonetDB is highly related:

Cache-Conscious Radix-Decluster projections S. Manegold, P. A. Boncz, N. Nes, M. L. Kersten. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pp 684-695, Toronto, Canada, September 2004.
Optimizing Main-Memory Join On Modern Hardware. S. Manegold, P. A. Boncz, M. L. Kersten. IEEE Transactions on Knowledge and Data Eng., 14(4):709-730, July 2002.
Generic Database Cost Models for Hierarchical Memory Systems. S. Manegold, P. A. Boncz, M. L. Kersten. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pp 191-202, Hong Kong, China, September 2002.
What happens during a Join? - Dissecting CPU and Memory Optimization Effects. S. Manegold, P. A. Boncz, M. L. Kersten. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pp 339-350, Cairo, Egypt, September 2000.
Database Architecture Optimized for the New Bottleneck: Memory Access. P. A. Boncz, S. Manegold, M. L. Kersten. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pp 54-65, Edinburgh, United Kingdom, September 1999.