Есть база данных с тремя таблицами: documents, words, documents_words. В последней, как не трудно догадаться, три столбца: document_id, word_id, weight. Задача: на запрос "мама мыла раму" нужно вывести все документы, в которых есть эти слова (условие «И»), отсортированными по суммарному весу слов в этих документах.
Замечание первое: третья (join-) таблица может быть большой, поэтому left join не поместится даже в 16 гигабайт памяти.
Замечание второе: поиск должен быть быстрым (меньше секунды) при любых (!) объемах данных и нормальных параметрах серверов: пара ядер по 2-3 ГГц, несколько гигов памяти, достаточный объем дисков на борту.
Вопрос: как это сделать?
14 июля 2007 в 2:03
Тогда возможна ситуация, что по каждому слову в первой десятке будут те документы, у которых другие слова имеют ничтожно низкий вес.
А те документы, у которых сумма весов действительно высокая, в отдельных списках будут на какой-нибудь 156 позиции.
Более грамотно это звучит так: вы не знаете распределения весов документов и их корреляции, чтобы на основании этой информации делать оценку необходимого размера одномерной выборки.
А чтобы посчитать распределение и корреляцию, нужно проделать более сложную и медленную работу, чем Map-Reduce при поиске.
13 июля 2007 в 17:01
я имею ввиду, для каждого документа, попавшего хоть в одну из этих "выборок", считать суммарный вес
13 июля 2007 в 16:03
Нет. Потому что документ, у которого очень большой вес "мама мыла", но низкий "раму" может быть в сумме топовым, но не будет выбран из-за того, что не попадет в топ-N по "раме".
13 июля 2007 в 16:00
а можно так?
для каждого слова в запросе (мама, мыла, раму, M=3 слова), находим N (количество докуметнов на страницу) топовых документов. Затем досчитываем для каждого документа (максимум для M*N) суммы слов и сортируем.
13 июля 2007 в 10:03
Да согласен, идея с битовой маской не очень хороша. Во всяком случае для такого большого кол=ва слов.
Про кластеризацию – это понятно, но все равно вы же собираетесь использовать субд с SQL ? По этому обычный select придется использовать при любых схемах.
13 июля 2007 в 1:00
Алексей все верно говорит. Более того, даже если на одной машине кусок таблицы слишком большой, то его можно мысленно поделить на N частей, делать выборки из этих частей и выбирать из "текущей" и "предыдущей" нужную страницу до тех пор, пока не будет пройдена вся таблица. При установке новой машины половину из этих частей скинуть на новую машину, распараллелив таким образом вычисления.
13 июля 2007 в 0:05
получение документа где встречаются заданные слова будет не очень быстрым.(мы либо перебираем все документы что не есть хорошо, либо индексируем по полю размером 10000 байт что тоже не очень эффективно)
и такой способ, имхо, требует больше памяти чем хранение таблицы смежностти
ну и наконец этот способ не позволяет хранить весслова в документе, что требуется по условию.
13 июля 2007 в 0:03
Не все гууд. работать должно 1 байт информации = 8 бит = 2^8 комбинаций. Итого можно закодировавать признак присутствует или нет слово из словаря в 256 слов (2^8 = 256), в инте 4 байтаи т.д.
должно хватить.
12 июля 2007 в 23:04
опс, нет не пойдет такой способ. слишком много будет занимать битовая маска для каждого документа
(
12 июля 2007 в 23:03
Такс , еще идея
Правда не знаю насколько реализуема на разных субд -в общем используем битовый массив слов для каждого документа.
Т.е. для каждого документа, в 1-м поле храним битовое значение ДА/НЕТ для каждого слова из справочника.
Думаю словарь не такой уж здоровый ~100 тыщ значимых слов… При условии что словарь относительно const.
12 июля 2007 в 22:05
Новый вариант коллективного решения.
Кластеризуем docs_words по doc_id. Внутри кластера благодаря индексу по словам выполняем запрос по каждому слову, сливаем списки и выбираем из каждого кластера по 30 топовых по сумме. После этого выбираем 30 топовых записей из всех кластеров, и по этим doc_id без труда получаем документы.
12 июля 2007 в 0:04
Я спрашиваю не потому, что занимаюсь этой задачей, а потому что мне интересна публика.
// Хакир, почему для себя ты выключил онлайн-режим? =)
12 июля 2007 в 0:03
А кто тебе сказал, что я не знаю ответ? =)
12 июля 2007 в 0:03
Да причем здесь ответ, я про саму задачу
12 июля 2007 в 0:02
Это и есть быстрое перемножение. Остается один вопрос: в какую память поместится 3 массива по несколько миллионов записей.
12 июля 2007 в 0:02
Олег, ты над каким проектом сейчас работаешь?
11 июля 2007 в 23:02
может я чего не понял но по-моему – это не декартово произведение.
каждый из этих массивов мы проходим один раз тк они отсортированы по id документа. слияние происходит так:
берем первый элемент от каждого массива
если у всех массивов они ( первые элементы совпадают ) то этот документ нас устраивает и мы добавляем его в итоговый список
если нет (id документов не совпадают), то выкидываем все (из тех кто был в своем массиве первым) кроме документа с максимальным id
11 июля 2007 в 22:04
Мысль в совершенно правильном направлении, но есть один момент.
общее количество документов — 10 000 000 000.
вхождений "мама" — 198 000 000.
вхождений "мыла" — 1 200 000.
вхождений "раму" — 2 500 000.
Задача сводится к быстрому декартовому произведению трех массивов по несколько миллионов записей в каждом. Т.е. к тому же, с чего и начали. =) А если слово только одно, то твоя схема не дает никакого преимущества.
Кластеризация нужна, но по другому полю.
UPD. Скорее, не декартово произведение, а пересечение множеств.
11 июля 2007 в 21:05
Алгоритмическое решение от меня и Антона Ланцова (id109830).
По word_id в таблице words должен быть индекс. К тому же она вероятно статична. Первый шаг – выбор id по словам из запроса.
Таблицу docs_words хочется хранить кластеризованно по word_id, а внутри кластера – упорядоченно по doc_id. Дискового пространства должно хватить для добавления новых записей в конец кластера (новые документы ведь имеют больший id?), а если слово из документа исчезло, запись удаляется.
Блоки, выбранные по word_id из docs_words (для чего желателен индекс по word_id в этой таблице), сливаются как списки по doc_id, по которому упорядочены записи внутри блока. При этом для элемента, попадающего в итоговый список, считается сумма весов.
В конце результаты слияния сортируются по сумме весов и для топ-30, скажем, выбираются документы из таблицы docs. (Тоже не помешает индекс.)
11 июля 2007 в 16:02
"временная таблица только для хранения ID поисковых слов" — это для тех, кто мыслит SQL-ем. Забудьте про сложные sql-конструкции, это задача не о них.
11 июля 2007 в 16:01
На практике нужно вывестивсего лишь топовые 10-20 документов (забудем на минутку о пейджинге, его несложно приделать). Но эти 10-20 нужно найти из 10 млрд, причем быстро.
11 июля 2007 в 15:02
Не временная таблица только для хранения ID поисковых слов, я думаю таких слов не более 10 обычно
11 июля 2007 в 15:01
Ну, во-первых выводить все документы – это неправильно, поскольку если хотя бы в 1000 документов встречаются эти слова – пользователю что нужна вся 1000. Значит предложение раз – пейджинг.
11 июля 2007 в 15:01
Никаких временных таблиц. Ибо их заполнение миллиардами документов – абсолютные тормоза и бесперспективное дело.
11 июля 2007 в 15:01
Это тем более плохо, если учитывать параллельность работы многих пользователей.
11 июля 2007 в 14:01
вообще можно без #Temp1 c еще 1 подзопросом, но иногда Ms SQL оптимизатор на подобных вещах клинит
11 июля 2007 в 14:01
Напоминаю, что документов — 10 миллиардов, а словарь — 100 тыс. слов. У вас не хватит никакой оперативной памяти для join-ов и таких вот подзапросов.
11 июля 2007 в 14:01
Ок, что можно решить без подзапросов и агрегатов ?
11 июля 2007 в 14:00
#Temp1 заполняется как в посте выше.
select A.document_id
from
(
select documents_words.document_id as document_id,
case
#Temp1.word_id is null then 0
else
1 end as WordsPresent
from
documents_words
join #Temp1 on #Temp1.word_id=documents_words.word_id
) AS A
Group by document_id
Having Sum(WordsPresent) = 3
11 июля 2007 в 13:00
Условие для слов — «И», а не «ИЛИ»
11 июля 2007 в 12:04
Если в documents_words есть индекс на word_id, то нужно сначала, выбрать во временную таблицу (#temp1) ID слов из таблицы words по значениям "мама", "рама" и .т.д. Т.е. как в примере, там будет всего 3 ID
Потом ее уже при join ть к documents_words:
select xxx from documents_words
join #Temp1 on #Temp1.word_id=documents_words.word_id
возможно, что некоторые SQL сервера будут работать быстрее с:
select xxx from documents_words
where word_id in (select word_id from #Temp1)
11 июля 2007 в 10:05
Алексей: вес вычисляется по отдельному алгоритму и этот алгоритм к задаче не имеет отношения. Важно, что, чем вес больше, тем выше значение слова в документе. Нет weight("мама"), есть weight("мама", "doc124967").
Максим: inner join [words] w on w.[word_id]=dw.[word_id] в данном случае не катит. Попробуйте на БД с 10 млрд документов и словарём 100 тыс. слов.
11 июля 2007 в 10:03
declare @temp table ([document_id] int primary key clustered, [sumweight] int)
insert into @temp
select [document_id], sum([weight]) from [documents_words] dw
inner join [words] w on w.[word_id]=dw.[word_id]
where w.[word] in ('Мама','мыла','раму')
group by [document_id]
select d.* from [documents] d
inner join @temp t on t.[document_id]=d.[document_id]
order by [sumweight] desc
Это если требуется отобрать документы, в которых есть все три слова.
Если любое из слов – меняем условие where.
Если сделать stored proc и запускать на серваке – то будет быстро.
11 июля 2007 в 3:02
"суммарному весу слов в этих документах" –
в смысле weight("мама") + weight("мыла") + weight("раму")
или sum_{word in doc} weight(word)?
(Если вес – это количество вхождений слова в документ, то вопрос снимается.)