PGConf.NN — конференция по PostgreSQL в Нижнем Новгороде

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

ZSON

Вот запилил ты вторую нормальную форму, все круто. Только запрос работает минутами на продакшн объемах.

Вот ты запилил объектную, а оно работает часами вместо минут.

Давай подождем, что человек скажет на тему представления иерархически структурированных данных в РСУБД. Если я правильно понимаю, он вообще считает «документный формат» ошибкой дизайна.

Угу. Давай поговорим про представление иерархически структурированных данных в РСУБД и связанные с этим накладные расходы.

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

Иерархическую структуру можно представить так, что будет возможно и быстрая вставка в середину, и быстрый поиск нужного поля, и какое-нить индексирование. Но для этого это представление должно быть с произвольным доступом. Так же как РСУБД может обращаться к нужной строке, не просматривая всю таблицу от начала, так и тут нужно уметь сразу обратиться к нужному полю. Если у нас вся структура сериализована в строку, которую читать, кроме как последовательно, нельзя, то это всё не получится. Опять тогда вопрос, зачем оно надо в таком виде?

Уточню: на всё это надо смотреть не в каком-то абстрактном ключе «нам пришёл запрос на получение поля 'var1' из сериализованной структуры в колонке 'data' строки по условию WHERE», а с учётом того, зачем это нужно клиентскому приложению. Потому что запрос выше, в большой вероятностью, можно переделать в «получить колонку 'datavar1'». Если нельзя - почему нельзя? В ответе на этот вопрос будет крыться ещё какая-то проблема, сводящая пользу от этих конструкций к чему-то маленькому.

Смысла нет. Раньше 16 байт делали, но сейчас для SIMD и 8 достаточно.

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

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

А уж вычислять оффсет по распарсенному json-у то какая быстрая.

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

В смысле «представить»? В голове? Для примера возьми любое описание pod из кубернетеса: есть массивы, есть куча вложенных объектов. И запрсти это в бинарном виде, в который ещё и в середину вставлять быстро.

Я серьезно. Я не могу представить даже в голове.

А потом моя работа стала вообще связана с ETL

Пошел гуглить акроним. Вспомнил молодость, когда с green plum в космос мигрировали…

А ты постарайся. С идеологией «все сериализовано в строку» конечно не выйдет, но отойди от неё.

Ты не туда полез. Давай сузим задачу. Представление деревьев (а к ним сводятся и JSON, и XML) в реляционных БД.

Я подаю тебе это в виде вопроса, потому, что ты потрудился расписать, как может выглядеть компактное представление JSON-а. Попробуй представить, как мы можем хранить деревья в РСУБД. И там всё должно стать ясно, почему мы используем документы для представления иерархических данных, а не деревья. И почему вообще такой отдельный класс БД (документ-ориентированные) появился.

Это про гонять данные между различными источниками-приемниками с попутной обработкой).

Чаще всего это извлечение, предобработка и закачивание в какую-нибудь аналитическую БД типа Druid или того же green plum.

Документ и так уже не «реляционная БД», поэтому рамок можно считать нет.

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

{"var1":3,"var5":{"a":64,"b":5},"var7":7}

Если «дерево» состоит из нескольких элементов - то пофиг как оно реализовано, и так и так будет быстрым

Ну вот в этом твоя ошибка. Нет, оно не будет быстрым. Если ты реализуешь дерево через ссылки parent/child, то у тебя O(Log N) для обращения к потомку через предка. В сочетании с другим обычным оверхедом РСУБД, это делает выборку поддерева очень долгой, так как нельзя всех потомков выбрать одним запросом.

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

Хранение дерева в виде текстового или бинарного документа — разновидность диапазонного метода. И, в частности, дает возможность извлекать всё дерево или поддерево не просто «одним запросом», а именно что очень быстро. В текстовом представлении под-деревья (что json, что xml) всегда представлены связным диапазоном адресов в документе. Формат-то может быть и тупой, но, таки, весьма важный.

Поскольку такие быстрые деревья статичны, то есть обновляемы только целиком, а не частями, то есть верхний предел на размер «документа». В Монге это, емнип, 16МБ. В PG — не знаю. И большие деревья должны вручную разбиваться на маленькие фрагменты, которые уже явно или неявно связываются, например, через parent/child. Или с помощью графа, или еще как, если это надо.

Вот такая простая математика.

Ну, им удалось как ускорить большинство операций на чтение, так и сделать возможным in-place update (если при этом не меняется размер чанка в тосте).

В сочетании с другим обычным оверхедом РСУБД, это делает выборку поддерева очень долгой, так как нельзя всех потомков выбрать одним запросом.

Вы мало что знаете о проектировании архитектур tree.
А они могут быть весьма разные …

Хранение дерева в виде текстового или бинарного документа — разновидность диапазонного метода.

Ну что за фантазии?
Эшо раз.

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

Вовка, так а я про что? Всё зависит от задачи. Но таки у нас или возможность выбирать под-дерево одним линейным сканированием диапазона адресов и статичное дерево, или динамическое дерево и необходимость явно бегать по parent/child. Даже если последнее на уровне SQL реализовано одним иерархическим запросом, «внизу» оно раскрывается в traversal, который над b-tree будет медленнее на 2-3 порядка, чем могло бы быть.

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

Тут надо смотреть, что ты называешь in-place update. Если мы для обновления документа можем переиспользовать storage без его перевыделения, то это одно. А вот если мы можем, например, в 100МБ-ный документ вставить поддерево за пару микросекунд так, что в итоге в БД запишется десяток страниц, то это совсем другое.

Для последнего есть амортизированные схемы, когда дерево хранится в а-ля куче/арене, в которой есть свободное место для новых элементов. в момент исчерпания места в этой куче будет певыделение storage (размера x2) для документа со сборкой мусора. Цена вопроса — нужно выделять больше места под документы, чем это реально необходимо. Асимптотика примерно такая же, как и для вставки в конец вектора.

Не знаю, это ли собираются реализовать в PG, и могут ли вообще.

Если мы для обновления документа можем переиспользовать storage без его перевыделения, то это одно. А вот если мы можем, например, в 100МБ-ный документ вставить поддерево за пару микросекунд так, что в итоге в БД запишется десяток страниц, то это совсем другое.

Про первое, естественно. Второе реализовать при текущей схеме хранения жсон вряд ли получится. Хотя есть разговары про datatype-aware тосты…

… b-tree

Иногда и b-tree приемлемо, а иногда нет …
Эффективное представление tree в memory и в файле весьма различно.
Хотя те кто этого не понимают будут всегда «лечить» решение задачи

стаканом КАСТОРКИ ...

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

Так мы про файл и говорим. Про обычную дисковую РСУБД.

С памятью, кстати, всё то же самое. Только масштаб задержек другой относительно диска. Но и требования к таким БД совсем другие.

Только масштаб задержек другой относительно диска. Но и требования к таким БД совсем другие.

Железо ныне весьма эффективно и покрывает изъяны алгоритмов.
Безусловно «шлифование» алгоритмов для работы /особенно с файлами/ нужно вести на больших объемах данных …

Все "как обычно" ...

Ну вот в этом твоя ошибка. Нет, оно не будет быстрым.

Кажется неправильно понят, в этом утверждении. Речь была о том, с одной стороны, что при N=5, допустим, что O(1), что

O(Log N)

, что O(N^2) - всё будет одинаково легко (потому что N маленькое). А, с другой, для N=5 это в любой случае неактуально, потому что такие объёмы - это не то, для чего требуется спецдвижок. Поэтому этот случай я просто не рассматривал, и рассматривал что-то вроде N=100 хотя бы.

Если ты реализуешь дерево через ссылки parent/child, то у тебя O(Log N) для обращения к потомку через предка.

Не понял почему O(Log N) и в любом случае для линейной строки всё ещё хуже.

В сочетании с другим обычным оверхедом РСУБД ... нельзя всех потомков выбрать одним запросом.

А мы и не говорим про реализацию дерева поверх РСУБД, мы говорим про реализацию дерева в ядре сервера базы данных, для доступа к нему из SQL-запросов каким-то спец. синтаксисом. Реализация разумеется на основе raw-доступа к файлам с данными некоего нового формата (не обычные таблицы).

В текстовом представлении под-деревья (что json, что xml) всегда представлены связным диапазоном адресов в документе.

Только чтобы узнать этот самый диапазон, надо посмотреть в среднем половину всего дампа. O(N*L), и N тут - количество записей, средняя длина одного поля в байтах, а вот для структурированного дерева будет O(log N) (потому как поля читать не надо). Минус в том что доступ в итоге будет фрагментированным, но при достаточно больших N это уже маловажно.

И большие деревья должны вручную разбиваться на маленькие фрагменты

Нет, не вручную. Такие оптимизации это как раз первоочередная задача движка. По аналогии могу предложить выкинуть оптимизатор SQL запросов и сказать «клиент должен вручную рассказывать базе в каком порядке и какими индексами пользоваться для выполнения запроса, да и сами индексы поддерживать тоже самостоятельно».

Да, для совсем маленьких деревьев будет быстрее прочитать их целиком, одной операцией, в кеш проца и там уже разбирать. Для больших - нужно parent-child. Для ещё более больших - нужны хеш-таблицы для списков child-ов parent'а. Разобраться где что нужно для оптимальной работы должен сервер, а не программист клиента.

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

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

Разные реализации могут быть.
В основном память для выделяемая для tree является списком блоков памяти … … …

Разные реализации могут быть ...

жду твоих апатчей в постргес

Безусловно «шлифование» алгоритмов для работы /особенно с файлами/ нужно вести на больших объемах данных …

Пожалуй все же пока за свое API могу сказать, что оно вроде на объемах 2 GB шустро работает.
Но буду «шлифовать» алгоритмы и архитектуру пока до планки 50GB.
Так что считаю, что у меня пока лишь что-то разработано …

Утешение одно - это не МАНИЛОВЩИНА ...

Ну, вот, я, как мог, объяснил тебе теоретически, в чем трудность. Дальше я рекомендую тебе просто побенчмаркать parent/child в PG или в MySQL.

Создай таблицу, навесь необходимые индексы, нагенери данных так, чтобы было в несколько раз больше объема RAM (нормальный режим для СУБД).

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

А про «легковесные ФС» забудь. Тебе надо с внешней памятью работать отказоустойчиво. Это либо журнал, либо WAL, либо CoW. И блочный уровень обмена данными с устройством.

Создай таблицу, навесь необходимые индексы

Я же писал уже несколько раз - речь не про дерево поверх таблицы (это понятно что будет оверхед), а про дерево как самостоятельную структуру данных. Для этого надо писать много кода, да, дополнительный движок считай с нуля, просто особенным типом данных в таблице не отделаешься. Это всё долго и сложно, но это минимум, при котором можно будет сказать «мы добавили поддержку иерархического представления информации». А пока что это - «тяп-ляп, у нас (у тех кто будет базой пользоваться) кодеры любят json, так давайте его и в базу засунем, чтоб ничего не переделывать и она сама из него поля доставала». Ну да, в качестве ускорителя для приложения с уже плохим дизайном это сработает, но в нормальной ситуации это и возникать не должно.

нагенери данных так, чтобы было в несколько раз больше объема RAM (нормальный режим для СУБД). И посмотри, сколько будет длиться выборка достаточно большого поддерева и сколько — вставка.

Опять - попробуй сделать выборку маленького поддерева из сериализованного в json дерева в несколько раз больше RAM, если ему не повезёт (ну как, вероятность 50%) оказаться ближе к концу дампа, чем к началу. Про вставку чего угодно (в начало) уж и говорить не приходится.

Это всё долго и сложно, но это минимум, при котором можно будет сказать «мы добавили поддержку иерархического представления информации».

Это не просто «долго и сложно». Тут еще нужно втиснуться в кучу дополнительных требований, необходимых для поддержки транзакционности и отказоустойчивости. И поверь мне на слово, b-tree используют вовсе не от лени. Это очень хорошая, универсальная, структура данных для внешней памяти. Есть и получше, но они лучше далеко не всегда и не во всем.

Опять - попробуй сделать выборку маленького поддерева из сериализованного в json дерева в несколько раз больше RAM,

А в чем проблема? Нужно правильно выбирать формат сериализации. Сериализуешь json/xml в виде DFUDS-дерева. По нему можно не только эффективную навигацию делать, но оно еще и subtree полностью поддерживает.

Можно взять LOUDS, оно примерно такое же, но subtree там менее эффективный. Зато, в отличие от DFUDS и BP, LOUDS-дерево — динамическое. Можно вставку/удаление делать при условии наличия динамического битового вектора с поддержкой rank/select.

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

Есть в НиНо достаточно крупное и известное на всю страну предприятие, где уже второй или третий год внедряют ERP на PG. Интересно, разработчики этой системы будут на этом сходняке или нет. По слухам, система изначально была сделана на MS SQL + Delphi, и работала на многих предприятиях по всей стране. Но заказчик был очарован импортозамещением и потребовал PG. Разрабочики сказали - yes, и переписали систему на PG + scala.