ProvSQL makes HAVING provenance practical by avoiding the self-join explosion

SQL provenance systems can explain which input rows produced an answer, but HAVING clauses create an awkward case: the answer depends on an aggregate and on a condition over that aggregate. A new ProvSQL implementation gives those conditions a direct provenance semantics instead of expanding them into repeated self-joins—and its benchmark shows why that distinction becomes operationally important.

The benchmark

The authors evaluated revision b3445d59 of the open-source ProvSQL PostgreSQL extension on a probabilistic image-retrieval database derived from COCO 2017 detections. The workload contained 239,377 images and 1,570,565 detected-object rows. Queries asked for images containing at least or at most k refrigerators, with k ranging from 0 to 15; no image contained more than 13. This is one fixed real-data workload, not a general SQL benchmark.

Each query was run three times on an Intel Core i7-12700 desktop with 64 GB RAM, Ubuntu 22.04 and PostgreSQL 18.6. The paper reports mean planning-plus-execution time and one-standard-deviation error bars. It compares ProvSQL’s direct HAVING semantics with an equivalent aggregation-free self-join rewrite.

For symbolic provenance, the direct implementation stayed between 0.2 and 0.6 seconds across the sweep. On COUNT() >= k, the self-join path was faster only through k=4; by k=11 it was 14× slower, and by k=15 it was 106× slower. For COUNT() <= k, crossover came at k=2, with the rewrite 77× slower at k=11 and 108× slower at k=15. Planning the 16-way self-join at k=15 took 62 seconds by itself.

Probability does not rescue the rewrite

Adding exact probability evaluation left the direct path between 0.2 and 0.5 seconds for every k. The specialized Poisson-binomial method produced no measurable gain on this workload because each image had at most 13 matching objects; the general evaluator could already handle those small circuits.

The rewritten queries paid for both additional joins and larger provenance circuits. Up to k=11 they were 12×–17× slower for the >= condition and 4×–8× slower for <=. At k=15, where planning dominated, the reported gaps reached 83× and 115× respectively.

What this result establishes

This is stronger than a paper-only algorithm claim. The implementation is pinned to a public ProvSQL commit, the project is MIT-licensed, its aggregate-provenance interface is documented, and the algebraic results are accompanied by machine-checked Lean proofs. That gives readers a concrete rerun path rather than only a chart.

The result is still narrow. It uses one object-detection database, one desktop, one PostgreSQL version and groups capped at 13 relevant rows. The paper also disables PostgreSQL’s genetic query optimizer because its selected plans timed out beyond five minutes for rewrites with at least 12 joins; exhaustive planning kept execution near 3 seconds but increased planning cost rapidly. The benchmark therefore demonstrates the structural cost of encoding HAVING through self-joins on this workload—not a universal 115× database speedup.

The practical conclusion is precise: when provenance must survive aggregate filtering, the query representation itself can become the bottleneck. A direct aggregate-aware circuit stayed stable as the threshold increased; the logically equivalent relational rewrite did not.