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

[ting668]

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 an intuitive approach inspired by attribute constraints, 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

[afs]

Confirmed