Построение специализированного индекса для поиска

[alexhemp]

Построение специализированного индекса для поиска

Итак - имеется - большой список строк (десятки миллионов), храниться в базе, но это для алгоритма не важно

Задача - поиск элементов по совпадению с началом строки, посредством организации своего специализированного индекса.

Т.е. для запроса "1234" нужно найти и "12345" и "123456"

Идея у меня пока только такая - использовать хэш-ф-цию для разбивки данных на некоторые "кластеры". Хеш - должен быть - монотонно возрастающим, чтобы "задавать границу снизу".
Т.е. H("1234") < H("12345") - нужен тот-же порядок что и для обычного сравнения строк.

Далее - строим уже нормальный индекс по кластерам и ищем в выборке (будет обычный линейный поиск).

Пока идея - сделать хеш 64-битным, чтобы влезал в BIGINT. Значения кодов сильно ограничены, латинские буквы + цифры, пока сделаю хэш просто выделением 6 бит на символ, итого влезет 10 символов, пространство поиска сильно сузится и LIKE вполне может заработать.

Строить бинарное дерево - слишком долго, обновлять индекс придется как минимум раз в сутки, а при использовании хешей - вообще не нужно будет обновлять
Основная проблема - вот эта "нечеткость" в поиске.

Но чует мое сердце, что способ не слишком элегантен, я его еще в институте проходил
Быть может кто-нибудь ткнет меня носом в какой-нибудь более сложный и наверняка более эффективный алгоритм?

 

[С.]

А тупой примитивный SUBSTRING() вместо "монотонно возрастающего хеша" и LIKE уже пробовали? Ну и как оно?

 

[kruglov]

Да просто LIKE '12345%' с индексом на поле длиной символов на 5-10 пробовали? И как?

 

[Alexandre]

alexhemp Хорошая статья была у А.Рыбак в ПхпИнсайд - 7 номер (возможно с номером я ошибаюсь)

чем тебя не устраивает использование Lucene или MnogoSearch?

 

[alexhemp]

С., kruglov
Я про алгоритм поиска спрашиваю. Возможности SQL-серверов я отлично знаю.

Alexandre
Они заточены под поиск в естественных текстах, и работают с минимальной единицей - словом. В исходных данных - "слов" никаких нет, коды достаточно случайны.

 

[magic]

Можно использовать индекс для первых n-символов и по нему искать. Такой вариант подходит?

 

[alexhemp]

Во первых индекс по строкам будет сильно тормозить вставки (они будут довольно интенсивные, полное обновление всей бызы - 2 недели).

Во вторых в полный рост встает проблема выбора этого N ;-)

Это на практике строковой вариант моей идеи с целочисленным индексом.

Похоже другого варианта нет...

 

[chira]

alexhemp

и всётаки, попробуй использовать индекс + LIKE '12345%' и оптимизировать вставку в таблицу, например, используя INSERT DELAYED ...

 

[alexhemp]

Господа - повторюсь, вопрос теоретический! Он об алгоритме поиска, похоже модератор не понял этого.

chira
Теперь по пунктам:

Вставки оптимизированы - дальше некуда - LOAD DATA INFILE.
В документации подробно расписано как оптимизировать LOAD DATA - это все понятно, и очевидно.

Насчет варианта с LIKE - да, он использует индекс. Но цена его создания на мой взгляд - высока, требуется балансировка весьма немаленького дерева, в несколько миллионов СТРОК длинной 15-20 символов.

Мой вариант с хешами дает более легкие вставки, хеш считается независимо от других строк, стоимость индекса по хешу - значительно ниже - у него фиксированный размер в 4/8 байт.

Ну и EXPLAIN показал результаты - с хэшем использовался индекс и 28 строк проверено, из 30 тысяч строк.
C LIKE на тех-же данных - 703 строки.

По мере увеличения тестовой базы проведу другие эксперименты, но думаю отрыв моего алгоритма от LIKE будет только возрастать. На следующей неделе волью миллионов 5 реальных строк и посмотрю

Ладно, насколько я понял, никто не строит своих поисковых алгоритмов в больших базах, все пользуют штатные ф-ции SQL-серверов.

Топик можно закрывать.

 

[chira]

alexhemp

зачем закрывать?
очень интересно было бы узнать результат твоих мучений ...
по ходу ответь на несколько вопросов (если не трудно)
1. что ты подразумеваешь по понятием "кластера", т.е. какая будет физическая реализация в MySQL
2. как ты предполагаешь связывать данные кластера с данными в своих таблицах? Или кластер это виртуальное понятие и будет просто дополнительное BIGINT поле в таблице?
3. такое впечатление, что сам хеш и индекс для него будет занимать на несколько порядков меньше ресурсов, чем в варианте с LIKE?

Мой вариант с хешами дает более легкие вставки, хеш считается независимо от других строк, стоимость индекса по хешу - значительно ниже - у него фиксированный размер в 4/8 байт.

Может я неправ и данные специально будут подготавливаться заранее (если это LOAD DATA INFILE)?

и если это пока твои теоретитеские изыскания

Господа - повторюсь, вопрос теоретический!

хотелось бы увидеть результаты твоих тестов

По мере увеличения тестовой базы проведу другие эксперименты, но думаю отрыв моего алгоритма от LIKE будет только возрастать. На следующей неделе волью миллионов 5 реальных строк и посмотрю

насчёт:

Ладно, насколько я понял, никто не строит своих поисковых алгоритмов в больших базах, все пользуют штатные ф-ции SQL-серверов.

не нужно обобщать все SQL сервера.
в более "навороченых" SQL серверах, например в Oracle, есть уже встроенные механизмы оптимизации в том числе упоминаемые тобой хеш фунции

удачи

 

[alexhemp]

1. Насчет "кластеров", я их применял в теоретическом значении - это часть некого множества, члены которого имеют сходные характеристики - т.е. "кластер" - в математическом смысле, как часть выборки.

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

Для поиска нужно лишь вычислить хэш для искомой строки, а потом просмотреть соотв. список.

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

По предварительным прикидкам в базе будет постоянно около 10 миллионов записей, которые будут обновляться регулярно, причем не по одной записи - а база целиком будет замещаться новыми данными - и нагрузка на построение индекса будет заметна.

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

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

 

[Alexandre]

Хорошая статья была у А.Рыбак в ПхпИнсайд - 7 номер

alexhemp

читал? Он занимался оптимизацией поиска и морфологинй.

Они заточены под поиск в естественных текстах, и работают с минимальной единицей - словом. В исходных данных - "слов" никаких нет, коды достаточно случайны.

это что за данные (задача такая...), мне просто всегда случалось сталкиваться только поиском в тексте...
Кстати у Рыбака там как раз уделено вниманию построению индексов

 

[alexhemp]

Alexandre

У меня не ТЕКСТЫ.

У меня артикулы товаров.
Пример строки : MPD1785942-X2A.

Отличие от интернет-магазина - таких артикулов - миллионы, это составные части различных механизмов, приборов и т.п.
В одном товаре их может быть легко 1000 различных частей, а то и 10000 (турбина какая-нить).

В отличие от поиска по сайту - нет никаких HTML документов описывающих эти артикулы. В базе просто огромная таблица -
артикул, цена, количество. ОТДЕЛЬНО будут справочники по артикулам, но там дай бог 1% от общего объема будет описан, поиск там правда тоже - по номеру.

Это - СПЕЦИАЛИЗИРОВАННАЯ база, с Web-интерфейсом к ней.

Статью читал - там поиск ПО САЙТУ, в этом я разбираюсь не хуже автора статьи.

 

[AnToXa]

alexhemp
внимательно читал только последнее твое сообщение, так что сорри, если уже предлагалось.

делается элементарно
если руками, без баз:
http://en.wikipedia.org/wiki/Trie
http://en.wikipedia.org/wiki/Radix_tree
http://en.wikipedia.org/wiki/Ternary_search_tree

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

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

если не префикс, то можно чуть более общий механизм.
разбиваем все строки на "классы эквивалентности" скажем выбирая строку из 1, 5 и 7 символов, собсна для них также делаем по таблице.

 

[alexhemp]

AnToXa

Я не вижу смысла в разбиении таблицы на несколько, только для того чтобы уменьшить размер и время построения индекса. Это - будут "костыли" из-за необходимости использовать индекс по строкам.

Строить дерево индекса вручную - смысла нет, SQL-сервер строит индексы значительно эффективнее.

Префиксов никаких устойчивых нет. Деталь из другого комплекта может называться X-11-23-VVVZ-A/11
Каждый вендор использует свою систему, от сквозной нумерации до запарной схемы с черточками, и это еще без китайских заменителей.

Последний абзац я и комментировать не хочу - ты вообще читал топик? Я ТАК И СДЕЛАЛ, только твой "класс эквивалентности" и есть значение хеш-ф-ции.

Это КЛАССИЧЕСКИЙ алгоритм.

Плиз, если не решали подобных задач - не пишите в топик.

 

[AnToXa]

Я не вижу смысла в разбиении таблицы на несколько, только для того чтобы уменьшить размер и время построения индекса. Это - будут "костыли" из-за необходимости использовать индекс по строкам.

ну если вы его не видите, то это не значит, что этого смысла нет, не так ли?

Строить дерево индекса вручную - смысла нет, SQL-сервер строит индексы значительно эффективнее.

ошибаетесь, сами тут про специализированые базы разглагольствуете, а против других специализированых инструментов протестуете.

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

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

Плиз, если не решали подобных задач - не пишите в топик.

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

 

[Wicked]

Идея у меня пока только такая - использовать хэш-ф-цию для разбивки данных на некоторые "кластеры". Хеш - должен быть - монотонно возрастающим, чтобы "задавать границу снизу".
Т.е. H("1234") < H("12345") - нужен тот-же порядок что и для обычного сравнения строк.

Для этого нужна взаимооднозначность функции H. А хэш-функции, как известно, НЕ взаимооднозначны.

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

Статью читал - там поиск ПО САЙТУ, в этом я разбираюсь не хуже автора статьи.

Объясни мне, пожалуйста, чем принципиально поиск по сайту отличается от твоего?

 

[Alexandre]

Для этого нужна взаимооднозначность функции H. А хэш-функции, как известно, НЕ взаимооднозначны

думаю это ускорит поиск, у съуженнный поиск можно уже проверить на однозначность.

 

[alexhemp]

AnToXa

ну если вы его не видите, то это не значит, что этого смысла нет, не так ли?

Конечно не значит - но я говорю о выбранном мною алгоритме, и о том что подсказывает мне опыт.

ошибаетесь, сами тут про специализированые базы разглагольствуете, а против других специализированых инструментов протестуете.

Я не протестую. Я знаю как устроен индекс в БД, это дерево поиска. Сомневаюсь что на PHP я напишу более эффективный алгоритм. Мне ехать нужно а не шашечки.

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

Смысл предлагать мне то, что я уже сам написал в теме? А свое свободное время я трачу как хочу.

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

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


Wicked

Для этого нужна взаимооднозначность функции H. А хэш-функции, как известно, НЕ взаимооднозначны.
Соответственно, если H-взаимооднозначная функция, то и сама суть кластера ("для каждого элемента считается значение некой хэш-ф-ции, если значение совпадает - они попадают в один список.
") тут тоже неуместна, т.к. эти списки будут единичной длины.

Я опечатался, нужно читать как H("1234") <= H("12345")

Объясни мне, пожалуйста, чем принципиально поиск по сайту отличается от твоего?

Тем что поиск по сайту производится В ТЕКСТАХ. А текст состоит из СЛОВ. Длина текста - в среднем на порядки выше чем у моих данных. Текстов либо не очень много, либо они меняются редко.

Alexandre

думаю это ускорит поиск, у съуженнный поиск можно уже проверить на однозначность.

Все именно так, в этом и суть алгоритма хэш-поиска.

 

[Wicked]

перечитав трэд...

1) "Основная проблема - вот эта "нечеткость" в поиске."
можно поподробнее?

2) "он все-же предполагает линейный поиск в кластере, и тут все упрется в размер кластера"
заметь, что даже у INT'а хватает размерности, чтобы очень разреженно содержать твои 10млн записей (~99.8% останутся свободными), так что тут важнее будет, насколько у твоих строк будут совпадать префиксы.

3) Индекс на INT-поле все еще будет Б-деревом (которое используется и для строк), так что балансировка дерева индекса всё еще будет иметь место. Вообще, что-то мне подсказывает, что у поля char(4) binary производительность будет сродни int-овому: те же 4 байта, тот же fixed row, тот же B-tree индекс.

4) Про поисковики текстов: там используется инверсный индекс. Многие идеи оптимизации оных можно и тебе перенять. Я, например, сделал поисковик, похожий на Фишеровский, в котором щас 10 млн записей в инверсном индексе. При этом полная переиндексация происходит примерно за 20 минут. Что несколько меньше двух недель И не надо от ТЕКСТОВЫХ поисковиков так открещиваться, ибо я свой могу перенастроить хоть под твою задачу, хоть под индексацию exe-файлов "словами" по 33 байта.

5) не хочешь поделиться инфой, как у тебя сайчас информация хранится?