Xpoint
   [напомнить пароль]

100 млн записей + 100 параметров в каждом - поиск по параметрам

Метки: [без меток]
2006-07-05 15:38:04 [обр] firestorm[досье]

Уважаемые, есть такая задача:
Есть таблица, в ней 100 млн. записей. К у каждой записи есть примерно 100 параметров, причем каждая запись относится к одному из миллиона документов (ста тысяч, не знаю точно)

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

Другими словами: Есть ID документа (их разных - 100 тыс), ID записи (их 100млн), Название записи + 100 параметров.

Мне надо найти ID документа, в котором есть Название записи=aaa с определенными параметрами, в котором есть запись с названием bbb с ее параметрами и тд - до 5 записей на документ.

На маленьких таблицах это реализуется с помощью join, на большой будет тормозить.
Причем выборка будет ограничиваться 1000 документами, хотя запрос может выбирать даже все 100 тыс документов (в каждом из документов может встречаться одна из записей - априори это не известно).

Мне кажется, что такая линейная структура БД не подходит под эту задачу - какая должна быть правильная структура под нее?

спустя 2 часа 18 минут [обр] GRAy(8/259)[досье]

Не совсем понятно что значит

ID документа, в котором есть Название записи=aaa с определенными параметрами, в котором есть запись с названием bbb с ее параметрами и тд - до 5 записей на документ.

Это взаимодополняющие условия или просто параллельные? Для параллельных запрос может выглядеть так:

select distinct doc_id
from zapisi z
where 
  z.name = 'aaa' and z.param1 = 'val1' and param2 = 'val2' ... and paramN = 'valN'
  or
  z.name = 'bbb' and z.param1 = 'val11' and param = 'val22' ... and paramM = 'valMM'
  or
  ... и т.д.

Дла взаимодополняющие соотв. or заменяем на and.
Это будет эффективно только если существуют индексы на соотв. наборы параметров (все возможные сочетания встречающиеся в запросах) - что, разумеется невозможно. Маловероятно что у всех 100 миллионов записей все 100 полей заполнены - следовательно нужно это оптимизировать. Дальше всё зависит от предметной области, необходимо проанализировать, какие поля из этих 100 наиболее употребимы - их оставить в главной таблице, а все остальные вынести в таблицу(ы)-раширения. Можно их организовать так же как и главную, а можно в виде записей [id, field_name, field_value]. Первый вариант громоздок, и потребует outer-join`oв для получения всего списка атрибутов, второй более эффективен в плане хранения, но крайне неудобен при выборке большого числа параметров (тоже требует outer-join`ов, но гораздо большего их кол-ва, фактически на каждый извлекаемый параметр).
Давать советы о "вообще" правильной структуре занятие практически бессмысленое - как показывает практика, в любой предметной области находятся ситуации когда удобней отступить от общих правил.

спустя 57 минут [обр] Закиров Руслан(12/343)[досье]
Задача похожа более общий случай пересечение в одной таблице. Хотя не совсем понятно зачем вам 100 столбцов в таблице или у вас не 100. Прще понять, когда видно структуру, а не сумбурное описание.
спустя 4 часа 22 минуты [обр] firestorm[досье]

привожу пример, может быть он чуть более понятный.
таблица zapisi

поля: Id, docId, zapis, param1, param2... param100
по такой структуре записей в таблице 100 млн

запрос:
SELECT * from zapisi as z1, zapisi as z2
   WHERE z1.zapis = "A" and z2.zapis = "S"
   and z1.docid = z2.docid and z1.param1 = z2.param2
   and z2.param10=7 and z2.param15=31

По моим представлениям такое должно работать медленно на такой таблице.
Вероятность поиска по любому из 100 параметров одинакова.

>а можно в виде записей [id, field_name, field_value]
Условно говоря, это такая таблица расширения и есть. Только с дополнительными параметрами. И тут потребуются join-ы, которые будут тормозить процесс...

спустя 24 минуты [обр] GRAy(8/259)[досье]
firestorm[досье] бр, ну зачем вам self-join здесь? Это, кроме тормозов, ещё и странный результат вам даст. Предположим, у вас для определённого docid существует 10 записей с полем zapis="A" и 100 записей полем zapis="B" в итоге (если не брать фильтр по параметрам) в результате у вас будет 1000 записей - зачем вы усложняете бд жизнь? ;)
спустя 1 час 51 минуту [обр] Закиров Руслан(12/343)[досье]

GRAy[досье] Я например не вижу другого выхода, кроме self-join'а. Вот вам пример записей удовлетворяющих условию выше приведенного запроса:

docid, zapis, param1,param2,...,param10,...param15,...
X      A      Y      ...        ...        ...
X      S      ...    Y          7          31

Без объединений нельзя выбрать что-то такое:

firestorm[досье] При такой структуре будет невозможно покрыть все запросы индексами, нужно переходить либо к развертыванию колонок param* в записи в той же таблице, либо в отдельной:

1) (id, docid, zapis, param_name, param_value)
2) (id, docid, zapis) + (zapis_id, param_name, param_value)
спустя 9 часов [обр] firestorm[досье]
Руслан, Вы все правильно поняли, спасибо за ответ. А чем отличается такая схема от той, что я предложил изначально? Ведь максимум будет 100 млн * 100 записей = 10млрд в таблице параметров... Пусть даже и с индексами...
спустя 1 час 48 минут [обр] GRAy(8/259)[досье]

Хм... да, я не правильно понял начальные условия. Получается что надо делать столько self-join`ов, сколько записей с определёнными параметрами необходимо чтобы было у документа. Тем не менее, если надо получить только id`шники документов, имхо, можно обойтись без self-join`а:

select docid
from zapisi z
where (z.zapis='A' and z.param1='Y') /* первый вид записей, который должен быть в наших документах */
   or (z.zapis='S' and param2='Y' and param10=7 and param15=31) /* второй вид записи */
group by docid
having count(distinct zapis) = 2 /* эту цифру надо определить до того как делать селект */

Цифра "2" - это кол-во видов записей, которые должны присутствовать в документе. Таким образом мы получим только те docid которые имеют все необходимые нам записи.

спустя 7 часов [обр] Закиров Руслан(12/343)[досье]

GRAy[досье] Уже обсуждалось, что HAVING гораздо медленнее JOIN'ов так как выполняется без использования индексов и после выполнения всех других операций. Могу поискать тему если надо.

firestorm[досье] У вашей структуры проблема с индексами. Например у вас есть запрос z2.zapis = 'xxx' AND z2.param10=7 and z2.param15=31. Для того чтобы максимально использовать индексы, нужно создать индекс по всем полям (zapis, param10, param15), но такой индекс не будет применяться для многих других запросов. О причинах можно прочитать в статье (Оптимизация запросов с помощью индексов (Составные индексы)). Структуры, которые я предложил, позволят применять индексы гораздо чаще, но в тоже время это увиличит количество объединений. Честно говоря, в данной ситуации нельзя выбрать правильно решение без тестирования на реальных данных.

Мне кажется, что невозможно чтобы все сто параметров были актульны для любой записи, то есть у вас там есть параметры, которые актульны только для записей с конкретным значением поля zapis. Так что в результате будет не 10млрд. записей, а значительно меньше.

спустя 43 минуты [обр] GRAy(8/259)[досье]
Закиров Руслан[досье] А having здесь не для скорости, а только для того чтобы отсечь записи, которые не полностью соответсвуют набору условий - и их, я думаю, будет на несколько порядков меньше. Как, по-идее, будет действовать субд в таком варианте - сначала она найдёт все записи соотв каждому набору условий в скобочках и объединит по типу union`а, потом сгруппирует по docid с параллельным накоплением count`а и отсечением тех веток, которые нарушают having. В основном я расчитываю, что этот вариант хорошо распараллеливается (в отличие от join`а), т.е. примерный explain plan для него может выглядеть так:
- filter sort group by
-- union all (index search I_Zapis_Param1)
-- union all (index search I_Zapis_Param2_Param10_Param5)
Union`ы сервер может разделить по двум потокам выполнения, ну потенциально ничего ему не мешает применить оптимизацию для group by.
спустя 13 минут [обр] GRAy(8/259)[досье]
Вот более точный explain plan, который я у себя получил:
спустя 1 час 19 минут [обр] Закиров Руслан(12/343)[досье]
GRAy[досье]
  1. Ваш запрос с HAVING не соответствует запросу 100 млн записей + 100 параметров в каждом - поиск по параметрам (339604), моя табличка была примером.
  2. Попробуйте сравнить HAVING с JOIN на нескольких тысячах записей.
  3. Что вам дает параллельность?
  4. Посмотрите на это со стороны лишних операций. Допустим у вас первый UNION даст 10000 записей и второй столько же, но пересекаться они будут только сотней записей, но до того момента БД должна будет отсортировать 20000 записей, и отфильтровать полученные 19901 группу по количеству элементов в группе.
  5. О какой такой оптимизации GROUP BY идет речь?
  6. Опять же все зависит от БД. Я мыслю в рамках убогой MySQL. B vjue c 60% увереностью утверждать, что Pg тут не далеко уйдет.
спустя 27 минут [обр] GRAy(8/259)[досье]
Закиров Руслан[досье] Чем не соответсвует? Нужные docid не выдаёт? Я проверил и в частности дла вашей таблички - выдаёт. Я не говорю что having это панацея, но при опредённых раскладах по данным - это будет работать не медленней и как раз из-за пресловутой параллельности. СУБД (Oracle в моём случае) сможет вывести каждый из union`ов в отдельный поток исполнения (для многопроцессорного сервера это хорошо ускорит селект в целом), в случае с join`ом ей это будет крайне сложно сделать, т.к. выборка по каждому следующему индексу зависит от предыдущей. Под оптимизацией GROUP BY я имел ввиду раннее отсечение обработки неподходящих под having групп - хотя в тут это скорее всего невозможно. Короче, предлагаю прекратить препираться ;). Я просто привёл потенциально рабочий вариант, но при таких объёмах данных так или иначе надо смотреть на расклад и/или менять структуру.
Powered by POEM™ Engine Copyright © 2002-2005