Recursive SELECT query to return rates of arbitrary depth?

Question

This is my first time attempting a recursive SQL query to traverse N parent-child relationships upward, and I don't know where to start. Any help would be appreciated.

Scenario is that I have two tables - rate and rate_plan. Rates belong to a rate plan which is applied to a user.

CREATE TERM rate_plan (
   id                  integer PRIMARY KEY NOT NULL
                       DEFAULT nextval('rate_plan_id'),

   descr               varchar(64) NOT NULL,

   parent_rate_plan_id integer NOT NULL REFERENCES rate_plan(id)
);

CREATE TABLE rate (
   id                integer PRIMARY KEY NOT NULL
                     DEFAULT nextval('rate_id'),

   prefix            varchar(24) NOT NULL,

   rate_plan_id      integer NOT NULL 
                     REFERENCES rate_plan(id)
);

A typical query to get a rate:

SELECT * FROM rate  
   WHERE (
      rate_plan_id = ${user rate plan ID} 
      AND prefix = ${prefix}
   )
   ORDER BY LENGTH(prefix) ASC;

What I would like is to return the most-specific (LENGTH()-iest prefix) rate, but not being limited to ${user rate plan ID}, but instead picking rates from those affiliated with any number of rate plans in a rate_plan.parent_rate_plan_id hierarchy. The recursion should bottom out when rate_plan.parent_rate_plan_id = NULL.

I would just do a JOIN, but I need to accommodate N parent-child relationships, not just two.

This is on PostgreSQL 9.x. I tried WITH RECURSIVE and UNION ALL, joining rate_plan to rate on every SELECT and trying to filter by parent, but got nowhere, due to an inadequate understanding of how those constructs work.

I'm not entirely understanding what you're trying to do. But in the docs on CTEs, there's an example query for graphs, that builds a path of parent nodes using an array. Do the same for your tree: the query you want should then be (hopefully) obvious, e.g. every node whose parents include the node with your prefix, or whatever it is you're looking for exactly. — Denis de Bernardy, Dec 15 '13 at 10:46
Could you prepare some sample data (a few inserts) and enter it into this sqlfiddle: http://www.sqlfiddle.com/#!15/89073/1 ? Then attach a link to SQLFiddne, and explain please your requirements on the basis of this data and show expected results. — krokodilko, Dec 15 '13 at 11:00
[Postgres major versions](http://www.postgresql.org/support/versioning/) include the first digit after the dot. The current version is *9.3*. — Erwin Brandstetter, Dec 15 '13 at 11:20

Erwin Brandstetter · Accepted Answer · 2013-12-15T19:49:28.953

2

This might be what you are looking for, according to your description:

the most-specific (LENGTH()-iest prefix) rate, but not being limited to ${user rate plan ID}, but instead picking rates from those affiliated

WITH RECURSIVE cte AS (
   SELECT id, parent_rate_plan_id
   FROM   rate_plan  
   WHERE  id = ${user rate plan ID} 

   UNION ALL
   SELECT rp.id, rp.parent_rate_plan_id
   FROM   cte
   JOIN   rate_plan rp ON rp.id = cte.parent_rate_plan_id
   )
SELECT *
FROM   cte
JOIN   rate r ON r.rate_plan_id = cte.id
ODER   BY length(prefix) DESC
LIMIT  1;

Recursion stops automatically as soon as the top node (parent_rate_plan_id IS NULL) is reached.

It's more effective to join to rate once after you have collected all plans.

The manual on (recursive) CTEs.

edited Dec 15 '13 at 19:49

answered Dec 15 '13 at 12:03

Erwin Brandstetter

605,456
145
1,078
1,228

This seems to be the right idea; however, Postgres won't let me run it as "WITH cte", complaining about it being self-referential. But when I run it as WITH RECURSIVE, it seems to recurse infinitely. – Alex Balashov Dec 15 '13 at 14:55
I stand corrected; I implemented your recommendation incorrectly. This does indeed appear to do it! Thank you. – Alex Balashov Dec 15 '13 at 15:07
@AlexBalashov: Added the missing `RECURSIVE` clause. – Erwin Brandstetter Dec 15 '13 at 19:50

Recursive SELECT query to return rates of arbitrary depth?

1 Answers1

Linked