Push versus pull-based loop fusion in query engines

DOI10.1017/S0956796818000102MaRDI QIDQ4577821zbMATH OpenOpenAlexWikidataFDO

Authors Amir Shaikhha, Mohammad Dashti, Christoph Koch

Publication date 3 August 2018

Published in Journal of Functional Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.09166

Mathematics Subject Classification ID

Theory of programming languages (68N15) Database theory (68P15)

Abstract: Database query engines use pull-based or push-based approaches to avoid the materialization of data across query operators. In this paper, we study these two types of query engines in depth and present the limitations and advantages of each engine. Similarly, the programming languages community has developed loop fusion techniques to remove intermediate collections in the context of collection programming. We draw parallels between the DB and PL communities by demonstrating the connection between pipelined query engines and loop fusion techniques. Based on this connection, we propose a new type of pull-based engine, inspired by a loop fusion technique, which combines the benefits of both approaches. Then we experimentally evaluate the various engines, in the context of query compilation, for the first time in a fair environment, eliminating the biasing impact of ancillary optimizations that have traditionally only been used with one of the approaches. We show that for realistic analytical workloads, there is no considerable advantage for either form of pipelined query engine, as opposed to what recent research suggests. Also, by using microbenchmarks we show that our proposed engine dominates the existing engines by combining the benefits of both.

Recommendations

• scientific article; zbMATH DE number 3900188
• Query batching optimization in database systems
• On the complexity of loop fusion
• scientific article; zbMATH DE number 1875352
• Languages and Compilers for Parallel Computing

Cites work

• A type-theoretic reconstruction of the visitor pattern
• Architecture of a Database System
• Automatic synthesis of typed -programs on term algebras
• Comprehending monads
• Deforestation: Transforming programs to eliminate trees
• Exploiting vector instructions with generalized stream fusion
• Harnessing the multicores: nested data parallelism in Haskell
• scientific article; zbMATH DE number 176725 (Why is no real title available?)
• Improving flow analyses via ΓCFA
• Optimizing object queries using an effective calculus
• Shortcut fusion for accumulating parameters & zip-like functions
• The essence of the <scp>Iterator</scp> pattern
• Types and programing languages

Describes a project that uses

Uses Software

• GHC
• Scala
• MonetDB
• DBToaster
• Volcano

This page was built for publication: Push versus pull-based loop fusion in query engines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577821)