CTEs y Queries Recursivas

Álvaro Hernández Tortosa <aht@Nosys.es>

Acerca de mí

● Álvaro Hernández Tortosa <aht@Nosys.es>● Fundador y Director Técnico en NOSYS● ¿Qué hacemos en NOSYS?

✔ Formación, consultoría y desarrollo de software con PostgreSQL (y Java)✔ Partners de EnterpriseDB✔ Formación avanzada en Java con Javaspecialists.eu: Java Master Course y Java Concurrency Course✔ Partners de Amazon AWS. Formación y consultoría en AWS

● Twitter: @ahachete● LinkedIn: http://es.linkedin.com/in/alvarohernandeztortosa/

Common Table Expression (CTE)

● Son como VIEWS temporales, con nombre, que se pueden crear al vuelo para simplificar la escritura de consultas

● Se utilizan con la cláusula WITH:✔ puede haber tantas “vistas temporales” como se quiera✔ se pueden hacer JOINs entre ellas y referenciar entre ellas también✔ incluso a sí mismas, para dar lugar a la recursividad

● Disponibles desde PostgreSQL 8.4(escribibles desde 9.1)

WITH en 1 slide

SELECT cols FROM tabla1INNER JOIN (SELECT colsFROM tabla 2) AS tabla2ON (…)JOIN (SELECT colsFROM tabla 3) AS tabla3ON (…)WHERE …

WITH tabla2 AS (SELECT cols FROM tabla2), tabla3 AS (SELECT cols FROM tabla3)SELECT cols FROM tabla1INNER JOIN tabla2 ON (…)JOIN tabla3 ON (…)WHERE …

l

Sin CTEs CTEs (WITH)

Sintaxis

WITH [ RECURSIVE ] with_query_name [ (column_name [, …]) ] AS (select | values | insert | update | delete)[, …]SELECT … with_query_name …

Ejemplos

WITH tabla AS (SELECT 1) SELECT * FROM tabla;

WITH tabla (i) AS (SELECT 1) SELECT i FROM tabla;

WITH seq (i) AS ( SELECT generate_series(1,10)), seq2 (i) AS ( SELECT * FROM seq WHERE i%2=0)SELECT i FROM seq2RIGHT OUTER JOIN seq ON (seq.i = seq2.i);

Ejemplos (II)

WITH regional_sales AS (

SELECT region, SUM(amount) AS total_sales

FROM orders GROUP BY region

), top_regions AS (

SELECT region

FROM regional_sales WHERE tot_sales > (

SELECT SUM(tot_sales)/10 FROM regional_sales

)

)

SELECT region, product, SUM(quantity) AS product_units,

SUM(amount) AS product_sales

FROM orders

WHERE region IN (SELECT region FROM top_regions)

GROUP BY region, product;http://www.postgresql.org/docs/9.3/static/queries-with.html

Ejemplos (III): WITH con mutación de datos

-- Obtener las filas actualizadas

WITH t AS (

UPDATE products SET price = price * 1.05

RETURNING *

)

SELECT * FROM t; -- cuidado: “FROM t”, no “FROM products”

-- Realizar varias operaciones al tiempo

WITH moved_rows AS (

DELETE FROM products

WHERE "date" >= '2010-10-01' AND "date" < '2010-11-01'

RETURNING *

)

INSERT INTO products_log SELECT * FROM moved_rows;http://www.postgresql.org/docs/9.3/static/queries-with.html

Estructuras auto-referenciadas en RDBMSs

● Los grafos, árboles y estructuras recursivas son difíciles de representar en RDBMSs

● La solución “típica” es una tabla auto-referenciada, donde la FK apunta a la propia tabla

● El problema es: ¿cómo realizar una consulta que deba recorrer el árbol, el grafo, o recursivamente la tabla?

● Y la solución naive es con lenguajes procedurales, pero ¿puede hacerse de otra manera?

Ejemplo: para cada red, saber el “path” completo

CREATE TABLE ip_network (

mask cidr PRIMARY KEY,

name varchar ,

parent_network cidr REFERENCES ip_network (mask),

CONSTRAINT network_contained_in_parent_network CHECK (

parent_network IS NULL OR mask << parent_network

)

);

SELECT * FROM ip_network ORDER BY random() LIMIT 3;

mask | name | parent_network

--------------+------------+----------------

10.0.32.0/19 | Storage | 10.0.0.0/16

10.0.17.0/24 | S.S. Reyes | 10.0.16.0/20

10.0.16.0/28 | dom0 | 10.0.16.0/24

Procesado a nivel de aplicación

Solución a nivel de BBDD: queries recursivas

Sintaxis:

WITH RECURSIVE nombre AS ( -- valor inicial SELECT cols FROM tabla UNION ALL -- o UNION -- elemento recursivo: se apunta a sí mismo SELECT cols FROM nombre -- condición de terminación WHERE …) SELECT * FROM nombre;

Recordatorio: UNION vs. UNION ALL

aht=> SELECT * FROM generate_series(1,2) UNION SELECT * FROM generate_series(1,2) ORDER BY 1 ASC;

generate_series

-----------------

1

2

aht=> SELECT * FROM generate_series(1,2) UNION ALL SELECT * FROM generate_series(1,2) ORDER BY 1 ASC;

generate_series

-----------------

1

1

2

2

Ejemplos

WITH RECURSIVE t(n) AS (

VALUES (1)

UNION ALL

SELECT n+1 FROM t WHERE n < 100

) SELECT sum(n) FROM t;

WITH RECURSIVE subdepartment AS (

SELECT * FROM department WHERE name = 'A'

UNION ALL

SELECT d.* FROM department AS d

JOIN subdepartment AS sd

ON (d.parent_department = sd.id)

) SELECT * FROM subdepartment ORDER BY name;

http://www.postgresql.org/docs/9.3/static/queries-with.html

http://wiki.postgresql.org/wiki/CTEReadme

Resolviendo el “path completo” en redes IP

WITH RECURSIVE ip_network_recursive (mask, mask_path, name, parent_network, is_leaf) AS (

SELECT mask, abbrev(mask), name, parent_network, parent_network IS NULL

FROM noc.ip_network

UNION

SELECT i1.mask, abbrev(i2.mask) || ' > ' || i1.mask_path, i1.name, i2.parent_network, i2.parent_network IS NULL

FROM ip_network_recursive AS i1

INNER JOIN noc.ip_network AS i2

ON (i1.parent_network = i2.mask)

) SELECT name, mask, mask_path

FROM ip_network_recursive

WHERE is_leaf;

Resolviendo el “path completo” en redes IP (II) name | mask_path

--------------------------+----------------------------------------------------

NOSYS - private | 10.0/16

NOSYS - public | 62.93.188.160/27

NOSYS - private - legacy | 192.168.5/24

Service | 10.0/16 > 10.0.16/20

Storage | 10.0/16 > 10.0.32/19

Out of band management | 10.0/16 > 10.0.64/20

Reserved | 10.0/16 > 10.0.0/20

Easynet datacenter | 10.0/16 > 10.0.16/20 > 10.0.16/24

Easynet datacenter | 10.0/16 > 10.0.64/20 > 10.0.64/24

S.S. Reyes | 10.0/16 > 10.0.16/20 > 10.0.17/24

S.S. Reyes | 10.0/16 > 10.0.64/20 > 10.0.65/24

dom0 | 10.0/16 > 10.0.16/20 > 10.0.16/24 > 10.0.16.0/28

domu - core services | 10.0/16 > 10.0.16/20 > 10.0.16/24 > 10.0.16.16/28

domu | 10.0/16 > 10.0.16/20 > 10.0.16/24 > 10.0.16.32/27

domu | 10.0/16 > 10.0.16/20 > 10.0.16/24 > 10.0.16.64/26

domu | 10.0/16 > 10.0.16/20 > 10.0.16/24 > 10.0.16.128/25

El caso de Disqus

● Disqus, la plataforma para “outsourcing” de comentarios en una web

● Los comentarios son de naturaleza jerárquica (aka recursiva)

● Migraron de MySQL con procesado de la jerarquía en la aplicación a PostgreSQL con soporte de queries recursivas. Resultados:

✔ 5x mejora velocidad ejecución de consultas✔ 20x mejora latencia global sirviendo comentarios

Alternativa para árboles: la extensión ltree

● Extensión (CREATE EXTENSION ltree) para árboles

● Usa paths materializados por lo que puede ser más eficiente que CTEs

● Tiene índices y operadores “built-in”

INSERT INTO comments (user_id, path) VALUES (1, '0001');

INSERT INTO comments (user_id, path) VALUES (6, '0001.0002'), (7, '0001.0004'), (18, '0001.0004.0005');

SELECT * FROM comments WHERE path <@ '0001.0002';

http://www.postgresql.org/docs/9.3/static/ltree.html

Más información

● http://www.postgresql.org/docs/9.3/static/queries-with.html

● http://wiki.postgresql.org/wiki/CTEReadme

● http://momjian.us/main/writings/pgsql/cte.pdf

● http://pgexercises.com/questions/recursive/

CTEs y Queries Recursivas

Álvaro Hernández Tortosa <aht@Nosys.es>