Снова о деревьях / forpes.ru

Главная
Снова о деревьях

Снова о деревьях +16

30.04.2018 13:57

Ihariv 17 5300 Источник

Весна, пора подумать о деревьях. Деревья в реляционных — DB это один из самых острых вопросов при работе с данными. В данном топике сравним быстродействие Materialized Path и Adjacency List методов с помощью команды «explain analize».

На днях я проходил собеседование в одной хорошей компании и пришел к выводу, что не все готовы изучать предмет с которым работают более досконально. А именно то, что порой неявное и неправильное на первый взгляд решение может быть самым верным.

Я решил разобраться чуть более детально, в чем проблема и провести тест двух самых простых вариантов. Materialized Paths (MP) и Adjacency List (AL). Nested Sets я не рассматриваю в виду цели данного топика. А его цель, сравнить выбор parentId_parentId_parentId и выбор :pid числа.

Казалось бы, быстрее всего выбор пройдет по числу. Но рассмотрим поближе. Очень редко нам нужно выбирать отдельную ветку без наследников. Очень часто количество вложенности или просто число наследником не контролируется.

Поэтому я взял несколько разных родительских веток с вложенностью в 5 уровней по 10-30 элементов в каждом узле. Получил чуть меньше миллиона записей. Вполне рабочие цифры для не слишком активного блога, почтового клиента и т.д.

Создаем таблицу tree и индексы к ней для двух типов дерева одновременно (для чистоты эксперимента.

-- Table: public.tree

-- DROP TABLE public.tree;

CREATE TABLE public.tree
(
    id integer NOT NULL DEFAULT nextval('tree_id_seq'::regclass),
    name text COLLATE pg_catalog."default",
    pid integer,
    btree integer[]
);


-- Index: btree_idx

-- DROP INDEX public.btree_idx;

CREATE INDEX btree_idx
    ON public.tree USING gin
    (btree);

-- Index: pid_idx

-- DROP INDEX public.pid_idx;

CREATE INDEX pid_idx
    ON public.tree USING btree
    (pid);

Наиболее внимательные заметили странное поле btree. Мы говорим абстрактно, а делаем оптимизировано.

Итак мы создали условное дерево, два поля для разных методов и уникальный идентификатор. Добавляем в него данные к примеру так:

// Generate ...
func (c *TreeController) Generate() {

    for i := int64(0); i < 10; i++ {
        pidStr := ""
        cur_i_id, _ := c.GenerateRecurse(0, pidStr)
        for j := 0; j < 30; j++ {
            pidStr := strconv.Itoa(int(cur_i_id))
            cur_j_id, _ := c.GenerateRecurse(cur_i_id, pidStr)
            for z := 0; z < 10; z++ {
                pidStr := strconv.Itoa(int(cur_i_id)) + "," + strconv.Itoa(int(cur_j_id))
                cur_z_id, _ := c.GenerateRecurse(cur_j_id, pidStr)
                for z1 := 0; z1 < 10; z1++ {
                    pidStr := strconv.Itoa(int(cur_i_id)) + "," + strconv.Itoa(int(cur_j_id)) + "," + strconv.Itoa(int(cur_z_id))
                    cur_z1_id, _ := c.GenerateRecurse(cur_z_id, pidStr)
                    for z2 := 0; z2 < 10; z2++ {
                        pidStr := strconv.Itoa(int(cur_i_id)) + "," + strconv.Itoa(int(cur_j_id)) + "," + strconv.Itoa(int(cur_z_id)) + "," + strconv.Itoa(int(cur_z1_id))
                        c.GenerateRecurse(cur_z1_id, pidStr)
                    }
                }
            }
        }
    }
}

// GenerateRecurse ...
func (c *TreeController) GenerateRecurse(pid int64, treepid string) (int64, error) {

    v := models.Tree{
        Name:  "test -- " + treepid,
        Pid:   pid,
        Btree: "{" + treepid + "}"}
    return models.AddTree(&v)
}

Здесь я намеренно не хотел заморачиваться с рекурсиями, потому написал так. Изначально хотел рекурсивно сделать, а потом подумал, что это тема для отдельного топика, и оставил как есть.

Запросы я выполнил проще. Открыл pgAdmin4 и запустил EXPLAIN ANALYZE с включенным Cost и timing флагами.

А интересовали нас два запроса.

Для MP:


SELECT * FROM tree
WHERE btree && ARRAY[:pid]
ORDER BY array_length(btree, 1);

Для AL:

WITH RECURSIVE nodes(id,name,pid, btree) AS (
    SELECT s1.id, s1.name, s1.pid, s1.btree
    FROM tree s1 WHERE pid = :pid
        UNION
    SELECT s2.id, s2.name, s2.pid, s2.btree
    FROM tree s2, nodes s1 WHERE s2.pid = s1.id
)
SELECT * FROM nodes
order by pid asc;

Где :pid — id родителя.

Запрос для AL метода весьма и весьма запутанный. А этот запрос придется достаточно часто использовать.

Из результата я уберу сортировку, она выполняется в обоих запросах сопоставимое время, причем достаточно большое, и без него результат будет более впечатлителен.

Вот красивые картинки:

Как то все просто, но это для MP. Смотрим запрос для AL:

Уже красивее, но смотрим, что Total Cost у MP в полтора раза больше… А все потому что у нас индекс хранит не числа, а массив чисел. Но несмотря на это в результате скорость выполнения у MP на порядок выше. И чем больше вложенностей и количество родительских элементов, том больше разница в скорости.

Кроме того простота выборки из запросов с легкостью позволяют собирать данные через ORM систему одним запросом. Большим минусом MP является более сложный метод переноса данных из одной ветки в другую, но тем не менее достаточно прозрачный. А такие операции как правило не носят массового характера и акцентировать внимание на это не совсем верно при такой разнице в производительности.

На скриншотах все данные актуальные, это не пиковые значения, а вполне средние. Но даже в пиковых значениях разница в скорости не менее 5 раз (самый медленный MP и самый быстрый AL метод.

Согласитесь, весьма неплохой бонус для тех кто хочет действительно во всем разобраться.

Комментарии (17)

apapacy
30.04.2018 22:25
#10784068
Не совсем ясно почему в качестве теста взят запрос родителя родителя. А что будет если нужно узнать для произвольного элемента цепочку всех элементов до корневого элемента?

Деревья в DB это один из самых острых вопросов при работе с данными

Я бы уточнил в реляционных базах данных. Ведь есть же графовые базы данных. Среди них бесплатные и достаточно стабильные (orientdb, arangodb). К сожалению они еще не и меют той стабильности и производительности что PostgreSQL и MySQL, но все что они предлагают в плате функционала это очень интересно.
1. Ihariv Автор
  30.04.2018 22:44
  #10784084
  +1
  так тоже проще. просто выбираем
  
  SELECT * FROM tree WHERE id != :id AND array[id] && ( SELECT btree FROM tree WHERE id = :id ) ORDER BY btree;
  
  И опять обходимся без рекурсии. Можно так же самому достать id родителей и просто выбрать селектом с помощью команды IN
1. Ihariv Автор
  30.04.2018 22:56
  #10784094
  Я бы уточнил в реляционных базах данных.
  Замечание по делу. Поправил. А работа с нереляционными базами данных — тема для отдельного топика. Они настолько разные, что наверное можно диссертацию написать.
1. mspain
  01.05.2018 13:37
  #10784400
  Не имеют производительности Постгреса? Посмеялся. Очень громко. Плотно работаю с Нео4ж (comunity edition), никакой рсубд и рядом не лежал. Например дамп вконтакте с 450млн узлов и 15млрд связей — ищет кратчайшие пути длиной 6-10 за милисекунды.
  1. Ihariv Автор
    01.05.2018 14:37
    #10784446
    Плотно работаю с Нео4ж (comunity edition)
    — Очень интересно, нужно будет попробовать. Спасибо за наводку.
  1. apapacy
    01.05.2018 22:17
    #10784802
    Neo4j не рассматривал т.к. у них слишком строгая лицензия на community edition (персональное использование и внутри организации) что мне заведомо не подходит.
    По производительности также (postgres vs orientdb) я рассматривал не только поиск но и вставку записей на одной машине без шардинга. Тут даже скорее на первое место выходит стабильность и надежность, чем только скорость.
1. crocodile2u
  01.05.2018 16:00
  #10784490
  А что будет если нужно узнать для произвольного элемента цепочку всех элементов до корневого элемента?
  В случае MP, разве это не то, что хранится для эл-та в поле btree? Ответ в таком случае будет
  
  SELECT btree FROM tree WHERE id = :id
  
  Или я заработался и не понял вопроса?
  1. apapacy
    01.05.2018 21:39
    #10784764
    Наверное я что-то недопонял задавая вопрос. Сейчас посмотрел более внимательно наверное в btreе действительно хранится полный путь. Просто при прочтении статьи не нашел этого явно оговоренным.
    
    crocodile2u
    02.05.2018 17:01
    #10785452
    Ну просто так работает MP: хранит полный путь до корневого эл-та, в виде массива или строки, в зависимости от возможностей СУБД.

LireinCore
30.04.2018 22:29
#10784070
Так уже сделано в виде расширения:
https://postgrespro.ru/docs/postgrespro/10/ltree

Ihariv Автор
30.04.2018 22:29
#10784072
Да, спасибо. Просто не всегда можно использовать расширение (к примеру прав нет на установку). Да и сравнение без расширения более наглядно.
1. elmigranto
  01.05.2018 17:07
  #10784572
  Расширение встроено в постгрес, нужно просто сказать create extension и получить кучу операторов и правильную индексацию.
  
  https://www.postgresql.org/docs/10/static/ltree.html

Fortop
01.05.2018 14:10
#10784426
demiurg.livejournal.com/52346.html этот кейс не рассматривали?
1. greabock
  01.05.2018 14:27
  #10784434
  Этот шаблон называется closure table.
  Автор и NS как-то пропустил. Видимо NS и CT недостойны )
  1. Ihariv Автор
    01.05.2018 14:35
    #10784444
    NS я пропустил, поскольку он значительно сложнее и в добавлении записей и в последующем обслуживании.
1. Ihariv Автор
  01.05.2018 14:34
  #10784442
  SQL Trees. RAL
  По описанию автора все тот же самый добрый Materialized Path. Сделал бы по описанному выше методу — не пришлось бы ждать заполнения данных так долго. В моем случае миллион записей субъективно заполнилось за минут 20. Но сама попытка попробовать свое и приход к выводу хранения всех родителей очень хороший результат.
  1. Ihariv Автор
    01.05.2018 15:23
    #10784472
    точнее closure table — одна из разновидностей Materialized Path

Снова о деревьях +16

Комментарии (17)

Ihariv Автор

Ihariv Автор

Ihariv Автор

Ihariv Автор

Ihariv Автор

Ihariv Автор

Ihariv Автор