Efficient Massively Parallel Join Optimization for Large Queries
Authors:
Open Access
- 10 June 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 122-135
Abstract
Modern data analytical workloads often need to run queries over a large number of tables. An optimal query plan for such queries is crucial for being able to run these queries within acceptable time bounds. However, with queries involving many tables, finding the optimal join order becomes a bottleneck in query optimization. Due to the exponential nature of join order optimization, optimizers resort to heuristic solutions after a threshold number of tables. Our objective is two fold: (a) reduce the optimization time for generating optimal plans; and (b) improve the quality of the heuristic solution. In this paper, we propose a new massively parallel algorithm, MPDP, that can efficiently prune the large search space (via a novel plan enumeration technique) while leveraging the massive parallelism offered by modern hardware (Eg: GPUs). When evaluated on real-world benchmark queries with PostgreSQL, MPDP is at least an order of magnitude faster compared to state-of-the-art techniques for large analytical queries. As a result, we are able to increase the heuristic-fall-back limit from 12 relations to 25 relations with same time budget in PostgreSQL. Also, to handle queries with even larger number of tables, we augment MPDP to a well-known heuristic, IDP2 (iterative DP version 2) and a novel heuristic, UnionDP. By systematically exploring a much larger search space, these heuristics provides query plans that are up to 7 times cheaper as compared to the state-of-the-art techniques while being faster to compute.Keywords
All Related Versions
Funding Information
- EU H2020 project SmartDataLake (825041)
This publication has 16 references indexed in Scilit:
- Parallelizing query optimization on shared-nothing architecturesProceedings of the VLDB Endowment, 2016
- How good are query optimizers, really?Proceedings of the VLDB Endowment, 2015
- Optimizing join enumeration in transformation-based query optimizersProceedings of the VLDB Endowment, 2014
- Parallelizing query optimizationProceedings of the VLDB Endowment, 2008
- Dynamic programming strikes back2008
- Iterative dynamic programmingACM Transactions on Database Systems, 2000
- Rapid bushy join-order optimization with Cartesian products1996
- A genetic algorithm tutorialStatistics and Computing, 1994
- On the optimal nesting order for computing N -relational joinsACM Transactions on Database Systems, 1984
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973