33 - СУБД. Сравнение производительности разных схем хранения дерева

Лектор: Дмитрий Барашев

Использовался PostgreSQL 9.4.1, запущенный в Докер-контейнере из официального образа постгреса https://hub.docker.com/r/library/postgres/. Настройки постгреса (https://wiki.postgresql.org/wiki/Tuning_Your_PostgreSQL_Server) не менялись. В частности, 128M отведено под разделяемую память для дисковых страниц, 4М отведено рабочей памяти запроса. Размер всей БД равен 16М, так что скорее всего она вся целиком помещается в оперативную память.

Тесты выполнялись на лаптопе с процессором Intel i5 с 12Gb оперативной памяти.

Запросы, выдающие всё поддерево заданной вершины

-- Для списков смежностей

CREATE OR REPLACE FUNCTION GetSubtreeAdjList(_parent_id INT)
RETURNS TABLE(
id INT,
value TEXT,
parent_id INT,
level INT
) AS $$
BEGIN
RETURN QUERY
WITH RECURSIVE BFS AS (
SELECT K.id, K.value, K.parent_id, 0 AS level
FROM Keyword K
WHERE K.id = _parent_id

UNION ALL
SELECT Child.id, Child.value, Parent.id AS parent_id, Parent.level + 1 AS level
FROM Keyword Child JOIN BFS Parent ON (Child.parent_id = Parent.id)
)
SELECT * FROM BFS;

RETURN;
END;
$$ LANGUAGE plpgsql;

Запросы, выдающие поддерево заданной глубины

-- Для списков смежностей
CREATE OR REPLACE FUNCTION GetShallowSubtreeAdjList(_parent_id INT, _depth INT)
RETURNS TABLE(
id INT,
value TEXT,
parent_id INT,
level INT
) AS $$
BEGIN
RETURN QUERY
WITH RECURSIVE BFS AS (
SELECT K.id, K.value, K.parent_id, 0 AS level
FROM Keyword K
WHERE K.id = _parent_id

UNION ALL
SELECT Child.id, Child.value, Parent.id AS parent_id, Parent.level + 1 AS level
FROM Keyword Child JOIN BFS Parent ON Child.parent_id = Parent.id
WHERE Parent.level