Backjumping, yet and again

[Chat-Wane]

Implement a generic BackendBackjumpingIterator, long overdue.

Let us consider the following query:

SELECT * WHERE {
  ?s p1 ?o .
  ?o p2 ?x .
  ?s p3 ?y }

The join order is that of the query. Sometimes, ?s p3 ?y may fail, yet the engine enumerates all bindings of ?o p2 ?x. It would be better to backjump [1] directly to the first triple pattern since the variable ?s is a probable cause of failure.

In terms of implementation, this means:

• Throwing an exception in the has_next() with the incriminated variable and let the iterator that actually sets the variable catch it, so it can next() it accordingly.
• For the sake of genericity, we must wrap each scan iterators into a backjump iterator that can throw, and make sure that every iterator properly forwards the exception.

This demonstrated remarkable performance improvements in compiled version of SPARQL queries, does this holds on the iterator/volcano model?

---

[1] R. J. Bayardo Jr., and D. P. Miranker. Processing Queries for First-Few Answers. In Proceedings of the fifth international conference on Information and knowledge management (1996).

[Chat-Wane]

Backjumping iterators constitute a mean to provide sideways information passing between iterators. This is a key component of an improved WanderJoin approach [2]: a random step is better exploited by creating a batch of random walks starting from this step, but if the former random step fails to meet a constraint of downstream iterators, the whole batch can be cancelled. Therefore, the overhead of this optimization becomes marginal, while it provides more accurate estimates.

Issue

The current iterator model is pull-based. For instance, when we have tp1 . tp2, this is the iterator of tp2 that calls for new items from tp1. Which means that we cannot exploit exceptions to provide the mechanism for free.

Indeed, we would prefer a push-based iterator model where tp1 feeds tp2 with new items, therefore when tp2 fails, it throws, and the throw is catch by the producer tp1 that can feed a different item (ofc, it makes more sense when 3 iterators are involved, as shown in the first example of this thread).

---

[2] Pan Hu, and Boris Motik. Accurate Sampling-Based Cardinality Estimation for Complex Graph Queries. ACM Trans. Datab. Syst., Vol. 49, No. 3, Article 12. (2024)

[Chat-Wane]

Dug up an old performance analysis of backjumps (executing rust compiled SPARQL queries) where we observe a significant improvement when the join order is not optimal (top). The improvement is marginal when the join order is good (bottom).

(Performed on JobRDF)