Abstract

State-of-the-art query engines pursue a pipeline-based query execution model. Using such a model, a pipeline computes a query plan fragment up to a pipeline breaker resulting in an intermediate result, which will be consumed by subsequent pipelines. Interestingly, the ordering of execution of such pipelines poses an opportunity for memory savings. Within this paper, we tackle the challenge to compute an optimal schedule of the individual pipelines with respect to minimizing the memory consumption needed for a particular query execution plan. We therefore will precisely state the problem and show the potential of an optimal pipeline execution ordering. We will then provide a formal model to describe the search space and propose four different algorithms to identify optimal/near-optimal schedules. The paper also presents insights into our implementation within a prototypical query execution engine and reports results relying on the Join Order Benchmark scenarios. Specifically, the experimental evaluation focuses on the identified memory savings and the stability of the query runtime behavior. Furthermore, the evaluation reports on the small overhead of the proposed search algorithms during the planning time, thus emphasizing the practical applicability of our approach.