You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@jena.apache.org by "faubulous (via GitHub)" <gi...@apache.org> on 2026/08/21 12:16:20 UTC
[PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
faubulous opened a new pull request, #4161:
URL: https://github.com/apache/jena/pull/4161
GitHub issue resolved #4160
Pull request Description:
`TransformFilterDisjunction` rewrites `filter(e1 || e2, P)` into a disjunction that evaluates `P` once per disjunct, so a solution satisfying k disjuncts is returned k times where the filter returns it once. `FILTER(?x = :c || ?x = :c)` returns every matching row twice under the default optimizer, and `FILTER(?x = :c || ?x != :d)` returns rows with `?x = :c` twice; disabling `optFilterDisjunction` restores the correct multiset.
Two changes together restore filter semantics:
- **Repeated disjuncts are dropped first** — `(A || A)` is `A` — so the degenerate duplicate that generated queries really contain (LDBC SPB emits `FILTER(?pf = :c || ?pf = :c)`) collapses to a single equality that grounds the pattern, rather than being either doubled (before) or left unoptimized (declined).
- **The expansion is applied only when the disjuncts are mutually exclusive**: every remaining disjunct must test one and the same variable against a constant (`=` or `sameTerm`) and the constants must be pairwise known to be different values (`NodeValue.notSameValueAs`, with an indeterminate comparison treated as possibly equal). That makes the rewrite an exact partition. The motivating case — `?x IN (...)` over distinct constants, including mixed IRI/literal lists — keeps its expansion; every other disjunction is now evaluated as the filter it is.
Several existing algebra tests pinned the unsound expansions; their expectation is now that the filter is left alone.
----
- [x] Tests are included.
- [ ] Documentation change and updates are provided for the [Apache Jena website](https://github.com/apache/jena-site/)
- [x] Commits have been squashed to remove intermediate development commit messages.
- [x] Key commit messages start with the issue number (GH-xxxx)
By submitting this pull request, I acknowledge that I am making a contribution to the Apache Software Foundation under the terms and conditions of the [Contributor's Agreement](https://www.apache.org/licenses/contributor-agreements.html).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "afs (via GitHub)" <gi...@apache.org>.
afs commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-6044039846
@faubulous -- Which forms actually show up for real in the benchmark?
Is it just the two part `||` of `A = B || A = B` case?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881372712
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
Sorry for the spam. I did not anticipate that Claude would write responses in my name without asking. That's a no go. Never worked with it on public PRs so a newbie error. Sincere apologies.
So.. the way I see it is that these do provide similar functionality but differ in the details. There might be a way to consolidate them, but then we'd need to touch a lot more code in other classes. This widens the scope of this fix. Should this be handled in a different PR or do you want to address this here? To me the code duplication is another defect on its own already.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3867357471
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
It looks like there are two places this sort of logic is being done; maybe the intent is to keep them separate. A third, similar implementation might benefit from sharing some code; caution that it may be intended to keep the implementations separate. [Place 1](https://github.com/apache/jena/blob/790b3dc08fccb6be1ea2868b97bfcbae8f113062/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterInequality.java#L173), [Place 2](https://github.com/apache/jena/blob/790b3dc08fccb6be1ea2868b97bfcbae8f113062/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterEquality.java#L174)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881277115
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
Review Comment:
Good question. It is not on an execution path — this runs once per query at optimize time, not per solution, and `n` is the number of disjuncts in a single FILTER, typically a handful. But `?x IN (...)` lists in generated queries can get long, and that is precisely the shape that can be made linear, so I have done that.
The constants are now partitioned:
- **IRIs and blank nodes** — `NVCompare.sameValueAs` is `sameTerm` for those value spaces (`VSPACE_URI`, `VSPACE_BLANKNODE`), so they have a canonical representative and distinctness is a `HashSet` membership test. A long all-IRI `IN` list is O(n).
- **Literals** — any pair involving one stays pairwise.
On why literals cannot get the same treatment, since it is not obvious: a hash key is sound only if `sameValueAs(a,b) ⇒ key(a) == key(b)` (over-collision only costs us the optimization; under-collision is the unsoundness this PR is about). Numeric equality goes through `XSDFuncOp.compareNumeric`, which calls `classifyNumeric(nv1, nv2)` and promotes to the **wider of the two operand types**. The comparison type is a property of the pair, not of either element, and the result is that value equality is not transitive:
| pair | promoted to | result |
|---|---|---|
| `"0.1"^^xsd:decimal` vs `"0.1"^^xsd:double` | `OP_DOUBLE` | equal |
| `"0.1"^^xsd:double` vs `"0.1000000000000000055511151231257827…"^^xsd:decimal` | `OP_DOUBLE` | equal |
| `"0.1"^^xsd:decimal` vs `"0.1000000000000000055511151231257827…"^^xsd:decimal` | `OP_DECIMAL` | **not equal** |
(the third literal is the exact value of the double `0.1`.)
With no transitivity there are no equivalence classes, so any sound key has to merge all three — and, extended along the numeric line, every numeric into one bucket, which is just the pairwise loop again. Sorting is out for the same reason. Hence hashing only the half that has a canonical representative.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "afs (via GitHub)" <gi...@apache.org>.
afs commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5453975586
A possibility: change the optimization to be for `IN`.
```
FILTER ( ?x IN (<uri1>, <uri2>,<uri3>) )
```
This would be more natural to write; the variable is in a single place, the values (which still need checking as to whether they are expressions etc) in another.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881279274
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
The duplication is real — thanks for the pointers. I looked at reusing either of those (and `ExprLib.isAssignmentSafeEquality`, which performs the identical decomposition), but they cannot be used as they stand, because they answer a stricter question than this one needs.
All three fuse the structural extraction with an *assignment-safety* policy: can this test be turned into a substitution, given that a `FILTER =` does value matching where the graph does term matching? That policy rejects value-matched literals:
| disjunct | `isAssignmentSafeEquality` |
|---|---|
| `?x = ex:nope` | true |
| `?x = "1.5"^^xsd:double` | **false** |
| `?x = "1"^^xsd:integer` | **false** |
| `sameTerm(?x, "NaN"^^xsd:double)` | true |
Mutual exclusivity is a purely structural question — does this disjunct pin one variable to one constant? — and gating it on groundability would decline `?x = "1.5"^^xsd:double || ?x = ex:nope`, which this PR expands correctly today (the IRI branch grounds the pattern, the double stays a filter). So conflating them would be a behaviour regression rather than a refactor.
What *is* genuinely shared is the ~12-line argument-order-agnostic `(var, constant)` decomposition, which all four sites now repeat. The clean fix is to extract that one primitive — somewhere like `ExprLib`, returning the pair or null — and have each transform apply its own policy on top; `isAssignmentSafeEquality` would use it too. That touches three existing classes for reasons unrelated to this correctness fix, so I would rather do it as a follow-up PR than widen this one. Happy to open it once this lands, unless you would prefer it here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881372712
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
Sorry for the spam. I did not anticipate that Claude would write responses in my name. That's a no go. Never worked with it on public PRs so a newbie error. Sincere apologies.
So.. the way I see it is that these do provide similar functionality but differ in the details. There might be a way to consolidate them, but then we'd need to touch a lot more code in other classes. This widens the scope of this fix. Should this be handled in a different PR or do you want to address this here? To me the code duplication is another defect on its own already.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5435472674
@ThomasThelen Thanks for your comments! I'll have a look at it asap.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5454056575
@afs Are you suggesting to rewrite the original query? I completely agree with your suggestion.
But as I mentioned in the [issue](https://github.com/apache/jena/issues/4160) this is part of a SPARQL benchmark suite which I can't change. So it seems people are writing this kind of queries and Jena falling back to evaluating the query twice or n-times is not a desirable behaviour in my opinion.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881277115
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
Review Comment:
Good question. It is not on an execution path — this runs once per query at optimize time, not per solution, and `n` is the number of disjuncts in a single FILTER, typically a handful. But `?x IN (...)` lists in generated queries can get long, and that is precisely the shape that can be made linear, so I have done that.
The constants are now partitioned:
- **IRIs and blank nodes** — `NVCompare.sameValueAs` is `sameTerm` for those value spaces (`VSPACE_URI`, `VSPACE_BLANKNODE`), so they have a canonical representative and distinctness is a `HashSet` membership test. A long all-IRI `IN` list is O(n).
- **Literals** — any pair involving one stays pairwise.
On why literals cannot get the same treatment, since it is not obvious: a hash key is sound only if `sameValueAs(a,b) ⇒ key(a) == key(b)` (over-collision only costs us the optimization; under-collision is the unsoundness this PR is about). Numeric equality goes through `XSDFuncOp.compareNumeric`, which calls `classifyNumeric(nv1, nv2)` and promotes to the **wider of the two operand types**. The comparison type is a property of the pair, not of either element, and the result is that value equality is not transitive:
| pair | promoted to | result |
|---|---|---|
| `"0.1"^^xsd:decimal` vs `"0.1"^^xsd:double` | `OP_DOUBLE` | equal |
| `"0.1"^^xsd:double` vs `"0.1000000000000000055511151231257827…"^^xsd:decimal` | `OP_DOUBLE` | equal |
| `"0.1"^^xsd:decimal` vs `"0.1000000000000000055511151231257827…"^^xsd:decimal` | `OP_DECIMAL` | **not equal** |
(the third literal is the exact value of the double `0.1`.)
With no transitivity there are no equivalence classes, so any sound key has to merge all three — and, extended along the numeric line, every numeric into one bucket, which is just the pairwise loop again. Sorting is out for the same reason. Hence hashing only the half that has a canonical representative.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "afs (via GitHub)" <gi...@apache.org>.
afs commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5455482212
No query rewrite.
Which forms actually show up for real in the benchmark?
```
FILTER((?primaryFormat = cwork:InteractiveFormat) || (?primaryFormat = cwork:InteractiveFormat))
```
but are there other forms?
It isn't applicable in many cases - the constants have to same-term matches so e.g. not numbers.
So restrict to a few safe cases (only one `||` for example) if it makes a measurable difference.
Support the `IN` form as a second optimization.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3866972485
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null;
+ ExprFunction2 test = (ExprFunction2)e;
+ Expr left = test.getArg1();
+ Expr right = test.getArg2();
+ Expr varExpr = null;
+ Expr constExpr = null;
+ if ( left.isVariable() && right.isConstant() ) {
+ varExpr = left;
+ constExpr = right;
+ } else if ( right.isVariable() && left.isConstant() ) {
+ varExpr = right;
+ constExpr = left;
+ } else
+ return null;
+ if ( var != null && !var.equals(varExpr.asVar()) )
+ return null;
+ return constExpr.getConstant();
+ }
+
+ /** The variable of a disjunct {@link #constantTestedAgainst} accepted. */
+ private static Var singleVariable(Expr e) {
+ ExprFunction2 test = (ExprFunction2)e;
+ return test.getArg1().isVariable() ? test.getArg1().asVar() : test.getArg2().asVar();
+ }
+
+ private static boolean provablyDistinctValues(NodeValue nv1, NodeValue nv2) {
Review Comment:
It could be quick enough to throw in a unit test
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null;
+ ExprFunction2 test = (ExprFunction2)e;
+ Expr left = test.getArg1();
+ Expr right = test.getArg2();
+ Expr varExpr = null;
+ Expr constExpr = null;
+ if ( left.isVariable() && right.isConstant() ) {
+ varExpr = left;
+ constExpr = right;
+ } else if ( right.isVariable() && left.isConstant() ) {
+ varExpr = right;
+ constExpr = left;
+ } else
+ return null;
+ if ( var != null && !var.equals(varExpr.asVar()) )
+ return null;
+ return constExpr.getConstant();
+ }
+
+ /** The variable of a disjunct {@link #constantTestedAgainst} accepted. */
+ private static Var singleVariable(Expr e) {
+ ExprFunction2 test = (ExprFunction2)e;
+ return test.getArg1().isVariable() ? test.getArg1().asVar() : test.getArg2().asVar();
+ }
+
+ private static boolean provablyDistinctValues(NodeValue nv1, NodeValue nv2) {
Review Comment:
It could be quick enough to throw in a unit test for this function
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5432319997
Testing the exclusive logic I ran into an issue where the same result is getting returned twice. This might be related to the dedup logic [here](https://github.com/apache/jena/pull/4161/changes#diff-976b008aaf18fe48bcf54a22c44c1f845cf0276ac53959d98b6a5146004f0881R129)
Save as data.ttl
```turtle
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
@prefix ex: <http://example/> .
ex:obs1 ex:reading "NaN"^^xsd:double .
ex:obs2 ex:reading "1.5"^^xsd:double .
```
Save as query.rq
```sparql
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
SELECT * {
?s ?p ?x
FILTER( sameTerm(?x, "NaN"^^xsd:double) || sameTerm("NaN"^^xsd:double, ?x) )
}
```
```
$ arq --datadata.ttl --query query.rq
------------------------------------------------------------------------
| s | p | x |
========================================================================
| <http://example/obs1> | <http://example/reading> | "NaN"^^xsd:double |
| <http://example/obs1> | <http://example/reading> | "NaN"^^xsd:double |
------------------------------------------------------------------------
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881274850
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null;
+ ExprFunction2 test = (ExprFunction2)e;
+ Expr left = test.getArg1();
+ Expr right = test.getArg2();
+ Expr varExpr = null;
+ Expr constExpr = null;
+ if ( left.isVariable() && right.isConstant() ) {
+ varExpr = left;
+ constExpr = right;
+ } else if ( right.isVariable() && left.isConstant() ) {
+ varExpr = right;
+ constExpr = left;
+ } else
+ return null;
+ if ( var != null && !var.equals(varExpr.asVar()) )
+ return null;
+ return constExpr.getConstant();
+ }
+
+ /** The variable of a disjunct {@link #constantTestedAgainst} accepted. */
+ private static Var singleVariable(Expr e) {
+ ExprFunction2 test = (ExprFunction2)e;
+ return test.getArg1().isVariable() ? test.getArg1().asVar() : test.getArg2().asVar();
+ }
+
+ private static boolean provablyDistinctValues(NodeValue nv1, NodeValue nv2) {
Review Comment:
Done.
Claude response:
`provablyDistinctValues` is now package-private and `TestTransformFilters` (same package) tests it directly:
- `NaN` / `NaN` → **true**. This one is worth pinning explicitly: it is value distinctness working as designed, and it is exactly why `sameTerm` disjuncts must not be judged by it — the bug you found on the PR.
- `"1"^^xsd:integer` / `"01"^^xsd:integer` → false (same value, different terms)
- `"1"^^xsd:integer` / `"1.0"^^xsd:double` → false (value-equal across the numeric tower)
- distinct / identical IRIs → true / false
- timezone-less `xsd:dateTime` against one with a timezone → false (indeterminate comparison, so nothing is proved)
The new pairwise predicate `provablyExclusive` is tested the same way, including the `sameTerm`/`NaN` case and the `sameTerm` pair whose terms differ but whose values are equal.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5453796266
Sure, no problem. I really appreciate Jena a lot and what you guys provide to the community. Thanks a lot in return! :+1:
The case you spotted is pretty well observed. I had Claude write a fix for it and it seemed to be very trigger happy and pushed the results already. So now we can review it together.. :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5440565822
> @ThomasThelen Thanks for your comments! I'll have a look at it asap.
Thanks for your time! I'm not the most qualified to be looking at arq and the _semantics_ of the changes made here - but happy to look at structure as a once over
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3867073261
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
Review Comment:
This looks O(n^2) to me - is this a hot path that could have performance degraded?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "ThomasThelen (via GitHub)" <gi...@apache.org>.
ThomasThelen commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3867357471
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
It looks like there are two places this sort of logic is being done; maybe the intent is to keep them separate. A third, similar implementation might benefit from sharing some code; I can't say for certain whether it's warranted here though. [Place 1](https://github.com/apache/jena/blob/790b3dc08fccb6be1ea2868b97bfcbae8f113062/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterInequality.java#L173), [Place 2](https://github.com/apache/jena/blob/790b3dc08fccb6be1ea2868b97bfcbae8f113062/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterEquality.java#L174)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881302894
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
Review Comment:
This one is rather tricky: We are looking at expressions like FILTER(A || B || A). In such scenarios we need to pairwise compare all possible variants to be on the safe side. However, this is done at query optimisation time and not for every solution. So it's only run once. Moreover, the amount of expressions to be evaluated is rather limited so the exponential O is not a huge problem here in practise.
But I thought of an alternative where we'd compute a hash value for every expression in the previous loop and then just check if we already have found a match. The issue is that this only works for non-literal values because of SPARQL literal comparison semantics (see explanation below).
So we could add an optimised path here that checks for equality of non-literals quickly and only compare the remaining literals with O(n^2). Would that be OK with you or do you have other ideas?
### Literal Comparison Semantics
This is what Claude tells me.. but it sounds plausible:
The chain is `provablyDistinctValues` → `NodeValue.notSameValueAs` → `NVCompare.sameValueAs` → `XSDFuncOp.compareNumeric`, and that last one calls `classifyNumeric(fName, nv1, nv2)`, which picks the wider of the two operand types (integer → decimal → float → double) and compares in that type. The comparison type is a property of the pair, not of either element — so there is no per-element value to hash.
The concrete consequence is that numeric equality is not transitive:
```
"0.1"^^xsd:decimal vs "0.1"^^xsd:double → promoted to OP_DOUBLE → equal
"0.1"^^xsd:double vs "0.1000000000000000055511151231257827…"^^xsd:decimal → OP_DOUBLE → equal
"0.1"^^xsd:decimal vs that same decimal → OP_DECIMAL → BigDecimal.compareTo → not equal
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881279274
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
Review Comment:
The duplication is real — thanks for the pointers. I looked at reusing either of those (and `ExprLib.isAssignmentSafeEquality`, which performs the identical decomposition), but they cannot be used as they stand, because they answer a stricter question than this one needs.
All three fuse the structural extraction with an *assignment-safety* policy: can this test be turned into a substitution, given that a `FILTER =` does value matching where the graph does term matching? That policy rejects value-matched literals:
| disjunct | `isAssignmentSafeEquality` |
|---|---|
| `?x = ex:nope` | true |
| `?x = "1.5"^^xsd:double` | **false** |
| `?x = "1"^^xsd:integer` | **false** |
| `sameTerm(?x, "NaN"^^xsd:double)` | true |
Mutual exclusivity is a purely structural question — does this disjunct pin one variable to one constant? — and gating it on groundability would decline `?x = "1.5"^^xsd:double || ?x = ex:nope`, which this PR expands correctly today (the IRI branch grounds the pattern, the double stays a filter). So conflating them would be a behaviour regression rather than a refactor.
What *is* genuinely shared is the ~12-line argument-order-agnostic `(var, constant)` decomposition, which all four sites now repeat. The clean fix is to extract that one primitive — somewhere like `ExprLib`, returning the pair or null — and have each transform apply its own policy on top; `isAssignmentSafeEquality` would use it too. That touches three existing classes for reasons unrelated to this correctness fix, so I would rather do it as a follow-up PR than widen this one. Happy to open it once this lands, unless you would prefer it here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on code in PR #4161:
URL: https://github.com/apache/jena/pull/4161#discussion_r3881274850
##########
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformFilterDisjunction.java:
##########
@@ -148,6 +171,81 @@ public static Op expandDisjunction(Expr expr, Op subOp) {
return op;
}
+ /**
+ * Is at most one disjunct true of any one solution? Each branch of the expansion
+ * re-evaluates the pattern, so a solution that satisfies {@code k} disjuncts comes
+ * back {@code k} times where the filter returns it once. For example
+ * <pre>
+ * FILTER(?x = :c || ?x != :d)</pre>
+ * must not be expanded: a solution with {@code ?x = :c} satisfies both disjuncts.
+ * <p>
+ * The safe case is: every disjunct tests one and the same variable against a
+ * constant, and the constants are pairwise known to be different values, so the
+ * tests are mutually exclusive. Constants whose comparison is indeterminate (an
+ * unknown datatype, a timezone-less date) are treated as possibly equal.
+ */
+ private static boolean isSafeDisjunction(List<Expr> exprList) {
+ Var var = null;
+ List<NodeValue> constants = new ArrayList<>(exprList.size());
+ for ( Expr e : exprList ) {
+ NodeValue constant = constantTestedAgainst(e, var);
+ if ( constant == null )
+ return false;
+ if ( var == null )
+ var = singleVariable(e);
+ constants.add(constant);
+ }
+
+ for ( int i = 0 ; i < constants.size() ; i++ ) {
+ for ( int j = i + 1 ; j < constants.size() ; j++ ) {
+ if ( !provablyDistinctValues(constants.get(i), constants.get(j)) )
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * The constant of a {@code variable = constant} or {@code sameTerm(variable, constant)}
+ * disjunct (either argument order), where the variable is {@code var} - or any
+ * variable when {@code var} is null. Null when the disjunct has another shape.
+ */
+ private static NodeValue constantTestedAgainst(Expr e, Var var) {
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null;
+ ExprFunction2 test = (ExprFunction2)e;
+ Expr left = test.getArg1();
+ Expr right = test.getArg2();
+ Expr varExpr = null;
+ Expr constExpr = null;
+ if ( left.isVariable() && right.isConstant() ) {
+ varExpr = left;
+ constExpr = right;
+ } else if ( right.isVariable() && left.isConstant() ) {
+ varExpr = right;
+ constExpr = left;
+ } else
+ return null;
+ if ( var != null && !var.equals(varExpr.asVar()) )
+ return null;
+ return constExpr.getConstant();
+ }
+
+ /** The variable of a disjunct {@link #constantTestedAgainst} accepted. */
+ private static Var singleVariable(Expr e) {
+ ExprFunction2 test = (ExprFunction2)e;
+ return test.getArg1().isVariable() ? test.getArg1().asVar() : test.getArg2().asVar();
+ }
+
+ private static boolean provablyDistinctValues(NodeValue nv1, NodeValue nv2) {
Review Comment:
Done. `provablyDistinctValues` is now package-private and `TestTransformFilters` (same package) tests it directly:
- `NaN` / `NaN` → **true**. This one is worth pinning explicitly: it is value distinctness working as designed, and it is exactly why `sameTerm` disjuncts must not be judged by it — the bug you found on the PR.
- `"1"^^xsd:integer` / `"01"^^xsd:integer` → false (same value, different terms)
- `"1"^^xsd:integer` / `"1.0"^^xsd:double` → false (value-equal across the numeric tower)
- distinct / identical IRIs → true / false
- timezone-less `xsd:dateTime` against one with a timezone → false (indeterminate comparison, so nothing is proved)
The new pairwise predicate `provablyExclusive` is tested the same way, including the `sameTerm`/`NaN` case and the `sameTerm` pair whose terms differ but whose values are equal.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-5453576186
@ThomasThelen Thanks — that is a real bug, and it is fixed and pushed.
You were right that the dedup is involved, but it turned out to be two defects combining.
**1. The exclusivity test was asking the wrong question.** `provablyDistinctValues` decides whether the constants are different *values*, via `NodeValue.notSameValueAs`. But `sameTerm` matches by *term*. For two identical `"NaN"^^xsd:double` constants, `NVCompare.sameValueAs` takes its same-term fast path into `sameExceptNaN`, which returns `false` for a NaN double or float — so `notSameValueAs(NaN, NaN)` is `true`. The two disjuncts were therefore declared mutually exclusive, even though every term equal to NaN satisfies both.
**2. The dedup was syntactic.** It used `List.contains`, i.e. `Expr.equals`, so `sameTerm(?x, "NaN"^^xsd:double)` and `sameTerm("NaN"^^xsd:double, ?x)` — one test written two ways — were not recognised as the same disjunct.
Both are addressed:
- disjuncts are now deduplicated on (operator, variable, constant) instead of on argument order, since `=` and `sameTerm` are both symmetric;
- two `sameTerm` disjuncts are exclusive exactly when the **terms** differ. Where at least one disjunct is `=`, a solution satisfying both makes the constants value-equal, so `notSameValueAs` remains the right test there.
Your query now returns one row, and it stays optimised — the two writings collapse into a single grounded branch:
```
(assign ((?x "NaN"^^xsd:double)) (bgp (triple ?s ?p "NaN"^^xsd:double)))
```
I checked each case against the same query with `optFilterDisjunction=false`, which is the semantics the optimizer has to preserve:
| query | optimized | reference |
|---|---|---|
| `sameTerm(?x,"NaN"^^xsd:double) \|\| sameTerm("NaN"^^xsd:double,?x)` | 1 | 1 |
| `?x = "1.5"^^xsd:double \|\| ?x = ex:nope` | 1 | 1 |
| `?x = ex:a \|\| ?x = ex:b \|\| ?x = ex:c` | 0 | 0 |
| `?x = "1.5"^^xsd:double \|\| ?x != ex:d` | 2 | 2 |
There is a regression test for the exact query you posted, plus direct unit tests for the comparison itself (see the reply on `provablyDistinctValues`). Full `jena-arq` suite: 16595 tests, 0 failures.
A side benefit of making the rule term-aware: `sameTerm(?x, "1"^^xsd:integer) || sameTerm(?x, "01"^^xsd:integer)` is genuinely exclusive — a term cannot be both — and is now expanded where the value-based rule declined it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org
Re: [PR] GH-4160: Apply the filter-disjunction rewrite only when the disjuncts are mutually exclusive [jena]
Posted by "faubulous (via GitHub)" <gi...@apache.org>.
faubulous commented on PR #4161:
URL: https://github.com/apache/jena/pull/4161#issuecomment-6066085829
Hi @afs,
the query are [A5, A13 and A14 from the LDBC Semantic Publishing Benchmark (SPB)](https://github.com/ldbc/ldbc_spb_bm_2.0/blob/91b98aafc7dc3e7e8a99d1eb3201bc55b1fdb512/datasets_and_queries/sparql/advanced/aggregation_standard/query14.txt#L60). This is a templated query and the generator produces such pairs from a pool of given IRIs where identical pairs occur quite often. In the benchmark itself there are no chains of three or more.
However, according to Claude the following query variants are also affected:
- **Three-part chains** with a repeat: `?f=:A || ?f=:A || ?f=:A` gives 3 rows instead of 1, and `?f=:A || ?f=:B || ?f=:A` gives 3 instead of 2. Three distinct IRIs are fine.
- **Reversed operands**, `?f = :A || :A = ?f`, and `sameTerm(?f,:A) || sameTerm(?f,:A)`.
- **Two variables**, `?f = :A || ?c = :B`, and mixing with !=, `?f = :A || ?f != :B`.
- **?f IN (:A, :A)** also duplicates. ARQ's optFilterExpandOneOf turns IN into || before the disjunction rewrite runs.
I asked it to provide a way to reproduce this. Here is what it returned:
**The data:** BBC's English football teams reference set from the SPB repo, 175 KB, 116 teams:
https://github.com/ldbc/ldbc_spb_bm_2.0/blob/91b98aafc7dc3e7e8a99d1eb3201bc55b1fdb512/datasets_and_queries/datasets/english-football-teams-2.ttl
**The query:** a search-box style lookup that matches either the short name or the slug. This is the "two different variables, one solution can satisfy both" form:
```
PREFIX domain: <http://www.bbc.co.uk/ontologies/domain/>
PREFIX sport: <http://www.bbc.co.uk/ontologies/sport/>
SELECT ?team ?name WHERE {
?team a sport:CompetitiveSportingOrganisation ;
domain:name ?name ;
domain:shortName ?short ;
domain:slug ?slug .
FILTER (?short = "Arsenal" || ?slug = "arsenal")
}
```
To run it:
```bash
curl -LO https://raw.githubusercontent.com/ldbc/ldbc_spb_bm_2.0/91b98aafc7dc3e7e8a99d1eb3201bc55b1fdb512/datasets_and_queries/datasets/english-football-teams-2.ttl
arq --data english-football-teams-2.ttl --query arsenal.rq
arq --set arq:optFilterDisjunction=false --data english-football-teams-2.ttl --query arsenal.rq
```
Results:
- With the default optimizer: Arsenal (<http://www.bbc.co.uk/things/c4285a9a-…#id>) is returned twice.
- With the transform switched off: Arsenal is returned once, which is correct.
Arsenal matches both conditions, and arq --explain shows the filter turned into a (disjunction …) with one branch per condition. Arsenal is found by both branches, so it comes back twice.
Two other forms show the same thing on this file:
- **`IN` with a repeated value:** `?team sport:competesIn ?comp FILTER(?comp IN (<…461a3103…#id>, <…461a3103…#id>))` returns 40 rows instead of 20. Each team in that competition appears twice, because ARQ turns the IN into || first.
- **An IRI test or a literal test:** `FILTER(?id = <http://dbpedia.org/resource/Arsenal_F.C.> || ?name = "Arsenal")` returns 3 rows instead of 2.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@jena.apache.org
For additional commands, e-mail: pr-help@jena.apache.org