Optimizing iceberg queries with complex joins

Published

Conference Paper

© 2017 ACM. Iceberg queries, commonly used for decision support, find groups whose aggregate values are above or below a threshold. In practice, iceberg queries are often posed over complex joins that are expensive to evaluate. This paper proposes a framework for combining a number of techniques-a-priori, memoization, and pruning- to optimize iceberg queries with complex joins. A-priori pushes partial GROUP BY and HAVING condition before a join to reduce its input size. Memoization caches and reuses join computation results. Pruning uses cached results to infer that certain tuples cannot contribute to the final query result, and short-circuits join computation. We formally derive conditions for correctly applying these techniques. Our practical rewrite algorithm produces highly efficient SQL that can exploit combinations of optimization opportunities in ways previously not possible. We evaluate our PostgreSQL-based implementation experimentally and show that it outperforms both baseline PostgreSQL and a commercial database system.

Full Text

Duke Authors

Cited Authors

  • Walenz, B; Roy, S; Yang, J

Published Date

  • May 9, 2017

Published In

Volume / Issue

  • Part F127746 /

Start / End Page

  • 1243 - 1244

International Standard Serial Number (ISSN)

  • 0730-8078

International Standard Book Number 13 (ISBN-13)

  • 9781450341974

Digital Object Identifier (DOI)

  • 10.1145/3035918.3064053

Citation Source

  • Scopus