apache / apache/jena

TransformFilterDisjunction returns duplicate solutions for overlapping disjuncts

Open
#4,160 1 comment 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.