Support for merge join and ordered indexes

[hmottestad]

Some data sources can return statements in a particular order. Data stored in a B-tree has a natural order due to the natur of a B-tree.

The current join strategy for RDF4J is the iterate over the left data source and for each row create a new iterator from the right data source. This takes advantage the fact that we can bind the result from the left iterator when we create the right iterator, which makes it very selective.

For larger datasets the above approach can cause a lot of IO requests. An example could be that we are joining all ?a a foaf:Person with ?a foaf:age ?age. If we have 100 000 000 people, then that ends up being 1 000 000 000 new iterators for retrieving the age.

Instead we can take advantage of the ordering of the indexes and retrieve:

• ?a a foaf:Person from the OPSC index (O and P are constant)
• ?a foaf:age ?age from the PSOC index (P is constant)

These two iterators would both be ordered on the subject (S) variable (?a). We can then do a merge join, which is very efficient both IO wise and memory wise.

This issue aims to:

• support inner join using merge join
• allow for specifying the order when retrieving statements
• inform the query join optimizer about which statement orderings that are available
• pick merge join when possible (and appropriate)
• support ordered indexes in the ExtensibleStore

[kenwenzel]

This would be really cool.

[kenwenzel]

@hmottestad How will this compare to the existing hash joins?

[hmottestad]

The hash joins are used for negation, so it's a bit of a different use case. Merge join is meant to be an alternative to regular join, but faster for large joins.

Our current approach is akin to indexed nested loop join, we loop through the left side and do indexed lookups on the right side. With smart read ahead and caching it would be possible to reduce the IO, but worst case we end up with O(N log(N) ) reads from disk with a B+ tree index.

With merge join we would do two range queries against the index, so basically O(2) reads. It's not quite true to call it O(2) because the range query reads one block at a time from the B+ tree, so we could call it O(N/K) where K is the size of each block.

So it's basically a more optimal way of joining large amounts of data when the underlying store has ordered indexes.

Does LMDB have ordered indexes?

[hmottestad]

(The hash joins are sometimes used for joins where there are scoping issues, so it's not only for negation.)

[kenwenzel]

Yes, LmdbStore uses the same indexing scheme as the NativeStore.

We also experiment with hash-joins to optimize fetching of time-series data where each property of an item has multiple time-tagged values:
https://github.com/linkedfactory/linkedfactory-pod/blob/3948b866f227749576428ed72c58cc0cf12cf28a/bundles/io.github.linkedfactory.service/src/main/scala/io/github/linkedfactory/service/rdf4j/KvinEvaluationStrategy.java#L192

[JervenBolleman]

We should think about how we can pass this about information about sorted iterators on to GROUP BY and ORDER BY operators.

e.g.

SELECT ?o
WHERE {?s ?p ?o}
ORDER BY ?o

If the statementpattern evaluation step/iterarator provides information to order step/iterator we can avoid redoing a lot of work.

Same for the GROUP BY, if encounter order is fixed or partially fixed we might avoid building the large hash table.

Knowing the order can also help filters. e.g.

SELECT ?o
WHERE {?s ?p ?o . FILTER (?o < 10)}

If we know that ?o is ordered we can stop iterating the first time we hit ?o < 10 = false. This kind of early termination can be a big win.

[hmottestad]

Group by is probably the most important one. In the short term it can probably be solved by adding a getOrder() to the CloseableIteration interface. Then the group by iterator can decide for itself if it can take advantage of ordered data. The more advanced approach would be for the join order optimizer to take into consideration the order of the underlying data to produce a better query plan.

The order of the index doesn't have to be using the same comparator as SPARQL uses for ORDER BY or <, etc. It's actually more likely that it will be incompatible because the common approach to indexes is to use a long number to represent an RDF Value and have a lookup table that can convert the long number to the RDF Value. Essentially this means that it's not very likely that we will be able to optimize ORDER BY or filters with comparison operators.

[JervenBolleman]

The order of the index doesn't have to be using the same comparator as SPARQL uses for ORDER BY or <, etc. It's actually more likely that it will be incompatible because the common approach to indexes is to use a long number to represent an RDF Value and have a lookup table that can convert the long number to the RDF Value. Essentially this means that it's not very likely that we will be able to optimize ORDER BY or filters with comparison operators.

FYI @hmottestad for the readonly sail I am still working on the comparison between the long index for the values is equivalent to the SPARQL values comparison. So for me it could work.

[hmottestad]

We could check if the comparator returned by SailDataset is a ValueComparator instance.