Algorithm speeds up evaluating complex database queries near submodular width
Guanaco: A Global-Uniformity Algorithm for Near-Submodular-Width Conjunctive Query Evaluation
DatabasesData Structures and Algorithms
Summary
Evaluating complex database queries can take a long time, especially as the queries become more complicated. The authors present an algorithm called Guanaco that can perform these queries much faster by cleverly organizing the data and the way pieces of it are combined. This algorithm works especially well for queries measured by something called submodular width and uses simple steps to make the data consistent and uniform, which helps speed up the process. Their method generalizes well and offers a simpler explanation for why such query evaluations can be done efficiently.
What this means in practice
- •For database engineers: Optimize query planning systems by using Guanaco to efficiently evaluate complex conjunctive queries near the submodular width limit.
- •For data integration teams: Improve performance when joining multiple large data sets by applying Guanaco’s global uniformity step to control degree discrepancies.
A theory result. No direct application yet.
Authors
Mahmoud Abo Khamis, Hubie Chen
Abstract
We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive queries. We believe the algorithm and its analysis to be notably simple, indeed, together we believe they form a highly simple argument that conjunctive query evaluation can be performed in essentially submodular width time. In the case of Boolean conjunctive queries, the algorithm is based on interleaving three simple primitives: a subroutine for establishing a form of consistency; a subroutine for establishing global uniformity, which, briefly speaking, partitions relations as needed to control discrepancies between average degree and maximum degree; and, a simple step that joins pairs of existing relations to form new relations.