We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes classical and recent worst-case algorithmic results on computing joins. In addition, we use our framework and the same algorithm to show a series of what are colloquially known as beyond worst-case results. The framework allows us to prove results for data stored in Btrees, multidimensional data structures, and even multiple indices per table. A key idea in our framework is formalizing the inference one does with an index as a type of geometric resolution; transforming the algorithmic problem of computing joins to a geometric problem. Our notion of geometric resolution can be viewed as a geometric analog of logical resolution. In addition to the geometry and logic connections, our algorithm can also be thought of as backtracking search with memoization.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Funnily enough, this hypergraph view is used to describe symptomatic query complexity for cyclical joins, the simplest if which is "count triangles in adjacency list" (naive RDBMS yields O(n²) on pathological data, despite the wrist case optimal tactic being something like O(n + #Triangles), with #Triangles limited inherently to O(n^(1.5))).
See https://arxiv.org/abs/1404.0703 for some reading material and one particular way at beyond worst case (i.e., sharing worst case asympotics with the best constant time algorithm, but better performance on non-pathological data (a more precise notion is complicated; there are at least 3 different useful definitions)) runtime performance.
AFAIK the worst cyclical query on a 2-column table is "k-clique counting", from a POV of performance between WCOJ and what Postgres can do (asympotics).
It's all about efficient range reads and seek operations.
You can compute set operations pretty efficiently using sorted indices that support a "find next or greater" operation.
For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate := next(candidate) on each set, updating the candidate with the next smallest possible value, and adding it to the output set when a candidate was returned by all sets.
The algorithm is worst case optimal up to a log factor, and can even be extended to perform generic constraint programming and multiway joins as a subset of that.
Fascinatingly it's related to the DPLL algorithm for sat solving.
http://erikdemaine.org/papers/SODA2000/
https://arxiv.org/abs/1404.0703
https://arxiv.org/abs/1310.3314
https://arxiv.org/abs/1203.1952
https://arxiv.org/abs/1803.09930
Some of the more exciting ideas I've seen recently:
http://arxiv.org/abs/1310.3314 - Understanding the core difficulty in answering relational queries and examples of problems for which current query optimisers always produce plans which are asymptotically suboptimal
http://arxiv.org/abs/1404.0703 - The first theoretical analysis which can relate the choice of indexes to worst-case bounds. Presents a single join algorithm which is asymptotically optimal on every problem without even using cardinality estimates.
http://arxiv.org/abs/1210.0481 - A join algorithm that meets some of the bounds of the above paper and is also fast in practice and can be incrementally…
Read the full comment
maintained.
https://infosys.uni-saarland.de/projects/octopusdb.php - Treating index creation, query optimising, view materialisation, incremental maintenance etc as one large optimisation problem.
http://www.vldb.org/pvldb/vol4/p539-neumann.pdf - Compiling query plans to LLVM because the query plans / indexes are good enough to make the plan cpu-bound instead of memory-bound
http://hyper-db.de/HyperTechReport.pdf - Running OLAP and OLTP workloads on the same database without interference
It seems possible that in the future, far from having a Cambrian explosion of specialised databases, we will be able to store everything in a single db and treat questions of data layout, partitioning, indexing etc as a direct optimisation problem.
Out of the examples I would take a look at the LogicBlox Stuff,
they gave join algorithm research a big push with their Leapfrog-Triejoin.
The following papers ascend in difficulty, and are based on each other, but offer a fascinating glimpse into the connection of DPLL SAT solving and Conjunctive Query evaluation.
https://openproceedings.org/2014/conf/icdt/Veldhuizen14.pdf
https://arxiv.org/abs/1310.3314
https://arxiv.org/abs/1404.0703
As for reasoning and decidability, I think we need to clarify the decidability we're talking about. Decision problems are decidable or undecidable, and when one talks about decidability for a logic one usually means the decision problem…
Read the full comment
wether a given formula of the logic is valid or not.
Everything finite is always decidable, because you can just enumerate all possibilities.
And logics without negation (like Datalog without stratified negation) are generally (?) decidable because you can just construct a Herbrand interpretation accordingly.
However when we talk about correctness and formal reasoning there are other decision problems which are relevant, most of them revolve around stuff like "does this program implement this specification?", "does this program terminate?", "is this program keeping these invariants?", "are these two programs equal?"
Note that even if these problems are undecidable, it doesn't mean that they're always undecidable, just that they're not decidable in general, e.g. the halting problem is undecidable, but I can give you infinitely many turing-machines which always halt.
The pure side effect free fragment you describe is still at least as (?) powerful as FOL, even HOL if you include the meta predicates like call, thanks to the build-in predicates like forall. Heck I guess the build-in arithmetic alone will cost you decidability (of validity).
Datalog is even more restricted than what you describe and equality of two Datalog programs is not decidable according to
https://core.ac.uk/download/pdf/82609701.pdf
So the question is, how much reasoning a.k.a. how many decision problems can you actually do/solve on Datalog and Prolog. For Datalog, I'd say quite a bit, but not everything, and for Prolog I'd argue very little. But both give you a lot of power in return and that's the price you have to pay.
Edit:
And yeah, I don't envy you, on having to work with side-effectful prolog code. At some point it's just writing C with extra steps, ground through the Warren Abstract Sausage Machine. ^^'
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.