|
|
Задавайте вопросы, мы ответим
Вы не зашли.
Собственно вопрос в оптимизации хранения флагов и выборок по ним.
1). Лучше хранить их побитово и делать выборки с помощью побитовой маски?
where (bitsflag&3)=3
2). Или быстрее будут выборки, когда флаги будут храниться в отдельных полях.
where flag1='yes' and flag2='yes'
Интересует выигрыш именно в скорости.
Флагов где-то десяток-два.
Таблицы большие, где-то с десяток миллионов записей.
Отредактированно Shad (02.10.2007 23:56:20)
Неактивен
1. Запросы вида "(вычисляемое выражение) = значение" никогда не будут использовать
индекс, поэтому они плохи сами по себе.
2. Хранить флаги строками - не нужно, индексы по строкам будут работать отвратительно
медленно (по сравнению с числами).
3. Хранить флаги отдельно побитово (столбцы типа BIT) - это замечательно с точки зрения
места, но индекс имеет смысл натягивать только на очень большое количество таких
столбцов, т.к. у бинарного поля будет очень маленькая cardinality на 10кк строк 
--
Я бы остановился или на варианте
where flags = 3
(почти Ваш первый вариант, но использует индекс), или на
flag1=1 and flag2=1
(с индексом на flag1, flag2)
Минусы, впрочем, тоже очевидны, т.к. индекс будет использоваться только при правильном
указании последовательности флагов.
Отредактированно paulus (03.10.2007 00:06:53)
Неактивен
Как вариант можно создать несколько составных ключей для разных наборов атрибутов. Такое можно себе позволить, только если INSERTы редки.
Неактивен
Спасибо за ответ.
Я во втором своем варианте предполагал, что будут использоваться не строки, а enum. Или с этим типом индекс тоже не используется?
Можно еще немного пообсуждать предложенные вами варианты?
1. Вариант с простым сравнением "flags=3".
Подразумевается, что флаги мы храним так же, как и раньше, побитово? А если нужно сделать выборку по одному из установленным флагов, то будем писать что-то вроде:
flags=1 or flags=3 or flags=5 or flags=9 or flags=17 or flags=33 or ... и так столько раз, сколько у нас флаговых бит (ну или через "IN(1,3,5,9,17,33,...)")
А если надо сделать более сложные выборки (с десятками флагов в разных состояниях)? Что-то мне уже как-то становится не по себе.
2. Вариант "flag1=1 and flag2=1" собственно понятен.
Вопрос только "по правильному указанию последовательности флагов". Что вы имели в виду, можно чуть подробнее.
Неактивен
1. IN может оказаться достаточно большим
Для Вашего десятка битов с двумя фиксированными это 2^8 = 256 комбинаций.
Хотя, с другой стороны, это не так уж и много. Или я считаю не правильно?
2. Последовательно - это принцип работы индексов. Пусть у Вас есть индекс,
натянутый на поля (f1, f2, f3). Тогда он будет использоваться так:
запрос "f1=1 and f2=1 and f3=1" - отлично, весь индекс используется
запрос "f1=1 and f2=1 and f4=1" - используется только часть индекса (f1,f2)
запрос "f2=1 and f3=1 and f4=1" - индекс не используется, потому что нет f1.
Используется только самая левая часть полей в индексе.
--
Вообще, случай с IN для десяти битов мне представляется сейчас оптимальным.
Для 20 битов вы не сможете выписать IN за разумное время
Неактивен
Обсуждения с rgbeast навели на мысль, что надо бить флаги на кусочки по несколько бит
и писать через IN. Т.е. как-то так:
1. Есть 20 бит информации. Мы ее бьем на три байта по 8 бит: f1, f2, f3.
2. Натягиваем индексы на (f1, f2, f3), (f1, f3), (f2, f3), (f3).
3. Ищем с помощью f1 IN (...) and f2 IN (...) and f3 IN (...), произвольно опуская куски,
если они не нужны.
Неактивен
paulus написал:
запрос "f1=1 and f2=1 and f4=1" - используется только часть индекса (f1,f2)
Это даже если есть отдельный индекс для f4? Он не поможет в таком запросе?
(Updated: исходя из вашего предыдущего поста, сделал вывод, что не поможет). 
paulus написал:
Вообще, случай с IN для десяти битов мне представляется сейчас оптимальным.
Для 20 битов вы не сможете выписать IN за разумное время
Вот. Этого я и боюсь. Живые проекты имеют свойство усложнятся.
(Updated: хотя идея с разбиением на несколько составных битовых полей греет мне душу).
Отредактированно Shad (03.10.2007 01:51:29)
Неактивен
А Вы уверены, что нужно хранить именно битовую информацию и по ней искать?
Наверняка, есть какие-то более разумные (и более селективные) критерии поиска,
чем наличие нескольких бит информации.
Неактивен
Да вобщем-то речь идет о флагах, никак не связанных между собой.
Я, честно говоря, не вижу, как выборки по ним можно логически чем-то заменить.
Неактивен
В обсуждении с paulus, возникла мысль, что если аттрибутов много всего, а для каждой записи их мало, то есть много нулей и мало единичек (аналог разреженной матрицы), то можно использовать другой алгоритм.
Каждому атрибуту приписать слово, а атрибуты все вместе хранить в строковом поле через пробел. Например 'strong green wide active" или "inuse white flexible active". Поиск строк с необходимыми атрибутами можно проводить, используя FULLTEXT индекс (аналог того, что используют поисковые системы). При этом нужно учитывать, что если стрибут присущ более половине строк, то FULLTEXT-поиск не будет учитывать такие атрибуты при выборке (будет считать их общеупотребимыми stop-словами). Поведение по умолчанию можно отключить, перекомпилировав MySQL
Неактивен
Ну, может, там помимо флагов есть еще поле "цвет глаз", которое является решающим
А не просто флаги "наличие головы", "наличие усов".
Я имею в виду, что можно применять не только знание о том, что есть поля, но и знание
о том, что в них содержится. Зачастую очень упрощает запросы и способы хранения
информации
А вообще задачка прикольная
Неактивен
Да нет, атрибуты равномерненько так перемешаны. Никаких разреженных матриц.
Неактивен
Я вот тут еще что подумал... Вам насколько нужно это быстро отдавать? Если это
какой-то внутренний статистический запрос (т.е. время ~секунды приемлемо), то
можно сделать хитрое читерство:
CREATE TABLE flagger (id INT NOT NULL, flags INT NOT NULL) ENGINE=InnoDB;
CREATE TABLE data (id INT NOT NULL KEY AUTO_INCREMENT, ...);
Таблица flagger _без_ индексов вообще, 10кк строк * 8 байт на строку = 80 мегабайт.
InnoDB, чтобы влезло целиком в buffer_pool и работало из памяти
Запросы организовывать так:
SELECT ... FROM data WHERE id IN (SELECT id FROM flagger WHERE flags & mask = mask);
Есть подозрение, что Вам наверняка нужны не все флаги с маской, а только первые
50, скажем. Это LIMIT. LIMIT вы внутрь такого селекта не подпишете, но подпишете его
сбоку:
SELECT STRAIGHT JOIN ... FROM flagger f JOIN data d USING(id) WHERE flags & mask = mask LIMIT 50;
Или, если хочется, чтобы летало сразу (а не после загрузки в innodb buffer pool),
то положить данные в MEMORY-табличку или в MyISAM-табличку в tmpfs.
Неактивен
Я так понимаю, суть последнего предложенного варианта в том, чтобы вынести флаги в отдельную (небольшую) таблицу и загрузить ее в память? И ускорение будет достигнуто именно за счет использования памяти?
PS: Limit -это само собой. Но он не всегда спасает.
Отредактированно Shad (03.10.2007 16:37:07)
Неактивен
Да. Скорость будет не очень большая, но вполне приемлемая.
LIMIT спасает всегда. Это очень хороший стимул оптимизатору использовать индексы.
Неактивен
Я в том смысле, что для моей задачи нужно ставить не LIMIT 50, а LIMIT 200000.
И он не всегда даст преимущество - чаще количество найденных записей будет меньше лимита.
Неактивен
Интересно, что же Вы такое храните там
Неактивен
Записи, которые нужно искать по флагам.
Неактивен
А если хранить информацию о флагах во внешней таблице?
Типа "Многие-ко-многим!
Индекс хорошим будет и не будет избыточности если флаги не оптимальны...
Неактивен
Если флаг булевый, то CARDINALITY индекса не будет большим в любом случае
Неактивен
