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

    Вслед за Ораклом со своим ‘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.


    ну вот такой пост для начала ;-)

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 10

      0
      познавательно, будем практиковаться
        0
        Классно! Всегда хорошо, когда добавляются адекватные возможности.
        Но хотелось бы объективного бенчмарка по производительности такой иерархии по сравнению с materialised path и nested trees =)
          –1
          и что бенчмарк даст? вы откажетесь от adjacency list если будет всё плохо? вы перейдёте исключительно на него, если всё хорошо?
          выбор метода хранения древовидных структур процесс зависящий от тонны критериев.
            0
            Все существенные тесты имеет смысл проводить на собственных реальных данных. Но общий бенчмарк покажет общую тенденцию и выделит вырожденные случаи.

            Ну разумеется все проекты я переделывать не брошусь =)
            Просто такое ощущение, что adjacency list будет медленее для работы, нацеленной на приоритет выборки данных. Видимо самому и придется делать общий бенчмарк)))
          –2
          Блин, аффтар! Прогоните текст через спеллер!
            –1
            плохая статья…
            первый же пример приведённый в статье слишком перегружен для восприятия — ну как может помочь разобраться в новом (mysql и oracle всё-таки более популярны) синтаксисе «реализация аналога sys_connect_by_path»? Если хочется рассказать о каких-то фичах то нужно начинать с простейших примеров, как это сделано в стандартной документации (http://www.postgresql.org/docs/8.4/static/queries-with.html)

            WITH RECURSIVE t(n) AS (
            SELECT 1
            UNION ALL
            SELECT n+1 FROM t
            )

            ps и кавычки в именах полей в примерах ну совершенно лишние
              +1
              возможно вы и правы,
              но цель у меня была написать статью с примерами которыми сталкивался сам.Не очень хотелось дублировать существуещее и писать в стиле учебника, которых много в сети.
                0
                Вот я эту статью прочитал раз пять, так и не понял зачем оно. Новичкам — бесполезняк, опытным еще больший бесполезняк.
              +1
              Может примеры и сложны, но информация для меня очень интересна. спасибо автору.
                –1
                сделан
                реализовано

                Only users with full accounts can post comments. Log in, please.