optimizing queries with LIMIT or extremely large intermediate results

[pfps]

The following query from WDbench opts is silly, but it illustrates a place where QLever could be faster. Because the OPTIONAL can only increase the size of the result, it is only necessary to create 10000000 results for the join in the main basic graph pattern. What QLever used to do was to relatively quickly run out of memory for the join, which wasn't great because only a few of these results are needed to produce a final result. With the recent changes QLever instead runs out of time, which is arguably worse. If the limit was pushed down through the sort and onto the join, QLever would perform much better on this query, and also other queries where a LIMIT can be used to limit the number of intermediate results.

Even if LIMIT isn't pushed down, the size of the intermediate result is known, so a good cost, in both time and space, to compute it can be determined. If either is significantly greater than the available resource, then the query could be aborted without actually performing the join. Care does have to be taken here, as evidenced by Virtuoso's laughable time estimates.

SELECT * WHERE {
  ?x1 <http://www.wikidata.org/prop/direct/P106> <http://www.wikidata.org/entity/Q188094> .
  ?x2 <http://www.wikidata.org/prop/direct/P27> <http://www.wikidata.org/entity/Q155> .
  ?x3 <http://www.wikidata.org/prop/direct/P31> <http://www.wikidata.org/entity/Q5> .
  OPTIONAL {
    ?x3 <http://www.wikidata.org/prop/direct/P21> ?x4 .
  }
}
LIMIT 10000000

[pfps]

I tried ad-freiburg/qlever#2699 on my benchmarks.

It turns 71 failures in WDbench opts into 4. The non-failures take about 11% of the time they took before. WDbench opts was the worst-performing of all the benchmark components that I run.

[hannahbast]

@pfps Thanks for the update, a few questions:

1. Can you give an example of one of the four queries? Did these four queries already fail before or is this a new failure?
2. Do I understand correctly, that Cleanup code that keeps track of triple statistics during index building #2629 improves the running time of 67 queries by almost a factor of 10?
3. By components you mean the different parts of WDBench?

A comment: WDBench and its siblings are great for "fuzzing" (lots of queries, including many strange ones, which is great for finding bugs). As a performance benchmark, they are strange because they put a lot of weight on a small and rather random selection of weird queries. In this case, 67 queries improving due to a single minor tweak of limited practical relevance

[pfps]

@hannahbast

• The four remaining failures have always failed.
• The PR is not Cleanup code that keeps track of triple statistics during index building #2629, but Overhaul LIMIT + OFFSET and optimize more agressively #2699. The PR improves the run time of WDbench opts by about a factor of 10 and cuts the number of failures from 71 to 4.
• By components I mean what I report on - the different parts of WDbench plus your WDQS benchmark, the WGPB benchmark, and the SCHOLIA benchmark.

Here is the summary table for all of these except the SCHOLIA benchmark, comparing the QLever current as of a few days ago and PR #2699. Only the time for non-failing queries is counted and it is the arithmetic sum of the times, in seconds.

Benchmark            Count    results-current-2026-02-04   | - - results-current-2026-02-08     - - |     
                           Fail  Time        Results       dFail Time/  Time        Results   Results/   
wgpb                  850    0     11           168,112      0   1.05     11           168,112   1.00   
wdqs                  298    2    880       211,679,712      0   0.99    872       211,679,712   1.00   
single_bgps           280    0      2       303,961,810      0   1.21      3       303,961,810   1.00   
multiple_bgps         681    3    112     4,284,577,655      0   1.00    112     4,284,577,655   1.00   
opts                  498   71  6,669     2,450,782,822    -67   0.11    703     2,450,782,822   1.00   
paths                 660    8  1,431     1,018,423,330      0   0.99  1,415     1,018,423,330   1.00   
c2rpqs                539    2    838     1,023,893,693      0   1.00    839     1,023,893,693   1.00   
TOTAL                3806   86  9,946     9,293,487,134    -67   0.40  3,958     9,293,487,134   1.00   

Here are the four opt queries that fail in PR #2699.

SELECT * WHERE { ?x1 <http://www.wikidata.org/prop/direct/P17> <http://www.wikidata.org/entity/Q159> . ?x2 <http://www.wikidata.org/prop/direct/P31> <http://www.wikidata.org/entity/Q486972> . OPTIONAL { ?x2 <http://www.wikidata.org/prop/direct/P625> ?x3 . } OPTIONAL { ?x4 <http://www.wikidata.org/prop/direct/P1082> ?x4 . }  } LIMIT 10000000
SELECT * WHERE { ?x1 <http://www.wikidata.org/prop/direct/P1971> ?x2 . ?x1 <http://www.wikidata.org/prop/direct/P26> ?x3 . ?x1 <http://www.wikidata.org/prop/direct/P39> <http://www.wikidata.org/entity/Q11696> . OPTIONAL { ?x1 <http://www.wikidata.org/prop/direct/P18> ?x4 . ?x5 <http://www.wikidata.org/prop/direct/P18> ?x6 . }  } LIMIT 10000000
SELECT * WHERE { ?x1 <http://www.wikidata.org/prop/direct/P30> ?x2 . ?x1 <http://www.wikidata.org/prop/direct/P31> <http://www.wikidata.org/entity/Q6256> . OPTIONAL { ?x2 <http://www.wikidata.org/prop/direct/P242> ?x3 . ?x1 <http://www.wikidata.org/prop/direct/P41> ?x4 . ?x5 <http://www.wikidata.org/prop/direct/P41> ?x6 . }  } LIMIT 10000000
SELECT * WHERE { ?x1 <http://www.wikidata.org/prop/direct/P31> <http://www.wikidata.org/entity/Q123266> . OPTIONAL { ?x1 <http://www.wikidata.org/prop/direct/P131> ?x2 . } OPTIONAL { ?x3 <http://www.wikidata.org/prop/direct/P1082> ?x4 . ?x1 <http://www.wikidata.org/prop/direct/P36> ?x3 . ?x5 <http://www.wikidata.org/prop/direct/P625> ?x6 . } OPTIONAL { ?x1 <http://www.wikidata.org/prop/direct/P2046> ?x7 . } OPTIONAL { ?x1 <http://www.wikidata.org/prop/direct/P1082> ?x8 . }  } LIMIT 10000000