Speeding up Qdags with Generalized Hypertree Decompositions

Diego Arroyuelo, Gabriel Carmona, Gonzalo Navarro, and Matilde Rivas

Qdags have proved to be extremely compact representations of graph databases that can still solve basic graph patterns in worst-case-optimal time. Their times are competitive in practice for queries with few variables, but their performance quickly degrades as the number of variables grows over 3. In this paper we combine Qdags with a Generalized Hypertree Decomposition (GHD) of the query, into subqueries with fewer variables. Apart from possibly breaking the AGM bound, implementing GHDs over Qdags has the advantages of reducing the number of variables per subquery, of exploiting the compositionality of Qdags (which return the output in Qdag form), and of using little working space for the intermediate results, which is a problem of GHD compared to standard worst-case-optimal algorithms. We implement the new operations required on Qdags (semijoins) to apply Yannakakis' algorithm over the final acyclic query. We also implement algorithms that find the optimal GHD according to the AGM bounds of the subqueries and the specificities of the Qdag cost model. The result is a much stronger Qdag-based index that can efficiently handle large queries while matching or outperforming competing systems.