QTM: Modelling Query Execution with Tasks
Steffen Zeuch, Johann-Christoph Freytag · 2014
Over the last decade, several approaches for parallel query execution have emerged. The performance of these approaches is mainly affected by the non-manageable cache hierarchy. However, each approach exploits the capabilities of modern processors differently. Furthermore, the comparison is diffi-cult due to different operator-to-resource assignments dur-ing run-time (scheduling strategy) and the number of tuples each operator processes (chunk size). In this paper, we first classify common DBMS by their scheduling strategies and chunk sizes. Then, we propose a task model called Query Task Model (QTM) that opens a design space for database schedules. With QTM, we gen-eralize the modeling of parallel query execution such that different approaches become comparable. Using QTM, we model an arbitrary QEP as a set of tasks. Each task repre-sents a particular piece of work on a subset of data. Our evaluation of different schedules modeled in QTM shows, that a tuple-at-a-time schedule cannot exploit mod-ern hardware efficiently. In contrast, an operator-at-time schedule increases the performance due to increased cache utilization. However, a buffer-at-a-time schedule that takes the cache hierarchy into account outperforms schedules that do not. Furthermore, we show that a schedule that is op-timized for data cache locality does not necessarily outper-form a schedule optimized for instruction cache locality. We identify a sweet spot where the ratio of data locality and instruction locality produces the fastest schedules. 1.