Проблема с индексным поиском по документам

[boric]

Итак протестировал варианты по базе из 30000 документов по фразе из 4-х слов, где три слова встречаются примерно в половине документов, а одно примерно в 3-4. тысячах. Т.е. фраза неприятная. Всего на выходе получилось 2400 найденных документов.

Что имеем?

1) Алгоритм с последовательной выборкой по каждому из слов, начиная с наименее частотного с последующим уменьшением выборок через добавление в WHERE условия IN(список_найденных_id_документов_на_предыдущем_ша ге) - нашел документы за 2.3 секунды.
Если выборку не ограничивать в селектах на каждом шаге, а пересечение множеств делать например на пхп/питоне и пр., то запросы выполняются совокупно около 15 сек. На выборку и перегонку 15-20 тысяч документов по 4-5 сек затрачивается. Фигово.

2) Вариант селекта с объединением таблицы самой с собой по числу слов в запросе - нашел документы за 8.3 сек. Тоже фигово. При объединении 4 таблиц уже тормоза есть, а при объединении более 5-6 таблиц mysq практически падает. Но при фразах 1-3 слова - этот метод очень быстр.

3) Запрос с группировкой показал время - 0.285 сек. Т.е. для данного неприятного запроса - лучший вариант.

Вроде бы очевидно, что лучший - 3-й вариант. А вот фигушки. Если в запросе использовать хотябы одно очень низкочастотное слово, то 1-й вариант выполняется за 0.2 сек. (притормаживает из-за IN), 2-й вариант - за 0.007 сек, а 3-й вариант - без изменений - 0.27 сек. Т.е. в этом случае на порядки более быстрый - 2-й вариант (через многократное объединение таблицы самой с собой).

В третьем варианте время выполнения похоже будет прямо-пропорционально количеству записей в таблице, т.к explane показвает rows_examine=40000-80000. Индексы полей, похоже, не задействуются. Еще на некоторых 4-х словных запросах он в несколько раз дольше почему то выполнялся.

Селект такой:

SELECT doc_id FROM indextable WHERE word_id IN (461264) OR word_id IN (463565) OR word_id IN (463533) OR word_id IN (461252) GROUP BY doc_id HAVING count(*) = 4

В общем не знаю пока, что делать.

Добавлено через 36 минут
Для селекта с группировкой составной индекс помог. Скорость не на много увеличилась и examine снизился не сильно - с 77000 до 50000. Но надеюсь с составным индексом время выполнения будет не прямо зависеть от объема, а логарифмически.

Добавлено через 1 час 18 минут
Да, еще забыл сказать: документов то 30 тысяч, а вот соответствий "слово-документ" в сабжевой таблице - 13 миллионов. Т.е. запросы делаются к таблице с числом записей 13,000,000

[yayayagogogo]

Я знал, что будет так

[Atomic]

Сообщение от yayayagogogo

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

Ахаха, вы что ищите в документах в момент ввода поискового запроса?
Поисковики распарсивают документ до неузнаваемости до того как он (вернее некая выжимка) попадет в поисковую базу

[yayayagogogo]

Этот топик как раз и создан, дабы определить каким образом поисковые системы делают такой быстрый поиск. Поделитесь вашими знаниями, но только не словами, типа "прикручивают", "распарсивают", "внедряют". До политика вам еще далеко.

[boric]

Atomic

Ахаха, вы что ищите в документах в момент ввода поискового запроса?
Поисковики распарсивают документ до неузнаваемости до того как он (вернее некая выжимка) попадет в поисковую базу

Собственно это и есть мой второй большой ВОПРОС:

Каким образом можно ЗАРАНЕЕ вычислить веса для связок "запрос-документ", если запрос состоит из заранее неизвестной комбинации слов??? Ведь очевидно, что для больших объемов "на лету" это делать нереально.

ЗЫ1:
Яндекс однако по своей формуле матрикснет "на лету" вычисляет веса. Разумеется очень ограниченно. Каждый запрос обрабатывается параллельно несколькими тысячами серверов. В общем можно понять, почему он борется с автоматическими запросами. Хотя с другой стороны все коммерческие запросы наверняка закешированны.

ЗЫ2:
Смотрю сейчас во всяких пдф-ках доступные старинные формулы ранжирования. Блин практически во всех интересных формулах (кроме самых простых и очевидных) есть ошибки, по крайней мере в таком виде они часто дают обратный результат. Или это размноженные опечатки и неточности или спеиально так делают...

[yayayagogogo]

Сообщение от boric

Каким образом можно ЗАРАНЕЕ вычислить веса для связок "запрос-документ"

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

[boric]

yayayagogogo

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

Такой предрассчет можно сделать только для однословных запросов, т.е. заранее для каждого слова из словаря рассчитать веса связок "слово-документ". Но если запрос состоит из нескольких слов, все сложнее. Можно конечно и в этом случае будет использовать рассчитанные веса "слово-документ", но только если для нас будет приемлемо снижение полоноты и точности выборки, т.к. обрезание произойдет без учета связей слов запроса. Или можно?

Например запрос "мама мыла раму".
Для каждого слова у нас заранее рассчитаны веса связок "слово-документ". Предположим, все три слова из данного запроса имеются в 10 миллионах документах. В рамках sql-запроса с группировкой я могу конечно сделать сортировку этой выборки по сумме весов слов запроса в каждом документе с последующим limit. Но во-первых, сумма весов это достаточно примитивный критерий, а во-вторых сортировка такая будет безиндексная, т.е. долгая (а в выборке у нас 10 миллионов). Если же обрезание выборки делать индивидуально по каждому слову запроса (в соответствии с весами), то у нас снижается полнота и точность выборки.

[yayayagogogo]

В таблице с анкорами указаны целиком анкоры за минусом мусора (для, как, вот и т.д.). Те сайты, которые не имеют ссылающихся анкоров ротируются как низшие. Для уменьшения области поиска, нужно все документы классифицировать по тематике, соответственно и анкоры.

Нужно создать таблицы, слово в документе = тематика, запрос = тематика.

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

Результат получу только через 10-15 дней.

[boric]

yayayagogogo
В общем понятно, что по-любому придется жертвовать точностью и полнотой, что в общем-то яндекс с гуглом и делают.

нужно все документы классифицировать по тематике, соответственно и анкоры.

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

Нужно создать таблицы, слово в документе = тематика, запрос = тематика.

При такой схеме (слово в документе = тематика) к какой тематике будет отнесена фраза "звездные войны"? Вероятно к темам астрономии и политики, но не к кино. Возможно к кино тоже частично отнесется за счет других факторов, но в любом случае темы "астрономия" и "политика/история" будут не верны. Можно попытаться обрабатывать такие запросы, как единый термин, но все через чур усложняется.

[Андрей Барыкин]

Сообщение от boric

SELECT doc_id FROM indextable WHERE word_id IN (461264) OR word_id IN (463565) OR word_id IN (463533) OR word_id IN (461252) GROUP BY doc_id HAVING count(*) = 4

Безотносительно к задаче, почему такой извращенный запрос?
1) = работает быстрее, чем IN
2) так вроде красивее(может и быстрее) word_id IN (461264, ..., ...)

Запрос динамически формируется?