Работа с битовой маской

[avalak]

Добавьте пожалуйста подствеку кода и форматирование

[slang]

Правильно я понимаю, что это — «прощайте индексы»? Если у вас будет 1 000 000 сущностей, содержащих параметр-флаг, то для выборки по этому флагу Вы устроите полный проход таблицы?

[soider]

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

[slang]

Вы разработчик онлайн-игрушки с миллионом пользователей. Задача вывести 50 пользователей на страницу, конечно, заблокированных не нужно выводить, и скрытых тоже, а ещё отсортировать просят по уровню доступа. Все эти настройки записаны в виде одной битовой маски в поле flags (судя по коду оно не BINARY и фильтрация происходит в PHP). Это залёт?

[WebResult]

Понимаю, однако такой подход не везде следует использовать. объем данных требует использовать критерий как ключ, то описанный подход не самый удачный. Такой подход подойдет, когда следует хранить много настроек для одной сущности и по ним нужна фильтрация.
Данный метод подойдет и к хранению данных из checkbox-ов с последующим обращением к ним.

[WebResult]

Не согласен с фильтрацией на строне php. Вовсе не так. Фильтрация происходит на строне sql. На стороне php реализован механизм для работы с классами Yii для работы с базой.

[Halfi]

Фильтрация идет на стороне SQL, но фильтрация замедляет запрос в 10 раз! В чем преимущество данного подхода перед классическим подходом с хранением данных в булен поле? Я не вижу ни одного, зато вижу огромный минус в снижении производительность более чем в 10 раз за счет:

• Отсутствия индексов по полям
• Сложное условие

Основной принцип в разработке — реализуйте простые решения. Битовая маска идеально подходит для сложения прав при реализации мульти ролей.

[WebResult]

Собственно говоря, суть этой статьи была не в том, чтобы предложить битовую маску для реализации большинства задач, которые подходят, а в том, чтобы дать готовое решение для работы с битовой маской на Yii.
По поводу замедления запросов в 10 раз: откуда такая цифра? Если проводились тесты- то на каких объемах данных? Со сколькими битами велась фильтрация? Я думаю, что говорить о быстродействии можно только в рамках конкретной задачи. Хотя Ваше замечание в некоторых случаях действительно верно.
К вопросу по индексам- не вижу проблем с созданием индексов при условии, что флаги меняются редко. Тогда запрос идет по одному поле, в отличие от нескольких полей в Вашем случае.

[JiLiZART]

Так то это всё в Behavior бы и куда нибудь выложить)

[JiLiZART]

В общем вот на скорую руку gist.github.com/1287389 пойду проверять )

[JiLiZART]

Автор молодец, с первого раза заработало )

[WebResult]

спасибо за высокую оценку!

[WebResult]

Обязательно. Я хотел сначала закончить идею про битовые флаги. После второй части выложу сразу готовый инструмент на yii-extentions и дам линк в топик.

[WebResult]

что именно сложного было в моем коде?
2 метода — это простая логика, с которой должен быть знаком как раз любой пятиклассник.
что касается метода фильтрации- то тут нужно знать как работать с CDbCriteria в Yii и как работать с той же булевой логиков в sql. Возможно, некоторые детали можно, а может, и нужно было написать по другому, тогда пишите, что не так.

[WebResult]

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

[WebResult]

Все дело в том, что при проектировании базы данных нужно иметь представление о требованиях. Если предполагается, что набор свойств может быть порядка нескольких десятков и разрядности может не хватить- тогда эту схему применять не стоит. Однако, пример с серилизацией здесь не уместен, т.к. это действительно зло и никаких методов для фильтрации через такие поля не существует без костылей. А предлагаемый мной метод позволяет и фильтровать и оптимизировать работу с флагами.

[Flam]

так а в чем смысл то? не раздувать таблицу полями?

[WebResult]

Да, к тому же, таким способом появляется удобный интерфейс работы с подобными данными, как с единым функциональным элементом. Вроде, getFlag- можно для некоторых данных интерпретировать как получить настройку.

[ainu]

Можно в теории добавлять пользовательские поля, например фильтр по каталогу с уймой параметров.
И доспустим, ищем телефоны, где:
Экран 480 — нет
Экран 300 — да
Экран 600 — нет
Память 1 гиг — да
Память 2 гига — да
Андроид — да
Win Mobile — нет
Итого можно очень быстрым запросом
SELECT * FROM phones WHERE `options` = 0101110
Причём даже в NoSQL можно опции хранить как ключ — значение.
Это гораздо быстрее, чем WHERE Экран = 300 AND (memory = 1 or memory = 2) AND is_android = 1

[ainu]

Если options сделать индексным то это вообще будет мгновеннее некуда

[Strate]

И? Много телефонов найдётся у которых есть такой набор опций? (имеется ввиду память И 1 гиг, И 2 гига)

[ainu]

Верно. Надо делать временные таблицы в памяти, и делать подробный поиск уже по ним. Эта тема уже обсуждалась, и всё равно этот метод позволяет использовать NoSQL решения на огромной скорости.
Даже банальный `options` = 0100110 OR `options` = 0101010 будет быстрым, тк. по индекируемому полю поиск будет бегать весьма шустро.
Если речь идёт о таком поекте, как хабрахабр, можно хранить бит устарелости, бит захабренности, бит опубликованности, и далее, быстро отфильтровав огромную базу, получив результат как небольшую таблицу в памяти, делать уже любые хитрые фильтрации и сортировки и что душа пожелает.
В случае с твиттером, можно хранить бит «горячих» новостей, в случае с гуглом, бит для каждого региона, сортируя предварительно данные в сотню раз быстрее, вообще не проводя поиск по ненужным регионам.

[Strate]

И в итоге мы всё равно приходим к WHERE… OR… OR… OR и т.д. Лучше проектировать базу по другому.

[slang]

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

[ainu]

SELECT WHERE field = число это самый быстрый из всех возможных фильтраций. Курсор, который бегает по базе данных, в этом случае быдедет бегать гораздо быстрее, чем проводя OR в КАЖДОЙ строке базы данных. В случае поиска числа 1024 он пройдёт 10000 строк до числа 1024, возьмёт пачку и успокоится.

[slang]

Мне кажется, Вы плохо понимаете как работает оптимизатор базы данных, индексы и B-деревья. Никаких OR в каждой строке не будет, более того, разнося по разным полям настройки, Вы будете использовать логическое умножение, что будет только сужать выборку. Бесспорно, выборка по индексу конкретного значения будет быстрой операцией, но Вы не учитываете что это не цель. Последующая обработка результата, его сортировка и ограничения накладываемые этим подходом сведут на нет изначальное преимущество, при куда менее прозрачной модели приложения. Более того, поиск одного конкретного значения это частный случай, на практике построенные запросы будут куда сложнее.

[Halfi]

а если у на будет такие критерии поиска:
Экран 480 — не имеет значения
Экран 300 — не имеет значения
Экран 600 — не имеет значения
Память 1 гиг — не имеет значения
Память 2 гига — не имеет значения
Андроид — да
Win Mobile — не имеет значения

Сколько OR'ов у вас будет? И обычно так происходит поиск, а не по точным критериям и в данном случае будет поиск по одному, двум индексным полям, нежели мы будем подготавливать данные (например если стоит флаг андроид да, то вин ставить на нет, не ставить же это поле пользователю), а потом еще и делать кучу OR для поиска любого разрешения экрана. Реализация логики подготовки данных усложнит, утяжелит и замедлит ваш код в разы! Пишите проще!

[ainu]

>Если материал оказался полезным, я буду рад опубликовать продолжение данной темы,
Конечно, продолжайте. Сама тема битовых масок довольно интересна, не только в контексте Yii. У меня уже глаза горят, как до этого раньше не дошёл. В Q/A как то было обсуждение быстрой фильтрации каталога (как в Яндекс-маркете), там подход был похожим, но обсуждалась только теория.
А тут — реализация.

[zvirusz]

Какой-то у вас getFlag сложный…

    public function getFlag($idBit){
        return $this->flags & (1 << $idBit);
    }

[zvirusz]

Ну и двухстрочный setFlag, правда более тяжкий для восприятия :)

    public function setFlag($idBit = 0, $bit = 1) {
        $this->flags = ($this->flags | (1 << $idBit)) ^ (!$bit << $idBit);
        $this->save(true, array('flags'));
    }

[sectus]

Мне показалась странной работа с флагами таким образом. Обычно, в качестве констант хранят не номер бита, а само значение. Это позволит ввести (если надо) дополнительные константы, которые комбинируют предыдущие.

const FLAG_LAYOUT_LEFT=1;
const FLAG_LAYOUT_RIGHT=2;
const FLAG_LAYOUT_TOP=4;
const FLAG_LAYOUT_BOTTOM=8;

const FLAG_LAYOUT_LEFT_AND_RIGHT = 3;
const FLAG_LAYOUT_TOP_AND_BOTTOM = 12;
const FLAG_LAYOUT_ALL = 15;

Так же будут упрощены установки флага:

$this->flags |= self::FLAG_LAYOUT_ALL;

снятия флага:

$this->flags ^= self::FLAG_LAYOUT_LEFT;
$this->flags ^= self::FLAG_LAYOUT_RIGHT;

проверки флага:

($this->flags & self::FLAG_LAYOUT_TOP) === self::FLAG_LAYOUT_TOP;
($this->flags & self::FLAG_LAYOUT_LEFT) === self::FLAG_LAYOUT_LEFT;

[WebResult]

Не уверен, что такой подход будет всегда уместен. Хотя такая идея тоже имеем место быть.
Например, мне нужно проверить, установлен ли определенный бит, вне зависимости от других. Описанный мною подход я обычно использую для определения определенных битов. Кроме того, может возникнуть ситуация, когда в запросе может оказаться несколько требований к флагам из разных мест. Например, часть требований заложены в моделе поумолчанию, в defaultScope, часть требований мы вводим через noBlock(), например. Еще часть закладываем напрямую в findAll() через параметры. Причем, эти параметры зависимые и изначально мы не всегда можем определить и найти комбинированные значения, которые предложены Вами. Т.к. В экшонах могут быть случаи, когда мы абстрагируемся от модели и не знаем, какая она будет и какие флаги в ней уже заложены и какие понадобятся…

[sectus]

Комбинирование флагов — это так, бесплатное приложение к подходу. Основная идея в том, чтобы использовать битовые маски как битовые маски, а не как массив.

define('FLAG_CIRCULAR', 128);
define('FLAG_PUBLIC', 256);

class some
    {
    const FLAG_BLOCKED = 1;
    const FLAG_BIG = 2;
    const FLAG_LAST = 4;
    const FLAG_BEST = 8;
    const FLAG_COLORED = 16;
    const FLAG_PREMIUM = 32;
    const FLAG_WITH_SOUND = 64;

    public $flags = self::FLAG_BLOCKED;

    }

$lang_array = array(1 => 'заблокирована', 2 => 'большая', 4 => 'последняя',
    8 => 'лучшая', 16 => 'цветная', 32 => 'высшего качества', 64 => 'со звуком',
    128 => 'круглая', 256 => 'общедоступная');

$some = new some();

$some->flags ^= some::FLAG_BLOCKED; //не заблокирована

$some->flags |= some::FLAG_LAST; //эта вещь последняя
$some->flags |= some::FLAG_COLORED; //цветная
$some->flags |= some::FLAG_PREMIUM; //высшего качества
$some->flags |= some::FLAG_WITH_SOUND; //и со звуком
$some->flags |= FLAG_CIRCULAR; //так же она круглая
$some->flags |= 512; //ещё какой-то флаг

echo 'Эта вещь: ';
foreach ($lang_array as $key => $title)
    if (($some->flags & $key) === $key)
        echo '
'.$title;

echo '

Заблокирована? ';
echo (($some->flags & some::FLAG_BLOCKED) === some::FLAG_BLOCKED)? 'Да':'Нет';

echo '

Установлен ли флаг, который заранее не определён? ';
echo (($some->flags & 512) === 512)? 'Да':'Нет';