rdf4j
rdf4j copied to clipboard
eclipse-rdf4j
LmdbStore picks wrong join order leading to timeouts
Current Behavior
We have observed a performance regression when running a rather complex query (see below) on an LmdbStore repository with 2M+ statements, containing ~60_000 nanopublications, as compared to NativeStore. NativeStore completes the query in ~5 seconds. LmdbStore times out, despite multiple retries.
Query:
prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>
prefix fip: <https://w3id.org/fair/fip/terms/>
prefix dct: <http://purl.org/dc/terms/>
prefix dce: <http://purl.org/dc/elements/1.1/>
prefix npa: <http://purl.org/nanopub/admin/>
prefix npx: <http://purl.org/nanopub/x/>
prefix np: <http://www.nanopub.org/nschema#>
select ?fip_index ?fip_title ?decl_np where {
graph npa:graph {
?fip_index npx:hasNanopubType npx:NanopubIndex .
?fip_index npa:hasValidSignatureForPublicKey ?pubkey .
filter not exists { ?index_np_x npx:invalidates ?fip_index ; npa:hasValidSignatureForPublicKey ?pubkey . }
?fip_index np:hasAssertion ?index_a .
?fip_index rdfs:label ?fip_title .
?fip_index dct:created ?index_date .
?decl_np npa:hasValidSignatureForPublicKey ?decl_pubkey .
filter not exists { ?decl_np_x npx:invalidates ?decl_np ; npa:hasValidSignatureForPublicKey ?decl_pubkey . }
?decl_np npx:hasNanopubType fip:FIP-Declaration .
?decl_np dct:created ?date .
}
graph ?index_a {
?fip_index npx:includesElement ?decl_np .
}
filter not exists {
graph npa:graph {
?fip_newer_index npa:hasValidSignatureForPublicKey ?pubkey .
filter not exists { ?fip_newer_index_x npx:invalidates ?fip_newer_index ; npa:hasValidSignatureForPublicKey ?pubkey . }
?fip_newer_index dct:created ?newer_date .
# Matching on the title string is an ugly hack:
?fip_newer_index rdfs:label ?fip_title .
}
filter(?newer_date > ?index_date).
}
}
Index setup: spoc,posc,ospc,cspo,cpos,cosp. Note: to use this index setup in LmdbStore, you need to use the code from my recent PR fixing a bug that limits indexes to 5 (#5279). But you can also reproduce the issue without the cosp index.
Dataset to reproduce (no worries, it's all open data...): https://ostrzyciel.pl/nextcloud/s/jyD98QtHky4fJZH
We've figured out that you can work around this issue by changing the last portion of the query to:
filter not exists {
# Matching on the title string is an ugly hack:
graph npa:graph {
?fip_newer_index rdfs:label ?fip_title .
}
graph npa:graph {
?fip_newer_index npa:hasValidSignatureForPublicKey ?pubkey .
filter not exists { ?fip_newer_index_x npx:invalidates ?fip_newer_index ; npa:hasValidSignatureForPublicKey ?pubkey . }
?fip_newer_index dct:created ?newer_date .
}
filter(?newer_date > ?index_date).
}
basically, forcing the ?fip_newer_index rdfs:label ?fip_title pattern to be evaluated first.
Initially I thought this was because LmdbStore was picking the wrong indexes for the job, so I went digging. I hacked RDF4J until it gave up a query plan with index names, and I got this:
LmdbStore query plan
Projection (resultSizeActual=674, totalTimeActual=60.0s, selfTimeActual=4.39ms)
╠══ ProjectionElemList
║ ProjectionElem "fip_index"
║ ProjectionElem "fip_title"
║ ProjectionElem "decl_np"
╚══ Filter (resultSizeActual=674, totalTimeActual=60.0s, selfTimeActual=4.37ms)
├── Not (totalTimeActual=59.9s)
│ Exists (totalTimeActual=59.9s)
│ Filter (resultSizeActual=0, totalTimeActual=59.9s, selfTimeActual=59.7ms)
│ ╠══ And (totalTimeActual=0.058ms)
│ ║ ├── Compare (>)
│ ║ │ Var (name=newer_date)
│ ║ │ Var (name=index_date)
│ ║ └── Not (totalTimeActual=0.058ms)
│ ║ Exists (totalTimeActual=0.058ms)
│ ║ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=0.058ms, selfTimeActual=0.009ms)
│ ║ ╠══ StatementPattern [index: cpos] FROM NAMED CONTEXT (costEstimate=4.2K, resultSizeEstimate=8.4K, resultSizeActual=4, totalTimeActual=0.046ms, selfTimeActual=0.046ms) [left]
│ ║ ║ s: Var (name=fip_newer_index_x)
│ ║ ║ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ ║ ║ o: Var (name=fip_newer_index)
│ ║ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ║ ╚══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K, resultSizeActual=4, totalTimeActual=0.003ms, selfTimeActual=0.003ms) [right]
│ ║ s: Var (name=fip_newer_index_x)
│ ║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ ║ o: Var (name=pubkey)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ Join (JoinIterator) (resultSizeActual=1.8K, totalTimeActual=59.8s, selfTimeActual=30.1s)
│ ├── StatementPattern [index: cpos] FROM NAMED CONTEXT (costEstimate=3.9M, resultSizeEstimate=2.8K, resultSizeActual=41.4M, totalTimeActual=8.3s, selfTimeActual=8.3s) [left]
│ │ s: Var (name=fip_newer_index)
│ │ p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
│ │ o: Var (name=newer_date)
│ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ └── Join (JoinIterator) (resultSizeActual=1.8K, totalTimeActual=21.5s, selfTimeActual=2.5s) [right]
│ ╠══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=84, resultSizeEstimate=7.0K, resultSizeActual=1.8K, totalTimeActual=19.0s, selfTimeActual=19.0s) [left]
│ ║ s: Var (name=fip_newer_index)
│ ║ p: Var (name=_const_9285ccfc_uri, value=http://www.w3.org/2000/01/rdf-schema#label, anonymous)
│ ║ o: Var (name=fip_title)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K, resultSizeActual=1.8K, totalTimeActual=1.44ms, selfTimeActual=1.44ms) [right]
│ s: Var (name=fip_newer_index)
│ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ o: Var (name=pubkey)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=704, totalTimeActual=96.3ms, selfTimeActual=25.2ms)
╠══ StatementPattern [index: posc] FROM NAMED CONTEXT (costEstimate=340321.5M, resultSizeEstimate=1.0M, resultSizeActual=9.0K, totalTimeActual=6.73ms, selfTimeActual=6.73ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_4668a6cc_uri, value=http://purl.org/nanopub/x/includesElement, anonymous)
║ o: Var (name=decl_np)
║ c: Var (name=index_a)
╚══ Filter (resultSizeActual=704, totalTimeActual=64.4ms, selfTimeActual=9.0ms) [right]
├── And (totalTimeActual=2.48ms)
│ ╠══ Not (totalTimeActual=1.61ms)
│ ║ Exists (totalTimeActual=1.61ms)
│ ║ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=1.61ms, selfTimeActual=0.081ms)
│ ║ ├── StatementPattern [index: cpos] FROM NAMED CONTEXT (costEstimate=46, resultSizeEstimate=8.4K, resultSizeActual=0, totalTimeActual=1.53ms, selfTimeActual=1.53ms) [left]
│ ║ │ s: Var (name=decl_np_x)
│ ║ │ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ ║ │ o: Var (name=decl_np)
│ ║ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ║ └── StatementPattern FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K) [right]
│ ║ s: Var (name=decl_np_x)
│ ║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ ║ o: Var (name=decl_pubkey)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ Not (totalTimeActual=0.873ms)
│ Exists (totalTimeActual=0.873ms)
│ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=0.873ms, selfTimeActual=0.286ms)
│ ├── StatementPattern [index: cpos] FROM NAMED CONTEXT (costEstimate=46, resultSizeEstimate=8.4K, resultSizeActual=320, totalTimeActual=0.467ms, selfTimeActual=0.467ms) [left]
│ │ s: Var (name=index_np_x)
│ │ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ │ o: Var (name=fip_index)
│ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ └── StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K, resultSizeActual=320, totalTimeActual=0.121ms, selfTimeActual=0.121ms) [right]
│ s: Var (name=index_np_x)
│ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ o: Var (name=pubkey)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=52.9ms, selfTimeActual=12.4ms)
╠══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=0.50, resultSizeEstimate=636, resultSizeActual=4.5K, totalTimeActual=7.38ms, selfTimeActual=7.38ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_cfcf8555_uri, value=http://www.nanopub.org/nschema#hasAssertion, anonymous)
║ o: Var (name=index_a)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=33.1ms, selfTimeActual=12.0ms) [right]
├── StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=1.00, resultSizeEstimate=360, resultSizeActual=4.5K, totalTimeActual=4.61ms, selfTimeActual=4.61ms) [left]
│ s: Var (name=fip_index)
│ p: Var (name=_const_6162292e_uri, value=http://purl.org/nanopub/x/hasNanopubType, anonymous)
│ o: Var (name=_const_76ef696e_uri, value=http://purl.org/nanopub/x/NanopubIndex, anonymous)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=16.6ms, selfTimeActual=2.39ms) [right]
╠══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=1.00, resultSizeEstimate=1.6K, resultSizeActual=1.0K, totalTimeActual=3.52ms, selfTimeActual=3.52ms) [left]
║ s: Var (name=decl_np)
║ p: Var (name=_const_6162292e_uri, value=http://purl.org/nanopub/x/hasNanopubType, anonymous)
║ o: Var (name=_const_15c396b8_uri, value=https://w3id.org/fair/fip/terms/FIP-Declaration, anonymous)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=10.6ms, selfTimeActual=1.33ms) [right]
├── StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=53, resultSizeEstimate=2.8K, resultSizeActual=1.0K, totalTimeActual=0.895ms, selfTimeActual=0.895ms) [left]
│ s: Var (name=fip_index)
│ p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
│ o: Var (name=index_date)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=8.42ms, selfTimeActual=1.44ms) [right]
╠══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=53, resultSizeEstimate=2.8K, resultSizeActual=1.0K, totalTimeActual=0.996ms, selfTimeActual=0.996ms) [left]
║ s: Var (name=decl_np)
║ p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
║ o: Var (name=date)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=5.99ms, selfTimeActual=1.6ms) [right]
├── StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=84, resultSizeEstimate=7.0K, resultSizeActual=1.0K, totalTimeActual=0.886ms, selfTimeActual=0.886ms) [left]
│ s: Var (name=fip_index)
│ p: Var (name=_const_9285ccfc_uri, value=http://www.w3.org/2000/01/rdf-schema#label, anonymous)
│ o: Var (name=fip_title)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=1.0K, totalTimeActual=3.5ms, selfTimeActual=1.52ms) [right]
╠══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K, resultSizeActual=1.0K, totalTimeActual=0.945ms, selfTimeActual=0.945ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
║ o: Var (name=pubkey)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ StatementPattern [index: cspo] FROM NAMED CONTEXT (costEstimate=324, resultSizeEstimate=104.8K, resultSizeActual=1.0K, totalTimeActual=1.03ms, selfTimeActual=1.03ms) [right]
s: Var (name=decl_np)
p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
o: Var (name=decl_pubkey)
c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
The indexes are fine. I then started suspecting the join order is wrong, so I ran the exact same query on NativeStore:
NativeStore query plan
Projection (resultSizeActual=5.5K, totalTimeActual=1.5s, selfTimeActual=1.91ms)
╠══ ProjectionElemList
║ ProjectionElem "fip_index"
║ ProjectionElem "fip_title"
║ ProjectionElem "decl_np"
╚══ Filter (resultSizeActual=5.5K, totalTimeActual=1.5s, selfTimeActual=15.5ms)
├── Not (totalTimeActual=496ms)
│ Exists (totalTimeActual=496ms)
│ Filter (resultSizeActual=0, totalTimeActual=496ms, selfTimeActual=86.4ms)
│ ╠══ And (totalTimeActual=64.3ms)
│ ║ ├── Compare (>)
│ ║ │ Var (name=newer_date)
│ ║ │ Var (name=index_date)
│ ║ └── Not (totalTimeActual=64.3ms)
│ ║ Exists (totalTimeActual=64.3ms)
│ ║ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=64.3ms, selfTimeActual=14.1ms)
│ ║ ╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=3.4K, resultSizeEstimate=6.9K, resultSizeActual=24.9K, totalTimeActual=27.8ms, selfTimeActual=27.8ms) [left]
│ ║ ║ s: Var (name=fip_newer_index_x)
│ ║ ║ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ ║ ║ o: Var (name=fip_newer_index)
│ ║ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ║ ╚══ StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K, resultSizeActual=24.9K, totalTimeActual=22.4ms, selfTimeActual=22.4ms) [right]
│ ║ s: Var (name=fip_newer_index_x)
│ ║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ ║ o: Var (name=pubkey)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ Join (JoinIterator) (resultSizeActual=57.9K, totalTimeActual=346ms, selfTimeActual=52.5ms)
│ ├── StatementPattern FROM NAMED CONTEXT (costEstimate=9.7M, resultSizeEstimate=8.5K, resultSizeActual=57.9K, totalTimeActual=60.1ms, selfTimeActual=60.1ms) [left]
│ │ s: Var (name=fip_newer_index)
│ │ p: Var (name=_const_9285ccfc_uri, value=http://www.w3.org/2000/01/rdf-schema#label, anonymous)
│ │ o: Var (name=fip_title)
│ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ └── Join (JoinIterator) (resultSizeActual=57.9K, totalTimeActual=233ms, selfTimeActual=38.2ms) [right]
│ ╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K, resultSizeActual=57.9K, totalTimeActual=104ms, selfTimeActual=104ms) [left]
│ ║ s: Var (name=fip_newer_index)
│ ║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ ║ o: Var (name=pubkey)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ StatementPattern FROM NAMED CONTEXT (costEstimate=224, resultSizeEstimate=50.2K, resultSizeActual=57.9K, totalTimeActual=90.4ms, selfTimeActual=90.4ms) [right]
│ s: Var (name=fip_newer_index)
│ p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
│ o: Var (name=newer_date)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=12.7K, totalTimeActual=980ms, selfTimeActual=68.6ms)
╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=39137.1M, resultSizeEstimate=48.2K, resultSizeActual=57.5K, totalTimeActual=167ms, selfTimeActual=167ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_4668a6cc_uri, value=http://purl.org/nanopub/x/includesElement, anonymous)
║ o: Var (name=decl_np)
║ c: Var (name=index_a)
╚══ Filter (resultSizeActual=12.7K, totalTimeActual=744ms, selfTimeActual=47.3ms) [right]
├── And (totalTimeActual=63.4ms)
│ ╠══ Not (totalTimeActual=19.6ms)
│ ║ Exists (totalTimeActual=19.6ms)
│ ║ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=19.6ms, selfTimeActual=1.43ms)
│ ║ ├── StatementPattern FROM NAMED CONTEXT (costEstimate=41, resultSizeEstimate=6.9K, resultSizeActual=0, totalTimeActual=18.2ms, selfTimeActual=18.2ms) [left]
│ ║ │ s: Var (name=decl_np_x)
│ ║ │ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ ║ │ o: Var (name=decl_np)
│ ║ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ║ └── StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K) [right]
│ ║ s: Var (name=decl_np_x)
│ ║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ ║ o: Var (name=decl_pubkey)
│ ║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ ╚══ Not (totalTimeActual=43.8ms)
│ Exists (totalTimeActual=43.8ms)
│ Join (JoinIterator) (resultSizeActual=0, totalTimeActual=43.8ms, selfTimeActual=6.63ms)
│ ├── StatementPattern FROM NAMED CONTEXT (costEstimate=41, resultSizeEstimate=6.9K, resultSizeActual=10.2K, totalTimeActual=26.0ms, selfTimeActual=26.0ms) [left]
│ │ s: Var (name=index_np_x)
│ │ p: Var (name=_const_65655733_uri, value=http://purl.org/nanopub/x/invalidates, anonymous)
│ │ o: Var (name=fip_index)
│ │ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
│ └── StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K, resultSizeActual=10.2K, totalTimeActual=11.2ms, selfTimeActual=11.2ms) [right]
│ s: Var (name=index_np_x)
│ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ o: Var (name=pubkey)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=634ms, selfTimeActual=27.0ms)
╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=0.50, resultSizeEstimate=59.4K, resultSizeActual=28.7K, totalTimeActual=82.9ms, selfTimeActual=82.9ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_cfcf8555_uri, value=http://www.nanopub.org/nschema#hasAssertion, anonymous)
║ o: Var (name=index_a)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=524ms, selfTimeActual=33.2ms) [right]
├── StatementPattern FROM NAMED CONTEXT (costEstimate=1.00, resultSizeEstimate=693, resultSizeActual=28.7K, totalTimeActual=38.3ms, selfTimeActual=38.3ms) [left]
│ s: Var (name=fip_index)
│ p: Var (name=_const_6162292e_uri, value=http://purl.org/nanopub/x/hasNanopubType, anonymous)
│ o: Var (name=_const_76ef696e_uri, value=http://purl.org/nanopub/x/NanopubIndex, anonymous)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=452ms, selfTimeActual=17.4ms) [right]
╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=1.00, resultSizeEstimate=17.6K, resultSizeActual=23.0K, totalTimeActual=235ms, selfTimeActual=235ms) [left]
║ s: Var (name=decl_np)
║ p: Var (name=_const_6162292e_uri, value=http://purl.org/nanopub/x/hasNanopubType, anonymous)
║ o: Var (name=_const_15c396b8_uri, value=https://w3id.org/fair/fip/terms/FIP-Declaration, anonymous)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=200ms, selfTimeActual=16.6ms) [right]
├── StatementPattern FROM NAMED CONTEXT (costEstimate=92, resultSizeEstimate=8.5K, resultSizeActual=23.0K, totalTimeActual=26.1ms, selfTimeActual=26.1ms) [left]
│ s: Var (name=fip_index)
│ p: Var (name=_const_9285ccfc_uri, value=http://www.w3.org/2000/01/rdf-schema#label, anonymous)
│ o: Var (name=fip_title)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=157ms, selfTimeActual=20.0ms) [right]
╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K, resultSizeActual=23.0K, totalTimeActual=23.3ms, selfTimeActual=23.3ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
║ o: Var (name=pubkey)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=114ms, selfTimeActual=17.0ms) [right]
├── StatementPattern FROM NAMED CONTEXT (costEstimate=220, resultSizeEstimate=48.4K, resultSizeActual=23.0K, totalTimeActual=24.9ms, selfTimeActual=24.9ms) [left]
│ s: Var (name=decl_np)
│ p: Var (name=_const_98105c55_uri, value=http://purl.org/nanopub/admin/hasValidSignatureForPublicKey, anonymous)
│ o: Var (name=decl_pubkey)
│ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
└── Join (JoinIterator) (resultSizeActual=23.0K, totalTimeActual=72.1ms, selfTimeActual=18.5ms) [right]
╠══ StatementPattern FROM NAMED CONTEXT (costEstimate=224, resultSizeEstimate=50.2K, resultSizeActual=23.0K, totalTimeActual=27.2ms, selfTimeActual=27.2ms) [left]
║ s: Var (name=fip_index)
║ p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
║ o: Var (name=index_date)
║ c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
╚══ StatementPattern FROM NAMED CONTEXT (costEstimate=224, resultSizeEstimate=50.2K, resultSizeActual=23.0K, totalTimeActual=26.4ms, selfTimeActual=26.4ms) [right]
s: Var (name=decl_np)
p: Var (name=_const_41af0e58_uri, value=http://purl.org/dc/terms/created, anonymous)
o: Var (name=date)
c: Var (name=_const_d85dcec0_uri, value=http://purl.org/nanopub/admin/graph, anonymous)
The key difference is for patterns with s: Var (name=fip_newer_index). Comparing the join orders directly, we see this:
| LmdbStore | NativeStore |
|---|---|
| newer_date | fip_title |
| fip_title | pubkey |
| pubkey | newer_date |
If we use the GRAPH npa:graph { ?fip_newer_index rdfs:label ?fip_title . } trick, it forces this pattern to come first, and we get a similar join order as in NativeStore, which fixes the issue.
If I understand all this correctly (please bear with me, it's my first time with RDF4J's query planner), then the issue is that LMDB incorrectly estimates the cardinality for the pattern ?fip_newer_index dct:created ?newer_date . – resultSizeEstimate=2.8K, resultSizeActual=41.4M. It thinks that it's a very selective pattern, when in reality it's not.
And then I tried looking at LmdbStore's cardinality estimation algorithm, sighed, and decided that an RDF4J core wizard will probably know better. 😆
Expected Behavior
The query should complete on LmdbStore in about the same time as in NativeStore.
Steps To Reproduce
- Set up an LmdbStore with
spoc,posc,ospc,cspo,cposindexes. - Load it up with this data: https://ostrzyciel.pl/nextcloud/s/jyD98QtHky4fJZH
- Run the query listed at the start of the issue.
- Observe the timeout.
Version
latest main
Are you interested in contributing a solution yourself?
Perhaps?
Anything else?
I'd be happy to contribute a solution, but I do not understand the internals of LmdbStore enough.
Hi @Ostrzyciel,
we are aware of this problem. LMDB does not expose node counts and so we have to use sampling to compute estimations. Either we could use more samples and/or we add HLL based counts.
All ideas are Welcome :-)
I'll take a look next week.
Best regards, Ken
Thanks!
we are aware of this problem. LMDB does not expose node counts and so we have to use sampling to compute estimations. Either we could use more samples and/or we add HLL based counts.
Ah! That explains a lot, I had no idea about this limitation. Shame, because RocksDB does expose an API like this: https://github.com/facebook/rocksdb/wiki/Approximate-Size I guess it comes down to a different design philosophy (LMDB – minimalism and small footprint, Rocks – features galore).
HLL or another sketch algorithm may make sense. I had a very good experience with Apache DataSketches before. I don't exactly understand how to employ HLL in this specific case, but there are also sketches that allow for intersection operations – maybe that?
One very wild and probably very incorrect idea would be to simply subtract the memory pointer of the first value in range from the last's memory pointer, and divide by average key+value size (which should be pretty predictable). From what I can see, the Java API does expose these pointers. But, I have zero idea if they are actually monotonic and at least semi-linear.
I've added a commit for testing some approaches here: https://github.com/kenwenzel/rdf4j/tree/GH-5283-lmdb-cardinality-estimation
I've changed the calculation of estimated rows between sampled buckets and it helps for the query.
But we have to investigate this further.
You can play with Statistics.MAX_BUCKETS and Statistics.MAX_SAMPLES_PER_BUCKET.
BTW, if you know that a pattern is highly selective then you should put it into a subquery as those are evaluated first.
I've added a commit for testing some approaches here: https://github.com/kenwenzel/rdf4j/tree/GH-5283-lmdb-cardinality-estimation
I've changed the calculation of estimated rows between sampled buckets and it helps for the query. But we have to investigate this further. You can play with
Statistics.MAX_BUCKETSandStatistics.MAX_SAMPLES_PER_BUCKET.
Nice! Yeah, more samples makes sense. I'd love to help with this, but I'd have to dive deep into the algorithm first, which is not easy :)
BTW, if you know that a pattern is highly selective then you should put it into a subquery as those are evaluated first.
Yes, that's correct, but in this case the pattern depends on a join with an earlier part of the query (via the ?fip_title variable). From what I understand, a subquery wouldn't help in this case. The trick with putting the pattern in a separate GRAPH clause worked, because it forced a specific join order.
It all very much reminds me of the various hacks implemented in Blazegraph that let you reorder joins however you like: https://github.com/blazegraph/database/wiki/QueryOptimization#join-order-optimization But the nice part was that you could always enable the RTO, which would try a few orders for you and pick the best one... very friendly for beginners. But that's a separate issue, I think 😆
@kenwenzel I'm sure you've seen the HLL estimator that the ExtensibleStore has: https://github.com/eclipse-rdf4j/rdf4j/blob/main/core/sail/extensible-store/src/main/java/org/eclipse/rdf4j/sail/extensiblestore/evaluationstatistics/ExtensibleDynamicEvaluationStatistics.java
Maybe it'll help if you want to develop something similar for the LMDB Store.
@hmottestad Yes - this is really cool. We've already exchanged on this some time ago. I've just wanted to circumvent the staleness problem by not relying on a second data structure that needs maintenance. But maybe we need to re-investigate such solutions. Apache DataSketches also looks very interesting.
fyi: Halyard had a nice take on calculating statistics and using them at runtime using VoID - https://www.linkedin.com/pulse/inside-halyard-6-statistics-based-acceleration-sparql-adam-sotona/
just saw https://github.com/JervenBolleman/void-generator from @JervenBolleman and it looks similar to what halyard does for statistics. can this void-generator be used for query planning?
also, this might play well with adding service-description support as some point (https://www.w3.org/TR/sparql11-service-description/)
@nguyenm100 Thank you for the pointers. The VoiD-based generation is indeed interesting for static data sets. I think for dynamic data we need to rely on incremental computations of statistics or on some heuristics like implemented in NativeStore or LmdbStore.
@nguyenm100 https://github.com/nguyenm100 yes a VoID file can be used to generate statistics useful for query planning. Comunica uses it today for that purpose. I am actually going to work the other way round, and generate a VoID file from the query planning statistics.
On Wed, Apr 16, 2025 at 3:47 PM kenwenzel @.***> wrote:
@nguyenm100 https://github.com/nguyenm100 Thank you for the pointers. The VoiD-based generation is indeed interesting for static data sets. I think for dynamic data we need to rely on incremental computations of statistics or on some heuristics like implemented in NativeStore or LmdbStore.
— Reply to this email directly, view it on GitHub https://github.com/eclipse-rdf4j/rdf4j/issues/5283#issuecomment-2809649515, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHQYFMKYKNMKQUKAZ2LNY32ZZNQBAVCNFSM6AAAAAB2BH3CU2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQMBZGY2DSNJRGU . You are receiving this because you were mentioned.Message ID: @.***> kenwenzel left a comment (eclipse-rdf4j/rdf4j#5283) https://github.com/eclipse-rdf4j/rdf4j/issues/5283#issuecomment-2809649515
@nguyenm100 https://github.com/nguyenm100 Thank you for the pointers. The VoiD-based generation is indeed interesting for static data sets. I think for dynamic data we need to rely on incremental computations of statistics or on some heuristics like implemented in NativeStore or LmdbStore.
— Reply to this email directly, view it on GitHub https://github.com/eclipse-rdf4j/rdf4j/issues/5283#issuecomment-2809649515, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHQYFMKYKNMKQUKAZ2LNY32ZZNQBAVCNFSM6AAAAAB2BH3CU2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQMBZGY2DSNJRGU . You are receiving this because you were mentioned.Message ID: @.***>
-- Jerven Bolleman @.***
@kenwenzel not sure query planning requires up to the second stats to be useful. when I was playing with halyard, even a general ratio was useful (eg generally, the cardinality of this subject is greater than the cardinality of this other subject) and stats generation when a big update occurred was all that was needed. that said, if we have confidence in the incremental computations, by all means...
another argument for generated statistics is that they could be run to fix the query planner whereas a run-time heuristics may require a code change to fix.