Pull to refresh

Рекурсивные (Иерархические) запросы в PostgreSQL

Reading time 7 min
Views 66K
Вслед за Ораклом со своим ‘connet by prior ‘ все остальные СУБД вводят свои реализации иерархических запросов (ИЗ). Хотелось бы рассказать широкой аудитории как это сделано в PostgreSQL.

История


Начиналось все вот так
From: Evgen Potemkin <evgent@ns.terminal.ru>
Subject: Proposal of hierachical queries (a la Oracle)
Date: 2002-11-14 11:52:28 GMT
Hi there!
I want to propose the patch for adding the hierarchical queries
posibility. It allows to construct queries a la Oracle for ex:
SELECT a,b FROM t CONNECT BY a PRIOR b START WITH cond;B
I've seen this type of queries often made by adding a new type, which
stores position of row in the tree. But sorting such tree are very
tricky (i think).
Patch allows result tree to be sorted, i.e. subnodes of each node will
be sorted by ORDER BY clause.
with regards, evgen


затем
From: Tatsuo Ishii <ishii@postgresql.org>
Subject: RFP: Recursive query in 8.4
Date: 2008-02-19 08:36:00 GMT (1 year, 12 weeks, 6 days ago)
Hi,
As I promised before we would like to propose implementing the
recursive query as defined in the standard for PostgreSQL 8.4.
The work is supported by Sumitomo Electric Information Systems Co.,
Ltd. (http://www.sei-info.co.jp/) and SRA OSS, Inc. Japan
(http://www.sraoss.co.jp).


Ну И начиная с 8.4 версии Postgresql стала поддерживать рекурсивный запрос.

Теория



ИЗ в PostgreSQL реализовано на базе стандратной SQL clause WITH. Давайте немного углубимся: не рекурсивный WITH позволяет удешивить повторяющиеся подзапросы, разделить сложный запрос на несколко меньших, является удобным так сказать ярлыком для обращения к подзапросу и само посебе удобно в плане экономии времени при написании кода. как в примере ниже удалось избежать использования подзапроса в WHERE за счет применения временой таблицы top_regions сформированой специально для этого запроса.

  1. WITH regional_sales AS (
  2. SELECT region, SUM(amount) AS total_sales
  3. FROM orders
  4. GROUP BY region
  5. ), top_regions AS (
  6. SELECT region
  7. FROM regional_sales
  8. WHERE total_sales > (SELECT SUM(total_sales)/10 FROM regional_sales)
  9. )
  10. SELECT region,
  11. product,
  12. SUM(quantity) AS product_units,
  13. SUM(amount) AS product_sales
  14. FROM orders
  15. WHERE region IN (SELECT region FROM top_regions)
  16. GROUP BY region, product;
* This source code was highlighted with Source Code Highlighter.


Добавление необязательного оператора RECURSEVE позволяет запросу в Postgre обращатся к своимже выходным данным. алгоритм запроса должен сосоять из друх частей. первая часть это основа, обычно возвращающий одну строку с исходной точкой иерархии или части иерархии. Тоесть место в иерархии откуда будет начат отсчет ( например корень). и вторя рекурсивная часть которая будет связыватся с временой таблицой которую мы объявили после WITH. объединяются первая и вторая части оператором UNION или UNION ALL. что бы этот сумбурный набор слов привести в порядок привидем пример.
Создадим таблицу в которой будет описана структара одной компании
CREATE TABLE KPO
(
"ID" character varying(55),
"DESCRIPTION" character varying(255),
"PARENT" character varying(55
) ;


после внесения туда данных:
Select * from kpo



ID DESCRIPTION PARENT
== ====== ================================ =======
KPO KARACHAGANAK PETROLEUM OPERATING {null}
AKSAY AKSAY KPO
URALSK KPO KPO
LONDON LONDON KPO
KPC KPC AKSAY
U2 UNIT-2 AKSAY
U3 UNIT-3 AKSAY
PROD PRODACTION KPC
MAINT MAINTENANCE AKSAY
CMMS CMMS TEAM MAINT


Теперь сам рекурсивный запрос:

  1. WITH RECURSIVE temp1 ( "ID","PARENT","DESCRIPTION",PATH, LEVEL ) AS (
  2. SELECT T1."ID",T1."PARENT", T1."DESCRIPTION", CAST (T1."ID" AS VARCHAR (50)) as PATH, 1
  3.     FROM KPO T1 WHERE T1."PARENT" IS NULL
  4. union
  5. select T2."ID", T2."PARENT", T2."DESCRIPTION", CAST ( temp1.PATH ||'->'|| T2."ID" AS VARCHAR(50)) ,LEVEL + 1
  6.      FROM KPO T2 INNER JOIN temp1 ON( temp1."ID"= T2."PARENT")      )
  7. select * from temp1 ORDER BY PATH LIMIT 100
* This source code was highlighted with Source Code Highlighter.


Первая часть (строки 2-3) возвращает во временую таблицу первую строку в данном случае корневую запись наешей структуры, от которой будет начинатся отсчет в нашей иерархии. вторая часть( строки 4-5) добавляет в эту же временую таблицу записи связаные с уже содеражащейся в temp1 строкой через JOIN (ID = PARENT) и так до конца пока все листья нашего ROOTa не окажутся в temp1.
Так же в даном примере была сыметирована Ораколавская функция sys_connect_by_path.



«ID» «PARENT» «DESCRIPTION» «path» «level»
KPO   KARACHAGANAK PETROLEUM OPERATING KPO 1
AKSAY KPO AKSAY KPO->AKSAY 2
KPC AKSAY KPC KPO->AKSAY->KPC 3
PROD KPC PRODAUCTION KPO->AKSAY->KPC->PROD 4
MAINT AKSAY MAINTENANCE KPO->AKSAY->MAINT 3
CMMS MAINT CMMS TEAM KPO->AKSAY->MAINT->CMMS 4
U2 AKSAY UNIT-2 KPO->AKSAY->U2 3
U3 AKSAY UNIT-3 KPO->AKSAY->U3 3
LONDON KPO LONDON KPO->LONDON 2
URALSK KPO URALSK KPO->URALSK 2


В Postgre нет встроеной проверки на зацикливание, поэтому если данные мы получили от ребят которые занимались непосредствено созданием структуры в Excel, мы должны проверить эту структуру на целостность. иногда достаточно использовать UNION вместо UNION ALL но это только иногда. если вы в первой части задали отправную точку в иерархии и елси даже гдето в иерархии есть обрывы в принципе зпустив вышеупомянутый квери ошибки не будет, просто строки «отщипенцы» будут проигнорированы. Но нам же надо знать где ошибка, и реализовать это можно внедрив дополнительную проверку перед выполнением UNION.
  1. WITH RECURSIVE temp1 ( "ID","PARENT","DESCRIPTION",PATH, LEVEL, cycle ) AS (
  2. SELECT T1."ID",T1."PARENT", T1."DESCRIPTION", cast (array[T1."ID"] as varchar(100)[]) , 1 , FALSE
  3.     FROM KPO T1
  4. union all
  5. select T2."ID", T2."PARENT", T2."DESCRIPTION", cast(temp1.PATH || T2."ID" as varchar(100) []) ,LEVEL + 1 ,
  6.     T2."ID" = any (temp1.PATH)
  7.      FROM KPO T2 INNER JOIN temp1 ON( temp1."ID"= T2."PARENT") AND NOT CYCLE     )
  8.  
  9. select * from temp1 WHERE CYCLE IS TRUE LIMIT 100;
* This source code was highlighted with Source Code Highlighter.


Здесь как видете создается такое же поле Path но уже все предшествующие родители организованны в массиве, что дает нам возможно сравнивать нам каждуй новый “ID” на дубликат ну и если в массиве уже есть такая запись тогда во временную таблицу строка заносится с флагом и в следущий проход мы уже не используюм эту строку для поиска потомков, благодоря этому избегается зацикливанияе (union all… WHERE … AND NOT CYCLE).

Совет с официального сайта: используйте оператор LIMIT как это делал я в примерах. это поможет вам сохранить нервы.

Практические примеры



Теория хоршо конечно, но где все это можно применить на практике, темболле в свете стоимости таких запросов.
Кроме того что бы красиво нарисовать иерархию в одном запросе, и найти например все листья токогото “ID” есть еще и другие задачи.
Часто вам надо сделать изменения, такие как например изменить код телефона всем сотрудникам определенного департамента в телефонном справочнике. конечно можно использовать колонку в таблице работников или даже сделать префикс к “ID”. но все это делает базу не гибкой и не маштабируемой. Намного лучше сделать отдельную таблицу Работники которая будет отображать иерархию с тремя колонками “ID “, “PARENT “, “HIERARCHID”. поле “HIERARCHID” позволит сделать вам болле чем одну иерархическую структуру. Таблицу назовем для примера ANCESTOR которая будет тоже состоять из трех колонок “ID”, “ANCESTOR”, “HIERARCHID”. в поле “ANCESTOR” будут содержатся все предки, помните массив «Path» из примера 3. так вот заполнить эту таблицу можно как раз с помощью рекурсивного запроса.
  1. insert into ancestor ( “ID” "ANCESTOR", "HIERARCHID")
  2. WITH RECURSIVE temp1 ( "ID","PARENT","DESCRIPTION",PATH, LEVEL, cycle ) AS (
  3. SELECT T1."ID",T1."PARENT", T1."DESCRIPTION", cast (array[T1."ID"] as varchar(100)[]) , 1 , FALSE
  4.     FROM KPO T1 
  5. union all
  6. select T2."ID", T2."PARENT", T2."DESCRIPTION", cast(temp1.PATH || T2."ID" as varchar(100) []) ,LEVEL + 1 ,
  7.     T2."ID" = any (temp1.PATH)
  8.      FROM KPO T2 INNER JOIN temp1 ON( temp1."ID"= T2."PARENT") AND NOT CYCLE  
  9.        )
  10. select "ID" AS "LOCATION", PATH[1] AS "ANCESTOR" , 'DEPT' AS "DID" from temp1
* This source code was highlighted with Source Code Highlighter.


получится вот такая табличка



LOCATION ANCESTOR HIERARCHID
========= ========= ==========
AKSAY AKSAY DEPT
AKSAY KPO DEPT
CMMS KPO DEPT
CMMS MAINT DEPT
CMMS CMMS DEPT
CMMS AKSAY DEPT
KPC AKSAY DEPT
KPC KPC DEPT
KPC KPO DEPT
KPO KPO DEPT
LONDON LONDON DEPT
LONDON KPO DEPT
MAINT AKSAY DEPT
MAINT MAINT DEPT
MAINT KPO DEPT
PROD KPO DEPT
PROD AKSAY DEPT
PROD KPC DEPT
PROD PROD DEPT
U2 AKSAY DEPT
U2 KPO DEPT
U2 U2 DEPT
U3 U3 DEPT
U3 AKSAY DEPT
U3 KPO DEPT
URALSK KPO DEPT
URALSK URALSK DEPT


Теперь уже все наши селекты и апдейты будем делать используя эту таблицу. например с темеже телефонными номерами это будет выглядеть примерно так:

Update EMPLOYEE SET “TELNUM” = ‘545-454’ FROM ANCESTOR WHERE “ANCESTOR”.”ANCESTOR” = ‘AKSAY’ AND EMPLOYEE.”LOCATION” = ANCESTOR.”LOCATION” AND EMPLOYEE.ISDPRT = ‘N’ ;

Да еще надо будет предусматреть тригер на обновление таблицы при внесении новой или удалении записи в таблице KPO.

Продолжим,

Допустим что имеется таблица в которую заносятся логи, представим что вам необходимо посчитать сколько записей за предыдущий месяц было сделано и сгруппированно по дням. для это вам понадобится эталонный календарь за прошлый месяц, например что бы не пропустить день когда записей небыло. вот такой календарь ( список дней в одну колонку) можно получить таким запросом.
  1. WITH RECURSIVE t(n) AS (
  2. VALUES (1)
  3. UNION ALL
  4. SELECT n+1 FROM t WHERE n < (SELECT cast (extract ('day' from date_trunc('month',current_date) - interval '24 hour') as integer))
  5. )
  6. SELECT to_date ( n || '-'||extract ('month' from date_trunc('month',current_date) - interval '24 hour')
  7.    || '-'||extract ('year' from date_trunc('month',current_date) - interval '24 hour'), 'dd-mm-yyyy')
  8. FROM t;
* This source code was highlighted with Source Code Highlighter.


Еще один не очень полезный пример на закуску. Оригинальная идея Грейм Джоба (Graeme Job). результат лучше смотреть в текстовом файле.
  1. WITH RECURSIVE z(ix, iy, cx, cy, x, y, i) AS (
  2. SELECT ix, iy, x::float, y::float, x::float, y::float, 0
  3. FROM (select -1.88+0.016*i, i from generate_series(0,150) as i) as xgen(x,ix),
  4. (select -1.11+0.060*i, i from generate_series(0,36) as i) as ygen(y,iy)
  5. UNION ALL
  6. SELECT ix, iy, cx, cy, x*x - y*y + cx, y*x*2 + cy, i+1
  7. FROM z
  8. WHERE x * x + y * y < 16::float
  9. AND i < 27
  10. )
  11. SELECT array_to_string(array_agg(substring(' .,,,-----++++%%%%@@@@#### ',
  12. greatest(i,1), 1)),'')
  13. FROM (
  14. SELECT ix, iy, max(i) AS i
  15. FROM z
  16. GROUP BY iy, ix
  17. ORDER BY iy, ix
  18. ) AS zt
  19. GROUP BY iy
  20. ORDER BY iy
* This source code was highlighted with Source Code Highlighter.


ну вот такой пост для начала ;-)
Tags:
Hubs:
+44
Comments 10
Comments Comments 10

Articles