Ищем быстро, еще быстрее

[toxicdream]

А ларчик просто открывался!
Молодцы.

[ElfW]

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

[ainu]

Для меня, когда увидел в Q/A, было озарением, всегда считал, что noSQL — это для хранения всякого рода голосов за комментарии, вёздочек добавлено в избранное и твитов, не более.
Метод прост и прекрасен.

[ainu]

Доп. вопрос: когда имеется в виду MemTable, какое ПО подразумевается?
memcached тут никак не поможет, там могут пропадать отдельные элементы индекса, да и не для хранения он создан.

[serebro]

Может быть это что-то подобное MySQL Memory storage engine dev.mysql.com/doc/refman/5.0/en/memory-storage-engine.html

[Nevkontakte]

Если я правильно понял, то автор как раз использует SQL базу данных, а под MemTable подразумевает временную таблицу, хранимую в памяти. Это умеют большинство реляционных СУБД, не только MySQL.
Сразу отвечая на ваш комментарий ниже, процесс обработки получается такой:
Большая таблица с данными → Предварительная (неточная) фильтрация → Маленькая временная таблица в памяти → Точная фильтрация → Вывод результатов.

[ainu]

Этот процесс подходит для обработки, например, диапазонов значений.
Я имел в виду ситуацию с Да/Нет/Не важно. В этом случае таблица в памяти будет достаточно большой, например, при запросе сотовых телефонов без тачскрина.

[Nevkontakte]

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

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

[zerkms]

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

[psman]

Да, все верно.
Неточная фильтрация отсеивает много изначально неверных строк, что сильно ускоряет дальнейшие работы.

[zerkms]

То что она отсеивает и так понятно, просто непонятно ваше предложение вычитывать все данные в память. Зачем, если субд и сама может выполнить скан по отсечённому множеству?

[psman]

В моей конкретной реализации в хранимой процедуре создавалась временная таблица в нее сваливались все данные и дальнейшая работа была с этой таблицей. После выполнения поиска она уничтожалась.

[zerkms]

Эм, в чём смысл? Вы вычитывали из таблицы ворох данных, которые субд могла вычитать сразу, выдав непосредственно результат?

Вы теряли на дополнительном чтении/записи время же.

Но это уже не принципиально, мне гораздо интереснее ниже про поиск :-) Ответите? :-)

[psman]

Выборка данных путем запроса с одним/двумя условиями намного быстрее, чем километровый запрос.

по поиску отвечаю в порядке очередности :)

[zerkms]

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

[psman]

допустим у нас 250 показателей в таблице, пусть даже просто битовых

что будет быстрее?
select * from tovar where key=5648

или

select * from tovar where (a1=true) and (a2=false) and… and (a250=true)

[zerkms]

1. Я говорил про второй этап выполнения запроса, когда индексы БД уже ничего сделать не могут
2. Умный оптимизатор так и так склеит все ключи, чтобы искать по индексу (если B-Tree) или просто возьмёт как есть (если bitmap). Разница будет несущественная.

[psman]

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

Чем больше база, тем существеннее любые «леваки»
Я преклоняю голову перед создателями SQL, но все же частные случаи работают намного быстрее общих решений.

В задаче отсеивать неуникальные тексты по шинглам частный случай быстрее решения в лоб на… ну 215 тыс текстов по 1-1.2 килобайта отсеивается за 1 секунду на неттопе на атоме330 и без расхода кучи памяти. Решение в лоб — это около 27-35 минут на фильтрацию 100 вариантов статей между собой.

[zerkms]

Не совсем вас понимаю :-(

У вас везде в примерах используется полный набор атрибутов объекта. А по полному набору поиск «в лоб» будет работать точно так же, как и поиск по хэшу. Ровно потому, что субд сделает ту же самую работу, что делаете и вы, вручную.

[psman]

Все делается поэтапно.
имеем 10 млн строк

сделали фильтр по чекбоксам да/нет

получили 10 тыс строк

вот на этом моменте в принципе можно и остановится. мы УЖЕ имеем в префильтрованной темповой таблице данных на порядки меньше исходных. В них найти нужное «в лоб» можно без большого ущерба для производительности.

[zerkms]

Я это прекрасно понимаю. И говорю о другом:

что в случае поиска по 100% совпадению (оператор «равно») поиск по списку аттрибутов типа:

t1 = 1 AND t2 = 0 AND t3 = 1

будет таким же эффективным, как и

hashfield = 101

потому что оптимизатор сделает ту же самую работу, что и вы делаете вручную.

[psman]

Хотелось бы проверить на практике, если честно. Есть повод написать вторую статью :)

[sirus]

и мне вот тоже интересно в чем разница

[psman]

В понедельник найду время для полноценного теста

[Suor]

Не все БД умеют делать составные индексы. А составные и функциональные индексы скорее всего заменят все или большую часть этих уловок.

[ainu]

И еще я правильно понимаю, что запрос, сравнивающий, индексы (домашнее задание), будет делать уже скрипт-обработчик, а не БД?

[psman]

А не обязательно. По факту sql умеет работать с логическими операциями.

[zerkms]

Да, тоже не понял. Уважаемый автор, можно нам немного подробнее? :-)

[psman]

можно :)
я просто не так подробно и понятно расписал.

Допустим у нас есть в базу товар

100000010101 — tovar

нам надо найти
1000хх00хххх — findkey

соответственно битовая маска будет
111100110000 — findmask

Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey

мы должны взять tovar и сбросить у него в 0 все биты, которые отмечены в findmask а потом сравнить с findkey

Мы отсеиваем бОльшую часть товаров, у которых параметры точно не равны нашим заданным. При этом те параметры, что „не важны“ мы не учитываем.

[zerkms]

Допустим у нас есть в базу товар

100000010101 — tovar

нам надо найти
1000хх00хххх — findkey

соответственно битовая маска будет
111100110000 — findmask

Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey

Ничего не понял :-( Переходы от findkey до findmask и далее до ещё одного (?!?!?) findkey какие-то неочевидные :-S

[psman]

Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.

нам надо по findmask сбросить в 0 все биты в ключе товара
Проще всего это сделать через AND

Соответственно проверка будет (tovar AND findmask = findkey)

[zerkms]

Это медленная проверка, которая приведёт к фуллскану.

[psman]

Фулскан из 10 тыс строк, вместо 12-30-100 млн строк как было бы без префильтра? да без проблем.

[Suor]

Так если мы делаем фулскан, то зачем извращения?

[psman]

что быстрее: фулскан 10 млн строк или 10 тыс?

[Suor]

зачем извращения кроме первого (объединения кучи флажков в ключ)?

[zerkms]

Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.

нам надо найти
1000хх00хххх — findkey

соответственно битовая маска будет
111100110000 — findmask

Эм, не совпадает. Если findkey = 1000хх00хххх, тогда findmask согласно вашему описанию должно быть не 111100110000, а 000011001111

[psman]

Сорри, торможу, но сути не меняет.
Нам надо во всех незначащих битах сбросить в нули (или единицы, как угодно и удобнее) все, что имеет значение «не важно»

По сути мы делаем вид, будто вместо «не важно» мы выбрали «нет», но благодаря битовой маске мы все ответы «да» в товаре сбрасываем по ней в ответы «нет».

[zerkms]

Нет, поиск по этому хэшу автор предлагает выполнять в виде вычисления, которое на уровне базы превращается в фуллскан :-S

[psman]

Да, фулскан из префильтрованных ранее данных.
Даже если делать выборку по «да/нет/не важно» по честному, то выборка по чекбоксам уменьшает число строк, в которых надо это сделать.

[zerkms]

Вот что я выше и пытаюсь сказать, что where field1=… and field2=… будет работать не хуже

[zerkms]

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

Плюс добавлять в составной индекс таки нужно все поля, чтобы было совсем отлично.

[fishandchips]

вы абсолютно правы.

пнредположим, что чекбокса всего два. в любом случае psman сначала делает фулскан по по первому, пишет результат во временную таблицу, потом читает ее и ищет в ней по второму. это тоже самое что AND плюс время на запись-чтение временной таблицы.
в чем прирост скорости если вам все равно нужно просмотреть все записи на предмет чекбокс1=0 и чекбокс2=1 запроса например? Кол-во сравнений значений полей ваш выбор во временную таблицу НЕ уменьшит никак. Аргумент о том, что из таблицы отсеяных по первому запросу 1000 строк выбрать чекбокс2=1 быстрее, чем из всей таблицы неверен — чтобы выбрать 1000 отсеянных вам все равно нужно сначала выбрать из 1000000 товары с чекбокс1=0. Фактически вы делаете два последовательных запроса — один к большой таблице, второй — к маленькой. Запросить большую с AND как минимум не медленнее.

почему не сделать маску вида 11_00_01… где 1 -обязательно ДА (например, вай-фай нужен обязательно), 0 — обязательно НЕТ (без блютуса), _ — неважно (карта памяти пофиг). Вместо кучи полей в таблице товаров пишем одно text или VARCHAR в зависимости от кол-ва чекбоксов. В нем строка длины = кол-во чекбоксов 010101..0101. Ищем LIKE%. Должно быть не медленнее как минимум чем AND на кучу полей (ибо % только справа). Маска из POST с запросом получается моментально из значения чекбокса и знаемой нами инфы о том, какого типа чекбокс (пустой=пофиг или пустой=НЕТ) имеем.

[psman]

разницу в скорости поиска по тексту и логические операции с числом — несоизмеримы по скорости.
AND делается всего на 1 поле. 1 поле на 1 строку.

[fishandchips]

если у вас 100 чекбоксов = 100 полей в таблице и AND делается фактически (как бы вы не вставляли промежуточные таблицы) 100 раз.
LIKE% дает вам таблицу с 1 текстовым полем, возможность использовать селекты (а не только чекбоксы — пишете кроме 0-1 любые исмволы соответсвенно занчению поля селекта), и главное что 1 сравнение LIKE% на 100символьную строку ничуть не медленнее 100 сравнений однобитных полей — попробуйте сами

[fishandchips]

LIKE% это не фуллтекст поиск — де-факто сравниваются (в зависимости от кодировки) 8-16битные chars. У вас 1битные да-нет, но их — 100 полей! Сделайте тест.

[psman]

Вы видно не допоняли. Я все чекбоксы объединил в одно Х битное число.
AND выполняется одно на 1 строку в уже профильтрованной выборке.

[psman]

по факту нет 100 полей, есть 1 число с разрядность равному числу чекбоксов + дополнение до кратности 8 (что бы побайтно считать)
по факту 100 чекбоксов — это int(13)

[fishandchips]

угу, это правильно и хорошо. но это использование временной таблицы (то есть два последовательных SELECTа) при этом нисколько не делает поиск быстрее, чем LIKE% по всей таблице 1 раз. Кроме того, в последнем случае вы групируете ВСЕ чекбоксы (включая те которые имеют значение «все равно») в одну строку.
Ведь фактически вы создаете мемтэйбл только потому, что не можете сразу фильтровать поля с опцией «все равно». А это принуждает вас к искуственной конструкции со вторым SELECTом по промежуточной таблице, который не нужен.
Кол-во сравнений при фильтрации LIKE% сделает такое же как при побитовых операциях.
И во всех случаях как правильно указал г-н zerksm скорость будет такая же (а с двумя таблицами даже медленнее) как с where and..and по 100 полям.

[psman]

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

Тест будет и по этому поводу сделаю отдельное дополнение

[psman]

100000010101 -товар

100000000000 — ищем (findkey)

какие биты будут «не важно»?

[zerkms]

Ну судя по всему неважными должны быть как минимум 1, 3 и 5, остальные — не принципиально.

Опять же — товар 100000010101 выбран уже по результатам чекбоксов и поиска по 100% совпадению??

[psman]

если мы ищем 100000000000
и нет «незначащих битов», то товар 100000010101 нам не подходит

мы сможем его найти, только если в маске будет 000000010101

тогда мы делаем 100000010101 AND (not 000000010101) = 100000000000 — равно нашему «поисковому запросу»

я туплю с битовыми операциями по выходным, но как то так.

[zerkms]

А если есть незначащие биты — тогда у вас быстрого поиска не получается. И тогда непонятно откуда вы взяли уменьшение 12М исходных рядов на 2 порядка.

[psman]

Уменьшение произошло в результате фильтрации по чекбоксам.

Сначала мы отбираем по чекбоксам (получаем на порядки меньшее число строк), потом по радио (да/нет/не важно) (получаем еще меньшее число) и потом по диапазонам (из остатка строк, можно делать и «по честному»)

[NervousSnake]

Если я правильно поняла, то схема такая:
— если нужно выбрать все «неважно», то надо только проверить индекс 2 на = 0
— если нужно «нет», то индекс1 = 1, индекс2 = 0
— если нужно «да», то индекс2 = 1, индекс2 = 1

[zerkms]

Тогда нужно подробнее остановиться на построении индекса1 и 2. Как они получаются?

[zerkms]

Точнее даже не так. Что такое индекс1 и индекс2?

Это какие-то числа, строящиеся на основе данных сущности или на основе входных данных от пользователя?

[NervousSnake]

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

Хотя надо почитать что там выше отписали :)

[zaitsevyan]

как я понял это решение больше подходит для таблиц вида:

product info|parametr1|parametr2|parametr3|…
— а что делать если имеем такую структуру: товар относится к какой-то категории, этой категории назначается от 1 до N параметров по которым будет характеризоваться товар, и в конце концов мы имеем таблицу:

product id|parametr id|value
— и поиск по такому затруднителен…
что можете подсказать не этот случай?
я временно вижу 2 выхода — сделать некую денормализацию бд — вроде как для каждой категории можно создать свою таблицу, но поиск по всему сайту будет затруднителен, но проще по выбраной категрии, или сделать одну большую таблицу в абстрактными колонками для параметров, которые будут заполнятся относительно каждого товара так как надо,
и второй способ: оставить как есть, но поиск будет похож на такой:
SELECT product_id,COUNT(*) as cnt WHERE (parametr_id=A && value=AV) || ((parametr_id=B && value=BV)||… )&& cnt=M, M- количество параметров по которым проверяем

как-то так, но мне кажется все что я написал не лучший выбор

[zerkms]

Запрос с таким where ни одна субд не оптимизирует нормально.

[zaitsevyan]

вот в этом то и проблема и как ее решить красиво и хорошо я еще не нашел/не придумал

[zerkms]

Через UNION

[hemule]

Всегда можно сделать вьюху в качестве промежуточного «индекса».

[zerkms]

Не напасёшься так вьюх на все комбинации. Да и вьюхи никак не оптимизируют выборки, только упрощают запись некоторых запросов (и напрягают оптимизаторы).

[hemule]

Насколько я себе представляю, вьюха нужна одна, которая денормализует вашу нормальную структуру. Не нравится автоматическая вьюха — создайте промежуточную «таблицу-индекс» и заполняйте ее сами, на приложении по расписанию или как-то еще. В любом случае скорость выдачи результата запроса поиска — важнее.

[zerkms]

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

[zerkms]

psman, вот у нас есть 120-битные числа для каждого из товаров. И есть 120-битное число, отражающее поисковый запрос.

Как теперь искать вторым по первому? Пусть, для определённости, база данных у нас оракл или mysql.

[ainu]

Сначала поиск по noSQL базе данных ключа-значение либо по специальной таблице, где индекс — и есть это число.

select all from table where ( сложные параметры поиска ) and id in (Select id from table where filter=<128битноечисло>.)

[ainu]

Вру, простите.
Я использовал следующее решение
Select id from table where filter=<128битноечисло>
Формируется строка, где через запятуюю нужные id, далее
select all from table where and id in (123,23,34,453,463,345,435,345,345) and ( сложные параметры поиска )

[zerkms]

Ничего не изменилось, комментарий ниже :-)

[ainu]

Всегда считал, что
быстрое выражение and медленное выражение
чем
медленное выражение and быстрое выражение
Поэтому сказал что вру.
P.S. У меня такое ощущение, что я упускаю из виду чтото важное.

[zerkms]

Вы упускаете из виду, что запрос Select id from table where filter=<128битноечисло> вернёт пустое множество, потому что, как я показал в примере ниже, искомый фильтр у нас 0x0...01, а в базе нет ни одного товара с абсолютно такими характеристиками.

[zerkms]

Пусть у нас сотовые телефоны, и самым младшим битом будет «если_телефон_слайдер» (1 — да, 0 — нет)

Тогда при выборе этого бита единственным — у нас искомое число будет 0x00...1 (все нули, кроме последнего), в то время как для каждого из товаров, очевидно, другие биты также будут ненулевыми.

Так что подзапрос не вернёт нам ничего.

[hemule]

Не совсем понимаю, как вы производится сравнение с поисковым «запросом» в вашем примере? Как строковое, или числовое что ли?

[zerkms]

Это был ответ на запрос

Select id from table where filter=<128битноечисло>.

Очевидно что в таком запросе 2 числа будут сравниваться как 2 числа.

Потому я и спросил автора, как он предлагает хранить и сравнивать эти данные, в mysql и оракле, для примера.

[hemule]

Понял. Мне кажется автор топика имел в виду какой-то другой способ сравнения.

[zerkms]

Вот поэтому я и задал мой вопрос выше :-)

В mysql, например, есть тип SET, который позволит искать быстро по битовой маске, а вот в оракле аналогов не знаю.

[zerkms]

Плюс не совсем понятно откуда взялся nosql, автор же говорит исключительно о rdbms, не?

[psman]

Select * From tovarhash Where keyhash=«поисковоеЧисло» Само поисковое число с двоичном виде представляет собой 120 битку… 16 байт.
Т.е. мы просто ищем по 16 битному ключу.

[zerkms]

Я выше давал пример, если у нас поисковое число 00000000...1 (ищем по единственной галочке), тогда мы получим пустое множество на выходе, потому что очевидно, что товары будут иметь по несколько единиц в хэше.

[zerkms]

Давайте на примере.
В таблице 3 товара, у каждого товара по 3 характеристики:

name | hash
— Товар1 | 111
Товар2 | 101
Товар3 | 010

Запрос: 001

В результате должны получить первый и второй товар. Запрос Select * From tovarhash Where keyhash=«поисковоеЧисло» вернёт 0 записей.

[psman]

хорошо, у нас поисковое число 00000001b = 1hex

в товарах у нас есть их биты, которые мы прсто запишем числами

26
134
75
245
221
и т.п.

если среди них не поисковому числу, то значит и товара такого нет

[zerkms]

Отчего же нет?

У товара 221 — 11011101 — вот такой вот хэш. Который вполне себе соответствует искомому 00000001b

[psman]

нет. у этого товара чекбоксы стоят как
11011101 = да/да/нет/да/да/да/нет/да

а ищем по 000000001 = нет/нет/нет/../нет/нет/да

все нормально, товар этот нам не подходит, в нем есть то, что нам не нужно

[zerkms]

В начале вы сделали отсылку к яндекс-маркету. А в нём чекбоксы носят опциональный характер и в ЯМ запрос, который я показал выше, выдаст 2 записи.

В случае, если вы строите систему, в которой нужно 100% совпадение — плясок с дополнительным полем вообще не нужно, достаточно просто построить составной индекс поверх всех полей (причём совершенно не важно в каком порядке — потому что они нам нужны все) и база с удовольствием воспользуется этим индексом для поиска.

[psman]

В нем чекбоксы имеют скрытое значение «не важно»

[zerkms]

Угу, это меня с самого начала и сконфузило, судя по всему.

[zerkms]

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

[VBart]

Это хорошо когда схема с самого начала известна. Вы сразу написали, мол есть «ДАНО». А если этого ДАНО нет, и пользователь может добавлять товары с произвольным набором полей, и сам создавать произвольные критерии для отбора.

Вот тогда noSQL и выручают, когда схема не определена.

[can3p]

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

( idx1 & idx2 ) == ( field & idx2 )

[zerkms]

Вы поняли что такое idx1 и idx2? Не могли бы вы рассказать? А то такое ощущение, что это очевидно в этом топике для всех, кроме меня.

[can3p]

В первом индексе хранятся значения чекбоксов всех видов — просто да/нет, и да/нет/пофигу
Во втором индексе нулями отмечены позиции необязательных параметров.

Суть второго индекса в том, что с его помощью мы обнуляем соответствующие позиции как в числе запроса, так и в сравниваемых полях базы данных, чтобы они не влияли на результаты сравнения чисел.

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

[psman]

Выше я расписал суть.
начинается здесь habrahabr.ru/blogs/programming/114113/?reply_to=3677608#comment_3678297

[Albertum]

www.triz-ri.ru/themes/method/creative/creative50.asp#met10
ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ

Есть таблица, с большим количеством полей. И постоянно приходится делать выборку из этой таблицы, с большим количеством условий типа поле1 = значение1, поле2 <> значение2, и т.д.
При таком раскладе запросы становятся очень большими, дольше выполняются. Иногда, при сложных запросах, где объединяются несколько таких «больших подзапросов», база данных просто отказывается выполнять их, ссылаясь на слишком сложный запрос.

[noonesshadow]

Предложенный алгоритм в любом случае требует как минимум одного полного просмотра всех записей…
И это такой велосипед…
Просто, вам не подходит то как база данных (подозреваю, mysql) применяет индексы по умолчанию. Надо в самом SELECT написать порядок применения существующих индексов. И будет счастье :)

[psman]

Фильтр по «чекбоксам» — это всего лишь запрос вида Select * From tovar Where bitkey=«наше число»
остальные все более сложные запросы делаются по существенно уменьшенной таблице.

[zerkms]

А почему не из подзапроса просто?

SELECT * FROM tovar WHERE точные условия AND id IN (SELECT id From tovar Where bitkey=«наше число»)

[zerkms]

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

Если субд не применяет «правильные» индексы, то не нужно считать, что это оптимизатор глупый, нужно взять несколько литров кофе и проанализировать ситуацию. В 99% случаев виноват оказывается всё таки программист или ДБА.

[noonesshadow]

Я точно знаю, что в конкретной описанной ситуации «много индексных столбцов, таблица товаров, в которой в столбцы развернуты все свойства товаров, среди которых много нулевых значений, и требуется быстрая выборка» mysql лажает и нужно указывать индексы вручную. Так что это тот самый 1% :)

[zerkms]

Индексных столбцов много не надо. У автора по N параметров 100% совпадение. Достаточно сделать составной индекс по этим N параметрам.

[noonesshadow]

Индекс один, индексных столбцов много.
Если предметная область такая, что у товаров много свойств и по ним нужно выбирать, то правильно, логично, и др., чтобы БД соответствовала предметной области.
При количестве индексных столбцов больше 63 версии mysql 5.2.* не использовали индекс.

[zerkms]

5.2?

В документации, кстати, навскидку ограничения на число столбцов в составном индексе найти не смог.

[zerkms]

УУУУУУпс, нашёл: An index may consist of up to 16 columns.

Т.е. всё ещё печальнее, чем я предполагал.

Как вы смогли туда 63+ уместить-то? :-)

[noonesshadow]

По умолчанию, без изменения исх. кодов или пересборки:

[noonesshadow]

Да, так вот. PS: ненавижу окошко для публикации комментариев, и ограничение на 5 минут, и невозможность удалить/изменить свой комментарий.

По умолчанию для MyISAM 16 столбцов в индексе / 64 индекса в таблице
Первое значение редактируется в исходниках, я уже точно не помню, где именно, потому что дело было давно, но происходит это относительно просто
Второе меняется конф. опцией --with-max-indexes
Ставил 128/218, все работало, НО больше 63 неправильно определяло индексы :)

[zerkms]

Тогда пардон и ой, вы счастливый обладатель 1% :-)

[noonesshadow]

В вашем алгоритме будет минимум один полный просмотр всех записей. Так что принципиальным критерием для его успеха будет только то, влезет ли вся БД в память (кэшем ли, noSQL ли, неважно). С диском такое чудо, как сравнение по битовой маске, не получится (а от индекса не будет толку, индекс строится для антисимметричного отношения)
Если все влазит в память, и обычные запросы where тупят, тогда проблема только в том, что это MySQL, ему нужно рассказать force index, чего именно вы хотите.

[voidlizard]

Всего 12 миллионов записей и такие извращения? Речь о MySQL? Чекбоксы можно завести в булевые колонки, завести на них индекс, и постгрес будет использовать bitmap scan.
для слайдеров можно использовать просто btree. 12 миллионов записей это очень мало.

[voidlizard]

да, а поскольку народ валом валит, то все атрибуты http-запроса можно отсортировать по весу, взять или не брать от него md5 или sha1 и кэшировать в мемкэшед или типа того, что бы даж до СУБД не доводить. более или менее популярные комбинации попадут рано или поздно в кэш, и не будут грузить сервер вообще.

[worker4food]

Автор почти переизобрел фильтр Блума.