TransformFilterDisjunction returns duplicate solutions for overlapping disjuncts
- Dominant language
- Java
- Stars
- 1.4k
- Forks
- 712
- Avg merge
- 15h 41m
- Merged PRs (30d)
- 53
Description
### Version
6.1.0
### What happened?
Hi there!
I ran some benchmarks against the [LDBC Semantic Publishing Benchmark](https://ldbcouncil.org/benchmarks/spb/) suite. One particular query (A14) turned out to be very slow so I had my Claude investigate the issue. It seems that when you write duplicate filter conditions it leads to ARQ evaluating the query twice. Example: FILTER(?f = X || ?f = X).
I had it write a patch and test which I'd like to provide as an PR. What follows is a description of the bug generated by Claude:
## Summary
The default optimizer's `TransformFilterDisjunction` rewrites `filter(e1 || e2, P)` into
`(disjunction branch1 branch2)`, evaluating the pattern once per disjunct. When a solution
satisfies more than one disjunct it is returned once per satisfied disjunct, where the
filter returns it once. The rewrite is a union, not a partition, and nothing checks that
the disjuncts are mutually exclusive.
## Minimal repro
```java
Model m = ModelFactory.createDefaultModel();
RDFParser.fromString("""
.
.
.
""", Lang.NTRIPLES).parse(m);
String q = """
SELECT ?s WHERE {
?s ?f
FILTER(?f = || ?f = )
}""";
try (QueryExecution qe = QueryExecutionFactory.create(q, m)) {
System.out.println(ResultSetFormatter.consume(qe.execSelect()));
}
```
Prints **4**; the answer is **2** (s1 and s2, once each). With
`qe.getContext().set(ARQ.optFilterDisjunction, false)` or optimization off it prints 2.
The identical-disjunct form is not artificial: LDBC SPB's generated queries contain
`FILTER((?primaryFormat = cwork:InteractiveFormat) || (?primaryFormat = cwork:InteractiveFormat))`
(query template A14), so on that benchmark every ARQ-based engine evaluates the whole
nine-triple pattern twice and returns a doubled bag that only the query's `LIMIT` hides.
Overlap does not require identical disjuncts. Also affected, for example:
- `FILTER(?x = :c || ?x != :d)` — a solution with `?x = :c` satisfies both disjuncts and
is returned twice (the current `TestTransformFilters.disjunction02` pins this expansion);
- `FILTER(?x = "1"^^xsd:integer || ?x = "01"^^xsd:integer)` — different terms, same value;
- `FILTER(?x = :c || ?y = :d)` — different variables, one solution can satisfy both.
## Cause
`TransformFilterDisjunction.expandDisjunction` creates one branch per disjunct with no
mutual-exclusion condition. `OpDisjunction` is executed as a plain union (bag semantics,
no dedup), which is only equivalent to the filter when at most one disjunct can be true
of any one solution.
## Proposed fix
Apply the transform only when every disjunct tests one and the same variable against a
constant (`=` or `sameTerm`) and the constants are pairwise known to be different values
(`NodeValue.notSameValueAs`, treating an indeterminate comparison as possibly equal) —
which makes the branches an exact partition. This keeps the motivating `?x IN (...)`
cases, including mixed IRI/literal lists, and leaves every other disjunction evaluated
as the filter it is.
### Relevant output and stacktrace
```shell
```
### Are you interested in making a pull request?
Yes
Contributor guide
Research direction
Start at TransformFilterDisjunction.expandDisjunction and read TestTransformFilters.disjunction02, which pins the current expansion. Verify the minimal duplicate-disjunct reproduction and the existing disjunction tests, then ensure overlapping disjuncts do not duplicate solutions while safe disjoint cases still use the optimization. Run the relevant filter transformation tests and the reproduction query to confirm the result.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100