SQL и флаги

    Конечно же речь пойдёт не о режиме игры Capture The Flag на сервере SQL, а об использования bit флагов. Битовые операции знакомы, наверное, всем, кто занимается панорамированием, независимо от среды и языка разработки. Однако использование флагов, на мой взгляд, для многих является экзотикой нежели повседневным инструментом. На Хабре не раз упоминали возможность удобную возможность .NET работать с флагами через enum, но ведь и SQL даёт нам отличные возможности для использования флагов!

    И так, рассмотрим простой пример — в некой аппликации должна быть некая система оповещения пользователей. Допустим вы строите форум и хотите дать возможность пользователю получать оповещения по почте: новый ответ в избранной теме, новое личное сообщение, новости форума.Беглый взгляд на задачу даст тривиальный дизайн таблиц:
    tblUsers {userID (PK) as int, name as nvarchar(50), password as nvarchar(50)}
    tblUserAlerts {userID (FK) as int, alertID (FK) as int}
    tblAlerts{alertID (PK) as int, message as nvarchar(50)}


    То есть существует таблица пользователей, таблица оповещений и связь между ними реализуется через вспомогательную таблицу дабы дать возможность каждому пользователю выбрать больше чем одно оповещение. Данные будут выглядеть примерно так:
    tblUsers
    1, «Вася», «хитрыйп4р0ль»

    tblUserAlerts
    1, 1

    tblAlerts
    1, «Вам пришло новое личное сообщение»

    А теперь рассмотрим пример с пользованием флага:
    tblUsers {userID (PK) as int, name as nvarchar(50), password as nvarchar(50), alerts as int},
    tblAlerts{alertID (PK) as int, message as nvarchar(50)}

    В данном варианте мы получаем ту же функциональность и при этом обходимся без дополнительной таблицы. В таблице tblAlerts мы задаём alertID как бит флаг с помощью то го же int (размер зависит от количества вариантов оповещений), а в таблице tblUsers поле alerts отображает бит маску оповещений. Допустим мы создаём 3 вида оповещений, значит в таблице tblAlerts будет 4 (нет оповещений + упомянутые 3 вида) строки флагами в поле alertID. Первым ID будет 0 — в битах будет выглядеть как 0000, значение, соответственно — нет оповещений. Затем мы добавляем наши оповещения зажигая каждый раз другой бит (каждый идентификатор будет степенью двойки ): 0001 = 1, 0010 = 2, 0100 = 4:
    tblAlerts
    0, NULL
    1, «Новый ответ в избранной теме»
    2, «Вам пришло новое личное сообщение»
    4, «У нас новость!»

    Теперь нам надо подписать пользователя, допустим, на новости и на оповещения о личных сообщения. Для этого мы суммируем идентификаторы этих оповещений и получаем 0110 = 6:
    tblUsers
    1, «Вася», «хитрыйп4р0ль», 6

    Теперь построим запрос в таблицу tblUsers, чтобы узнать кто из пользователей подписан на новости:
    SELECT * FROM tblUsers WHERE (tblUsers.alert & 4) > 0

    Смысл данной операции прост:
    0110 — наша маска
    0100 — флаг новостей
    0100 — результат ( то есть есть есть пересечение маски и флага, то результат будет больше нуля )

    Приятный аспект — можно сравнивать и маски. Допустим мы хотим получить список пользователей подписанных на все виды оповещений 1+2+4 = 7:
    SELECT * FROM tblUsers WHERE (tblUsers.alert & 7) = 7

    Заметьте, что между маской 6 и 7 есть пересечение, но результат будет отличным от 7
    0110 — маска пользователя
    0111 — маска проверки
    0110 — результат (пересечение или минимум из 7 и 6 = 6)

    С той же лёгкостью можно сделать запрос на список пользователей подписанных либо на оповещение об ответах либо на уведомление о личных сообщениях 1+2 = 3:
    SELECT * FROM tblUsers WHERE (tblUsers.alert & 3) > 0

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

    Вот таким нехитрым образом можно избавиться от связующей таблицы и даже упростить запросы. Однако минусом может стать не возможность сделать некоторые действия ( допустим JOIN ) через стандартный визуальный редактор запросов, так как стандарт будет сравнивать идентификаторы. Надо будет в ручную заменять сравнение на битовую операцию:
    SELECT tblUsers.*, tblAlerts.*
    FROM tblUsers INNER JOIN tblAlerts ON (tblUsers.alerts & tblAlerts.alertID) = tblAlerts.alertID
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      +3
      Логика прослеживалась до примеров «кто из пользователей подписан на ...». Флаги не индексируются, вот в чём беда, если нужны такие выборки — нечего городить огород.
      Упаковывать флаги в одно поле разумно когда по ним ничего не ищут, возможный пример — пользовательские настройки оформления, типа показывать или нет свой возраст, e-mail, icq…

      А зачем перед таблицами префикс tbl?
        0
        Флаги удобно использовать только при маленьком количестве опций, которые эти флаги отображают. Классический пример, конечно, это атрибуты файлов или права доступа. С таким маленьким количеством пермутаций индекс будет работать неплохо. И многие запросы можно оптимизировать добавив/заменив условия. Если нам надо получить пользователей отвечающих маске 6 (0110 — новости и на оповещения о личных сообщениях), то вместо битовой операции можно использовать:SELECT * FROM tblUsers WHERE (tblUsers.alert >= 6).

        SELECT * FROM tblUsers WHERE (tblUsers.alert & 7) = 7
        ведь можно заменить на:
        SELECT * FROM tblUsers WHERE tblUsers.alert = 7.

        В случае с OR (выбор подписчиков на флаг 2 или 4), то в запрос добавляется сравнение с минимумом SELECT * FROM tblUsers WHERE tblUsers.alert>=2 AND (tblUsers.alert & 6) > 0

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

        А насчёт префикса — для наглядности. Когда-то меня учили добавлять префикс tbl таблицам и fld полям, но при переходе от университетской теории к работе, стало ясно, что подобные префиксы — дурная практика.
        0
        Хм… А как же внешние ключи?
          0
          А что с внешними ключами (FK — как я понимаю)?
          Как я и говорил — проблема будет при использовании визуальных редакторов.
          Не получится просто перетянуть ключ из одной таблицы в другую на диаграмме и получить работающий constraint.

          Ещё раз повторюсь, что флаги в чистом виде используют лишь в небольших проектах. Из личного опыта скажу, что как правило используют и обычный ключ со связью через дополнительную таблицу и флаг. Таким образом запросы не требующие быстрого ответа (например ежемесячная статистика) делают через флаг, так как работа с одной таблицей намного удобней чем работа с тремя, да и порой быстрее (зависит от сценариев). При этом есть возможность использовать стандартные пути (через связывающую таблицу) для операций JOIN и т.д…

          Кстати дублирование данных часто используется для ускорения процессов. Допустим хранят имя (first name) и фамилию(last name) как по отдельности, так и вместе (full name), чтобы построить индекс и на этом общем (fullname) столбце, тем самым ускорив поиск, если подобные поиски неотъемлемая часть повседневной работы системы.
            0
            Мне кажется, вы просто привели не очень хороший пример. Для связи двух таблиц флаги неудачное решение. Сегодня у вас три сообщения, завтра десять и вам то и дело нужно будет править базу. А где гарантия что вы не ошибетесь в последовательности ключей (сделаете не 0-1-2-4-8-16, а 0-1-2-3-4-8-16). Появятся непонятные глюки.
            Плюс к этому вы можете в tblUsers.alerts записать число 1001 (в двоичной), но не определить элемент с id = 8 в tblAlerts. (Это к вопросу о внешних ключах) Снова появятся глюки.

            Флаги хорошо использовать, когда у вас в коде есть перечисление (я по C# сужу) и вы его используете как флаги в программе, и одновременно те же значения используете в бд. Но сами элементы перечисления в бд не храните.
              0
              От ошибок ввода, конечно никто не застрахован, но я думаю глупо считать это ключевым моментом, так речь идёт о статичной таблице (tblAlerts не должна расти иначе флаги неуместны). Возможно, пример действительно не самый удачный, но уж очень не хотелось использовать избитый хороший пример — права доступа (R/W/X), набор которых собственно неизменен. А вот насчёт внешних ключей в constraint — если не check, то всегда есть trigger. Ну и естественно часть data integrity решается определением соответствующего enum с флагами в том же C#.
          0
          Так по-моему для этих целей есть тип данных — SET, он-же по-сути битовой маской и является.
            0
            Во всяком случае в MS SQL Server 2005 указанного вами типа данных не существует.
              0
              Да, извиняюсь, привык смотреть на SQL со стороны MySQL'я :) в MySQL такой тип есть, и по-сути от битовой маски он отличается тем биты имеют названия в структуре таблицы, и в запросах работа ведется через них.
            +1
            Можно еще так сделать:

            0, Нет оповещений
            1, «Новый ответ в избранной теме»
            2, «Вам пришло новое личное сообщение»
            3, «У нас новость!»

            Теперь нам надо подписать пользователя, допустим, на новости и на оповещения о личных сообщения. Для этого мы конкатенируем ID алертов:
            tblUsers
            1, «Вася», «хитрыйп4р0ль», 23

            Теперь построим запрос в таблицу tblUsers, чтобы узнать кто из пользователей подписан на новости:
            SELECT * FROM tblUsers WHERE alerts like '%3%'

            Вообще для данного конкретного примера это не лучшее решение, так как обновлять данные о том, на что пользователь подписался/отписался будет трудоемко. Но для случаев в которых эта информация заводится единожды, очень удобно. Пример: информация о том, по каким дням недели вылетает определенный рейс.
              0
              like тут еще большее зло чем побитовые операции…

              У меня другой вопрос. Например вы получили сообщение — «Вам пришло новое личное сообщение» — и где у нас ID нового сообщение которое вы получили?

              Или же «Новый ответ в избранной теме» — и как мне туда попасть?

              Надо еще собзать таблицу где хранить ID тех скажем так items о которых вы сообщаете пользователю…

              з.ы
              По моему реалтзация того что показано выше подходит только для хранения например «Мои любимые жанры музыки» где не будет использоватьс поиск, да и то я думаю что заюзать array для хранения сообщений а не таблицу будет целесообразнее…
                0
                Пример рассматривает связку пользователя и типа сообщения.
                Само сообщение генерируется и сохраняется совсем в другом месте. Моей задачей было сделать систему оповещений во внутреннем форуме системы администрации небольшого вап-портала. При генерации какого то определённого события, мне надо проверить нет ли для этого евента сообщения и подписан ли юзер на это уведомление. Сами уведомления и их текст к теме освящённой в посте отношения не имеют.
                0
                LIKE '%%' будет намного более тяжёлой операцией, да и к тому же сокращает возможности оптимизации.
                Во всяком случае поиск по маске становиться сложней (допустим нам надо найти подписчиков на тип сообщений 2 и 3):
                SELECT * FROM tblUsers WHERE alerts like '%3%' and alerts like '%2%'
                А с флагами решение частично использовало бы преимущество индекса, не имело бы значение в каком порядке были добавлены подписки и сколько ещё подписок существует у пользователя:
                SELECT * FROM tblUsers WHERE tblUsers.alert = 6 OR (tblUsers.alert & 6) > 0
                или можно пойти на шаг дальше (в зависимости от cost-function):
                SELECT * FROM (SELECT * FROM tblUsers WHERE tblUsers.alert>=6) as tblUsers1 WHERE (tblUsers1 .alert & 6) > 0
                Из-за использования подзапроса результат (tblUsers1 ) не будет иметь индексов, но так как в битовой операции они нам всё равно не помогали, то сокращение количества этих самых битовых операции сыграет положительную роль.
                Ещё на шаг дальше:
                SELECT * FROM (SELECT * FROM tblUsers WHERE tblUsers.alert=6 or tblUsers.alert > (SELECT MAX(alertID) FROM tblAlerts)) as tblUsers1 WHERE tblUsers1 .alert = 6 OR (tblUsers1 .alert & 6) > 0
                Так как таблица флагов (tblAlerts) подразумевает некое постоянство значений, то вместо постоянного выбора MAX(alertID) я использую глобальную перемененную просчитываемую лишь раз, которую передаю в необходимую процедуру.
                  0
                  Так какой, бишь, из этих запросов приводит к использованию индекса?
                    0
                    Те части условий где нет &…
                    Допустим вот так поиск будет с индексом:
                    SELECT * FROM tblUsers WHERE tblUsers.alert=6 or tblUsers.alert > (SELECT MAX(alertID) FROM tblAlerts)

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

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

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

                      Как я уже писал, правильный сценарий для категорий — это битовые флаги в описании самой категории, а потом нормальный джойн по id. Это, конечно, если надо все передать на SQL одним параметром.
                        0
                        Тут фишка в суммах и условиях. То есть если надо выбрать только по отмеченным категориям или как минимум по отмеченным. Из комбинированных можно сразу откидывать суммы меньше искомой (да, тут вы правильно заметили, что чем меньше номер, тем больше скан).
                          0
                          В итоге получается, что индексы вам выигрыша не дают. Про что и речь была в изначальном посте про категории.
                            0
                            Если по вашему сокращение скана от 300К до 100К — это не выигрыш, то не дают.
                            Если вернуться к изначальному посту, то там тоже очень специфичная пушка для мух. Не в каждой задаче стоит строить тяжёлую функцию сплита со временными таблицами (которые тоже лишены индексов и join так же потеряет в эффективности если не использовать union). Каждому сверчку своё.
                              0
                              От 300 до 100 — это повезло. У вас количество записей под сканом будет прямо пропорционально номерам категорий — и это еще если мы по одной записи ищем, а если по нескольким?

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

                              А еще лучше, конечно, просто использовать любой sql-builder.
                0
                Без индексов тяжко будет (если делать как Вы, через битовые операции). Пара более-менее сложных запросов с полным просмотром таблиц — и прощай, быстродействие.
                  0
                  Зависит от размеров таблиц. В моём проекте пользователей не много (меньше 5К) и никаких проблем быстродействия или нагрузки не возникало. К тому же правильное использование индексов (они ведь есть, просто работают в данном решении не на 100%) и построение с учётом execution plan и cost function решат большинство проблем со сложными запросами. Главное понимать, когда стоит применять флаги, а когда нет.

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

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