Dynamic programming strikes back

Abstract

Two highly efficient algorithms are known for optimally ordering joins while\navoiding cross products:\nDPccp, which is based on dynamic programming, and Top-Down Partition Search, \nbased on memoization.\nBoth have two severe limitations:\nThey handle only (1) simple (binary) join predicates and (2) inner joins.\nHowever, real queries may contain complex join predicates, involving more than \ntwo relations,\nand outer joins as well as other non-inner joins.\n\nTaking the most efficient known join-ordering algorithm, DPccp, as a starting \npoint,\nwe first develop a new algorithm, DPhyp,\nwhich is capable to handle complex join predicates efficiently.\nWe do so by modeling the query graph as a (variant of a) hypergraph and then \nreason about its\nconnected subgraphs.\nThen, we present a technique to exploit this capability to efficiently handle\nthe widest class of non-inner joins dealt with so far.\nOur experimental results show that this reformulation of\nnon-inner joins as complex predicates can improve optimization\ntime by orders of magnitude, compared to known algorithms dealing with complex \njoin predicates\nand non-inner joins.\nOnce again, this gives dynamic programming a distinct advantage over current \nmemoization techniques.