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 метода весьма и весьма запутанный. А этот запрос придется достаточно часто использовать.

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

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

image

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

image

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

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

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

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

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


  1. 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е действительно хранится полный путь. Просто при прочтении статьи не нашел этого явно оговоренным.


        1. crocodile2u
          02.05.2018 17:01
          #10785452

          Ну просто так работает MP: хранит полный путь до корневого эл-та, в виде массива или строки, в зависимости от возможностей СУБД.


  1. LireinCore
    30.04.2018 22:29
    #10784070

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


  1. 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


  1. 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