CODEWITHSUNDEEP
postgresqlrecursion
zelinka
zelinka

Reputation: 3413

Order by in a recursive query in postgres

I have the following query:

with recursive chain(id, weight, depth) as (
select rpCore.itemID2, rpCore.weight, 1 as depth from relations rpCore where itemID1 = 1048663
union 
select r.itemID2, c.weight + r.weight, c.depth + 1from chain c
inner join relations r
on (r.itemID1=id)
where c.depth < 3
order by c.weight + r.weight asc limit 10
) select * from chain order by weight asc limit 10;

If I run it, I get the following error:

ERROR: ORDER BY in a recursive query is not implemented
SQL state: 0A000
Character: 313

Because of the way the weights are structured (all positive, and added together) if I could get the recursive part of the query to order and limit itself, the outer part of the query would return the results I need, but it appears that you can't do an order by in the recursive part of a recursive query.

Is there any way to simulate this behavior? If I remove the limit statement, the query runs, but it runs very slowly due to the large number of (mostly unnecessary because of the final limit statement) rows.

Upvotes: 1

Views: 2863

Answers (1)

FuzzyChef
FuzzyChef

Reputation: 4071

As I understand your question, you want to add a LIMIT to the recursive CTE relation in order to prevent it from recursing over too many results, which makes the query slow.

The answer is you cannot do this. It's not only that it's not implemented in PostgreSQL; it's that what you're asking for isn't logically possible.

As PostgreSQL recurses over each set of related records, it accumulates a set which is de-facto ordered by depth. This is not the same ordering you want, which is by an unrelated column, "weight". For that reason, there is no way for Postgres to LIMIT based on weight without accumulating the full recursive data set first. So even if an ORDER BY statement in the CTE was supported, it wouldn't improve your performance at all.

I'll also point out that in any UNION query, the ORDER BY applies to the result data set, not to each part of the UNION. So you can't apply it just to "the recursive part".

You can, of course, terminate the recursion early by depth, as you have already done in this query. Changing UNION to UNION ALL will also improve performance.

Syntactically, you can implement what you want just by adding a 2nd CTE:

  with recursive chain(id, weight, depth) as (
  select rpCore.itemID2, rpCore.weight, 1 as depth 
  from relations rpCore 
  where itemID1 = 1048663
  union all
  select r.itemID2, c.weight + r.weight, c.depth + 1
  from chain c
  inner join relations r
  on (r.itemID1=id)
  where c.depth < 3
  ),
  chain_limit as (
  SELECT * FROM chain
  ORDER BY weight LIMIT 10
  )
  select * from chain_limit;

However, this won't help you with your performance goals.

Upvotes: 2

Related Questions