Логические поля в базах данных, есть ли противоядие


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

    В SQL логические поля используются в основном в двух случаях. Во-первых, когда действительно нужен бинарный атрибут, например, ‘купля/продажа’ в таблице сделок. Такие атрибуты редко меняются со временем.

    Во-вторых, для записи состояния конечного автомата, которым описывается запись. Имеется в виду, что логический объект, соответствующий записи таблицы, проходит ряд состояний, число которых и переходы между которыми определяются прикладной логикой. Простой пример — техника “soft-delete”, когда запись физически не уничтожается, а только помечается как удалённая.

    Если автомат сложный, таких полей может быть изрядное количество, в одной из наших таблиц 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.

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

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

    Дизъюнктивная нормальная форма


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

    Поисковый запрос в таком индексе является цепочкой из & (конъюнкцией), например, выражение: v1 & v2 & v3 & (!v4), эквивалентно v1:[1,1], v2:[1,1], v3:[1,1], v4:[0,0]. А все остальные поля имеют диапазон: [0,1].

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

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

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



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

    Алгоритм многомерной индексации


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

    image
    Фиг.1 двумерная Z-кривая, 3 и 6 итерации

    image
    Фиг.2 двумерная кривая Гильберта, 3 и 6 итерации

    • N-мерный симплекс со стороной 2 имеет 2**n вершин и (2**n-1) переходов между ними.
    • Элементарная итерация симплекса превращает каждую вершину симплекса в симплекс нижнего уровня.
    • Проделав нужное число итераций, можно построить гипер-кубическую решетку любого размера.
    • При этом каждый узел этой решетки будет иметь свой уникальный номер — путь, проделанный по нумерующей кривой от ее начала. При этом каждый узел этой решетки имеет значение по каждой из координат. Фактически, нумерующая кривая переводит многомерную точку в одномерное значение, пригодное для индексации обычным B-деревом.
    • Все узлы, находящиеся внутри симплекса любого уровня, находятся в пределах одного интервала и этот интервал не пересекается ни с одним симплексом того же уровня.
    • Следовательно, любой поисковый прямоугольник (параллелепипед) может быть разбит на небольшое число гипер-кубических подзапросов, в пределах каждого из которых индекс может быть прочитан одним поиском/траверзом.
    • К этому добавим магию низкоуровневой работы с B-деревом для того, чтобы не делать бесполезные запросы и … алгоритм готов.

    Вот как это работает на практике:


    Фиг.3 Пример поиска в двумерном индексе (Z-кривая)

    На фиг.3 показано разбиение исходного поискового экстента на подзапросы и найденные при этом точки. Использовался двумерный индекс, построенный на случайном равномерно распределенном наборе 100 000 000 точек в экстенте [1 000 000, 1 000 000].

    Логический многомерный индекс


    Раз уж речь зашла о многомерном индексировании, самое время задуматься, а насколько многомерным он может быть? Есть ли какие-то объективные ограничения?

    Конечно, ведь B-дерево имеет страничную организацию и для того, чтобы быть деревом, на странице должно гарантированно помещаться не менее двух элементов. Если принять страницу за 8К, значит на хранение одного элемента не может уходить больше 4К. В 4К без сжатия влезает около 1000 32-разрядных значений. Это довольно много, выше пределов любого разумного применения, можно сказать, что физические пределы практически не доступны.

    Есть и другая сторона, каждое дополнительное измерение отнюдь не бесплатно, на него уходит дисковое пространство и замедляется работа. С точки зрения “физического смысла”, в один индекс должны попадать поля, которые меняются одновременно и поиск по ним тоже идёт совместно. Никакого смысла индексировать всё подряд нет.

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

    Правда, есть нюансы:

    • До сих пор в индексируемом значении разряды разных координат перемешивались, в младших разрядах ключа оказывались младшие разряды координат … Поэтому порядок следования полей при индексации не имел значения.
    • Теперь же на хранение значения одного логического поля тратится один разряд. Т.е. какие-то логические поля попадут в конец ключа, а какие-то в начало. А это означает, что фильтрация по части полей будет проходить очень эффективно, а по некоторым очень неэффективно. В самом деле, если мы делаем поиск по самому младшему разряду, придётся прочитать весь индекс чтобы получить ответ. Но это (скорее всего) лучше, чем прочитать всю таблицу, чтобы ответить на тот же вопрос.
    • Возникает проблема выбора — все логические поля равны, но некоторые окажутся равнее прочих. Из общих соображений, необходимо смотреть на перекосы статистики, чем сильнее соотношение true/false для конкретного поля отстоит от равновесного, тем старше должен быть разряд, в котором окажется его значение.
    • Исчезает разбиение по типу нумерующей кривой, если раньше приходилось выбирать между Z-кривой и кривой Гильберта, на одноразрядных данных практической разницы нет.
    • NULL-ы. Если исходить из того, что NULL — это не неизвестное значение, а отсутствие какого бы то ни было значения, то такие записи не должны попадать в индекс. В одномерных индексах так и происходит. Но в нашем случае может оказаться, что часть логических полей содержит значения, а часть нет. В результате мы не можем положить это в индекс т.к. алгоритм поиска не умеет работать с троичной логикой. А следовательно, такие записи должно быть невозможно вставить в таблицу (при наличии многомерного индекса, необязательно логического, кстати)

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

    Численный эксперимент


    Построение индекса:

    • индекс будет 128-разрядным, т.е. построен по 128 логическим полям
    • и будет содержать 2**30 элементов
    • значением элемента индекса будет число от 0 до 2**30
    • ключом элемента индекса будет то же число, сдвинутое на 48 разрядов влево, т.е. логические поля с 48 по 78 будут заполнены разрядами числа в том же порядке
    • в результате получим 30 значимых логических полей в середине ключа, остальные разряды будут заполнены 0
    • Каждое из логических полей имеет равную статистику true/false
    • Все они статистически независимы

    Поиск:

    • Каждому эксперименту соответствует выбор нескольких подряд идущих логических полей и задание для них поисковых значений. Не потому, что алгоритм умеет искать только полосами, а из-за того, что так можно нагляднее представить результаты эксперимента, имеем всего две размерности — ширина полосы и её положение
    • Всего 24 серии экспериментов. В каждой серии будем искать такие значения, где полоса логических полей соответствующей ширины N (от 1 до 24 разрядов) принимает значение true.
    • В каждой серии будет подсерия экспериментов, в которой полоса логических полей выбранной ширины располагается с различными сдвигами S от начала полосы в 30 значимых логических полей. Всего (30-N) экспериментов в подсерии.
    • В каждом эксперименте делается поиск всех элементов индекса, удовлетворяющих условию, т.е. поля с номерами в интервале [48 + S, 48 + S + N -1] будем искать в интервале [1,1], остальные — в интервале [0,1]
    • Поиск делается с холодного старта
    • Результатом является число прочитанных дисковых страниц, с учетом кэширования (кэш на 4096 страниц)
    • Контроль правильности работы делается двумя путями — число найденных элементов должно быть равно 2**(30-N) и в найденных значениях можно проверить соответствующие разряды

    Итак,


    Фиг.4 Результаты, число прочитанных страниц в разных сериях

    По Y — отложены количества прочитанных страниц.
    По X — сдвиг полос от самого младшего (48) разряда к старшему. Полосы разной ширины подписаны и отмечены разными цветами.


    Фиг.5 Те же данные что и Фиг.4, другое представление

    По X — сдвиг полосы
    По Y — ширина полосы

    Что следует отметить:

    • хотя на картинках это прямо не видно, индекс работает правильно, это видно и по числу найденных элементов и по содержанию самих элементов
    • все полосы шириной не больше 10 со сдвигом 0 требуют сплошного чтения индекса
    • полосы шириной от 1 до 18 с ростом сдвига выходят на асимптоту 2**(-N) от размера всего индекса, что логично
    • для более широких полос асимптота — высота дерева, меньше неё чтений быть не может
    • на листовой странице индекса помещается чуть больше 1000 элементов, это видно по полосе шириной 10, которая при сдвиге 0 уже не требует чтения всего индекса, некоторые страницы удаётся пропускать
    • низкоуровневая фильтрация работает на удивление хорошо. Рассмотрим полосу шириной 10. Идеальный для поиска вариант — со сдвигом 20 (всего 30 значимых полей), когда в префиксе вообще нет неопределенных полей, данные можно найти единственным траверзом. В этой ситуации при поиске читается примерно 1/1000 индекса — 779 страниц.
      Промежуточный случай — сдвиг 10, у нас префикс и суффикс в 10 неизвестных полей. Число страниц — 2484, всего втрое хуже, чем в идеальном случае.
      И даже в худшем случае со сдвигом в 0 (префикс в 20 неизвестных полей) удаётся пропускать какие-то страницы.

    В целом можно признать алгоритм многомерной индексации работоспособным даже в таком доведенном до абсурда случае. А ведь рассматривается самый неудачный с точки зрения логического индекса вариант — равновероятные состояния по всем независимым логическим полям.

    Эксперимент на реальных данных


    Таблица 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 мсек.

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

    Но прежде чем данная техника сможет принести практическую пользу, предстоит еще очень много сделать. Так что, продолжение следует.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 28

      +3

      Вы так круто всё это развернули. Я даже не сразу понял, что речь идет о банальной битовой маске. Ближе нужно к народу-то быть )

        0
        На всё в IT можно смотреть как на банальную последовательность нулей и единиц.
        Вот конкретно эта маска с другой стороны является индексом (что само по себе и не ново).
        Интерес представляет скорее алгоритм поиска, который оказался применим к такой маске и умеет эффективно пропускать бесполезные данные и не пропускать полезные.
          +4

          я думаю, что речь про то, что из заголовка непонятно, что статья про true/false.
          во всяком случае я (почему-то) подумал, что речь про вычисляемые поля и долго не мог "въехать".


          быть может, удачнее было бы назвать "Логические поля (boolean) в базах данных, ..."?


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

            0
            Вообще, под эту категорию попадают не только boolean, но и числовые маски и символьные поля (Ex: IsProcessed='y').

            Да речь идёт о собственном движке с индексами, но в данном случае это не важно.
            Алгоритм общечеловеческий и его реализация была опубликована как расширение к PGSQL (отсюда и слон на заставке).
              +2

              Да речь идёт о собственном движке с индексами, но в данном случае это не важно.


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

                0
                Пожалуй, учту в дальнейшем.
            +4

            Да не, я без претензий, и плюс материалу поставил. Просто есть устоявшееся выражение "битовая маска", которое более менее описывает, что здесь происходит. Но за весь текст оно не встречается ни разу. Только это и вызвало такой диссонанс. А походу текста складывается впечатление, что это рокет-сайнс какой-то )
            Плюс, не хватает немножко практического sql, сравнения непосредственно с битовой маской (если бы мы сразу хранили все значения в маске) и фильтрацией по a^b. Ну это на заметку если вы хотите следующий материал по этой же теме писать.

              +2
              Сравнение с MSSQL таково:
              — запрос №3 (только count) MSSQL выполняет около 5 минут (с холодного старта и полчаса потянет)
              — сплошное чтение маски (эквивалентное запросу №5) занимает около минуты
              — запрос №3 через битовый индекс выполняется ~300 мсек
                +1

                Отлично, ждем следующего материала.

            0
            Разница в производительности в 200 раз (300мсек VS 60сек пример выше)
            делает эту «битовую маску» не такой уж и банальной
            0

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


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

              +1
              Ну, строго говоря, не пара битов, а в 8 раз.
              Иногда за счет выравнивания лишний разряд может потянуть за собой и 4 и 8 байт.
              А, например для синхронизации большого к-ва объектов, выгодно работать с общей битовой маской.
              0
              Если исходить из того, что NULL — это не неизвестное значение, а отсутствие какого бы то ни было значения, то такие записи не должны попадать в индекс.


              Что-то сомневаюсь, что в индексе нет места для NULL. Как тогда работает «select ....where field is null»?
                0
                Почему вы решили, что этот запрос использует индекс?
                Почему нельзя проиндексировать факт «field is null»?
                Какой физический смысл в индексации NULL-ов вместе с данными?
                  0
                  Я ничего не решил, просто спросил.
                  Есть логика конечного потребителя и ему надо, чтобы работало быстро
                    0
                    тогда пункт 2 — индексируем факт null|not null
                      +2
                      Походу да! Проверил план запроса на оракле. Поле имеет одномерный индекс.

                      «select… where field is null» — table full scan
                      «select… where field > 123» — index used
                        0
                        все таки есть способ включить null в индекс
                        www.dba-oracle.com/oracle_tips_null_idx.htm
                          +1
                          Вообще, NULL-ы — довольно токсичная штука, всё что с ними соприкасается тоже становится NULL-ом. Вот если вы хотите поместить такое значение в индекс, где оно окажется — в начале, конце (может сбоку)?

                          По вашей ссылке вижу попытку подменить null-ы «неизвестным значением».
                          Сошлюсь на несколько идеалистическую книжку Дейта и Дарвена «Database Explorations»
                          (см. «Chapter 27 Is SQL’s Three-Valued Logic Truth Functionally Complete?»,
                          «Chapter 28 A Critique of Nulls, Three-Valued Logic, and Ambiguity in SQL:
                          Critiquing Date's Critique») и просто на вики :).
                            0
                            :)) в потолке открылся налл, ты не смейся, ты пропал :))
                0

                Читать очень интересно, спасибо за статью (и за предыдущую тоже).


                Мне кажется, если уж речь идет о сотнях булевых полей, то может подойти и инвертированный (GIN) индекс. Наивный пример: массив[enum] + оператор @> в запросах.

                  0
                  Спасибо.

                  А чем это будет отличаться от варианта — «давайте просто проиндексируем все логические поля»?
                    +1

                    «давайте просто проиндексируем все логические поля» — слишком абстрактно. В конце концов, Вы в статье индексируете все логичесчкие поля, разве нет?


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


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

                      +1
                      Мысль то симпатичная: пусть конкретное поле — это наличие некоторого слова из словаря, давайте построим полнотекстовый индекс.

                      Но это эквивалентно построению одиночного индекса на каждое логическое поле,
                      так даже компактнее полнотекстового, ведь номер слова не присутствует.

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

                      В результате многомерный индекс получится и компактнее и быстрее.
                  0
                  Офигенно, круто. Люблю, когда оторванная от жизни математика (кривая Гильберта) оказывается настолько практичной.
                    0

                    Мы пошли другим путем. Булевые флаги перевели в флаговое перечисление. В БД — инты.
                    Всё отлично индексируется и работает.
                    Безусловно, в бд данные не читабельные, но в коде — все супер.

                      0

                      не понял, вот есть 10 полей, по 2 из них нужно отфильтровать — и как оно работает?

                        0

                        А вот поиск у нас в эластике.)
                        Для неё флаговое перечисление сериализуется в коллекцию значений. Причём значения хранятся не в интах, а в строковых значениях типа keyword. Это обеспечивает и читабельность, и отсутствие кореляций с другими значениями перечесления, если б хранились в интах.
                        Соответственно, поисковый фильтр формируется для указания наличия (или отсутствия) конкретных значений в коллекции.


                        В базе только по ключам что-то берётся.

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

                    Самое читаемое