ведущий разраб, тимлид, больной убл… в общем
0,1
рейтинг
20 февраля 2011 в 00:14

Разработка → Ищем быстро, еще быстрее

Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».

Я знаю, что на Хабре, да и вообще есть много сторонников noSQL решений (сам не без греха), но все же я сторонник сначала подумать, а уже потом выбирать решение.

Итак, что имеем в «ДАНО»
  • Имеем 120 чекбоксов — вариант 1/0
  • Имеем 30 «радио» с выбором «да/нет/не важно»
  • Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
  • Имеем самое главное: 12 млн записей в БД.
  • Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.


Истерика наступала от понимания, что надо обрабатывать более 100 запросов в секунду, а для этого придется продать «трешку» с видом на Кремль и купить еще железа.

Итак, начинаем думать, как сэкономить кучу денег и часть положить в свой карман в виде премии.
Хочу сразу заметить, мы не задаемся целью СРАЗУ получить список нужных строк из базы. Нам нужно сделать префильтрацию для ускорения процесса поиска и фильтрации.

Чекбоксы


Для начала все наши чекбоксы, которые имеют всего 2 варианта значения, мы преобразуем в биты и сгруппируем в одно «число». В нашем случае данное число будет 120 битным (128 битным для ровного счета). Это будет наш первый «индекс». По нему мы всегда сможем отфильтровать те товары, которые соответствуют нашим условиям. На практике, в среднем, таких товаров не более 10 тыс на всю базу. Остальные параметры можно смотреть уже только в этих 10 тыс товарах, а не «лопатить» всю базу.

Диапазоны


Любой диапазон (рост, вес, талия, объем бюста) можно разбить на интервалы и пронумеровать их. Поделим на 256 частей. Цифра взята «с потолка». В любом случае мы для диапазона 100$ — 1200$ мы получим 2 числа. Если взять на 1 — 100$ при максимуме в 25500$, то наш диапазон мы можем записать как 2|12 — по факту это 16 битное число. Таких чисел у нас будет по числу возможных диапазонов. Если их менее нескольких, то на этом мы остановимся, если их 100-10000, то все сложнее. Мы не можем адекватно быстро искать по 200-20000 битному ключу. Да и не станем, мы просто высчитаем его md5, а для ускорения процесса еще и преобразуем все в 128 битное число (каких то жалких 16 байт). В сочетании с множеством «чекбоксов» мы получим еще более точную выборку.

Да/нет/не важно


Алгоритм поиска данных значений с доп. параметром «не важно» почти похож на вариант с чекбоксами, за исключением того, что мы в 1 индекс записываем только да/нет (и 0, при выборе «не важно»). Во второй индекс будем ставить 0 при варианте «не важно» и 1 при любом другом.

Итого получаем 2 индекса:
1 индекс: 01010000001010101010001
2 индекс: 01111101110111101110111

Домашним заданием будет построить через Xor|And|Or запрос в котором мы обнулим все незначащие биты по индекс2 и сравним с индекс1.

Итак, мы из 12 млн записей нашли 0-100-500 подходящих по условиям. Именно эти записи уже стоит проверять целиком (120 битное поле чекбоксов, диапазон и множество «Да/нет/не важно»). Согласитесь, что полная проверка среди пары сотен строк — это намного быстрее, чем полноценный поиск.

….

Profit!!!


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

Подобный алгоритм Используется нами и в фильтре текстов по шинглам, когда из контрольной суммы получаем 32 битное число, которые сравнивать быстрее, чем 128 битные.
Подобная методика работает и в одной специализированной системе хранения документов, что позволяет в микросекунды найти в 2.2Gb базе текстов ссылки на документы, где находится искомое слово или фраза. Но, об этом чуть подробнее в другой статье.
@psman
карма
60,0
рейтинг 0,1
ведущий разраб, тимлид, больной убл… в общем
Реклама помогает поддерживать и развивать наши сервисы

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

Самое читаемое Разработка

Комментарии (117)

  • +3
    А ларчик просто открывался!
    Молодцы.
  • +19
    Должен заметить, что подход далеко не нов и оригинален, используется повсеместно. Однако автору зачет и плюс в карму за доходчивое объяснение внутренних процессов высоко нагруженных баз.
  • +1
    Для меня, когда увидел в Q/A, было озарением, всегда считал, что noSQL — это для хранения всякого рода голосов за комментарии, вёздочек добавлено в избранное и твитов, не более.
    Метод прост и прекрасен.
    • 0
      Доп. вопрос: когда имеется в виду MemTable, какое ПО подразумевается?
      memcached тут никак не поможет, там могут пропадать отдельные элементы индекса, да и не для хранения он создан.
      • +3
        Может быть это что-то подобное MySQL Memory storage engine dev.mysql.com/doc/refman/5.0/en/memory-storage-engine.html
      • +1
        Если я правильно понял, то автор как раз использует SQL базу данных, а под MemTable подразумевает временную таблицу, хранимую в памяти. Это умеют большинство реляционных СУБД, не только MySQL.
        Сразу отвечая на ваш комментарий ниже, процесс обработки получается такой:
        Большая таблица с данными → Предварительная (неточная) фильтрация → Маленькая временная таблица в памяти → Точная фильтрация → Вывод результатов.
        • 0
          Этот процесс подходит для обработки, например, диапазонов значений.
          Я имел в виду ситуацию с Да/Нет/Не важно. В этом случае таблица в памяти будет достаточно большой, например, при запросе сотовых телефонов без тачскрина.
          • +2
            Как правило, таких критериев указывается несколько. Поэтому очень легко убедиться, что количество данных после предварительной фильтрации будет на один-два порядка меньше даже в случае с несколькими критериями.

            Но даже в ситуации, когда критерии очень размытые и предварительную фильтрацию прошло довольно много данных, точную фильтрацию нужно делать там же в БД, поскольку нам не потребуется тратить ресурсы на передачу огромного массива данных в другое приложение, а так же БД изначально оптимизируются для обработки больших объемов данных.
        • +1
          Вот это как раз скользкий момент в статье. Непотяно зачем данные выгребать-сохранять в отдельную таблицу, если субд и так после отсечения откровенно неподходящих вариантов может выполнить скан по оставшимся (который в 100% случаев будет быстрее перезаписи в отдельную таблицу и скану по ней).
        • 0
          Да, все верно.
          Неточная фильтрация отсеивает много изначально неверных строк, что сильно ускоряет дальнейшие работы.
          • 0
            То что она отсеивает и так понятно, просто непонятно ваше предложение вычитывать все данные в память. Зачем, если субд и сама может выполнить скан по отсечённому множеству?
            • 0
              В моей конкретной реализации в хранимой процедуре создавалась временная таблица в нее сваливались все данные и дальнейшая работа была с этой таблицей. После выполнения поиска она уничтожалась.
              • 0
                Эм, в чём смысл? Вы вычитывали из таблицы ворох данных, которые субд могла вычитать сразу, выдав непосредственно результат?

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

                Но это уже не принципиально, мне гораздо интереснее ниже про поиск :-) Ответите? :-)
                • 0
                  Выборка данных путем запроса с одним/двумя условиями намного быстрее, чем километровый запрос.

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

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

                      или

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

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

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

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

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

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

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

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

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

                                t1 = 1 AND t2 = 0 AND t3 = 1

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

                                hashfield = 101

                                потому что оптимизатор сделает ту же самую работу, что и вы делаете вручную.
                                • 0
                                  Хотелось бы проверить на практике, если честно. Есть повод написать вторую статью :)
                                • 0
                                  и мне вот тоже интересно в чем разница
                                  • 0
                                    В понедельник найду время для полноценного теста
                                  • 0
                                    Не все БД умеют делать составные индексы. А составные и функциональные индексы скорее всего заменят все или большую часть этих уловок.
  • 0
    И еще я правильно понимаю, что запрос, сравнивающий, индексы (домашнее задание), будет делать уже скрипт-обработчик, а не БД?
    • 0
      А не обязательно. По факту sql умеет работать с логическими операциями.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Да, тоже не понял. Уважаемый автор, можно нам немного подробнее? :-)
      • 0
        можно :)
        я просто не так подробно и понятно расписал.

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

        100000010101 — tovar

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

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

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

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

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

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

          100000010101 — tovar

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

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

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

          Ничего не понял :-( Переходы от findkey до findmask и далее до ещё одного (?!?!?) findkey какие-то неочевидные :-S
          • 0
            Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
            findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.

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

            Соответственно проверка будет (tovar AND findmask = findkey)
            • +1
              Это медленная проверка, которая приведёт к фуллскану.
              • 0
                Фулскан из 10 тыс строк, вместо 12-30-100 млн строк как было бы без префильтра? да без проблем.
                • 0
                  Так если мы делаем фулскан, то зачем извращения?
                  • 0
                    что быстрее: фулскан 10 млн строк или 10 тыс?
                    • 0
                      зачем извращения кроме первого (объединения кучи флажков в ключ)?
            • 0
              Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
              findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.

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

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

              Эм, не совпадает. Если findkey = 1000хх00хххх, тогда findmask согласно вашему описанию должно быть не 111100110000, а 000011001111
              • 0
                Сорри, торможу, но сути не меняет.
                Нам надо во всех незначащих битах сбросить в нули (или единицы, как угодно и удобнее) все, что имеет значение «не важно»

                По сути мы делаем вид, будто вместо «не важно» мы выбрали «нет», но благодаря битовой маске мы все ответы «да» в товаре сбрасываем по ней в ответы «нет».
        • НЛО прилетело и опубликовало эту надпись здесь
          • +1
            Нет, поиск по этому хэшу автор предлагает выполнять в виде вычисления, которое на уровне базы превращается в фуллскан :-S
            • 0
              Да, фулскан из префильтрованных ранее данных.
              Даже если делать выборку по «да/нет/не важно» по честному, то выборка по чекбоксам уменьшает число строк, в которых надо это сделать.
            • НЛО прилетело и опубликовало эту надпись здесь
              • +1
                Вот что я выше и пытаюсь сказать, что where field1=… and field2=… будет работать не хуже
                • НЛО прилетело и опубликовало эту надпись здесь
                  • +1
                    Размер базы увеличится, но примерно на столько же, на сколько он увеличится за счёт добавления в индекс вычисленного вручную хэша, как предлагает автор.

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

                  пнредположим, что чекбокса всего два. в любом случае 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 с запросом получается моментально из значения чекбокса и знаемой нами инфы о том, какого типа чекбокс (пустой=пофиг или пустой=НЕТ) имеем.
                  • 0
                    разницу в скорости поиска по тексту и логические операции с числом — несоизмеримы по скорости.
                    AND делается всего на 1 поле. 1 поле на 1 строку.

                    • 0
                      если у вас 100 чекбоксов = 100 полей в таблице и AND делается фактически (как бы вы не вставляли промежуточные таблицы) 100 раз.
                      LIKE% дает вам таблицу с 1 текстовым полем, возможность использовать селекты (а не только чекбоксы — пишете кроме 0-1 любые исмволы соответсвенно занчению поля селекта), и главное что 1 сравнение LIKE% на 100символьную строку ничуть не медленнее 100 сравнений однобитных полей — попробуйте сами
                      • 0
                        LIKE% это не фуллтекст поиск — де-факто сравниваются (в зависимости от кодировки) 8-16битные chars. У вас 1битные да-нет, но их — 100 полей! Сделайте тест.
                        • 0
                          Вы видно не допоняли. Я все чекбоксы объединил в одно Х битное число.
                          AND выполняется одно на 1 строку в уже профильтрованной выборке.
                          • 0
                            по факту нет 100 полей, есть 1 число с разрядность равному числу чекбоксов + дополнение до кратности 8 (что бы побайтно считать)
                            по факту 100 чекбоксов — это int(13)
                            • 0
                              угу, это правильно и хорошо. но это использование временной таблицы (то есть два последовательных SELECTа) при этом нисколько не делает поиск быстрее, чем LIKE% по всей таблице 1 раз. Кроме того, в последнем случае вы групируете ВСЕ чекбоксы (включая те которые имеют значение «все равно») в одну строку.
                              Ведь фактически вы создаете мемтэйбл только потому, что не можете сразу фильтровать поля с опцией «все равно». А это принуждает вас к искуственной конструкции со вторым SELECTом по промежуточной таблице, который не нужен.
                              Кол-во сравнений при фильтрации LIKE% сделает такое же как при побитовых операциях.
                              И во всех случаях как правильно указал г-н zerksm скорость будет такая же (а с двумя таблицами даже медленнее) как с where and..and по 100 полям.
                              • 0
                                Создание «промежуточной» таблицы нужно для того, что бы в нее свалить частично отфильтрованные данные и уже по ним делать дальнейший поиск по прочим параметрам.

                                Тест будет и по этому поводу сделаю отдельное дополнение
          • 0
            100000010101 -товар

            100000000000 — ищем (findkey)

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

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

              Опять же — товар 100000010101 выбран уже по результатам чекбоксов и поиска по 100% совпадению??
              • 0
                если мы ищем 100000000000
                и нет «незначащих битов», то товар 100000010101 нам не подходит

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

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

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

                    Сначала мы отбираем по чекбоксам (получаем на порядки меньшее число строк), потом по радио (да/нет/не важно) (получаем еще меньшее число) и потом по диапазонам (из остатка строк, можно делать и «по честному»)
    • 0
      Если я правильно поняла, то схема такая:
      — если нужно выбрать все «неважно», то надо только проверить индекс 2 на = 0
      — если нужно «нет», то индекс1 = 1, индекс2 = 0
      — если нужно «да», то индекс2 = 1, индекс2 = 1
      • 0
        Тогда нужно подробнее остановиться на построении индекса1 и 2. Как они получаются?
        • +1
          Точнее даже не так. Что такое индекс1 и индекс2?

          Это какие-то числа, строящиеся на основе данных сущности или на основе входных данных от пользователя?
          • 0
            Я так понимаю, сущности.
            А данные пользователя — это соответствующая битовая маска уже.

            Хотя надо почитать что там выше отписали :)
  • 0
    как я понял это решение больше подходит для таблиц вида:

    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- количество параметров по которым проверяем

    как-то так, но мне кажется все что я написал не лучший выбор
    • +1
      Запрос с таким where ни одна субд не оптимизирует нормально.
      • 0
        вот в этом то и проблема и как ее решить красиво и хорошо я еще не нашел/не придумал
        • 0
          Через UNION
    • 0
      Всегда можно сделать вьюху в качестве промежуточного «индекса».
      • 0
        Не напасёшься так вьюх на все комбинации. Да и вьюхи никак не оптимизируют выборки, только упрощают запись некоторых запросов (и напрягают оптимизаторы).
        • 0
          Насколько я себе представляю, вьюха нужна одна, которая денормализует вашу нормальную структуру. Не нравится автоматическая вьюха — создайте промежуточную «таблицу-индекс» и заполняйте ее сами, на приложении по расписанию или как-то еще. В любом случае скорость выдачи результата запроса поиска — важнее.
          • +1
            для денормализации не нужны вьюхи, с ними потом сложнее будет. Удобнее сделать вычислимое поле (в субд, в которых оно есть) или вычислять в триггере.
  • +1
    psman, вот у нас есть 120-битные числа для каждого из товаров. И есть 120-битное число, отражающее поисковый запрос.

    Как теперь искать вторым по первому? Пусть, для определённости, база данных у нас оракл или mysql.
    • 0
      Сначала поиск по noSQL базе данных ключа-значение либо по специальной таблице, где индекс — и есть это число.

      select all from table where ( сложные параметры поиска ) and id in (Select id from table where filter=<128битноечисло>.)
      • 0
        Вру, простите.
        Я использовал следующее решение
        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 ( сложные параметры поиска )
        • 0
          Ничего не изменилось, комментарий ниже :-)
          • 0
            Всегда считал, что
            быстрое выражение and медленное выражение
            чем
            медленное выражение and быстрое выражение
            Поэтому сказал что вру.
            P.S. У меня такое ощущение, что я упускаю из виду чтото важное.
            • 0
              Вы упускаете из виду, что запрос Select id from table where filter=<128битноечисло> вернёт пустое множество, потому что, как я показал в примере ниже, искомый фильтр у нас 0x0...01, а в базе нет ни одного товара с абсолютно такими характеристиками.
      • 0
        Пусть у нас сотовые телефоны, и самым младшим битом будет «если_телефон_слайдер» (1 — да, 0 — нет)

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

        Так что подзапрос не вернёт нам ничего.
        • 0
          Не совсем понимаю, как вы производится сравнение с поисковым «запросом» в вашем примере? Как строковое, или числовое что ли?
          • 0
            Это был ответ на запрос

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

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

            Потому я и спросил автора, как он предлагает хранить и сравнивать эти данные, в mysql и оракле, для примера.
            • 0
              Понял. Мне кажется автор топика имел в виду какой-то другой способ сравнения.
              • +1
                Вот поэтому я и задал мой вопрос выше :-)

                В mysql, например, есть тип SET, который позволит искать быстро по битовой маске, а вот в оракле аналогов не знаю.
      • 0
        Плюс не совсем понятно откуда взялся nosql, автор же говорит исключительно о rdbms, не?
    • 0
      Select * From tovarhash Where keyhash=«поисковоеЧисло» Само поисковое число с двоичном виде представляет собой 120 битку… 16 байт.
      Т.е. мы просто ищем по 16 битному ключу.

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

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

          Запрос: 001

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

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

          26
          134
          75
          245
          221
          и т.п.

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

            У товара 221 — 11011101 — вот такой вот хэш. Который вполне себе соответствует искомому 00000001b
            • 0
              нет. у этого товара чекбоксы стоят как
              11011101 = да/да/нет/да/да/да/нет/да

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

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

                В случае, если вы строите систему, в которой нужно 100% совпадение — плясок с дополнительным полем вообще не нужно, достаточно просто построить составной индекс поверх всех полей (причём совершенно не важно в каком порядке — потому что они нам нужны все) и база с удовольствием воспользуется этим индексом для поиска.
                • 0
                  В нем чекбоксы имеют скрытое значение «не важно»
                  • 0
                    Угу, это меня с самого начала и сконфузило, судя по всему.
    • 0
      Я обычно как-то так делаю:
      where (товар & запрос)=запрос
      • 0
        Такой запрос никак не может быть оптимизирован субд, потому что поле участвует в выражении — привет фуллскан, а в статье, судя по всему, говорится о быстрых запросах.
        • 0
          Угу, Вы правы. Но сдается мне без манипуляций с этим полем задачу не решить.

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

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

    ( idx1 & idx2 ) == ( field & idx2 )
    • 0
      Вы поняли что такое idx1 и idx2? Не могли бы вы рассказать? А то такое ощущение, что это очевидно в этом топике для всех, кроме меня.
      • 0
        В первом индексе хранятся значения чекбоксов всех видов — просто да/нет, и да/нет/пофигу
        Во втором индексе нулями отмечены позиции необязательных параметров.

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

        Но я вполне вероятно ошибаюсь, т.к. в этом случае получается не простое сравнение чисел, а еще вдобавок операции над ними, что обещает совсем другую производительность.
  • +1
    www.triz-ri.ru/themes/method/creative/creative50.asp#met10
    ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ

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

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

        SELECT * FROM tovar WHERE точные условия AND id IN (SELECT id From tovar Where bitkey=«наше число»)
    • 0
      Ужасный совет. Хинты для индексов — последнее, к чему нужно обращаться.

      Если субд не применяет «правильные» индексы, то не нужно считать, что это оптимизатор глупый, нужно взять несколько литров кофе и проанализировать ситуацию. В 99% случаев виноват оказывается всё таки программист или ДБА.
      • +1
        Я точно знаю, что в конкретной описанной ситуации «много индексных столбцов, таблица товаров, в которой в столбцы развернуты все свойства товаров, среди которых много нулевых значений, и требуется быстрая выборка» mysql лажает и нужно указывать индексы вручную. Так что это тот самый 1% :)
        • 0
          Индексных столбцов много не надо. У автора по N параметров 100% совпадение. Достаточно сделать составной индекс по этим N параметрам.
          • 0
            Индекс один, индексных столбцов много.
            Если предметная область такая, что у товаров много свойств и по ним нужно выбирать, то правильно, логично, и др., чтобы БД соответствовала предметной области.
            При количестве индексных столбцов больше 63 версии mysql 5.2.* не использовали индекс.
            • 0
              5.2?

              В документации, кстати, навскидку ограничения на число столбцов в составном индексе найти не смог.
              • 0
                УУУУУУпс, нашёл: An index may consist of up to 16 columns.

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

                Как вы смогли туда 63+ уместить-то? :-)
              • 0
                По умолчанию, без изменения исх. кодов или пересборки:
                • 0
                  Да, так вот. PS: ненавижу окошко для публикации комментариев, и ограничение на 5 минут, и невозможность удалить/изменить свой комментарий.

                  По умолчанию для MyISAM 16 столбцов в индексе / 64 индекса в таблице
                  Первое значение редактируется в исходниках, я уже точно не помню, где именно, потому что дело было давно, но происходит это относительно просто
                  Второе меняется конф. опцией --with-max-indexes
                  Ставил 128/218, все работало, НО больше 63 неправильно определяло индексы :)
                  • 0
                    Тогда пардон и ой, вы счастливый обладатель 1% :-)
  • 0
    В вашем алгоритме будет минимум один полный просмотр всех записей. Так что принципиальным критерием для его успеха будет только то, влезет ли вся БД в память (кэшем ли, noSQL ли, неважно). С диском такое чудо, как сравнение по битовой маске, не получится (а от индекса не будет толку, индекс строится для антисимметричного отношения)
    Если все влазит в память, и обычные запросы where тупят, тогда проблема только в том, что это MySQL, ему нужно рассказать force index, чего именно вы хотите.
  • 0
    Всего 12 миллионов записей и такие извращения? Речь о MySQL? Чекбоксы можно завести в булевые колонки, завести на них индекс, и постгрес будет использовать bitmap scan.
    для слайдеров можно использовать просто btree. 12 миллионов записей это очень мало.
    • +1
      да, а поскольку народ валом валит, то все атрибуты http-запроса можно отсортировать по весу, взять или не брать от него md5 или sha1 и кэшировать в мемкэшед или типа того, что бы даж до СУБД не доводить. более или менее популярные комбинации попадут рано или поздно в кэш, и не будут грузить сервер вообще.
  • 0
    Автор почти переизобрел фильтр Блума.

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