Comments 117
А ларчик просто открывался!
Молодцы.
Молодцы.
Должен заметить, что подход далеко не нов и оригинален, используется повсеместно. Однако автору зачет и плюс в карму за доходчивое объяснение внутренних процессов высоко нагруженных баз.
Для меня, когда увидел в Q/A, было озарением, всегда считал, что noSQL — это для хранения всякого рода голосов за комментарии, вёздочек добавлено в избранное и твитов, не более.
Метод прост и прекрасен.
Метод прост и прекрасен.
Доп. вопрос: когда имеется в виду MemTable, какое ПО подразумевается?
memcached тут никак не поможет, там могут пропадать отдельные элементы индекса, да и не для хранения он создан.
memcached тут никак не поможет, там могут пропадать отдельные элементы индекса, да и не для хранения он создан.
Может быть это что-то подобное MySQL Memory storage engine dev.mysql.com/doc/refman/5.0/en/memory-storage-engine.html
Если я правильно понял, то автор как раз использует SQL базу данных, а под MemTable подразумевает временную таблицу, хранимую в памяти. Это умеют большинство реляционных СУБД, не только MySQL.
Сразу отвечая на ваш комментарий ниже, процесс обработки получается такой:
Большая таблица с данными → Предварительная (неточная) фильтрация → Маленькая временная таблица в памяти → Точная фильтрация → Вывод результатов.
Сразу отвечая на ваш комментарий ниже, процесс обработки получается такой:
Большая таблица с данными → Предварительная (неточная) фильтрация → Маленькая временная таблица в памяти → Точная фильтрация → Вывод результатов.
Этот процесс подходит для обработки, например, диапазонов значений.
Я имел в виду ситуацию с Да/Нет/Не важно. В этом случае таблица в памяти будет достаточно большой, например, при запросе сотовых телефонов без тачскрина.
Я имел в виду ситуацию с Да/Нет/Не важно. В этом случае таблица в памяти будет достаточно большой, например, при запросе сотовых телефонов без тачскрина.
Как правило, таких критериев указывается несколько. Поэтому очень легко убедиться, что количество данных после предварительной фильтрации будет на один-два порядка меньше даже в случае с несколькими критериями.
Но даже в ситуации, когда критерии очень размытые и предварительную фильтрацию прошло довольно много данных, точную фильтрацию нужно делать там же в БД, поскольку нам не потребуется тратить ресурсы на передачу огромного массива данных в другое приложение, а так же БД изначально оптимизируются для обработки больших объемов данных.
Но даже в ситуации, когда критерии очень размытые и предварительную фильтрацию прошло довольно много данных, точную фильтрацию нужно делать там же в БД, поскольку нам не потребуется тратить ресурсы на передачу огромного массива данных в другое приложение, а так же БД изначально оптимизируются для обработки больших объемов данных.
Вот это как раз скользкий момент в статье. Непотяно зачем данные выгребать-сохранять в отдельную таблицу, если субд и так после отсечения откровенно неподходящих вариантов может выполнить скан по оставшимся (который в 100% случаев будет быстрее перезаписи в отдельную таблицу и скану по ней).
Да, все верно.
Неточная фильтрация отсеивает много изначально неверных строк, что сильно ускоряет дальнейшие работы.
Неточная фильтрация отсеивает много изначально неверных строк, что сильно ускоряет дальнейшие работы.
То что она отсеивает и так понятно, просто непонятно ваше предложение вычитывать все данные в память. Зачем, если субд и сама может выполнить скан по отсечённому множеству?
В моей конкретной реализации в хранимой процедуре создавалась временная таблица в нее сваливались все данные и дальнейшая работа была с этой таблицей. После выполнения поиска она уничтожалась.
Эм, в чём смысл? Вы вычитывали из таблицы ворох данных, которые субд могла вычитать сразу, выдав непосредственно результат?
Вы теряли на дополнительном чтении/записи время же.
Но это уже не принципиально, мне гораздо интереснее ниже про поиск :-) Ответите? :-)
Вы теряли на дополнительном чтении/записи время же.
Но это уже не принципиально, мне гораздо интереснее ниже про поиск :-) Ответите? :-)
Выборка данных путем запроса с одним/двумя условиями намного быстрее, чем километровый запрос.
по поиску отвечаю в порядке очередности :)
по поиску отвечаю в порядке очередности :)
Очень спорно. Оптимизатор ищет лучший план и выполняет его. А лучший план это отсечение подходящих полей, поиск которых может быть выполнен с использованием индексов, плюс скан по оставшимся. Т.е. ровно то же самое, что вы и сделали вручную (минус время, которое вы потратили на чтение-запись в новую таблицу).
допустим у нас 250 показателей в таблице, пусть даже просто битовых
что будет быстрее?
select * from tovar where key=5648
или
select * from tovar where (a1=true) and (a2=false) and… and (a250=true)
что будет быстрее?
select * from tovar where key=5648
или
select * from tovar where (a1=true) and (a2=false) and… and (a250=true)
1. Я говорил про второй этап выполнения запроса, когда индексы БД уже ничего сделать не могут
2. Умный оптимизатор так и так склеит все ключи, чтобы искать по индексу (если B-Tree) или просто возьмёт как есть (если bitmap). Разница будет несущественная.
2. Умный оптимизатор так и так склеит все ключи, чтобы искать по индексу (если B-Tree) или просто возьмёт как есть (если bitmap). Разница будет несущественная.
пока оптимизатор клеит, мой вариант уже в выборке :)
согласитесь, что сделать 1 доп ключ — это время 5 минут.
Чем больше база, тем существеннее любые «леваки»
Я преклоняю голову перед создателями SQL, но все же частные случаи работают намного быстрее общих решений.
В задаче отсеивать неуникальные тексты по шинглам частный случай быстрее решения в лоб на… ну 215 тыс текстов по 1-1.2 килобайта отсеивается за 1 секунду на неттопе на атоме330 и без расхода кучи памяти. Решение в лоб — это около 27-35 минут на фильтрацию 100 вариантов статей между собой.
согласитесь, что сделать 1 доп ключ — это время 5 минут.
Чем больше база, тем существеннее любые «леваки»
Я преклоняю голову перед создателями SQL, но все же частные случаи работают намного быстрее общих решений.
В задаче отсеивать неуникальные тексты по шинглам частный случай быстрее решения в лоб на… ну 215 тыс текстов по 1-1.2 килобайта отсеивается за 1 секунду на неттопе на атоме330 и без расхода кучи памяти. Решение в лоб — это около 27-35 минут на фильтрацию 100 вариантов статей между собой.
Не совсем вас понимаю :-(
У вас везде в примерах используется полный набор атрибутов объекта. А по полному набору поиск «в лоб» будет работать точно так же, как и поиск по хэшу. Ровно потому, что субд сделает ту же самую работу, что делаете и вы, вручную.
У вас везде в примерах используется полный набор атрибутов объекта. А по полному набору поиск «в лоб» будет работать точно так же, как и поиск по хэшу. Ровно потому, что субд сделает ту же самую работу, что делаете и вы, вручную.
Все делается поэтапно.
имеем 10 млн строк
сделали фильтр по чекбоксам да/нет
получили 10 тыс строк
вот на этом моменте в принципе можно и остановится. мы УЖЕ имеем в префильтрованной темповой таблице данных на порядки меньше исходных. В них найти нужное «в лоб» можно без большого ущерба для производительности.
имеем 10 млн строк
сделали фильтр по чекбоксам да/нет
получили 10 тыс строк
вот на этом моменте в принципе можно и остановится. мы УЖЕ имеем в префильтрованной темповой таблице данных на порядки меньше исходных. В них найти нужное «в лоб» можно без большого ущерба для производительности.
Я это прекрасно понимаю. И говорю о другом:
что в случае поиска по 100% совпадению (оператор «равно») поиск по списку аттрибутов типа:
t1 = 1 AND t2 = 0 AND t3 = 1
будет таким же эффективным, как и
hashfield = 101
потому что оптимизатор сделает ту же самую работу, что и вы делаете вручную.
что в случае поиска по 100% совпадению (оператор «равно») поиск по списку аттрибутов типа:
t1 = 1 AND t2 = 0 AND t3 = 1
будет таким же эффективным, как и
hashfield = 101
потому что оптимизатор сделает ту же самую работу, что и вы делаете вручную.
И еще я правильно понимаю, что запрос, сравнивающий, индексы (домашнее задание), будет делать уже скрипт-обработчик, а не БД?
UFO just landed and posted this here
Да, тоже не понял. Уважаемый автор, можно нам немного подробнее? :-)
можно :)
я просто не так подробно и понятно расписал.
Допустим у нас есть в базу товар
100000010101 — tovar
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey
мы должны взять tovar и сбросить у него в 0 все биты, которые отмечены в findmask а потом сравнить с findkey
Мы отсеиваем бОльшую часть товаров, у которых параметры точно не равны нашим заданным. При этом те параметры, что „не важны“ мы не учитываем.
я просто не так подробно и понятно расписал.
Допустим у нас есть в базу товар
100000010101 — tovar
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey
мы должны взять tovar и сбросить у него в 0 все биты, которые отмечены в findmask а потом сравнить с findkey
Мы отсеиваем бОльшую часть товаров, у которых параметры точно не равны нашим заданным. При этом те параметры, что „не важны“ мы не учитываем.
Допустим у нас есть в базу товар
100000010101 — tovar
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey
Ничего не понял :-( Переходы от findkey до findmask и далее до ещё одного (?!?!?) findkey какие-то неочевидные :-S
100000010101 — tovar
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Искать мы будем по «поисковой битовой маске, но все „незначащие“ отмечаем как нули
получаем
100000000000 — findkey
Ничего не понял :-( Переходы от findkey до findmask и далее до ещё одного (?!?!?) findkey какие-то неочевидные :-S
Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.
нам надо по findmask сбросить в 0 все биты в ключе товара
Проще всего это сделать через AND
Соответственно проверка будет (tovar AND findmask = findkey)
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.
нам надо по findmask сбросить в 0 все биты в ключе товара
Проще всего это сделать через AND
Соответственно проверка будет (tovar AND findmask = findkey)
Это медленная проверка, которая приведёт к фуллскану.
Findkey — битовая маска с 1 при ответе «да» и 0 при ответе «нет» или «не важно»
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Эм, не совпадает. Если findkey = 1000хх00хххх, тогда findmask согласно вашему описанию должно быть не 111100110000, а 000011001111
findmask — битовая маска, где 1 при ответе «не важно» и 0 при любом другом.
нам надо найти
1000хх00хххх — findkey
соответственно битовая маска будет
111100110000 — findmask
Эм, не совпадает. Если findkey = 1000хх00хххх, тогда findmask согласно вашему описанию должно быть не 111100110000, а 000011001111
Сорри, торможу, но сути не меняет.
Нам надо во всех незначащих битах сбросить в нули (или единицы, как угодно и удобнее) все, что имеет значение «не важно»
По сути мы делаем вид, будто вместо «не важно» мы выбрали «нет», но благодаря битовой маске мы все ответы «да» в товаре сбрасываем по ней в ответы «нет».
Нам надо во всех незначащих битах сбросить в нули (или единицы, как угодно и удобнее) все, что имеет значение «не важно»
По сути мы делаем вид, будто вместо «не важно» мы выбрали «нет», но благодаря битовой маске мы все ответы «да» в товаре сбрасываем по ней в ответы «нет».
UFO just landed and posted this here
Нет, поиск по этому хэшу автор предлагает выполнять в виде вычисления, которое на уровне базы превращается в фуллскан :-S
Да, фулскан из префильтрованных ранее данных.
Даже если делать выборку по «да/нет/не важно» по честному, то выборка по чекбоксам уменьшает число строк, в которых надо это сделать.
Даже если делать выборку по «да/нет/не важно» по честному, то выборка по чекбоксам уменьшает число строк, в которых надо это сделать.
UFO just landed and posted this here
Вот что я выше и пытаюсь сказать, что where field1=… and field2=… будет работать не хуже
UFO just landed and posted this here
вы абсолютно правы.
пнредположим, что чекбокса всего два. в любом случае 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=0 и чекбокс2=1 запроса например? Кол-во сравнений значений полей ваш выбор во временную таблицу НЕ уменьшит никак. Аргумент о том, что из таблицы отсеяных по первому запросу 1000 строк выбрать чекбокс2=1 быстрее, чем из всей таблицы неверен — чтобы выбрать 1000 отсеянных вам все равно нужно сначала выбрать из 1000000 товары с чекбокс1=0. Фактически вы делаете два последовательных запроса — один к большой таблице, второй — к маленькой. Запросить большую с AND как минимум не медленнее.
почему не сделать маску вида 11_00_01… где 1 -обязательно ДА (например, вай-фай нужен обязательно), 0 — обязательно НЕТ (без блютуса), _ — неважно (карта памяти пофиг). Вместо кучи полей в таблице товаров пишем одно text или VARCHAR в зависимости от кол-ва чекбоксов. В нем строка длины = кол-во чекбоксов 010101..0101. Ищем LIKE%. Должно быть не медленнее как минимум чем AND на кучу полей (ибо % только справа). Маска из POST с запросом получается моментально из значения чекбокса и знаемой нами инфы о том, какого типа чекбокс (пустой=пофиг или пустой=НЕТ) имеем.
разницу в скорости поиска по тексту и логические операции с числом — несоизмеримы по скорости.
AND делается всего на 1 поле. 1 поле на 1 строку.
AND делается всего на 1 поле. 1 поле на 1 строку.
если у вас 100 чекбоксов = 100 полей в таблице и AND делается фактически (как бы вы не вставляли промежуточные таблицы) 100 раз.
LIKE% дает вам таблицу с 1 текстовым полем, возможность использовать селекты (а не только чекбоксы — пишете кроме 0-1 любые исмволы соответсвенно занчению поля селекта), и главное что 1 сравнение LIKE% на 100символьную строку ничуть не медленнее 100 сравнений однобитных полей — попробуйте сами
LIKE% дает вам таблицу с 1 текстовым полем, возможность использовать селекты (а не только чекбоксы — пишете кроме 0-1 любые исмволы соответсвенно занчению поля селекта), и главное что 1 сравнение LIKE% на 100символьную строку ничуть не медленнее 100 сравнений однобитных полей — попробуйте сами
LIKE% это не фуллтекст поиск — де-факто сравниваются (в зависимости от кодировки) 8-16битные chars. У вас 1битные да-нет, но их — 100 полей! Сделайте тест.
Вы видно не допоняли. Я все чекбоксы объединил в одно Х битное число.
AND выполняется одно на 1 строку в уже профильтрованной выборке.
AND выполняется одно на 1 строку в уже профильтрованной выборке.
по факту нет 100 полей, есть 1 число с разрядность равному числу чекбоксов + дополнение до кратности 8 (что бы побайтно считать)
по факту 100 чекбоксов — это int(13)
по факту 100 чекбоксов — это int(13)
угу, это правильно и хорошо. но это использование временной таблицы (то есть два последовательных SELECTа) при этом нисколько не делает поиск быстрее, чем LIKE% по всей таблице 1 раз. Кроме того, в последнем случае вы групируете ВСЕ чекбоксы (включая те которые имеют значение «все равно») в одну строку.
Ведь фактически вы создаете мемтэйбл только потому, что не можете сразу фильтровать поля с опцией «все равно». А это принуждает вас к искуственной конструкции со вторым SELECTом по промежуточной таблице, который не нужен.
Кол-во сравнений при фильтрации LIKE% сделает такое же как при побитовых операциях.
И во всех случаях как правильно указал г-н zerksm скорость будет такая же (а с двумя таблицами даже медленнее) как с where and..and по 100 полям.
Ведь фактически вы создаете мемтэйбл только потому, что не можете сразу фильтровать поля с опцией «все равно». А это принуждает вас к искуственной конструкции со вторым SELECTом по промежуточной таблице, который не нужен.
Кол-во сравнений при фильтрации LIKE% сделает такое же как при побитовых операциях.
И во всех случаях как правильно указал г-н zerksm скорость будет такая же (а с двумя таблицами даже медленнее) как с where and..and по 100 полям.
100000010101 -товар
100000000000 — ищем (findkey)
какие биты будут «не важно»?
100000000000 — ищем (findkey)
какие биты будут «не важно»?
Ну судя по всему неважными должны быть как минимум 1, 3 и 5, остальные — не принципиально.
Опять же — товар 100000010101 выбран уже по результатам чекбоксов и поиска по 100% совпадению??
Опять же — товар 100000010101 выбран уже по результатам чекбоксов и поиска по 100% совпадению??
если мы ищем 100000000000
и нет «незначащих битов», то товар 100000010101 нам не подходит
мы сможем его найти, только если в маске будет 000000010101
тогда мы делаем 100000010101 AND (not 000000010101) = 100000000000 — равно нашему «поисковому запросу»
я туплю с битовыми операциями по выходным, но как то так.
и нет «незначащих битов», то товар 100000010101 нам не подходит
мы сможем его найти, только если в маске будет 000000010101
тогда мы делаем 100000010101 AND (not 000000010101) = 100000000000 — равно нашему «поисковому запросу»
я туплю с битовыми операциями по выходным, но как то так.
Если я правильно поняла, то схема такая:
— если нужно выбрать все «неважно», то надо только проверить индекс 2 на = 0
— если нужно «нет», то индекс1 = 1, индекс2 = 0
— если нужно «да», то индекс2 = 1, индекс2 = 1
— если нужно выбрать все «неважно», то надо только проверить индекс 2 на = 0
— если нужно «нет», то индекс1 = 1, индекс2 = 0
— если нужно «да», то индекс2 = 1, индекс2 = 1
как я понял это решение больше подходит для таблиц вида:
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- количество параметров по которым проверяем
как-то так, но мне кажется все что я написал не лучший выбор
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- количество параметров по которым проверяем
как-то так, но мне кажется все что я написал не лучший выбор
Запрос с таким where ни одна субд не оптимизирует нормально.
Всегда можно сделать вьюху в качестве промежуточного «индекса».
Не напасёшься так вьюх на все комбинации. Да и вьюхи никак не оптимизируют выборки, только упрощают запись некоторых запросов (и напрягают оптимизаторы).
Насколько я себе представляю, вьюха нужна одна, которая денормализует вашу нормальную структуру. Не нравится автоматическая вьюха — создайте промежуточную «таблицу-индекс» и заполняйте ее сами, на приложении по расписанию или как-то еще. В любом случае скорость выдачи результата запроса поиска — важнее.
psman, вот у нас есть 120-битные числа для каждого из товаров. И есть 120-битное число, отражающее поисковый запрос.
Как теперь искать вторым по первому? Пусть, для определённости, база данных у нас оракл или mysql.
Как теперь искать вторым по первому? Пусть, для определённости, база данных у нас оракл или mysql.
Сначала поиск по noSQL базе данных ключа-значение либо по специальной таблице, где индекс — и есть это число.
select all from table where ( сложные параметры поиска ) and id in (Select id from table where filter=<128битноечисло>.)
select all from table where ( сложные параметры поиска ) and id in (Select id from table where filter=<128битноечисло>.)
Вру, простите.
Я использовал следующее решение
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 ( сложные параметры поиска )
Я использовал следующее решение
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 ( сложные параметры поиска )
Пусть у нас сотовые телефоны, и самым младшим битом будет «если_телефон_слайдер» (1 — да, 0 — нет)
Тогда при выборе этого бита единственным — у нас искомое число будет 0x00...1 (все нули, кроме последнего), в то время как для каждого из товаров, очевидно, другие биты также будут ненулевыми.
Так что подзапрос не вернёт нам ничего.
Тогда при выборе этого бита единственным — у нас искомое число будет 0x00...1 (все нули, кроме последнего), в то время как для каждого из товаров, очевидно, другие биты также будут ненулевыми.
Так что подзапрос не вернёт нам ничего.
Не совсем понимаю, как вы производится сравнение с поисковым «запросом» в вашем примере? Как строковое, или числовое что ли?
Плюс не совсем понятно откуда взялся nosql, автор же говорит исключительно о rdbms, не?
Select * From tovarhash Where keyhash=«поисковоеЧисло» Само поисковое число с двоичном виде представляет собой 120 битку… 16 байт.
Т.е. мы просто ищем по 16 битному ключу.
Т.е. мы просто ищем по 16 битному ключу.
Я выше давал пример, если у нас поисковое число 00000000...1 (ищем по единственной галочке), тогда мы получим пустое множество на выходе, потому что очевидно, что товары будут иметь по несколько единиц в хэше.
Давайте на примере.
В таблице 3 товара, у каждого товара по 3 характеристики:
name | hash
— Товар1 | 111
Товар2 | 101
Товар3 | 010
Запрос: 001
В результате должны получить первый и второй товар. Запрос Select * From tovarhash Where keyhash=«поисковоеЧисло» вернёт 0 записей.
В таблице 3 товара, у каждого товара по 3 характеристики:
name | hash
— Товар1 | 111
Товар2 | 101
Товар3 | 010
Запрос: 001
В результате должны получить первый и второй товар. Запрос Select * From tovarhash Where keyhash=«поисковоеЧисло» вернёт 0 записей.
хорошо, у нас поисковое число 00000001b = 1hex
в товарах у нас есть их биты, которые мы прсто запишем числами
26
134
75
245
221
и т.п.
если среди них не поисковому числу, то значит и товара такого нет
в товарах у нас есть их биты, которые мы прсто запишем числами
26
134
75
245
221
и т.п.
если среди них не поисковому числу, то значит и товара такого нет
Отчего же нет?
У товара 221 — 11011101 — вот такой вот хэш. Который вполне себе соответствует искомому 00000001b
У товара 221 — 11011101 — вот такой вот хэш. Который вполне себе соответствует искомому 00000001b
нет. у этого товара чекбоксы стоят как
11011101 = да/да/нет/да/да/да/нет/да
а ищем по 000000001 = нет/нет/нет/../нет/нет/да
все нормально, товар этот нам не подходит, в нем есть то, что нам не нужно
11011101 = да/да/нет/да/да/да/нет/да
а ищем по 000000001 = нет/нет/нет/../нет/нет/да
все нормально, товар этот нам не подходит, в нем есть то, что нам не нужно
В начале вы сделали отсылку к яндекс-маркету. А в нём чекбоксы носят опциональный характер и в ЯМ запрос, который я показал выше, выдаст 2 записи.
В случае, если вы строите систему, в которой нужно 100% совпадение — плясок с дополнительным полем вообще не нужно, достаточно просто построить составной индекс поверх всех полей (причём совершенно не важно в каком порядке — потому что они нам нужны все) и база с удовольствием воспользуется этим индексом для поиска.
В случае, если вы строите систему, в которой нужно 100% совпадение — плясок с дополнительным полем вообще не нужно, достаточно просто построить составной индекс поверх всех полей (причём совершенно не важно в каком порядке — потому что они нам нужны все) и база с удовольствием воспользуется этим индексом для поиска.
UFO just landed and posted this here
Это хорошо когда схема с самого начала известна. Вы сразу написали, мол есть «ДАНО». А если этого ДАНО нет, и пользователь может добавлять товары с произвольным набором полей, и сам создавать произвольные критерии для отбора.
Вот тогда noSQL и выручают, когда схема не определена.
Вот тогда noSQL и выручают, когда схема не определена.
Не могли бы вы поподробнее пояснить вариант с необязательными полями? Я так понимаю, что для подобного поиска, нужно применять второй индекс и к первому индексу и к полю в базе данных, т.е.
( idx1 & idx2 ) == ( field & idx2 )
( idx1 & idx2 ) == ( field & idx2 )
Вы поняли что такое idx1 и idx2? Не могли бы вы рассказать? А то такое ощущение, что это очевидно в этом топике для всех, кроме меня.
В первом индексе хранятся значения чекбоксов всех видов — просто да/нет, и да/нет/пофигу
Во втором индексе нулями отмечены позиции необязательных параметров.
Суть второго индекса в том, что с его помощью мы обнуляем соответствующие позиции как в числе запроса, так и в сравниваемых полях базы данных, чтобы они не влияли на результаты сравнения чисел.
Но я вполне вероятно ошибаюсь, т.к. в этом случае получается не простое сравнение чисел, а еще вдобавок операции над ними, что обещает совсем другую производительность.
Во втором индексе нулями отмечены позиции необязательных параметров.
Суть второго индекса в том, что с его помощью мы обнуляем соответствующие позиции как в числе запроса, так и в сравниваемых полях базы данных, чтобы они не влияли на результаты сравнения чисел.
Но я вполне вероятно ошибаюсь, т.к. в этом случае получается не простое сравнение чисел, а еще вдобавок операции над ними, что обещает совсем другую производительность.
Выше я расписал суть.
начинается здесь habrahabr.ru/blogs/programming/114113/?reply_to=3677608#comment_3678297
начинается здесь habrahabr.ru/blogs/programming/114113/?reply_to=3677608#comment_3678297
www.triz-ri.ru/themes/method/creative/creative50.asp#met10
ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ
Есть таблица, с большим количеством полей. И постоянно приходится делать выборку из этой таблицы, с большим количеством условий типа поле1 = значение1, поле2 <> значение2, и т.д.
При таком раскладе запросы становятся очень большими, дольше выполняются. Иногда, при сложных запросах, где объединяются несколько таких «больших подзапросов», база данных просто отказывается выполнять их, ссылаясь на слишком сложный запрос.
ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ
Есть таблица, с большим количеством полей. И постоянно приходится делать выборку из этой таблицы, с большим количеством условий типа поле1 = значение1, поле2 <> значение2, и т.д.
При таком раскладе запросы становятся очень большими, дольше выполняются. Иногда, при сложных запросах, где объединяются несколько таких «больших подзапросов», база данных просто отказывается выполнять их, ссылаясь на слишком сложный запрос.
Предложенный алгоритм в любом случае требует как минимум одного полного просмотра всех записей…
И это такой велосипед…
Просто, вам не подходит то как база данных (подозреваю, mysql) применяет индексы по умолчанию. Надо в самом SELECT написать порядок применения существующих индексов. И будет счастье :)
И это такой велосипед…
Просто, вам не подходит то как база данных (подозреваю, mysql) применяет индексы по умолчанию. Надо в самом SELECT написать порядок применения существующих индексов. И будет счастье :)
Фильтр по «чекбоксам» — это всего лишь запрос вида Select * From tovar Where bitkey=«наше число»
остальные все более сложные запросы делаются по существенно уменьшенной таблице.
остальные все более сложные запросы делаются по существенно уменьшенной таблице.
Ужасный совет. Хинты для индексов — последнее, к чему нужно обращаться.
Если субд не применяет «правильные» индексы, то не нужно считать, что это оптимизатор глупый, нужно взять несколько литров кофе и проанализировать ситуацию. В 99% случаев виноват оказывается всё таки программист или ДБА.
Если субд не применяет «правильные» индексы, то не нужно считать, что это оптимизатор глупый, нужно взять несколько литров кофе и проанализировать ситуацию. В 99% случаев виноват оказывается всё таки программист или ДБА.
Я точно знаю, что в конкретной описанной ситуации «много индексных столбцов, таблица товаров, в которой в столбцы развернуты все свойства товаров, среди которых много нулевых значений, и требуется быстрая выборка» mysql лажает и нужно указывать индексы вручную. Так что это тот самый 1% :)
Индексных столбцов много не надо. У автора по N параметров 100% совпадение. Достаточно сделать составной индекс по этим N параметрам.
Индекс один, индексных столбцов много.
Если предметная область такая, что у товаров много свойств и по ним нужно выбирать, то правильно, логично, и др., чтобы БД соответствовала предметной области.
При количестве индексных столбцов больше 63 версии mysql 5.2.* не использовали индекс.
Если предметная область такая, что у товаров много свойств и по ним нужно выбирать, то правильно, логично, и др., чтобы БД соответствовала предметной области.
При количестве индексных столбцов больше 63 версии mysql 5.2.* не использовали индекс.
5.2?
В документации, кстати, навскидку ограничения на число столбцов в составном индексе найти не смог.
В документации, кстати, навскидку ограничения на число столбцов в составном индексе найти не смог.
УУУУУУпс, нашёл: An index may consist of up to 16 columns.
Т.е. всё ещё печальнее, чем я предполагал.
Как вы смогли туда 63+ уместить-то? :-)
Т.е. всё ещё печальнее, чем я предполагал.
Как вы смогли туда 63+ уместить-то? :-)
По умолчанию, без изменения исх. кодов или пересборки:
Да, так вот. PS: ненавижу окошко для публикации комментариев, и ограничение на 5 минут, и невозможность удалить/изменить свой комментарий.
По умолчанию для MyISAM 16 столбцов в индексе / 64 индекса в таблице
Первое значение редактируется в исходниках, я уже точно не помню, где именно, потому что дело было давно, но происходит это относительно просто
Второе меняется конф. опцией --with-max-indexes
Ставил 128/218, все работало, НО больше 63 неправильно определяло индексы :)
По умолчанию для MyISAM 16 столбцов в индексе / 64 индекса в таблице
Первое значение редактируется в исходниках, я уже точно не помню, где именно, потому что дело было давно, но происходит это относительно просто
Второе меняется конф. опцией --with-max-indexes
Ставил 128/218, все работало, НО больше 63 неправильно определяло индексы :)
В вашем алгоритме будет минимум один полный просмотр всех записей. Так что принципиальным критерием для его успеха будет только то, влезет ли вся БД в память (кэшем ли, noSQL ли, неважно). С диском такое чудо, как сравнение по битовой маске, не получится (а от индекса не будет толку, индекс строится для антисимметричного отношения)
Если все влазит в память, и обычные запросы where тупят, тогда проблема только в том, что это MySQL, ему нужно рассказать force index, чего именно вы хотите.
Если все влазит в память, и обычные запросы where тупят, тогда проблема только в том, что это MySQL, ему нужно рассказать force index, чего именно вы хотите.
Всего 12 миллионов записей и такие извращения? Речь о MySQL? Чекбоксы можно завести в булевые колонки, завести на них индекс, и постгрес будет использовать bitmap scan.
для слайдеров можно использовать просто btree. 12 миллионов записей это очень мало.
для слайдеров можно использовать просто btree. 12 миллионов записей это очень мало.
да, а поскольку народ валом валит, то все атрибуты http-запроса можно отсортировать по весу, взять или не брать от него md5 или sha1 и кэшировать в мемкэшед или типа того, что бы даж до СУБД не доводить. более или менее популярные комбинации попадут рано или поздно в кэш, и не будут грузить сервер вообще.
Автор почти переизобрел фильтр Блума.
Sign up to leave a comment.
Ищем быстро, еще быстрее