Открыть список
Как стать автором
Обновить

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

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

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

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


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


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

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

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

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


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

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

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

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

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

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

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


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

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


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

«select… where field is null» — table full scan
«select… where field > 123» — index used
Вообще, 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») и просто на вики :).
:)) в потолке открылся налл, ты не смейся, ты пропал :))

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


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

Спасибо.

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

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


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


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

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

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

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

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

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

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

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


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

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