[JENA-441] In some cases it may be useful to apply DISTINCT before applying ORDER BY

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: Jena 2.10.0
• Fix Version/s: Jena 2.10.1
• Component/s: ARQ, Optimizer
• Labels: distinct optimization order project
• Assignee: Rob Vesse
• Reporter: Rob Vesse
• Created: 19/Apr/13 00:02
• Updated: 12/Nov/13 11:07
• Resolved: 25/Apr/13 17:42

Description

One of our internal users highlighted an interesting query where changing the plan makes a big difference in performance.

The query is essentially the following:

SELECT DISTINCT ?p
WHERE
{
?s ?p ?o
} ORDER BY ?p

Leaving the fact that it is a fundamentally dumb query to write the user had an interesting suggestion about the query plan, currently this generates the following:

(distinct
(project (?predicate)
(order (?predicate)
(quadpattern (quad <urn:x-arq:DefaultGraphNode> ?s ?predicate ?o)))))

For cases like this it may actually be much more performant to do the distinct first, because of the associated semantics of the various operators you can't just simply put distinct before the order but if you rewrite the query as follows:

SELECT ?p
WHERE
{
{ SELECT DISTINCT ?p WHERE

{ ?s ?p ?o }

}
} ORDER BY ?p

You get the likely much more performant plan:

(project (?predicate)
(order (?predicate)
(distinct
(project (?predicate)
(quadpattern (quad <urn:x-arq:DefaultGraphNode> ?/s ?predicate ?/o))))))

Clearly this optimization does not apply in the general case, I think it only applies in the case where you have a DISTINCT and all ORDER BY conditions are simple variables and only those variables are projected in which case I think you could produce a plan like the following:

(order (?predicate)
(project (?predicate)
(distinct
(quadpattern (quad <urn:x-arq:DefaultGraphNode> ?s ?predicate ?o)))))

I am pretty certain this applies in only a few cases and I haven't reproduced this with TDB to see if the performance difference is noticeable yet.

Andy - I will try and gather some more information and experiment with this so don't feel you have to look at this one for the time being.

Issue Links

• relates to: JENA-587 SELECT DISTINCT returns duplicate results
• links to: Test Queries