Dataset set difference operation is very slow

[edmondchuc]

The current Dataset set difference operation is very slow. On a reasonably small dataset with around 30k statements, it takes around 30 minutes to finish processing.

rdflib/rdflib/graph.py

Lines 878 to 888 in 91c8cbc

	def __sub__(self, other: Graph) -> Graph:
	"""Set-theoretic difference.
	BNode IDs are not changed."""
	try:
	retval = type(self)()
	except TypeError:
	retval = Graph()
	for x in self:
	if x not in other:
	retval.add(x)
	return retval

By using python's builtin set, I was able to reduce the processing time down to less than 1 second.

# Convert datasets to sets of quads for faster diff operations
logger.info("Extracting quads from current dataset")
ds_quads = set(ds.quads())
logger.info(f"Quads: {len(ds_quads)}")
logger.info("Extracting quads from previous dataset")
previous_ds_quads = set(previous_ds.quads())
logger.info(f"Quads: {len(previous_ds_quads)}")

# Compute diffs using set operations
# Statements in previous but not in current = deletions
logger.info("Computing deletions (previous - current)")
to_delete_quads = previous_ds_quads - ds_quads
# Statements in current but not in previous = additions
logger.info("Computing additions (current - previous)")
to_add_quads = ds_quads - previous_ds_quads

[edmondchuc]

Thinking about it a bit more, I think the current RDFLib code is correct, and the issue might be with the MemoryStore implementation. The current implementation code is correct because it delegates the lookup to the store implementation, potentially using store-specific optimisations for lookups, whereas my example code above dumps all the quads into an in-memory set to perform the diff.

[WhiteGobo]

I think a little optimization would be good, but just to go on a little tangent:

Theoreticly Graphs or rather Datasets dont need to list all their statements, when using iter, right? So imagine we have graph that describes some property, we might describe in different systems of measurement:

...
cube_descriptions: Dataset
measurement_systems: Namespace
properties: Namespace
my: Namespace
metric = cube_descriptions.query("""
    SELECT ?x
    WHERE { GRAPH measurement_systems:metric
        {my:first_cube properties:height ?x.}
    }
""")
print(metric)
# x: 3cm

empirical = cube_descriptions.query("""
    SELECT ?x
    WHERE { GRAPH measurement_systems:empirical
        {my:first_cube properties:height ?x.}
    }
""")
print(empirical)
# x: 1.181102 inch

So we now that our Dataset contains both triples (my:first_cube p:height "3"^^measurement:cm) and (my:first_cube p:height "1.18"^^measurement:inch). But we might not want to list both triples when iterating over the the graph. So now when we use sub in graph, using the current implementation of rdflib and using set holds different solutions:

g = Graph().parse("""my:first_cube p:height "3"^^measurement:cm""")
list(g - cube_descriptions)
# []
list(set(g) - set(cube_descriptions)))
# [(my:first_cube p:height "3"^^measurement:cm)]

In practice, i dont think anyone uses rdflib for something like this, so i think we could still place somewhere an optimization using sets and then just add somewhere a comment, so that people can read, what behaviour to expect.

[edmondchuc]

For those interested, I wrote a tiny script to benchmark the set theoretic difference operations over three RDFLib stores, and also compared how those stores performed with Python's builtin set. The RDF dataset used in the benchmarks was an n-quads file with 1000 statements.

RDFLib Dataset Set Difference Benchmark
Data file: data.nq

============================================================
Benchmarking: MemoryStore
============================================================

  Run 1/3:
    Parse time: 0.0410s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 2.4620s
    Result size: 370 quads

  Run 2/3:
    Parse time: 0.0398s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 2.3786s
    Result size: 370 quads

  Run 3/3:
    Parse time: 0.0561s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 2.4091s
    Result size: 370 quads

  Average parse time: 0.0456s
  Average set difference time: 2.4166s

============================================================
Benchmarking: MemoryStore (Python set)
============================================================

  Run 1/3:
    Parse time: 0.0377s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0033s
    Result size: 370 quads

  Run 2/3:
    Parse time: 0.0405s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0037s
    Result size: 370 quads

  Run 3/3:
    Parse time: 0.0387s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0032s
    Result size: 370 quads

  Average parse time: 0.0390s
  Average set difference time: 0.0034s

============================================================
Benchmarking: Oxigraph (oxrdflib)
============================================================

  Run 1/3:
    Parse time: 0.1588s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 9.1865s
    Result size: 370 quads

  Run 2/3:
    Parse time: 0.0393s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 9.1923s
    Result size: 370 quads

  Run 3/3:
    Parse time: 0.0442s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 9.1626s
    Result size: 370 quads

  Average parse time: 0.0808s
  Average set difference time: 9.1805s

============================================================
Benchmarking: Oxigraph (Python set)
============================================================

  Run 1/3:
    Parse time: 0.0606s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0134s
    Result size: 370 quads

  Run 2/3:
    Parse time: 0.0754s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0139s
    Result size: 370 quads

  Run 3/3:
    Parse time: 0.0416s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 0.0141s
    Result size: 370 quads

  Average parse time: 0.0592s
  Average set difference time: 0.0138s

============================================================
Benchmarking: BerkeleyDB
============================================================

  Run 1/3:
    Parse time: 0.1174s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 16.3041s
    Result size: 370 quads

  Run 2/3:
    Parse time: 0.1495s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 16.3482s
    Result size: 370 quads

  Run 3/3:
    Parse time: 0.1293s
    Dataset 1 size: 1000 quads
    Dataset 2 size: 1000 quads
    Set difference time: 16.2860s
    Result size: 370 quads

  Average parse time: 0.1321s
  Average set difference time: 16.3128s

============================================================
Benchmarking: BerkeleyDB (Python set)
============================================================

  Run 1/3:
    Parse time: 0.0923s
    Dataset 1 size: 1370 quads
    Dataset 2 size: 1370 quads
    Set difference time: 0.0354s
    Result size: 740 quads

  Run 2/3:
    Parse time: 0.1080s
    Dataset 1 size: 1370 quads
    Dataset 2 size: 1370 quads
    Set difference time: 0.0348s
    Result size: 740 quads

  Run 3/3:
    Parse time: 0.0688s
    Dataset 1 size: 1370 quads
    Dataset 2 size: 1370 quads
    Set difference time: 0.0680s
    Result size: 740 quads

  Average parse time: 0.0897s
  Average set difference time: 0.0461s

============================================================
SUMMARY
============================================================

Store                     Avg Parse (s)   Avg Diff (s)
-------------------------------------------------------
MemoryStore (default)     0.0456          2.4166
MemoryStore (Python set)  0.0390          0.0034
Oxigraph (oxrdflib)       0.0808          9.1805
Oxigraph (Python set)     0.0592          0.0138
BerkeleyDB                0.1321          16.3128
BerkeleyDB (Python set)   0.0897          0.0461

Fastest set difference: MemoryStore (Python set) (0.0034s)

[edmondchuc]

There's a cost to materialising the statements from the store when using Python's set. But it's worth it when we only need to pay the cost to access the store once as opposed to M*N in the current implementation. Plus, dumping statements from stores are usually quite fast (and definitely faster than arbitrary lookups when db cursors are involved).

The additional memory overhead of materialising statements is also a worthwhile trade-off, as it enables a usable and scalable implementation where the current approach is too expensive to be practical.