- PVSM.RU - https://www.pvsm.ru -
Часто в таблицах содержится большое количество логических полей, проиндексировать все из них нет возможности, да и эффективность такой индексации низка. Тем не менее, для работы с произвольными логическими выражениями в SQL пригоден механизм многомерной индексации о чем и пойдёт речь под катом.
В SQL логические поля используются в основном в двух случаях. Во-первых, когда действительно нужен бинарный атрибут, например, ‘купля/продажа’ в таблице сделок. Такие атрибуты редко меняются со временем.
Во-вторых, для записи состояния конечного автомата [1], которым описывается запись. Имеется в виду, что логический объект, соответствующий записи таблицы, проходит ряд состояний, число которых и переходы между которыми определяются прикладной логикой. Простой пример — техника “soft-delete”, когда запись физически не уничтожается, а только помечается как удалённая.
Если автомат сложный, таких полей может быть изрядное количество, в одной из наших [2] таблиц 58 (+14 устаревших) таких полей (включая наборы флагов) и это не что-то из ряда вон выходящее. Так не было задумано изначально, но по мере развития продукта и изменения внешних требований развиваются и соответствующие автоматы, приходят и уходят разработчики, меняются аналитики… в какой-то момент может оказаться безопаснее завести новый флаг, нежели разбираться во всех хитросплетениях. Тем более что накопились исторические данные и их состояния обязаны оставаться адекватными.
Завести флаг означает не только добавить поле соответствующего типа, но и учесть его в работе автомата, какие состояния оно затрагивает, в каких переходах участвует. На практике это выглядит так:
Для того чтобы выбрать записи, находящиеся в конкретном состоянии, редко когда достаточно фильтрации по одному из булевых полей. Обычно это целое выражение, иногда нетривиальное. Казалось бы, надо проиндексировать эти поля и SQL-процессор сам разберётся. Но не всё так просто.
Во первых, булевых полей может быть много, индексировать их все было бы слишком расточительно.
Во вторых, это может оказаться бесполезным т.к. селективность по каждому из полей будет низкой, а совместная вероятность статистикой SQL-процессора не покрывается.
Пусть, в таблице T1 есть два булевых поля: F1 & F2, а запрос
select F1, F2, count(1) from T1 group by F1, F2
выдаёт
F1 | F2 | COUNT |
---|---|---|
false | false | 499 |
false | true | 1 |
true | false | 1 |
true | true | 499 |
Т.е. хотя, по F1 & F2 выпадение true и false равновероятно, сочетание (true,false) выпадает только один раз из тысячи. В результате, если раздельно проиндексировать F1 & F2 и принудить использовать эти индексы в запросе, SQL-процессору пришлось бы прочитать по половине обоих индексов и пересечь результаты. Возможно, дешевле прочитать всю таблицу и вычислить выражение для каждой строчки.
И даже если собирать статистику по исполненным запросам, толку от нее будет мало т.к. статистика конкретно по полям, отвечающим за состояние автомата очень сильно плавает. Ведь в любой момент может прийти “обработчик” и половину строк из состояния S1 перевести в S2.
Для работы с такими выражениями напрашивается многомерный индекс, алгоритм которого был представлен ранее [4] и неплохо себя зарекомендовал.
Но прежде требуется разобраться каким образом произвольное логическое выражение превратится в запрос(ы) к индексу.
Единичный запрос к многомерному индексу представляет собой многомерный прямоугольник, ограничивающий пространство запроса. Если поле участвует в запросе, для него задаётся ограничение. Если нет, прямоугольник по этой координате ограничен только разрядностью данной координаты. Логические координаты имеют разрядность 1.
Поисковый запрос в таком индексе является цепочкой из & (конъюнкцией), например, выражение: v1 & v2 & v3 & (!v4), эквивалентно v1:[1,1], v2:[1,1], v3:[1,1], v4:[0,0]. А все остальные поля имеют диапазон: [0,1].
Учитывая это, наш взор сразу обращается в сторону ДНФ [5] — одной из канонических форм логических выражений. Утверждается, что любое выражение может быть представлено к виду дизъюнкции конъюнкций литералов. Под литералом здесь понимается логическое поле или его отрицание.
Иными словами, путём нехитрых манипуляций, любое логическое выражение может быть представлено в виде дизъюнкции нескольких запросов к многомерному логическому индексу.
Есть и одно НО. Такое преобразование в некоторых случаях может привести к экспоненциальному росту размера выражения. Например, преобразование из приводит к выражению размером в 2**n термов. В таких случаях прикладному разработчику стоит задуматься о физическом смысле того, что он делает, а со стороны SQL процессора всегда можно отказаться от использования логического индекса, если число конъюнкций превышает пределы разумного.
Для многомерной индексации используются свойства самоподобной нумерующей кривой на основе гипер-кубических симплексов со стороной 2. Как оказалось [4], практическое значение имеют два варианта таких кривых — Z-кривая и кривая Гильберта.
Фиг.1 двумерная Z-кривая, 3 и 6 итерации
Фиг.2 двумерная кривая Гильберта, 3 и 6 итерации
Вот как это работает на практике:
Фиг.3 Пример поиска в двумерном индексе (Z-кривая)
На фиг.3 показано разбиение исходного поискового экстента на подзапросы и найденные при этом точки. Использовался двумерный индекс, построенный на случайном равномерно распределенном наборе 100 000 000 точек в экстенте [1 000 000, 1 000 000].
Раз уж речь зашла о многомерном индексировании, самое время задуматься, а насколько многомерным он может быть? Есть ли какие-то объективные ограничения?
Конечно, ведь B-дерево имеет страничную организацию и для того, чтобы быть деревом, на странице должно гарантированно помещаться не менее двух элементов. Если принять страницу за 8К, значит на хранение одного элемента не может уходить больше 4К. В 4К без сжатия влезает около 1000 32-разрядных значений. Это довольно много, выше пределов любого разумного применения, можно сказать, что физические пределы практически не доступны.
Есть и другая сторона, каждое дополнительное измерение отнюдь не бесплатно, на него уходит дисковое пространство и замедляется работа. С точки зрения “физического смысла”, в один индекс должны попадать поля, которые меняются одновременно и поиск по ним тоже идёт совместно. Никакого смысла индексировать всё подряд нет.
С логическими полями всё по другому. Как мы видели, в одних и тех же механизмах могут быть задействованы десятки логических полей. А затраты на хранение/чтение довольно малы. Есть соблазн собрать всё без исключения логические поля в одном индексе и посмотреть что получится.
Правда, есть нюансы:
Ожидается, что логический многомерный индекс может в некоторых случаях работать не слишком эффективно. Строго говоря, любой индекс может работать неэффективно, если слишком большое количество данных попадает в область поиска. Но для логического многомерного индекса это усугубляется описанной выше зависимостью от порядка полей, когда ради небольшого результата придётся прочитать весь индекс. Насколько это является проблемой на практике, может показать только эксперимент.
Построение индекса:
Поиск:
Итак,
Фиг.4 Результаты, число прочитанных страниц в разных сериях
По Y — отложены количества прочитанных страниц.
По X — сдвиг полос от самого младшего (48) разряда к старшему. Полосы разной ширины подписаны и отмечены разными цветами.
Фиг.5 Те же данные что и Фиг.4, другое представление
По X — сдвиг полосы
По Y — ширина полосы
что следует отметить:
В целом можно признать алгоритм многомерной индексации работоспособным даже в таком доведенном до абсурда случае. А ведь рассматривается самый неудачный с точки зрения логического индекса вариант — равновероятные состояния по всем независимым логическим полям.
Таблица Trades, всего 278 479 918 строк, данные одного из тестовых контуров.
Результаты выполнения некоторых запросов в таблице ниже:
N | Запрос | Число строк в результате | Прочитано страниц |
---|---|---|---|
1 | IsProcessed==0 && NullStatus==0 | 6 273 | 9 |
2 | IsProcessed==0 && NullStatus==0 && IsCoverage==0 | 6 273 | 9 |
3 | IsCoverage==1 && QF_ICEBERG==1 | 1 388 128 | 386 |
4 | PutStatus==1 && PayStatus == 0 | 61 788 376 | 16 486 |
5 | IsProcessed==1 && NullStatus==0 && QF_CURR_PFI==0 && QF_TERMINATION==0 |
278 473 645 | 74 285 |
6 | IsProcessed==1 && PutStatus==0 && IsCoverage==1 |
1 650 240 | 447 |
7 | QF_UNK3==0 && QF_UNK4==0 | 23 392 | 19 |
На чтение/обработку одной страницы в среднем уходит 0.8 мсек.
Нет необходимости описывать смысл конкретных запросов, они здесь просто для демонстрации работоспособности. Которая, кстати, подтверждена.
Но прежде чем данная техника сможет принести практическую пользу, предстоит еще очень много сделать. Так что, продолжение следует.
Автор: Борис Муратшин
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/342501
Ссылки в тексте:
[1] конечного автомата: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82
[2] наших: https://arqatech.com/ru/products/qort/
[3] великих вымираний: https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B5_%D0%B2%D1%8B%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B8%D0%B5
[4] представлен ранее: https://habr.com/post/464057/
[5] ДНФ: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B7%D1%8A%D1%8E%D0%BD%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BD%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0
[6] Источник: https://habr.com/ru/post/483056/?utm_source=habrahabr&utm_medium=rss&utm_campaign=483056
Нажмите здесь для печати.