`DISTINCT` with `ORDER BY` on a non-injective expression is rewritten to `REDUCED` and leaks duplicate rows

No source file or test is named; first run the supplied SPARQL query with the N-Triples data against Jena 6.2.0. Trace the DISTINCT/REDUCED compilation and ORDER BY execution path, then add a regression test for this query. Done means the duplicate "a" value is eliminated and only the expected two rows remain.

Version

6.2.0

What happened?

Reporter: ting668

Environment

• Apache Jena Version: 6.2.0
• Java Version: 21.0.12+8-LTS

Description

While testing Apache Jena using a method based on attribute-constraint analysis, I found that SELECT DISTINCT combined with ORDER BY on a non-injective expression leaks duplicate rows: with ORDER BY STRLEN(?v) ?tag, the value "a"^^xsd:string is returned twice.

DISTINCT must eliminate duplicates among the projected solutions, so each distinct value of ?v must appear exactly once, independent of the ordering.

How to Reproduce and Expected Behavior

Note: The queries below are a minimized, simplified example reproducing the bug.

Buggy query (with the default graph loaded with the N-Triples data below):

SELECT DISTINCT ?v WHERE { ?s <urn:p> ?v . ?s <urn:q> ?tag . } ORDER BY STRLEN(?v) ?tag

Data (default graph, N-Triples):

<urn:s0> <urn:p> "a"^^<http://www.w3.org/2001/XMLSchema#string> .
<urn:s1> <urn:p> "b"^^<http://www.w3.org/2001/XMLSchema#string> .
<urn:s2> <urn:p> "a"^^<http://www.w3.org/2001/XMLSchema#string> .
<urn:s0> <urn:q> "1"^^<http://www.w3.org/2001/XMLSchema#integer> .
<urn:s1> <urn:q> "1"^^<http://www.w3.org/2001/XMLSchema#integer> .
<urn:s2> <urn:q> "2"^^<http://www.w3.org/2001/XMLSchema#integer> .

Expected behavior: the two "a"^^xsd:string solutions collapse under DISTINCT, leaving two rows:

[{"v":"\"a\"^^xsd:string"},{"v":"\"b\"^^xsd:string"}]

Actual behavior: the duplicate "a"^^xsd:string row is returned:

[{"v":"\"a\"^^xsd:string"},{"v":"\"a\"^^xsd:string"},{"v":"\"b\"^^xsd:string"}]

This suggests that the DISTINCT is compiled to REDUCED even though the ORDER BY expression STRLEN(?v) is not injective on the projected values: REDUCED does not guarantee duplicate elimination, so the duplicate "a" row leaks into the result.

Relevant output and stacktrace

Are you interested in making a pull request?

None