  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, in order to handle queries with even larger number
of tables, we augment MPDP to a well known heuristic, IDP$_2$ (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.
