MonetDB/X100: Hyper-Pipelining Query Execution

MonetDB/X100: Hyper-Pipelining Query Execution

Abstract

Database systems tend to achieve only low instructions-per-cycle efficiency on modern CPUs in compute-intensive application areas like decision support, OLAP, and multimedia retrieval. This paper starts with an in-depth investigation to the reason why this happens, focusing on the TPC-H benchmark. Our analysis of various relational systems and MonetDB leads us to a new set of guidelines for designing a query processor.

The second part of the paper describes the architecture of our new X100 query engine for the MonetDB system that follows these guidelines. On the surface, it resembles a classical Volcano-style engine, but the crucial difference to base all execution on the concept of vector processing makes it highly CPU efficient. We evaluate the power of MonetDB/X100 on the one hundred gigabyte version of TPC-H, showing its raw execution power to be between one and two orders of magnitude higher than previous technology.

One Introduction

Modern CPUs can perform enormous amounts of calculations per second, but only if they can find enough independent work to exploit their parallel execution capabilities. Hardware developments during the past decade have significantly increased the speed difference between a CPU running at full throughput and minimal throughput, which can now easily be an order of magnitude.

Proceedings of the two thousand five CIDR Conference

One would expect that query-intensive database workloads such as decision support, OLAP, data-mining, but also multimedia retrieval, all of which require many independent calculations, should provide modern CPUs the opportunity to get near optimal instructions-per-cycle efficiencies.

However, research has shown that database systems tend to achieve low instructions-per-cycle efficiency on modern CPUs in these application areas. We question whether it should really be that way. Going beyond the important topic of cache-conscious query processing, we investigate in detail how relational database systems interact with modern super-scalar CPUs in query-intensive workloads, in particular the TPC-H decision support benchmark.

The main conclusion we draw from this investigation is that the architecture employed by most DBMSs inhibits compilers from using their most performance-critical optimization techniques, resulting in low CPU efficiencies. Particularly, the common way to implement the popular Volcano iterator model for pipelined processing, leads to tuple-at-a-time execution, which causes both high interpretation overhead, and hides opportunities for CPU parallelism from the compiler.

We also analyze the performance of the main memory database system MonetDB, developed in our group, and its MIL query language. MonetDB/MIL uses a column-at-a-time execution model, and therefore does not suffer from problems generated by tuple-at-a-time interpretation. However, its policy of full column materialization causes it to generate large data streams during query execution. On our decision support workload, we found MonetDB/MIL to become heavily constrained by memory bandwidth, causing its CPU efficiency to drop sharply.

Therefore, we argue for combining the column-wise execution of MonetDB with the incremental materialization offered by Volcano-style pipelining.

We designed and implemented from scratch a new query engine for the MonetDB system, called X100,

that employs a vectorized query processing model. Apart from achieving high CPU efficiency, MonetDB/X100 is intended to scale up towards non main-memory (disk-based) datasets. The second part of this paper is dedicated to describing the architecture of MonetDB/X100 and evaluating its performance on the full TPC-H benchmark of size one hundred gigabytes.