Speed up listGraphNodes of TDB?

[SimonBin]

Version

4.7.0-SNAPSHOT

Question

In some queries like graph ?g {}, it is desirable to get a list of all named graphs currently in a dataset. However, this is exceptionally slow for huge datasets with billions of quads, as Jena has to run quads.findAll().distinct(), or even for some query types where ?g is unbound.

I wonder if it could be sped up somehow by making use of a G??? index, by bisecting to the right node after the end of each Graph and thus avoiding having to iterate through all quads?

[afs]

Looking for graph names uses the GSPO - the iterator is in the ideal place at the end of a graph because the graph boundaries are not significant in the index. The next quad is a new graph.

A special iterator could be written that worked directly on an index to find only the first part of a tuple (the indexes don't know about tuples - they store Record of which only the key part issued). The fast skip from finding a value for the first 8 bytes to the next different value.

This would be specific to the BPT implementation.

Maintaining a separate, additional datastructure for the graph names is possible but not-trivial in the delete(quad) case.

It's easy for adding data (check whether the graph name has been seen - a set in other words) but knowing when a graph name is not long in-use is not easy.

There's no reference count of triples in a graph which is needed to know if a delete removes the last quad in a graph.

Maintaining a reference count means knowing whether an add has an effect, or whether an add is for a triple that already exists. Ditto delete.

Indexes return the information at the low level (this is TDB2/BPT specific), but it isn't exposed all the way up the stack. It would restrict the possibility of remote or async streaming data if there is a response coming back from "add(quad)" or "delete(quad)". It doesn't work for TDB3/RocksDB where changes are batched to amortize overheads.

[SimonBin]

The fast skip from finding a value for the first 8 bytes to the next different value.

this was what I was thinking might be feasible. Currently, it takes 2 minutes on our data set (1bn tripples, 40 graphs) to just list the graphs. Which has a steep slow down on the query that Lorenz posted

which would be possible to answer in under 1 second if we can have the list of graphs

[LorenzBuehmann]

As usual thank's for the insights and the discussion Andy!
And as usual, I can provide a very simply example from our current project that makes us wondering if we could do something else:

TDB2 with ~ 1 billion triples in named graphs to keep the data separate for possible updates (e.g. an event dataset updates on a daily/weekly basis)

"Give me all events in a given region resp. bounding box"

SELECT ?e {
  GRAPH ?g {
    ?e spatial:withinBoxGeom ("POLYGON((19.49 50.62,26.87 50.626,26.87 46.43,19.49 46.43,19.49 50.62))"^^geo:wktLiteral)
  }
}

it's a very simple query here as sketch, but from what we could see from code or guess from JStack dump during execution, it iterates all quads with a distinct on the iterator to keep seen ?g bindings, then for each new seen graph it does the spatial index lookup - it's a custom property, so no way to make use of an pXXX index here. It definitely takes time to handle all graphs

For now we do some query rewriting that inlines all named graphs as a filter expression which seems to work as there is some query optimizer that expands FILTER(?g IN (:g1, :g2 , :g3, ...))

If you have some other hint for iterating all named graphs more efficiently, I'd be happy to test it.

[afs]

That's two questions, both different from the original.

The "distinct" would be made a distinctAdjacent (which is WIP).

The property function changes the situation because IIRC it's not a struct multi-function. Any optimization risks changing the query.

[rvesse]

See #1641 for the distinctAdjacent() change, it gives about a 20% performance boost vs 4.6.1 in my testing on some synthetic data (10s of thousands of names graphs with a few thousand triples per graph)

I haven't reproduced the exact scenario seen here (a few named graphs with millions of triples in each), will try that next

[afs]

There are two code paths.

Only property functions, which force everything to be in node-space will hit DatasetGraph.listGraphNodes. Property function disable quad form. withinBoxGeom being a good example - as a pattern, it could be moved out of the GRAPH block.

ec33bde should catch the other code path in NodeId space that is used by GRAPH ?g {}.

[SimonBin]

thanks for the ideas, I guess adjacent just doesn't matter much for this small amount of graphs:

duration of select ?e { ?e spatial:withinBoxGeom(...) } + unionDefaultGraph => 0.098 seconds

---

duration of select ?g { graph ?g {} } group by ?g => 83 seconds

duration of select ?e { graph ?g { ?e spatial:withinBoxGeom(...) } } => 82 seconds

---

with your patches

---

duration of select ?g { graph ?g {} } group by ?g => 82 seconds

duration of select ?e { graph ?g { ?e spatial:withinBoxGeom(...) } } => 82 seconds

---

[rvesse]

Even with our respective patches the iterator still has to iterate the full G??? index to find the graph nodes so you're still touching every record in the index and the iteration time will scale with the number of triples. You save a little bit of computation by using distinctAdjacent instead of distinct (and get fixed memory usage to boot) but the performance gain lessens as the size of the graphs increase.

Just ran a test with 125 million triples over 10 graphs and only got about a 10% boost with my patch

I expect @afs will probably look at the fast skip at some point in the future, but that's way lower in the TDB stack than I'm comfortable touching

[afs]

If the graphs are known - and we have only just heard it is 40 graphs - try putting the graphs into a general dataset where graph names is a set keys operation.

I expect @afs will

No.

[SimonBin]

the graphs are not known, but we will probably fake it by collecting the graphs at one point in time and injecting them and periodically update the list

[SimonBin]

another case probably similar to our spatial case. but does not involve custom property functions

SELECT (count(distinct ?thing) as ?count)
WHERE {
    graph ?g {
        ?thing a/rdfs:subClassOf* coy:Powerplant ;
    }
}

[afs]

A special iterator could be written that worked directly on an index to find only the first part of a tuple

The iterator that walks the B+trees data access is BPTreeRangeIterator. That would be code to use as a starting point for a new, separate iterator that does a unique prefix scan of an index, skipping recursing down the tree when first and last slow in a branch node have the same prefix.

[rvesse]

Yep I took a stab at this in between other bits today - see #1655 for the WiP