Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

Иерархия

Из песочницы Nested Sets для Javascript

15.09.2020 22:15:12 | Автор: admin
На любом современном сайте (да и на сайтах постарше) встречаются вложенные структуры, иерархия объектов, деревья. Самый распространенный пример каталог.

Сегодня множество проектов разрабатывается с использованием Javascript. Как же хранить древовидные структцры в этом случае? Об этом и хотелось бы поговорить.

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

Существуют различные алгоритмы для хранения деревьев и примером таких алгоритмов могут послужить Adjacency List, Matherialized Path, Nested Set и Closure Table.

Если посоветуете еще какие-то буду рад услышать и поучиться.

Когда я писал расширения для Joomla я часто использовал Nested Set. Именно в этой CMS я впервые встретил эту модель. Но теперь стек поменялся и сейчас это Javascript. Привычки остались, да и сайты на Joomla тоже. Нужно переносить данные на новые сервисы и проекты.

О Nested Sets довольно много информации в интернете и при желании вы всегда сможете ее найти, но тем не менее пару слов о этой модели данных я должен сказать.

Смысл Nested Set в том, что у каждого узла в иерархии существует пара ключей левый ключ и правый ключ. В зависимости от их значений осуществляется обход дерева. Положительными качествами алгоритма, на мой взгляд, является быстрота выборки данных. В этом алгоритме нет рекурсии. В то же время для изменения структуры дерева, добавления, удаления и переноса узлов, необходимо пересчитывать все ключи.

Чтобы использовать данные из Nested Set в проектах на Javascript нужен модуль который умел бы работать с этой моделью.

Поискав через npm я нашел модули, функционалом которых была выборка данных из структуры Nested Sets, т.е. все ключи уже должны были быть проставлены. Была необходимость править структуру, но такой возможности я не нашёл.

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

Таким образом одна и та же категория (данные категории) может лежать в разных родителях. Это позволит пользователям находить то, что они ищут быстрее при хорошо продуманной иерархии.

Хотя с точки зрения SEO появятся две страницы с разными URL и с одинаковым контентом, но это можно решить каноническими ссылками.

Если это не правильно прошу SEO-специалистов меня поправить.

В итоге я решил написать модуль и опубликовать его на npmjs.com.

Если кому-то пригодится буду очень рад.

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

Вот ссылка на npm, где вы можете скачать пакет.

Вот ссылка на github, где вы можете скачать исходники.

Документация есть и там и там.

Буду рад любым комментариям.

Хороших вам проектов и интересных задач.
Подробнее..
Категории: Javascript , Node.js , Npm , Деревья , Nested set , Иерархия

PostgreSQL Antipatterns Бесконечность не предел!, или Немного о рекурсии

01.10.2020 22:19:19 | Автор: admin
Рекурсия очень мощный и удобный механизм, если над связанными данными делаются одни и те же действия вглубь. Но неконтролируемая рекурсия зло, которое может приводить или к бесконечному выполнению процесса, или (что случается чаще) к выжиранию всей доступной памяти.


СУБД в этом отношении работают по тем же принципам "сказали копать, я и копаю". Ваш запрос может не только затормозить соседние процессы, постоянно занимая ресурсы процессора, но и уронить всю базу целиком, съев всю доступную память. Поэтому защита от бесконечной рекурсии обязанность самого разработчика.

В PostgreSQL возможность использовать рекурсивные запросы через WITH RECURSIVE появилась еще в незапамятные времена версии 8.4, но до сих пор можно регулярно встретить потенциально-уязвимые беззащитные запросы. Как избавить себя от проблем подобного рода?

Не писать рекурсивные запросы

А писать нерекурсивные. С уважением, Ваш К.О.

На самом деле, PostgreSQL предоставляет достаточно большое количество функционала, которым можно воспользоваться, чтобы не применять рекурсию.

Использовать принципиально другой подход к задаче


Иногда можно просто взглянуть на задачу с другой стороны. Пример такой ситуации я приводил в статье SQL HowTo: 1000 и один способ агрегации перемножение набора чисел без применения пользовательских агрегатных функций:

WITH RECURSIVE src AS (  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr), T(i, val) AS (  SELECT    1::bigint  , 1UNION ALL  SELECT    i + 1  , val * arr[i]  FROM    T  , src  WHERE    i <= array_length(arr, 1))SELECT  valFROM  TORDER BY -- отбор финального результата  i DESCLIMIT 1;

Такой запрос можно заменить на вариант от знатоков математики:

WITH src AS (  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime)SELECT  exp(sum(ln(prime)))::integer valFROM  src;

Использовать generate_series вместо циклов


Допустим, перед нами стоит задача сгенерировать все возможные префиксы для строки 'abcdefgh':

WITH RECURSIVE T AS (  SELECT 'abcdefgh' strUNION ALL  SELECT    substr(str, 1, length(str) - 1)  FROM    T  WHERE    length(str) > 1)TABLE T;

Точно-точно тут нужна рекурсия?.. Если воспользоваться LATERAL и generate_series, то даже CTE не понадобятся:

SELECT  substr(str, 1, ln) strFROM  (VALUES('abcdefgh')) T(str), LATERAL(    SELECT generate_series(length(str), 1, -1) ln  ) X;

Изменить структуру БД


Например, у вас есть таблица сообщений форума со связями кто-кому ответил или тред в социальной сети:

CREATE TABLE message(  message_id    uuid      PRIMARY KEY, reply_to    uuid      REFERENCES message, body    text);CREATE INDEX ON message(reply_to);


Ну и типовой запрос загрузки всех сообщений по одной теме выглядит примерно так:

WITH RECURSIVE T AS (  SELECT    *  FROM    message  WHERE    message_id = $1UNION ALL  SELECT    m.*  FROM    T  JOIN    message m      ON m.reply_to = T.message_id)TABLE T;

Но раз у нас всегда нужна вся тема от корневого сообщения, то почему бы нам не добавлять его идентификатор в каждую запись автоматом?

-- добавим поле с общим идентификатором темы и индекс на негоALTER TABLE message  ADD COLUMN theme_id uuid;CREATE INDEX ON message(theme_id);-- инициализируем идентификатор темы в триггере при вставкеCREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$BEGIN  NEW.theme_id = CASE    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события    ELSE ( -- или из сообщения, на которое отвечаем      SELECT        theme_id      FROM        message      WHERE        message_id = NEW.reply_to    )  END;  RETURN NEW;END;$$ LANGUAGE plpgsql;CREATE TRIGGER ins BEFORE INSERT  ON message    FOR EACH ROW      EXECUTE PROCEDURE ins();


Теперь весь наш рекурсивный запрос может быть сведен всего лишь к вот такому:

SELECT  *FROM  messageWHERE  theme_id = $1;

Использовать прикладные ограничители


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

Счетчик глубины рекурсии


Просто увеличиваем счетчик на единицу на каждом шаге рекурсии вплоть до момента достижения предела, который мы считаем заведомо неадекватным:

WITH RECURSIVE T AS (  SELECT    0 i  ...UNION ALL  SELECT    i + 1  ...  WHERE    T.i < 64 -- предел)

Pro: При попытке зацикливания мы все равно сделаем не более указанного лимита итераций вглубь.
Contra: Нет гарантии, что мы не обработаем повторно одну и ту же запись например, на глубине 15 и 25, ну и дальше будет каждые +10. Да и про вширь никто ничего не обещал.

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

см. Задача о зёрнах на шахматной доске

Хранитель пути


Поочередно дописываем все встретившиеся нам по пути рекурсии идентификаторы объектов в массив, который является уникальным путем до него:

WITH RECURSIVE T AS (  SELECT    ARRAY[id] path  ...UNION ALL  SELECT    path || id  ...  WHERE    id <> ALL(T.path) -- не совпадает ни с одним из)

Pro: При наличии цикла в данных мы абсолютно точно не станем обрабатывать повторно одну и ту же запись в рамках одного пути.
Contra: Но при этом мы можем обойти, буквально, все записи, так и не повторившись.

см. Задача о ходе коня

Ограничение длины пути


Чтобы избежать ситуации блуждания рекурсии на непонятной глубине, мы можем скомбинировать два предыдущих метода. Или, если не хотим поддерживать лишних полей, дополнить условие продолжения рекурсии оценкой длины пути:

WITH RECURSIVE T AS (  SELECT    ARRAY[id] path  ...UNION ALL  SELECT    path || id  ...  WHERE    id <> ALL(T.path) AND    array_length(T.path, 1) < 10)

Выбирайте способ на свой вкус!
Подробнее..
Категории: Программирование , Postgresql , Sql , Администрирование баз данных , Блог компании тензор , Sql tips and tricks , Рекурсия , Триггер , Иерархия

Как работать с иерархической структурой классов

22.04.2021 14:23:53 | Автор: admin

Задача классификации одна из самых известных в машинном обучении. Очень многие проблемы, решаемые с помощью ML, так или иначе сводятся к классификации распознавание изображений, например. И все выглядит просто и понятно, когда нам нужно определить объект в один из нескольких классов. А что если у нас не плоская структура из нескольких классов, а сложная разветвленная иерархия на 683 категории? Именно о таком случае мы сегодня и поговорим. Под катом рассказ о том, зачем в задачах классификации нужны сложные иерархии и как с ними жить.

В любой задаче классификации есть набор классов и есть модель, которая умеет предсказывать класс для новых данных. Допустим, модель бинарной классификации Спам/не спам, модель классификации настроения текста Хорошо/нейтрально/плохо. Классы обычно являются абстракцией реальности, а абстракция это всегда упрощение.

Однако реальность может быть гораздо сложнее, ведь имеется некоторая структура, взаимосвязи между классами. Одна из часто встречаемых в жизни структур это дерево иерархии. Существует множество вещей, которые можно классифицировать по одному принципу, но на разных уровнях абстракции или обобщения. Например, известная со школы классификация животных. На первом уровне это могут быть Млекопитающие и Рептилии, на втором Дельфины и Ящерицы. Определенный объект можно отнести к одному из классов на каждом уровне, причем все объекты, относящиеся к некоторому классу, также относятся и к родителю этого класса.

Это звучит понятно в школьном учебнике, но в контексте машинного обучения возникает множество вопросов:

  • Как с этим всем обращаться?

  • Какие классы предсказывать?

  • Сколько моделей тренировать для решения задачи?

  • Как работать с данными?

  • Как вносить изменения в иерархию классов и как реагировать на эти изменения с точки зрения модели?

Все эти проблемы мы разберем на примере задачи классификации, которую мы решаем в Контуре.

Постановка задачи

Мы работаем с чеками. В каждом чеке может встретиться много разных товаров, которые можно сгруппировать множеством разных способов. На данный момент нам интересно группировать эти товары с помощью дерева категорий, которое мы будем называть KPC (Khajiit Product Classification). Это здоровенное дерево, состоящее из 683 категорий.

Для этих категорий у нас есть Golden Set, наш размеченный набор данных (штрихкод категория KPC) для обучения. В датасете почти три миллиона записей и мы постоянно работаем над его дополнением и улучшением разметки.

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

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

Разметка данных

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

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

  • Активный.

  • Запланированный категория, на которую мы хотим классифицировать, но пока не можем (не хватает данных или не почистили разметку).

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

  • Удаленный.

В зависимости от статуса мы решаем, что делать с конкретной категорией на каждом из этапов классификации.

Также стоит упомянуть две отдельные группы категорий:

  • свалка (например Одежда (свалка)) группа для логического удаления некоторых товаров, которые невозможно категоризировать. Например, у нас есть товар Полное тестирование Тест 2 10шт, у которого из какого-то источника данных стоит категория Одежда. Наш аналитик данных понимает, что по факту категории у такого товара нет, поэтому такой товар отправляется в свалку, которая при обучении не рассматривается.

  • другое/другие (например Молочные товары, сыры и яйцо (другое)) группа для товаров, которые относятся к родительской категории, но не относятся (возможно, пока) ни к одной из дочерних.

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

Добавление категории

Добавить категорию мы можем в любое время, но для того, чтобы товары начали в неё попадать, необходимо:

  • Добавить категорию в KPC.

  • Переразметить обучающую выборку в соответствии с новой категорией (если товары новой категории раньше относились к другой категории проверить, что теперь они относятся к правильной).

  • Переобучить модель, чтобы она научилась классифицировать товары в новую категорию.

Удаление категории

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

Для удаления категории необходимо:

  • Перевести категорию в статус Архивная.

  • Решить, что мы делаем с товарами, которые относились к удаляемой и дочерним категориям.

  • Заменить удаляемую категорию у товаров в Golden Set.

  • Указать дочерним категориям новую родительскую категорию или её отсутствие (если дочерняя категория должна стать категорией верхнего уровня).

  • Переобучить модель, чтобы она перестала классифицировать товары в удаляемую категорию (и начала классифицировать эти товары в новые категории).

  • Перевести категорию в статус Удаленная.

Разбиение категории

Если появляется необходимость разбить одну категорию на несколько новых, нужно:

  • Обновить категории в Golden Set, чтобы отнести товары к новым категориям.

  • Переобучить модель, чтобы она научилась классифицировать товары в новые категории.

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

Обучение модели

На этапе обучения все сводится к обучению одного простого классификатора и иерархичность структуры, на первый взгляд, не добавляет никаких проблем. Однако перед обучением мы должны привести наши классы в порядок, чтобы в обучающей выборке не встречались одновременно дочерние и родительские классы (например, родительская категория Молочные продукты, яйца и сыры и дочерняя категория Яйца).

Такие коллизии плохо влияют на обучение товар может одновременно оказаться в обеих категориях и это может смутить нашу модель. Чтобы избежать таких случаев, перед обучением добавлен этап разрешения конфликтов дерева категорий (KPC collisions resolving).

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

Алгоритм разрешения конфликтов

Для начала разберемся с тем, что такое конфликт или коллизия. Коллизией мы считаем ситуацию, когда пара категорий ребенок/родитель одновременно представлена в KPC. То есть часть товаров размечена родительской категорией, часть дочерней. Как уже упоминалось выше, такие ситуации плохо влияют на обучение.

Для разрешения этих ситуаций мы будем маппить категории (то есть переносить все товары из одной категории в другую), а после обновлять наше дерево категорий (оставлять в рассмотрении только те категории, которые представлены в Golden set), проверяя, остались ли коллизии.

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

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

Future/Active на схеме это статусы категорий Запланированная/Активная, а present/NOT present in GS представлена ли категория в Golden set.

Еще один вопрос, который важно разобрать что мы хотим делать с Запланированными категориями? И что мы хотим делать с их детьми?

Есть несколько вариантов. Мы можем:

  • Использовать эти категории в классификации.

  • Не классифицировать и выбросить категории из GS.

  • Переразмечать эти категории в категорию-родителя.

  • Переразмечать эти товары в категорию другое/другие (например Молочные продукты, сыры и яйцо (другое))

После разбора таких случаев, ответов на архитектурные вопросы и итеративной разработки мы пришли к следующему алгоритму.

  1. Убрать удаленные, редко встречающиеся (меньше 10 товаров в golden set) и те категории, у которых в названии есть свалка.

  2. Если все дети категории в статусе Запланированный, то дочерние категории маппятся в родителя. Это происходит итеративно, так как после первого маппинга может возникнуть аналогичная ситуация на другом уровне дерева.

  3. Смаппить запланированные категории в sibling-категорию с другое/другие в названии, если такая есть.

  4. Удалить из Golden Set категории, у которых есть категории-потомки с товарами в Golden Set. Здесь происходит то самое разрешение конфликтов.

На каждом этапе мы рассматриваем уже обновленное дерево категорий. Важность этого пункта вытекла из разбора неочевидных ситуаций. Например, если не обновлять дерево (не убирать категории без товаров в GS и без потомков с товарами), то правило Смаппить всех Запланированных детей к родителю может не сработать из-за пустого, но активного ребенка.

Валидация модели

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

В первую очередь мы сравниваем базовые метрики accuracy (по всем классам) и accuracy/coverage. Необходимо следить за тем, чтобы баланс покрытия и точности не нарушался, а также за возможностью подобрать threshold для новой модели, при котором этот баланс соответствует нашим требованиям.

Во вторую очередь будем смотреть на метрики отдельно по каждому классу. Сначала на те, с которыми модель непосредственно знакома. Затем на родительские классы, путем агрегации (взвешенное среднее).

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

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

'errors' - sum of errors of confusing two labels,
'label_1_confuse' - count(true=label_1, pred=label_2) / 'errors',
'label_2_confuse' - count(true=label_2, pred=label_1) / 'errors',
'fraction_of_error_to_label_1' - count(true=label_1, pred=label_2) / total_label_1,
'fraction_of_error_to_label_2' - count(true=label_2, pred=label_1) / total_label_2,
'fraction_of_all_errors' - 'errors' / total_errors,
'fraction_of_all_errors_cumulative'

Выводы

  1. Для удобной итеративной работы с деревом категорий полезно ввести статусы категорий. Такие статусы позволят обрабатывать категории в разном состоянии разными способами.

  2. При валидации стоит агрегировать метрики для родительских категорий, чтобы иметь возможность сравнить две модели с разными наборами классов.

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

Подробнее..
Категории: Программирование , Машинное обучение , Data engineering , Блог компании контур , Классификация , Classification , Иерархия , Мультиклассовая классификация , Hierarchy , Hierarchical data , Иерархия классов

Инженерия для муравьев как не утонуть в сиропе

16.10.2020 10:22:46 | Автор: admin


Насекомые удивительные создания. Многие из них обладают крайне необычными свойствами и умениями. Кто-то испускает свет, кто-то может пережить ядерный удар, а кто-то бегает так быстро, что вынужден останавливаться, чтобы понять свое местоположение. Уникальностей много, как и семейств насекомых. Муравьи же уникальны своей численностью, организованностью и беспрекословной верой в монархию (Боже, храни Королеву). Разные виды муравьев проявляют те или иные навыки в зависимости от среды обитания и гастрономических предпочтений. К примеру, красные огненные муравьи (Solenopsis invicta) используют собственные тела для постройки живого плота, чтобы пережить наводнения. Однако этот метод спасения от смерти через утопление не является единственным, так как муравьи вполне способны использовать инструменты, чтобы избежать гибели. Ученые из Британского экологического общества (Лондон, Великобритания) выяснили, что черные огненные муравьи используют песок при сборе жидкой пищи, чтобы не утонуть. Как именно муравьи используют песок, меняется ли их поведение в зависимости от ситуации, и насколько эффективен такой навык выживания? Ответы на эти вопросы мы найдем в докладе ученых. Поехали.

Основа исследования


Муравьи прошли долгий путь эволюции, сделавший их самым развитым семейством насекомых в мире с точки зрения этологии, экологии и физиологии. Именно потому они вместе с термитами занимают примерно треть от общей биомассы планеты.


Документальный фильм о муравьях (BBC, Дэвид Аттенборо).

Говорить об особенностях муравьев можно часами, недаром существует целый раздел энтомологии их изучающий мирмекология. В рассматриваемом нами сегодня исследовании основной акцент был поставлен на качестве, которое присуще далеко не всем крупным млекопитающим с куда более развитой нервной системой, чем у муравьев. Речь, конечно же, об умении использовать инструменты.

На данный момент мы знаем множество примеров подобного поведения среди представителей фауны. Тем более удивительно, что ранее подобное считалось невозможным, а инструменты были прерогативой людей. Лишь в 60-е годы прошлого века были официально зафиксированы примеры использования инструментов среди шимпанзе. С тех пор список животных, использующих инструменты, пополнялся новыми видами, родами и семействами.

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


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

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

К 2010 году было зафиксировано порядка 50 случаев использования орудий труда у 30 различных родов насекомых. Среди них были и муравьи, а именно подсемейство Myrmicinae (виды: Pogonomyrmex badius, Solenopsis invicta Buren, Novomessor albisetosus и несколько видов из рода Aphaenogaster).

Позднее было установлено, что некоторые виды муравьев (например, Aphaenogaster longiceps) могут выбирать подходящий инструмент для добычи жидкой пищи, демонстрируя определенную гибкость муравьев в аспекте использования орудий труда.

И тут возникает вопрос могут ли муравьи менять инструменты и свое поведение в зависимости от ситуации?

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

Муравьи, собирающие пищу за пределами гнезда, должны эффективно выполнять свою задачу, параллельно выживая в условиях окружающей среды, где опасность заключается не только в хищниках, но и в самой местности. Даже сама пища может быть опасной. К примеру, экстрафлорный нектар (EFN от extrafloral nectar), выделяемый растениями, и медвяная падь (секрет насекомых, питающихся соком растений) являются важнейшим источником углеводов для развития колоний многих видов муравьев. Но из-за своего небольшого размера муравьи могут запутаться и утонуть в жидкости во время добычи пищи.


Главные герои исследования рабочие муравьи вида Solenopsis richteri Forel.

Возникает весьма любопытный вопрос осознают ли муравьи риски, связанные с добычей жидкой пищи, в том числе риск утонуть? Как оказалось, осознают. Ученые установили, что муравьи вида Solenopsis richteri Forel (черные огненные муравьи) могут распознавать увеличение риска утопления и соответственно корректировать свою стратегию использования инструментов.

Подготовка к опытам


Колония муравьев, участвующих в опытах, была собрана в округе Туника (штат Миссисипи, США). В специальных тестовых камерах (55х44х12 см) поддерживались необходимые для нормальной жизнедеятельности условия: температура 26 2 C, влажность 45% и неограниченный доступ к пище и воде (замороженные сверчки, 15% водный раствор сахара и дистиллированная вода).

Одним из аспектов, которые хотели проверить ученые, было поверхностное натяжение жидкости. Чтобы определить связь между риском утопления S. richteri и поверхностным натяжением жидкой пищи, была проведена оценка доли утонувших муравьев и степень сложности их спасения при различных концентрациях поверхностно-активного вещества (ПАВ).

Водный раствор сахара (15% по массе) использовался в качестве источника пищи на протяжении всего исследования. Подопытные муравьи могли спокойно плавать на поверхности раствора чистой воды с сахаром, возможно, из-за гидрофобных углеводородов на их кутикуле и высокого поверхностного натяжения раствора. Следовательно, чистый водный раствор сахара должен был представлять минимальный риск утопления для муравьев. Однако добавление ПАВ (TWEEN 80: 0%, 0.05%, 0.1%, 0.5%, 1% и 2%) снижает степень поверхностного натяжения, тем самым увеличивая риск утопления.

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

Во время опыта 1 мл водного раствора сахара с различными концентрациями ПАВ переносили в небольшой пластиковый контейнер (2.5 см в диаметре). Один рабочий муравей помещался в центр контейнера. Если муравей опускался на дно контейнера и не мог сбежать в течение 40 минут, его считали утонувшим. Для тех муравьев, которым удалось уцелеть, фиксировалось время, необходимое для спасения. В ходе данного опыта было использовано по 10 рабочих муравьев из каждой колонии (10 колоний всего).

На поведение муравьев может влиять и само ПАВ, используемое в опытах, а точнее его запах. Для оценки этого был использован ольфактометр с Y-образной трубкой. Две трубки вели к двум разным камерам. В одной присутствовал чистый воздух и жидкость с разной концентрацией ПАВ, в другой воздух с запахом TWEEN 80. В начало Y-трубки было помещено 80 особей, после его в течение 20 минут измерялось число особей, вошедших в ту или иную камеру на 3 см и глубже.

Далее были проведены тесты, связанные с риском утопления и формированием стратегии использования инструментов у подопытных муравьев. В тестовой камере был выбор инструментов: крупицы песка разного размера (крупные > 1.19 мм; средние 0.7071.19 мм и мелкие < 0.707 мм). Во время каждого теста была задействована колония муравьев из одной матки, 3 г муравьев и 0.2 г личинок. Каждую колонию переносили в пластиковый лоток (55х44х12 см) с искусственным гнездом.

В ходе данного опыта было 24 комбинации размера песка (крупный, средний, мелкий и смешанный) и концентрации поверхностно-активного вещества (0%, 0.05%, 0.1%, 0.5%, 1.0%, 2.0%), каждая из которых тестировалась отдельно по 12 заходов.

Через два часа после того, как песчинки были помещены в лоток, три пищевых контейнера (диаметром 2/5 см, каждый из которых содержал 1 мл раствора сахарной воды или сахарной воды с определенной концентрацией ПАВ) были помещены между песчинками и колонией муравьев.

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

Важно отметить, что муравьи данного вида способны строить уникальные конструкции для откачки жидкой пищи сифоны, состоящие из песчаных дорожек и песчаных насыпей. Чтобы подробно охарактеризовать эту конструкцию, весь процесс ее построения был записан для шести новых колоний с 1% ПАВ.

Для оценки эффективности столь необычной постройки муравьям были предоставлены песчинки разного размера (всего 12 г). Муравьи строили свою конструкцию для откачки жидкой пищи, после чего их убирали из тестовой камеры. Конструкцию сушили, а затем контролированно добавляли в нее 1 мл сахарной воды с 1% ПАВ. В ходе данного испытания измерялось время, необходимое для откачивания сахарной воды. Спустя 10 минут насыпь песка вне контейнера с пищей взвешивали и сушили. Разница веса до и после сушки показывала количество водного раствора сахара, содержащегося в структуре песка.

Также был проведен опыт, где муравьи строили песчаные структуры над контейнером с сахарной водой, после чего конструкцию сушили, а в камеру помещали другую колонию. Было два варианта: камера без конструкции и камера с конструкцией. Данный опыт проводился для оценки влияния подобных структур из песка на эффективность добычи пищи и на уровень смертности среди муравьев.

Результаты опытов


Сначала было оценено влияние поверхностного натяжения на степень риска утопления. При увеличении концентрации ПАВ поверхностное натяжение водного раствора сахара значительно снизилось с 77.17 0.24 до 43.28 0.24 мН/м (1A) и, соответственно, доля утонувших муравьев значительно увеличилась (1В).


Изображение 1

Что касается утонувших муравьев, то время их побега из сахарной воды увеличивалось с увеличением концентрации поверхностно-активного вещества (1C). Следовательно, наблюдалась очевидная отрицательная корреляция между временем, необходимым чтобы выбраться из сиропа, и поверхностным натяжением воды (1D).

Анализ поведенческих изменений на добавление ПАВ TWEEN 80 показал, что S. richteri не проявляют каких-либо явных предпочтений относительно TWEEN 80 (2A опыты без запаха ПАВ; 2В опыты с запахом ПАВ). Следовательно, добавление или удаление этого вещества не влияет на их поведение (с точки зрения реакции на запах вещества).


Изображение 2

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

Концентрация поверхностно-активного вещества, размер песчинок и их взаимодействие показали очевидное влияние на количество использованных песчинок (Таблица 1).


Таблица 1

Для сравнения, муравьи использовали значительно меньшее количество мелких песчинок внутри и снаружи пищевых контейнеров по сравнению с песчинками других размеров (3A и 3В), а в использовании крупнозернистых, средних и смешанных песчинок не было значительной разницы.

Что касается эффекта концентрации поверхностно-активного вещества, то добавление 0.05% ПАВ к сахарной воде привело к использованию большего количества песчинок в пищевых контейнерах по сравнению с контрольной группой и другими вариантами концентрации ПАВ (3D).


Изображение 3

Анализ данных со всех пищевых контейнеров с разными размерами песчинок показал, что число песчинок, использованных за пределами контейнера, практически не меняется в зависимости от концентрации ПАВ выше 0.05% (3E).

Любопытно, что при использовании песчинок разного размера и ПАВ 0.05% муравьи использовали больше песка именно внутри пищевого контейнера. Но комбинация песчинок любого размера с ПАВ больше 0.05% приводит к тому, что муравьи раскладывают песок вне контейнера.

Размер песчинок и концентрация ПАВ оказали значительное влияние на смертность муравьев (таблица 2).


Таблица 2

Число утонувших муравьев было меньше, когда были задействованы более крупные песчинки (3С).

При этом доля утонувших увеличивалась по мере увеличения концентрации ПАВ (3F). Самая численная смертность наблюдалась в случаях, когда концентрация ПАВ была выше 0.1% вне зависимости от размера песчинок.

Вполне логично, что муравьи предпочитали использовать более крупные песчинки, когда риск утопления увеличивался. Чем выше была концентрация ПАВ, тем больше крупных песчинок использовалось, особенно внутри контейнера с пищей.


Изображение 4

Когда концентрация ПАВ была выше 0.05%, муравьи начинали строить уникальные песчаные сооружения, чтобы соединить песчинки, размещенные внутри и снаружи контейнера (4A-4E).

Любопытно, что при концентрации ПАВ ровно 0.05%, муравьи размещали большую часть песчинок на внутренней стенке контейнера. Подобные конструкции наблюдались только при использовании поверхностно-активного вещества в сахарной воде.

Факт того, что муравьи строят разные песчаные конструкции при разных концентрациях ПАВ, подтверждает гибкость муравьев вида S. richteri в выборе стратегии использования инструментов.

А теперь стоит детальнее рассмотреть эти уникальные песчаные сооружения. Для изучения песчаных сифонов были сделаны записи строительства 13 таких структур.

На начальном этапе строительства муравьи просто питались сахарной водой внутри, когда ее только добавили в контейнер. Спустя 4-10 минут несколько особей утонули в сахарной воде, а другие начинали собирать и складывать песчинки внутри и снаружи контейнера.

Через 1.5 часа за пределами контейнера с пищей было больше песчинок, чем внутри (4A, 4B, 4E, видео ниже).




Муравьи приклеивали песчинки к стенке контейнера (снаружи и внутри), чтобы создать песчаную дорожку, соединяющую жидкость внутри и кучу песка снаружи.

Благодаря такой конструкции жидкая пища перемещалась из контейнера по песчаной дорожке, обеспечивая более безопасный сбор пищи (4A-4D).

Чаще всего к одному контейнеру подходила одна песчаная дорожка, а внешние песчаные насыпи располагались достаточно близко. Но в редких случаях дорожка была 11 см в длину (4E). Также была распространена практика строительства нескольких песчаных дорожек к одной насыпи. В строительстве данной конструкции муравьи использовали песчинки всех имеющихся размеров.

В среднем почти половина сахарной воды (49.67%) была перенесена в насыпь песка в течение пять минут (4F, видео ниже).




При наличии песчаных сифонов на 30 минуте наблюдений 89.87% из всех муравьев находились за пределами контейнера, а на 60 минуте 87.85% (4E, 4G, 4H).

Вполне ожидаемо, что наличие песчаных конструкций сильно повлияло на уровень смертности муравьев (таблица 3).


Таблица 3

При наличии песчаного сифона муравьев, питающихся внутри контейнера, было значительно меньше (5A и 5B). Данный показатель практически не менялся по отношению к концентрации ПАВ (5E и 5F).

Наличие сифона повысило эффективность сбора пищи на 8% (5C): без сифона 10.69 мг и с сифоном 11.54 мг. Этот показатель немного снижался при увеличении концентрации ПАВ (5G).

При наличии сифонной структуры наблюдалась меньшая доля утонувших муравьев, которая увеличивалась пропорционально увеличению концентрации поверхностно-активного вещества (5H).

Для более детального ознакомления с нюансами исследования рекомендую заглянуть в доклад ученых и дополнительные материалы (ссылка для скачивания файла .docx) к нему.

Эпилог


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

Риски, связанные с добычей пищи, влияют на поведение муравьев. Если риск велик, то муравьи стараются не лезть на рожон и начинают строить специальные конструкции из песка, которые переносят жидкую пищу в более безопасное место. За счет этого они могут спокойно собирать пищу, не боясь утонуть в ней.

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

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

Авторы исследования предполагают, что их труд позволит в будущем куда более детально изучить когнитивные механизмы и стратегии использования инструментов у социальных насекомых. Уникальна ли стратегия для каждого семейства/рода/вида или, возможно, есть некая универсальная стратегия, которой придерживаются все насекомые? Именно на этот вопрос ученые намерены найти ответ в будущих исследованиях.

Пятничный офф-топ:

Юмористическое, но правдивое видео о мутуализме среди муравьев.

Офф-топ 2.0:

Как бы сказал Эрмак из Mortal Kombat: We are many, you are but one

Благодарю за внимание, оставайтесь любопытствующими и отличных всем выходных, ребята! :)

Немного рекламы


Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
Подробнее..
Категории: Научно-популярное , Экология , Блог компании ua-hosting.company , Биотехнологии , Читальный зал , Инструменты , Коллективная работа , Выживание , Интеллект , Иерархия , Муравьи , Риски , Добыча пищи , Когнитивные способности , Колония

PostgreSQL Antipatterns DBA-детектив, или Три дела о потерянной производительности

18.11.2020 10:21:27 | Автор: admin
Сегодня вместо решения абстрактных алгоритмических задач мы выступим в роли детектива, по крупицам доставшейся информации исследующего неэффективные запросы, и рассмотрим три реальных дела, встречавшихся в разное время на просторах нашего приложения СБИС, когда простота и наивность при написании SQL превращалась в дополнительную нагрузку для PostgreSQL-сервера.


Дедукция и индукция помогут нам вычислить, что же все-таки хотел получить от СУБД разработчик, и почему это получилось не слишком оптимально. Итак, сегодня нас ждут:

  • Дело о непростом пути вверх
    Разберем в live-видео на реальном примере некоторые из способов улучшения производительности иерархического запроса.
  • Дело о худеющем запросе
    Увидим, как можно запрос упростить и ускорить в несколько раз, пошагово применяя стандартные методики.
  • Дело о развесистой клюкве
    Восстановим структуру БД на основании единственного запроса с 11 JOIN и предложим альтернативный вариант решения на ней той же задачи.

#1: Дело о непростом пути вверх



Давайте посмотрим на достаточно тривиальный запрос из недр функционала работы с каталогом товаров внутри складского учета, в котором вроде бы и ошибиться-то сложно.

WITH RECURSIVE h AS (  SELECT    n."@Номенклатура" id  , ARRAY[      coalesce(        (          SELECT            ne."Info"          FROM            "NomenclatureExt" ne          WHERE            ne."@Номенклатура" = n."@Номенклатура"          LIMIT 1        )      , '{}'      )    ] res  , n."Раздел" -- предок по иерархии  FROM    "Номенклатура" n  WHERE    n."@Номенклатура" = ANY($1::integer[])UNION -- уникализация  SELECT    h.id  , array_append(      h.res    , coalesce(        (          SELECT            ne."Info"          FROM            "NomenclatureExt" ne          WHERE            ne."@Номенклатура" = n."@Номенклатура"          LIMIT 1        )      , '{}'      )    ) -- расширение массива  , n."Раздел"  FROM    "Номенклатура" n  , h  WHERE    n."@Номенклатура" = h."Раздел" -- двигаемся вверх по иерархии в сторону предков)SELECT  h.id, h.resFROM  hWHERE  h."Раздел" IS NULL;

Мы пока ничего не знаем ни о структуре базы, ни о том, что этот запрос должен сделать восстановим все это, воспользовавшись утиным тестом:
Если нечто выглядит как утка, плавает как утка и крякает как утка, то это, вероятно, и есть утка.

Что/зачем делает запрос?


Любую оптимизацию производительности я рекомендую начинать с выяснения, что же вообще происходит в запросе, для чего именно он нужен.

В целом, это достаточно простой запрос, который идет рекурсивно по номенклатуре, вычитывая на первом шаге карточки товаров по списку идентификаторов, который был передан параметром.

WITH RECURSIVE / Path
На этом же шаге, помимо самого ID номенклатурной карточки, мы получаем идентификатор ее предка по иерархии и начинаем формировать массив-путь.

Subquery
Обратим внимание, что для каждой найденной записи номенклатуры будет произведен поиск связанной записи в соседней таблице NomenclatureExt. Явно это какая-то расширенная информация по номенклатурной карточке, связанная 1-в-1.

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

Path Filter
Ну, и в финале мы оставляем только те записи, которые являются финальными в цепочке то есть мы простроили путь вверх отдельно для каждого исходного идентификатора.

Проблемы в запросе


Какие очевидные проблемы при выполнении данного запроса нам грозят?

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

    Представим, что на первом шаге мы передали 60 идентификаторов в запрос и нашли эти 60 карточек из одного раздела. Несмотря на это, мы будем искать одного и того же предка те же 60 раз.
  2. Повторная вычитка связанной записи
    Поскольку мы вычитываем связанную запись независимо ни от чего, то и этот поиск мы делаем ровно столько же раз, сколько вычитываем запись основную.
  3. Вложенный запрос под уникализацией
    Одно и то же значение из связанной записи вычитывается каждый раз, и только после этого схлапывается до единственного экземпляра.

    То есть в нашем примере 59 из 60 вложенных запросов будут выполнены заведомо абсолютно зря.

Обратим внимание на конкретный вариант плана такого запроса:

  • 107 карточек вычитано Bitmap Scan на стартовой итерации рекурсии и плюсом к ним 107 индексных поисков связанных
  • Поскольку PostgreSQL заранее не понимает, сколько и каких записей мы найдем вверх по иерархии, он вычитывает сразу все 18K из номенклатуры с помощью Seq Scan. В результате, из 22мс выполнения запроса 12мс мы потратили на чтение всей таблицы и еще 5мс на ее хэширование, итого больше 77%.
  • Из вычитанных 18K нужными нам по результату Hash Join окажутся только 475 штук и теперь добавим к ним еще 475 Index Scan по связанным записям.
  • Итого: 22мс и 2843 buffers суммарно.

Что/как можно исправить?


Во-первых, стоит избавиться от дубль-чтений одних и тех же карточек при движении вверх по иерархии.

  1. Поскольку нам нужны сразу и идентификатор самой карточки, и идентификатор ее предка, будем вычитывать записи сразу целиком как (tableAlias).
  2. Вычитку будем производить с помощью конструкции = ANY(ARRAY(...)), исключая возможность возникновения неудобных JOIN.
  3. Для возможности уникализации и хэширования скастуем записи таблицы в (row)::text.
  4. Поскольку внутри рекурсии обращение к рекурсивной части может быть только однократным и строго не внутри вложенных запросов, вместо этого материализуем ее внутри отдельной CTE.
  5. Таблицу состоящую из единственного столбца можно свернуть с помощью ARRAY(TABLE X) до скалярного значения-массива. А если в ней и так одна запись, то использовать ее с нужной раскастовкой (TABLE X)::integer[].

-- рекурсивный подъем вверх до корня с поиском только уникальных записей, it AS (  SELECT    it::text -- иначе не работает уникализация через UNION  FROM    "Номенклатура" it  WHERE    "@Номенклатура" = ANY((TABLE src)::integer[])UNION  (    WITH X AS (      SELECT DISTINCT        (it::"Номенклатура")."Раздел"      FROM        it      WHERE        (it::"Номенклатура")."Раздел" IS NOT NULL    )    SELECT      it2::text    FROM      "Номенклатура" it2    WHERE      "@Номенклатура" = ANY(ARRAY(TABLE X))  ))

Поскольку мы получили только набор самих записей, теперь нам надо выстроить из них цепочки потомок-предок рекурсивным спуском сверху-вниз:

-- рекурсивный спуск вниз для формирования "пути" к каждой карточке, itr AS (  SELECT    ARRAY[(it::"Номенклатура")."@Номенклатура"] path  , it::"Номенклатура" -- запись исходной таблицы  FROM    it  WHERE    (it::"Номенклатура")."Раздел" IS NULL -- стартуем от "корневых" записейUNION ALL  SELECT    ARRAY[((_it.it)::"Номенклатура")."@Номенклатура"] || itr.path -- наращиваем "путь" спереди  , (_it.it)::"Номенклатура"  FROM    itr  JOIN    it _it      ON ((_it.it)::"Номенклатура")."Раздел@" IS NOT FALSE AND      ((_it.it)::"Номенклатура")."Раздел" = (itr.it)."@Номенклатура")

Теперь из полученных путей-из-ID восстановим значение поля Info из связанной таблицы. Но бегать так по каждому ID несколько раз для преобразования каждого отдельного пути будет очень долго, поэтому:

  • Соберем весь набор ID, встречающихся в путях. Но это ровно тот же набор, который дают ID самих наших извлеченных записей.
  • Извлечем опять сразу все нужные нам записи связанной таблицы за один проход через = ANY(ARRAY(...)).
  • Сложим все полученные значения нужного поля в hstore-словарик.

-- формируем словарь info для каждого ключа, чтобы не бегать по записям CTE, hs AS (  SELECT    hstore(      array_agg("@Номенклатура"::text)    , array_agg(coalesce("Info", '{}'))    )  FROM    "NomenclatureExt"  WHERE    "@Номенклатура" = ANY(ARRAY(      SELECT        (it)."@Номенклатура"      FROM        itr    )))

Остался последний шаг преобразовать цепочку ID в цепочку Info с помощью ARRAY(SELECT ... unnest(...)):

, ARRAY(    SELECT      (TABLE hs) -> id::text -- извлекаем данные из "словаря"    FROM      unnest(path) id  ) res

В результате, целиком наш запрос будет выглядеть примерно так:

-- список всех исходных IDWITH RECURSIVE src AS (  SELECT $1::integer[] -- набор ID в виде сериализованного массива)-- рекурсивный подъем вверх до корня с поиском только уникальных записей, it AS (  SELECT    it::text -- иначе не работает уникализация через UNION  FROM    "Номенклатура" it  WHERE    "@Номенклатура" = ANY((TABLE src)::integer[])UNION  (    WITH X AS (      SELECT DISTINCT        (it::"Номенклатура")."Раздел"      FROM        it      WHERE        (it::"Номенклатура")."Раздел" IS NOT NULL    )    SELECT      it2::text    FROM      "Номенклатура" it2    WHERE      "@Номенклатура" = ANY(ARRAY(TABLE X))  ))-- рекурсивный спуск вниз для формирования "пути" к каждой карточке, itr AS (  SELECT    ARRAY[(it::"Номенклатура")."@Номенклатура"] path  , it::"Номенклатура"  FROM    it  WHERE  WHERE    (it::"Номенклатура")."Раздел" IS NULL -- стартуем от "корневых" записейUNION ALL  SELECT    ARRAY[((_it.it)::"Номенклатура")."@Номенклатура"] || itr.path -- наращиваем "путь" спереди  , (_it.it)::"Номенклатура"  FROM    itr  JOIN    it _it      ON ((_it.it)::"Номенклатура")."Раздел@" IS NOT FALSE AND      ((_it.it)::"Номенклатура")."Раздел" = (itr.it)."@Номенклатура")-- формируем словарь info для каждого ключа, чтобы не бегать по записям CTE, hs AS (  SELECT    hstore(      array_agg("@Номенклатура"::text)    , array_agg(coalesce("Info", '{}'))    )  FROM    "NomenclatureExt"  WHERE    "@Номенклатура" = ANY(ARRAY(      SELECT        (it)."@Номенклатура"      FROM        itr    )))-- строим цепочку info для каждого id из оригинального набораSELECT  path[1] id, ARRAY(    SELECT      (TABLE hs) -> id::text -- извлекаем данные из "словаря"    FROM      unnest(path) id  ) resFROM  itrWHERE  path[1] = ANY((TABLE src)::integer[]); -- ограничиваемся только стартовым набором

  • Теперь на каждом шаге рекурсии (а их получается 4, в соответствии с глубиной дерева) мы добавляем, в среднем, всего по 12 записей.
  • Восстановление путей вниз заняло большую часть времени 10мс. Можно сделать и меньше, но это гораздо сложнее.
  • Итого, новый запрос выполняется 15мс вместо 22мс и читает только лишь 860 страниц данных вместо 2843, что имеет принципиальное влияние на время работы, когда нет возможности обеспечить постоянное присутствие этих данных в кэше.

#2: Дело о худеющем запросе



Второй запрос оказался намного кучерявее, но интереснее с практической точки зрения, поскольку вызывается очень часто для получения информации о персонах как внутри нашей корпоративной социальной сети, так и другими сервисами, использующими ее.

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

Регулярно возникают реплики типа "Вот ты ускорил запрос в 10 раз, но всего на 10мс оно же того не стоит! Мы лучше поставим еще пару реплик! Вместо 100MB памяти получилось 1MB? Да нам проще памяти на сервер добавить!"

Тут какой момент разработчик, вооруженный набором стандартных приемов, на оптимизацию запроса тратит константное время (= деньги), а с увеличением функционала и количества пользователей нагрузка на БД растет примерно как N(logN), а даже не линейно. То есть если сейчас ваш проект ест CPU базы на 50%, готовьтесь к тому, что уже через год вам придется ставить еще один такой же сервер (= деньги), потом еще и еще

Оптимизация запросов не избавляет от добавления мощностей, но сильно отодвигает их в будущее. Добившись вместо нагрузки в 50% всего 10%, вы сможете не расширять железо еще года 2-3, а вложить те же деньги, например, в увеличение штата или чьей-то зарплаты.

00: исходное состояние


00: исходный запрос, 7.2мс 
WITH personIds("Персона") AS (  SELECT    $1::uuid[]), persons AS (  SELECT    P."Персона"  , coalesce(P."Фамилия", '') "Фамилия"  , coalesce(P."Имя", '') "Имя"  , coalesce(P."Отчество", '') "Отчество"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ФамилияЛица"        ELSE          P."Фамилия"      END    , ''    ) "ФамилияЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ИмяЛица"        ELSE          P."Имя"      END    , ''    ) "ИмяЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ОтчествоЛица"        ELSE          P."Отчество"      END    , ''    ) "ОтчествоЛица"  , P."Примечание"  , P."Обновлено"  , P."Уволен"  , P."Группа"  , P."Пол"  , P."Логин"  , P."Город"  , P."ДатаРождения"  , P."$Создано"::date "ДатаРегистрации"  , coalesce(P."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(P."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  FROM    "Персона" P  WHERE    "Персона" = ANY((TABLE personids)::uuid[])), counts AS (  SELECT    NULL c), users AS (  SELECT    hstore(      array_agg("Персона"::text)    , array_agg(udata::text)    )  FROM    (      SELECT        "Персона"::text      , array_agg(u::text) udata      FROM        "Пользователь" u      WHERE        "Персона" IN (          SELECT            "Персона"          FROM            persons        ) AND        (          "Главный" OR          (            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )        )      GROUP BY 1    ) u2), T1 AS (  SELECT    persons."Персона"  , persons."Фамилия"  , persons."Имя"  , persons."Отчество"  , persons."ФамилияЛица"  , persons."ИмяЛица"  , persons."ОтчествоЛица"  , persons."Примечание"  , persons."Обновлено"  , persons."Город"  , coalesce(persons."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(persons."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  , counts.c "Всего"  , persons."Группа"  , (      SELECT        ARRAY(          SELECT            row_to_json(t2)          FROM            (              SELECT                "Пользователь" >> 32 as "Account"              , "Пользователь" & x'FFFFFFFF'::bigint "Face"              , coalesce("ЕстьПользователь", TRUE) "HasUser"              , coalesce("ЕстьПользователь", TRUE) AND coalesce("Входил", TRUE) "HasLoggedIn"              , coalesce("Уволен", persons."Уволен") "Fired"              FROM                (                  SELECT                    *                  FROM                    (                      SELECT                        (udata::"Пользователь").*                      FROM                        unnest(((TABLE users) -> "Персона"::text)::text[]) udata                    ) udata15                  WHERE                    "Уволен" IS DISTINCT FROM TRUE AND                    "Удален" IS DISTINCT FROM TRUE                ) udata2            ) t2        )    )::text[] "Users"  , coalesce(      (        SELECT          row_to_json(t3)        FROM          (            SELECT              "Пользователь" >> 32 as "Account"            , "Пользователь" & x'FFFFFFFF'::bigint "Face"            FROM              (                SELECT                  (udata::"Пользователь").*                FROM                  unnest(((TABLE users) -> "Персона"::text)::text[]) udata              ) udata2            WHERE              "Уволен" IS DISTINCT FROM TRUE AND              "Удален" IS DISTINCT FROM TRUE AND              "Пользователь" >> 32 = 5313189::int            ORDER BY              "ЕстьПользователь" DESC, "Входил" DESC            LIMIT 1          ) t3      )    , (        SELECT          row_to_json(t4)        FROM          (            SELECT              "Пользователь" >> 32 as "Account"            , "Пользователь" & x'FFFFFFFF'::bigint "Face"            FROM              (                SELECT                  (udata::"Пользователь").*                FROM                  unnest(((TABLE users) -> "Персона"::text)::text[]) udata              ) udata2            WHERE              "Уволен" IS DISTINCT FROM TRUE AND              "Удален" IS DISTINCT FROM TRUE AND              "Главный"            ORDER BY              "ЕстьПользователь" DESC, "Входил" DESC            LIMIT 1          ) t4      )    , (        SELECT          row_to_json(t5)        FROM          (            SELECT              "Пользователь" >> 32 as "Account"            , "Пользователь" & x'FFFFFFFF'::bigint "Face"            FROM              (                SELECT                  (udata::"Пользователь").*                FROM                  unnest(((TABLE users) -> "Персона"::text)::text[]) udata              ) udata2            WHERE              "Уволен" IS DISTINCT FROM TRUE AND              "Удален" IS DISTINCT FROM TRUE            LIMIT 1          ) t5      )    ) "PrimaryFaceAccount"  , (      SELECT        "Пользователь" >> 32      FROM        (          SELECT            "Пользователь"          FROM            (              SELECT                (udata::"Пользователь").*              FROM                unnest(((TABLE users) -> "Персона"::text)::text[]) udata            ) udata2          WHERE            "Главный"        ) t3      LIMIT 1    ) "MainAccount"  , ARRAY(      SELECT        "Значение"::int      FROM        "КонтактныеДанные"      WHERE        persons."Группа" AND        "Персона" = persons."Персона" AND        "Тип" = 'account'    ) "АккаунтыГруппы"  , persons."Пол"  , persons."Логин"  , persons."ДатаРождения"  , persons."ДатаРегистрации"  FROM    persons  , counts)SELECT  CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ФамилияЛица"    ELSE      "Фамилия"  END "LastName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ИмяЛица"    ELSE      "Имя"  END "FirstName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ОтчествоЛица"    ELSE      "Отчество"  END "PatronymicName", *FROM  T1;



Даже беглого взгляда на диаграмму выполнения достаточно, чтобы сразу увидеть, что в плане встречаются подозрительно одинаковые куски (SubPlan 8, SubPlan 10, SubPlan 12, SubPlan 14, SubPlan 16), внутри которых время тратится на unnest записей из массива внутри CTE.

Эти субпланы соответствуют подзапросам по развороту массива пользователей из hstore по ключу каждой отдельной персоны:

  , coalesce(      (        SELECT          row_to_json(T)        FROM          (            SELECT              ...            FROM              (                SELECT                  (udata::"Пользователь").*                FROM                  unnest(((TABLE users) -> "Персона"::text)::text[]) udata              ) udata2            WHERE              ...            ORDER BY              ...            LIMIT 1          ) T      )

Заметим, что все эти подзапросы работают с одним и тем же исходным набором данных, просто кто-то берет из него данные по одному условию, а кто-то по другому; кто-то сортирует, а кто-то нет; кто-то берет все поля из всех записей, а кто-то только пару из первой

  1. Можно ли сделать все то же самое за один проход? Конечно! В этом нам помогут FILTER (9.4+) и LATERAL (9.3+).
  2. Вместо построения JSON независимо в 5 разных местах (по одним и тем же записям, в основном). Построим эти JSON сразу для каждой исходной записи в полном (5 ключей) и коротком (2 ключа) вариантах.
  3. Сортировка исходного набора совпадает во всех местах, где используется. Где не используется значит, непринципиально для данных, и ее можно использовать все равно.
  4. LIMIT 1 можно успешно заменить на извлечение первого элемента массива: arr[1]. Так что собираем по каждому условию именно массивы.
  5. Для одновременного возврата нескольких агрегатов используем сериализацию в ARRAY[aggx::text, aggy::text].

01. FILTER + LATERAL + single JSON (4мс, -45%) 
WITH personIds("Персона") AS (  SELECT    $1::uuid[]), persons AS (  SELECT    P."Персона"  , coalesce(P."Фамилия", '') "Фамилия"  , coalesce(P."Имя", '') "Имя"  , coalesce(P."Отчество", '') "Отчество"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ФамилияЛица"        ELSE          P."Фамилия"      END    , ''    ) "ФамилияЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ИмяЛица"        ELSE          P."Имя"      END    , ''    ) "ИмяЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ОтчествоЛица"        ELSE          P."Отчество"      END    , ''    ) "ОтчествоЛица"  , P."Примечание"  , P."Обновлено"  , P."Уволен"  , P."Группа"  , P."Пол"  , P."Логин"  , P."Город"  , P."ДатаРождения"  , P."$Создано"::date "ДатаРегистрации"  , coalesce(P."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(P."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  FROM    "Персона" P  WHERE    "Персона" = ANY((TABLE personids)::uuid[])), counts AS (  SELECT    NULL c), users AS (  SELECT    hstore(      array_agg("Персона"::text)    , array_agg(udata::text)    )  FROM    (      SELECT        "Персона"::text      , array_agg(u::text) udata      FROM        "Пользователь" u      WHERE        "Персона" IN (          SELECT            "Персона"          FROM            persons        ) AND        (          "Главный" OR          (            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )        )      GROUP BY 1    ) u2), T1 AS (  SELECT    persons."Персона"  , persons."Фамилия"  , persons."Имя"  , persons."Отчество"  , persons."ФамилияЛица"  , persons."ИмяЛица"  , persons."ОтчествоЛица"  , persons."Примечание"  , persons."Обновлено"  , persons."Город"  , coalesce(persons."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(persons."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  , counts.c "Всего"  , persons."Группа"-- 8< --  , coalesce(usjs[1]::text[], '{}') "Users"  , coalesce(      (usjs[2]::json[])[1]    , (usjs[3]::json[])[1]    , (usjs[4]::json[])[1]    ) "PrimaryFaceAccount"  , ((usjs[5]::json[])[1] ->> 'Account')::bigint "MainAccount"-- 8< --  , ARRAY(      SELECT        "Значение"::int      FROM        "КонтактныеДанные"      WHERE        persons."Группа" AND        "Персона" = persons."Персона" AND        "Тип" = 'account'    ) "АккаунтыГруппы"  , persons."Пол"  , persons."Логин"  , persons."ДатаРождения"  , persons."ДатаРегистрации"  FROM    persons  , counts-- 8< --  , LATERAL (      SELECT        ARRAY[ -- массив сериализованных json[]          array_agg(json_f) FILTER (WHERE -- фильтрация по необходимому условию            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Пользователь" >> 32 = 5313189::int          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Главный"          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Главный"          )::text        ] usjs      FROM        (          SELECT -- готовим JSON для каждой записи сразу, потом только используем готовый            json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            , 'HasUser'            , coalesce("ЕстьПользователь", TRUE)            , 'HasLoggedIn'            , coalesce("ЕстьПользователь", TRUE) AND coalesce("Входил", TRUE)            , 'Fired'            , coalesce("Уволен", persons."Уволен")            ) json_f          , json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            ) json_s          , *          FROM            (              SELECT                (unnest).*              FROM                unnest(((TABLE users) -> "Персона"::text)::"Пользователь"[])            ) T          ORDER BY -- сортировка одна на всех            "ЕстьПользователь" DESC, "Входил" DESC        ) T    ) usjs-- 8< --)SELECT  CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ФамилияЛица"    ELSE      "Фамилия"  END "LastName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ИмяЛица"    ELSE      "Имя"  END "FirstName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ОтчествоЛица"    ELSE      "Отчество"  END "PatronymicName", *FROM  T1;



План уже много приятнее и много короче. Кто самое слабое звено теперь? unnest!

Так, стоп Мы в unnest по каждой персоне разворачиваем массив, который ранее засунули в hstore с ключом этой же персоны? А физически-то мы все равно отбираем в hstore независимо по каждой персоне.

Я это к тому, что мы сначала нашли, сгруппировали, сериализовали, потом достали, десериализовали, развернули Что бы серверу не поработать-то?..

  1. В общем, выносим формирование JSON в подзапрос именно по каждой из персон. В результате у нас исчезает CTE users и hstore.

02. Подзапрос (4мс, -45%) 
WITH personIds("Персона") AS (  SELECT    $1::uuid[]), persons AS (  SELECT    P."Персона"  , coalesce(P."Фамилия", '') "Фамилия"  , coalesce(P."Имя", '') "Имя"  , coalesce(P."Отчество", '') "Отчество"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ФамилияЛица"        ELSE          P."Фамилия"      END    , ''    ) "ФамилияЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ИмяЛица"        ELSE          P."Имя"      END    , ''    ) "ИмяЛица"  , coalesce(      CASE        WHEN nullif(P."ФамилияЛица", '') IS NOT NULL THEN          P."ОтчествоЛица"        ELSE          P."Отчество"      END    , ''    ) "ОтчествоЛица"  , P."Примечание"  , P."Обновлено"  , P."Уволен"  , P."Группа"  , P."Пол"  , P."Логин"  , P."Город"  , P."ДатаРождения"  , P."$Создано"::date "ДатаРегистрации"  , coalesce(P."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(P."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"-- 8< --  , (      SELECT        ARRAY[ -- массив сериализованных json[]          array_agg(json_f) FILTER (WHERE -- фильтрация по необходимому условию            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Пользователь" >> 32 = 5313189::int          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Главный"          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Главный"          )::text        ] usjs      FROM        (          SELECT -- готовим JSON для каждой записи сразу, потом только используем готовый            json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            , 'HasUser'            , coalesce("ЕстьПользователь", TRUE)            , 'HasLoggedIn'            , coalesce("ЕстьПользователь", TRUE) AND coalesce("Входил", TRUE)            , 'Fired'            , coalesce("Уволен", P."Уволен")            ) json_f          , json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            ) json_s          , *          FROM            "Пользователь"          WHERE            "Персона" = P."Персона" AND            (              "Главный" OR              (                "Уволен" IS DISTINCT FROM TRUE AND                "Удален" IS DISTINCT FROM TRUE              )            )          ORDER BY -- сортировка одна на всех            "ЕстьПользователь" DESC, "Входил" DESC        ) T    ) usjs-- 8< --  FROM    "Персона" P  WHERE    "Персона" = ANY((TABLE personids)::uuid[])), counts AS (  SELECT    NULL c), T1 AS (  SELECT    persons."Персона"  , persons."Фамилия"  , persons."Имя"  , persons."Отчество"  , persons."ФамилияЛица"  , persons."ИмяЛица"  , persons."ОтчествоЛица"  , persons."Примечание"  , persons."Обновлено"  , persons."Город"  , coalesce(persons."ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce(persons."ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  , counts.c "Всего"  , persons."Группа"  , coalesce(usjs[1]::text[], '{}') "Users"  , coalesce(      (usjs[2]::json[])[1]    , (usjs[3]::json[])[1]    , (usjs[4]::json[])[1]    ) "PrimaryFaceAccount"  , ((usjs[5]::json[])[1] ->> 'Account')::bigint "MainAccount"  , ARRAY(      SELECT        "Значение"::int      FROM        "КонтактныеДанные"      WHERE        persons."Группа" AND        "Персона" = persons."Персона" AND        "Тип" = 'account'    ) "АккаунтыГруппы"  , persons."Пол"  , persons."Логин"  , persons."ДатаРождения"  , persons."ДатаРегистрации"  FROM    persons  , counts)SELECT  CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ФамилияЛица"  ELSE    "Фамилия"  END "LastName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ИмяЛица"    ELSE      "Имя"  END "FirstName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ОтчествоЛица"    ELSE      "Отчество"  END "PatronymicName", *FROM  T1;



Кто теперь выглядит лишним?

  1. Очевидно, CTE personids (заменяем на inline-параметр с раскастовкой) и CTE counts (вообще какой-то странный атавизм, возвращающий один NULL).
  2. После этого замечаем, что все выборки у нас стали из единственной таблички, поэтому лучше убрать избыточные алиасы.

03. Inline-параметры (3.9мс, -46%) 
WITH persons AS (  SELECT    "Персона"  , coalesce("Фамилия", '') "Фамилия"  , coalesce("Имя", '') "Имя"  , coalesce("Отчество", '') "Отчество"  , coalesce(      CASE        WHEN nullif("ФамилияЛица", '') IS NOT NULL THEN          "ФамилияЛица"        ELSE          "Фамилия"      END    , ''    ) "ФамилияЛица"  , coalesce(      CASE        WHEN nullif("ФамилияЛица", '') IS NOT NULL THEN          "ИмяЛица"        ELSE          "Имя"      END    , ''    ) "ИмяЛица"  , coalesce(      CASE        WHEN nullif("ФамилияЛица", '') IS NOT NULL THEN          "ОтчествоЛица"        ELSE          "Отчество"      END    , ''    ) "ОтчествоЛица"  , "Примечание"  , "Обновлено"  , "Уволен"  , "Группа"  , "Пол"  , "Логин"  , "Город"  , "ДатаРождения"  , "$Создано"::date "ДатаРегистрации"  , coalesce("ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce("ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  , (      SELECT        ARRAY[ -- массив сериализованных json[]          array_agg(json_f) FILTER (WHERE -- фильтрация по необходимому условию            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Пользователь" >> 32 = 5313189::int          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Главный"          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Главный"          )::text        ] usjs      FROM        (          SELECT -- готовим JSON для каждой записи сразу, потом только используем готовый            json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            , 'HasUser'            , coalesce("ЕстьПользователь", TRUE)            , 'HasLoggedIn'            , coalesce("ЕстьПользователь", TRUE) AND coalesce("Входил", TRUE)            , 'Fired'            , coalesce("Уволен", p."Уволен")            ) json_f          , json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            ) json_s          , *          FROM            "Пользователь"          WHERE            "Персона" = p."Персона" AND            (              "Главный" OR              (                "Уволен" IS DISTINCT FROM TRUE AND                "Удален" IS DISTINCT FROM TRUE              )            )          ORDER BY -- сортировка одна на всех            "ЕстьПользователь" DESC, "Входил" DESC        ) T    ) usjs  FROM    "Персона" p  WHERE-- 8< --    "Персона" = ANY($1::uuid[])-- 8< --), T1 AS (  SELECT    "Персона"  , "Фамилия"  , "Имя"  , "Отчество"  , "ФамилияЛица"  , "ИмяЛица"  , "ОтчествоЛица"  , "Примечание"  , "Обновлено"  , "Город"  , coalesce("ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"  , coalesce("ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"  , NULL::bigint "Всего"  , "Группа"  , coalesce(usjs[1]::text[], '{}') "Users"  , coalesce(      (usjs[2]::json[])[1]    , (usjs[3]::json[])[1]    , (usjs[4]::json[])[1]    ) "PrimaryFaceAccount"  , ((usjs[5]::json[])[1] ->> 'Account')::bigint "MainAccount"  , ARRAY(      SELECT        "Значение"::int      FROM        "КонтактныеДанные"      WHERE        persons."Группа" AND        "Персона" = persons."Персона" AND        "Тип" = 'account'    ) "АккаунтыГруппы"  , "Пол"  , "Логин"  , "ДатаРождения"  , "ДатаРегистрации"  FROM    persons)SELECT  CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ФамилияЛица"  ELSE    "Фамилия"  END "LastName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ИмяЛица"    ELSE      "Имя"  END "FirstName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ОтчествоЛица"    ELSE      "Отчество"  END "PatronymicName", *FROM  T1;


Смотрим теперь на запрос очень-очень пристально, и задумываемся:

  1. Зачем нам лишняя CTE T1 (ведь CTE Scan стоит ресурсов)?
  2. Зачем мы один и тот же список полей переписываем дважды?
  3. Зачем дважды применяется coalesce на одни и те же поля?

04. Убрали все лишнее (3.2мс, -56%) 
WITH p AS (  SELECT    *-- 8< --  , CASE      WHEN nullif("ФамилияЛица", '') IS NOT NULL THEN        ARRAY[          coalesce("ФамилияЛица", '')        , coalesce("ИмяЛица", '')        , coalesce("ОтчествоЛица", '')        ]      ELSE        ARRAY[          coalesce("Фамилия", '')        , coalesce("Имя", '')        , coalesce("Отчество", '')        ]    END fio-- 8< --  , (      SELECT        ARRAY[ -- массив сериализованных json[]          array_agg(json_f) FILTER (WHERE -- фильтрация по необходимому условию            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Пользователь" >> 32 = 5313189::int          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE AND            "Главный"          )::text        , array_agg(json_s) FILTER (WHERE            "Уволен" IS DISTINCT FROM TRUE AND            "Удален" IS DISTINCT FROM TRUE          )::text        , array_agg(json_s) FILTER (WHERE            "Главный"          )::text        ] usjs      FROM        (          SELECT -- готовим JSON для каждой записи сразу, потом только используем готовый            json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            , 'HasUser'            , coalesce("ЕстьПользователь", TRUE)            , 'HasLoggedIn'            , coalesce("ЕстьПользователь", TRUE) AND coalesce("Входил", TRUE)            , 'Fired'            , coalesce("Уволен", p."Уволен")            ) json_f          , json_build_object(              'Account'            , "Пользователь" >> 32            , 'Face'            , "Пользователь" & x'FFFFFFFF'::bigint            ) json_s          , *          FROM            "Пользователь"          WHERE            "Персона" = p."Персона" AND            (              "Главный" OR              (                "Уволен" IS DISTINCT FROM TRUE AND                "Удален" IS DISTINCT FROM TRUE              )            )          ORDER BY -- сортировка одна на всех            "ЕстьПользователь" DESC, "Входил" DESC        ) T    ) usjs  FROM    "Персона" p  WHERE    "Персона" = ANY($1::uuid[]))-- 8< --SELECT  CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ФамилияЛица"  ELSE    "Фамилия"  END "LastName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ИмяЛица"    ELSE      "Имя"  END "FirstName", CASE    WHEN "ЕстьКорпАккаунт" OR "MainAccount" IS NOT NULL THEN      "ОтчествоЛица"    ELSE      "Отчество"  END "PatronymicName", *FROM  (    SELECT      "Персона"    , coalesce("Фамилия", '') "Фамилия"    , coalesce("Имя", '') "Имя"    , coalesce("Отчество", '') "Отчество"-- 8< --    , fio[1] "ФамилияЛица"    , fio[2] "ИмяЛица"    , fio[3] "ОтчествоЛица"-- 8< --    , "Примечание"    , "Обновлено"    , "Город"    , coalesce("ОтдельныйПрофиль", FALSE) "ОтдельныйПрофиль"    , coalesce("ЕстьКорпАккаунт", FALSE) "ЕстьКорпАккаунт"    , NULL::bigint "Всего"    , "Группа"    , coalesce(usjs[1]::text[], '{}') "Users"    , coalesce(        (usjs[2]::json[])[1]      , (usjs[3]::json[])[1]      , (usjs[4]::json[])[1]      ) "PrimaryFaceAccount"    , ((usjs[5]::json[])[1] ->> 'Account')::bigint "MainAccount"    , ARRAY(        SELECT          "Значение"::int        FROM          "КонтактныеДанные"        WHERE          p."Группа" AND-- 8< --          ("Персона", "Тип") = (p."Персона", 'account')-- 8< --      ) "АккаунтыГруппы"    , "Пол"    , "Логин"    , "ДатаРождения"    , "$Создано"::date "ДатаРегистрации"    FROM      p  ) T;-- 8< --



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

#3: Дело о развесистой клюкве



В своем докладе на конференции я говорил, что самая большая проблема, с которой приходится сталкиваться при оптимизации запросов алгоритмическая. То есть когда разработчик не заморачивается пониманием того, как конкретно БД должна/будет выполнять запрос.

Классический пример цепочка JOIN'ов, приводящая к развесистой клюкве из Nested Loop/Hash Join/Merge Join в плане. В особо клинических случаях к ней добавляется схлапывание полученной матрицы с помощью DISTINCT/GROUP BY.
Именно таким оказался запрос из последнего сегодняшнего дела:

Оригинальный запрос, 10.1мс, 11600 buffers 
SELECT DISTINCT ON (db."@ПулСерверов")  group_id."@ПулСерверов" "ИдГруппы", group_id."Название" "ИмяГруппы", CASE    WHEN group_id."Название" = 'Управление облаком' THEN      TRUE  ELSE    FALSE  END "ЭтоУправлениеОблаком", group_id."Тип" "Тип", group_id."Заблокирован" "Заблокирован", CASE    WHEN group_id."Тип" = 15 THEN      app."Код"  ELSE    group_id."Код"  END "Код", is_demo."@ПулСерверов" is not null "Демо", group_ext_id."ДопустимоеЧислоПользователей" "ДопустимоеЧислоПользователей", group_ext_id."Состояние" "Состояние", db."@ПулСерверов" "ИдБД", db_name."ИмяБД" "ИмяБД", hosts."Название" "ХостБД", db_name."Порт" "ПортБД", group_id. "Отстойник" "Отстойник", (    WITH params AS(      SELECT        cpv."Значение"      , cpv."Сайт"      FROM        "ОбщиеПараметры" cp      INNER JOIN        "ЗначенияОбщихПараметров" cpv          ON cp."@ОбщиеПараметры" = cpv."ОбщиеПараметры"      WHERE        cp."Название" = 'session_cache_time' AND        (cpv."Сайт" = 9 or cpv."Сайт" is null)    )    SELECT      coalesce(        (SELECT "Значение" FROM params WHERE "Сайт" = 9)      , (SELECT "Значение" FROM params WHERE "Сайт" IS NULL)      , (SELECT "ЗначениеПоУмолчанию" FROM "ОбщиеПараметры" WHERE "Название" = 'session_cache_time')      , 60::text      )::integer  ) "ТаймаутКэша", CASE    WHEN nullif(111, 0) IS NULL THEN      NULL    WHEN 111 = group_id."@ПулСерверов" THEN      TRUE    ELSE      FALSE  END "Эталонная", site."@Сайт" "ИдСайта", site."Адрес" "ИмяСайта"FROM  "ПулСерверов" group_idJOIN  "ПулРасширение" group_ext_id    ON group_id."@ПулСерверов" = group_ext_id."@ПулСерверов" AND NOT (group_id."@ПулСерверов" = ANY('{}'::integer[]))JOIN  "ПулСерверов" folder_db    ON group_id."@ПулСерверов" = folder_db."Раздел"JOIN  "ПулСерверов" db    ON folder_db."@ПулСерверов" = db."Раздел"LEFT JOIN  "Сервер" hosts    ON db."Сервер" = hosts."@Сервер"JOIN  "БазаДанных" db_name    ON db."@ПулСерверов" = db_name."@ПулСерверов"LEFT JOIN  (    WITH list_demo_app AS (      SELECT        ps0."ПулСерверов"      FROM        "ОбщиеПараметры" p0      INNER JOIN        "ОбщиеПараметры" p1          ON p1."Раздел" = p0."@ОбщиеПараметры" AND p0."Название" = 'Управление облаком'      INNER JOIN        "ОбщиеПараметры" p2          ON p2."Раздел" = p1."@ОбщиеПараметры" AND p1."Название" = 'Шайтан' AND p2."Название" = 'ЭтоДемонстрационнаяГруппа'      INNER JOIN        "ОбщиеПараметрыСервис" ps0          ON ps0."ОбщиеПараметры" = p2."@ОбщиеПараметры"    )    , list_demo_srv AS (      SELECT        pool1."@ПулСерверов"      FROM        list_demo_app ls      INNER JOIN        "ПулСерверов" pool0          ON ls."ПулСерверов" = pool0."@ПулСерверов"      INNER JOIN        "ПулСерверов" pool1          ON pool1."Раздел" = pool0."@ПулСерверов" AND pool1."Тип" = 15    )    SELECT      "@ПулСерверов"    FROM      list_demo_srv  ) is_demo    ON is_demo."@ПулСерверов" = group_id."@ПулСерверов"JOIN  "ПулСерверов" app    ON group_id."Раздел" = app."@ПулСерверов"LEFT JOIN  "Приложение" service    ON service."ПулСерверов" = group_id."@ПулСерверов"LEFT JOIN  "СайтПриложение" site_app    ON site_app."Приложение" = service."Раздел"LEFT JOIN  "Сайт" site    ON site."@Сайт" = site_app."Сайт"WHERE  group_id."Тип" = 15 AND  folder_db."Тип" = 8 AND  db."Тип" = 4 AND  db_name."ИмяБД" IS NOT NULL AND  (    (1 = 1 AND is_demo."@ПулСерверов" IS NOT NULL) OR    (1 = 2 AND is_demo."@ПулСерверов" IS NULL) OR    1 NOT IN (1, 2)  );


В этот раз я не буду подробно приводить запрос после каждой модификации, просто напишу мысли, которые возникли при анализе и приведу результат:

  1. В запросе используется 11 таблиц, провязанных JOIN'ами Это очень смело. Чтобы так делать безболезненно, вы должны точно знать, что после каждого шага связывания количество записей будет ограничено, буквально, единицами. Иначе рискуете получить join 1000 x 1000.
  2. Внимательно смотрим на запрос и строим понятийную модель БД. Разработчику, который это писал проще он ее и так знает, а нам придется восстановить на основе условий соединений, названий полей и бытовой логики. Вообще, если вы графически представляете, как у вас устроена БД, это может сильно помочь с написанием хорошего запроса. У меня получилось вот так:


  3. За счет DISTINCT ON(db."@ПулСерверов") мы ожидаем результат, уникализованный по записи db, в нашей схеме она вон аж в каком низу Но посмотрим на условия запроса в самом низу они из каждой сущности (group_id, folder_db, db) отсекают сверху вниз по значению типа существенные куски.
  4. Теперь самое интересное вложенный запрос, создающий выборку is_demo. Заметим, что его тело не зависит ни от чего то есть его можно смело поднять в самое начало основного WITH-блока. То есть лишнее выделение в подзапрос тут только усложняет все без какого-либо профита.
  5. Заметим, что условия is_demo."@ПулСерверов" = group_id."@ПулСерверов" и is_demo."@ПулСерверов" IS NOT NULL при LEFT JOIN этих таблиц, фактически, означает необходимость присутствия PK group_id среди идентификаторов в is_demo.

    Самое очевидное, что тут можно сделать так и переписать запрос, отбирая записи group_id по набору идентификаторов is_demo.
  6. Переписываем извлечение этих сущностей в независимые CTE, и с удивлением замечаем, что у нас на БД отсутствуют подходящие индексы по ПулСерверов(Тип, Раздел). Причем эти типы константны с точки зрения приложения, поэтому лучше триплет индексов ПулСерверов(Раздел) WHERE Тип = ....
  7. Вспомним, что пересечение нескольких CTE может быть весьма затратным, и заменим его на JOIN через словарь, предварительно сформировав его из записей group_id, folder_db и db ведь это одна исходная таблица ПулСерверов.
  8. Вложенный запрос получения параметра ТаймаутКэша просто переписываем, избавляя от ненужных CTE.

Результат: 0.4мс (в 25 раз лучше), 134 buffers (в 86 раз лучше) 
WITH demo_app AS (  SELECT    ps0."ПулСерверов"  FROM    "ОбщиеПараметры" p0  JOIN    "ОбщиеПараметры" p1      ON (p1."Раздел", p1."Название") = (p0."@ОбщиеПараметры", 'Шайтан')  JOIN    "ОбщиеПараметры" p2      ON (p2."Раздел", p2."Название") = (p1."@ОбщиеПараметры", 'ЭтоДемонстрационнаяГруппа')  JOIN    "ОбщиеПараметрыСервис" ps0      ON ps0."ОбщиеПараметры" = p2."@ОбщиеПараметры"  WHERE    p0."Название" = 'Управление облаком'), demo_srv as(  SELECT    pool1."@ПулСерверов"  FROM    demo_app ls  JOIN    "ПулСерверов" pool0      ON ls."ПулСерверов" = pool0."@ПулСерверов"  JOIN    "ПулСерверов" pool1      ON (pool1."Тип", pool1."Раздел") = (15, pool0."@ПулСерверов") -- CREATE INDEX CONCURRENTLY "iПС-tmp0-t15" ON "ПулСерверов"("Раздел") WHERE "Тип" = 15;), grp AS (  SELECT    grp  FROM    "ПулСерверов" grp  WHERE    "Тип" = 15 AND    "@ПулСерверов" = ANY(ARRAY(      SELECT        "@ПулСерверов"      FROM        demo_srv    ))), fld AS (  SELECT    fld  FROM    "ПулСерверов" fld  WHERE    "Раздел" = ANY(ARRAY(      SELECT        (grp)."@ПулСерверов"      FROM        grp    )) AND    "Тип" = 8 -- CREATE INDEX CONCURRENTLY "iПС-tmp0-t8" ON "ПулСерверов"("Раздел") WHERE "Тип" = 8;), dbs AS (  SELECT    dbs  FROM    "ПулСерверов" dbs  WHERE    "Раздел" = ANY(ARRAY(      SELECT        (fld)."@ПулСерверов"      FROM        fld    )) AND    "Тип" = 4 -- CREATE INDEX CONCURRENTLY "iПС-tmp0-t4" ON "ПулСерверов"("Раздел") WHERE "Тип" = 4;), srvhs AS (  SELECT    hstore(      array_agg((dbs)."@ПулСерверов"::text)    , array_agg((dbs)::text)    )  FROM    (      TABLE dbs    UNION ALL      TABLE fld    UNION ALL      TABLE grp    ) T)SELECT  (grp)."@ПулСерверов" "ИдГруппы", (grp)."Название" "ИмяГруппы", (grp)."Название" IS NOT DISTINCT FROM 'Управление облаком' "ЭтоУправлениеОблаком", (grp)."Тип", (grp)."Заблокирован", CASE    WHEN (grp)."Тип" = 15 THEN      app."Код"    ELSE      (grp)."Код"  END "Код", TRUE "Демо", grpe."ДопустимоеЧислоПользователей", grpe."Состояние", (dbn)."@ПулСерверов" "ИдБД", dbn."ИмяБД", dbh."Название" "ХостБД", dbn."Порт" "ПортБД", (grp)."Отстойник", (    SELECT      coalesce(        (          SELECT            "Значение"          FROM            "ЗначенияОбщихПараметров"          WHERE            "ОбщиеПараметры" = cp."@ОбщиеПараметры" AND            coalesce("Сайт", 9) = 9          ORDER BY            "Сайт" NULLS LAST          LIMIT 1        )      , "ЗначениеПоУмолчанию"      , '60'      )::integer    FROM      "ОбщиеПараметры" cp    WHERE      "Название" = 'session_cache_time'  ) "ТаймаутКэша", CASE    WHEN nullif(111, 0) IS NULL THEN      NULL    WHEN (grp)."@ПулСерверов" = 111 THEN      TRUE    ELSE      FALSE  END "Эталонная", site."@Сайт" "ИдСайта", site."Адрес" "ИмяСайта"--, *FROM  dbsJOIN  "БазаДанных" dbn    ON dbn."@ПулСерверов" = (dbs.dbs)."@ПулСерверов"JOIN LATERAL  (    SELECT      ((TABLE srvhs)->((dbs)."Раздел"::text))::"ПулСерверов" fld  ) fld ON TRUEJOIN LATERAL  (    SELECT      ((TABLE srvhs)->((fld)."Раздел"::text))::"ПулСерверов" grp  ) grp ON TRUEJOIN  "ПулРасширение" grpe    ON grpe."@ПулСерверов" = (grp)."@ПулСерверов"JOIN  "ПулСерверов" app    ON app."@ПулСерверов" = (grp)."Раздел"JOIN  "Сервер" dbh    ON dbh."@Сервер" = (dbs)."Сервер"LEFT JOIN  "Приложение" srv    ON srv."ПулСерверов" = (grp)."@ПулСерверов"LEFT JOIN  "СайтПриложение" site_app    ON site_app."Приложение" = srv."Раздел"LEFT JOIN  "Сайт" site    ON site."@Сайт" = site_app."Сайт"WHERE  dbn."ИмяБД" IS NOT NULL;



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

PostgreSQL Antipatterns:


SQL HowTo:

Подробнее..
Категории: Postgresql , Sql , Администрирование баз данных , Блог компании тензор , Sql tips and tricks , Реверс-инжиниринг , Array , Unnest , Distinct , Lateral , Иерархия , Json_build_object

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru