Оптимизация процесса для больших наборов данных - PullRequest
2 голосов
/ 27 августа 2010

В настоящее время у меня есть проект, в котором мы имеем дело с 30 миллионами + ключевых слов для рекламы с оплатой за клик.Мы поддерживаем эти списки в Oracle.Есть моменты, когда нам нужно удалить определенные ключевые слова из списка.Процесс включает в себя различные политики соответствия типов, чтобы определить, следует ли удалять ключевые слова:

  • EXACT : WHERE keyword = '{term}'
  • СОДЕРЖИТ : WHERE keyword LIKE '%{term}%'
  • TOKEN : WHERE keyword LIKE '% {term} %' OR keyword LIKE '{term} %' OR keyword LIKE '% {term}'

Теперь, когда список обрабатывается, он может использовать только один из типов совпадений, перечисленных выше.,Но все ключевые слова 30mil + должны быть проверены на совпадения, возвращая результаты для совпадений.В настоящее время этот процесс может занимать часы / дни в зависимости от количества ключевых слов в списке ключевых слов для поиска.

Есть ли у вас какие-либо предложения о том, как оптимизировать процесс, чтобы он работал намного быстрее?

ОБНОВЛЕНИЕ: Вот пример запроса для поиска Holiday Inn:

SELECT * FROM keyword_list 
WHERE
(
lower(text) LIKE 'holiday inn' OR
lower(text) LIKE '% holiday inn %' OR
lower(text) LIKE 'holiday inn %'
);

Вот пастбина для вывода EXPLAIN: http://pastebin.com/tk74uhP4

Некоторая дополнительная информация, которая может быть полезна.Ключевое слово может состоять из нескольких слов, таких как:

  • это пример ключевого слова
  • мне нравятся мои ключевые слова
  • ключевые слова отличные

Ответы [ 7 ]

5 голосов
/ 27 августа 2010

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

Единственные совпадения, которые могут использовать индекс, это те, которые начинаются с жестко закодированной строки (например, keyword LIKE '{term} %').

Чтобы обойти эту проблему, создайте новую таблицу индексации (не путать с индексом таблицы базы данных), сопоставляя отдельные термины со строками ключевых слов, ограничивающими эти термины;тогда ваш keyword LIKE '% {term} %' становится t1.keyword = index_table.keyword and index_table.term="{term}".

3 голосов
/ 27 августа 2010

Я знаю, что мой подход может выглядеть как ересь для ребят из RDBMS, но я проверял это много раз на практике, и в этом нет никакой магии. Нужно просто немного узнать о возможных скоростях ввода-вывода и обработки, а также о некоторых простых вычислениях. Короче говоря, СУБД не является подходящим инструментом для такого рода обработки.

Исходя из моего опыта, Perl способен выполнять сканирование регулярных выражений примерно в миллионах в секунду. Я не знаю, насколько быстро вы можете вывести его из базы данных (MySQL может работать до 200krows / s, поэтому вы можете сбросить все ваши ключевые слова за 2,5 минуты, я знаю, что Oracle здесь намного хуже, но я надеюсь, что это не более десяти раз т.е. 25 мин). Если ваши данные в среднем составляют 20 символов, ваш дамп будет 600 МБ, для 100 символов - 3 ГБ. Это означает, что при низкой скорости 100 МБ / с ваш ввод-вывод займет от 6 до 30 с. (Все задействованные операции ввода-вывода последовательны!) Это практически ничто по сравнению со временем дампа и обработки в perl. Сканирование может замедлиться до 100 к / с в зависимости от количества ключевых слов, которые вы хотите удалить (я испытал регулярное выражение с 500 шаблонами ветвления с этой скоростью), поэтому вы можете обработать полученные данные менее чем за 5 минут. Если полученная мощность не будет огромной (в десятки сотен), выходной IO не должен быть проблемой. В любом случае ваша обработка должна быть в минутах, а не часах. Если вы сгенерируете целые значения ключевых слов для удаления, вы можете использовать индекс в операции удаления, поэтому вы сгенерируете серию DELETE FROM <table> WHERE keyword IN (...), заполненную ключевыми словами, для удаления в количестве вплоть до максимальной длины оператора SQL. Вы также можете попробовать вариант, где вы будете загружать эти данные во временную таблицу, а затем использовать соединение. Я не знаю, что будет быстрее в Oracle. Это займет около 10 минут в MySQL. Вам не повезло, что вам приходится иметь дело с Oracle, но вы сможете удалить сотни {term} менее чем за час.

PS: Я бы порекомендовал вам использовать что-то с лучшими регулярными выражениями, такими как http://code.google.com/p/re2/ (включено в V8, также называемый node.js) или новый двоичный модуль в Erlang R14A, но слабый механизм регулярных выражений в perl не будет слабым местом в этой задаче это будет RDBMS.

2 голосов
/ 28 августа 2010

Ваш план объяснения говорит, что этот запрос должен занять минуту, но на самом деле он занимает часы? Простой тест на моем домашнем ПК подтверждает, что минута кажется разумной для этого запроса. И на сервере с некоторым приличным вводом-выводом это, вероятно, займет всего несколько секунд.

Проблема в том, что вы выполняете один и тот же запрос десятки раз последовательно для разных ключевых слов? Если это так, вам нужно объединить все поиски вместе, чтобы отсканировать таблицу только один раз.

2 голосов
/ 27 августа 2010

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

KEYWORD1 KEYWORD2 KEYWORD3

. Из-за этого вы вынуждены использовать LIKE для поискаи это, вероятно, причина медлительности.

Хотя я понимаю, что это может быть несколько болезненно, возможно, было бы лучше создать вторую таблицу, возможно, называемую KEYWORDS, которая будет содержать отдельные ключевые слова, которые относятся к данномузапись базовой таблицы (я буду называть базовую таблицу PPC, поскольку не знаю, как она на самом деле называется).Предполагая, что ваша текущая базовая таблица выглядит следующим образом:

CREATE TABLE PPC
 (ID_PPC       NUMBER PRIMARY KEY,
  KEYWORD      VARCHAR2(1000),
  <other fields>...);

Что бы вы могли сделать, это перестроить таблицы следующим образом:

CREATE TABLE NEW_PPC
 (ID_PPC       NUMBER PRIMARY KEY,
  <other fields>...);

CREATE TABLE NEW_PPC_KEYWORD
 (ID_NEW_PPC       NUMBER,
  KEYWORD      VARCHAR2(25),  -- or whatever is appropriate for a single keyword
  PRIMARY KEY (ID_NEW_PPC, KEYWORD));

CREATE INDEX NEW_PPC_KEYWORD_1
  ON NEW_PPC_KEYWORD(KEYWORD);

Заполните таблицу NEW_PPC_KEYWORD, потянувотдельные ключевые слова из старого поля PPC.KEYWORD, поместив их в таблицу NEW_PPC_KEYWORD.Имея только одно ключевое слово в каждой записи в NEW_PPC_KEYWORD, вы теперь можете использовать простое объединение, чтобы извлечь все записи в NEW_PPC, которые имеют ключевое слово, выполнив что-то вроде

SELECT P.*
  FROM NEW_PPC P
INNER JOIN NEW_PPC_KEYWORD K
  ON (K.ID_NEW_PPC = P.ID_NEW_PPC)
WHERE K.KEYWORD = '<whatever>';

Поделиться и наслаждаться.

2 голосов
/ 27 августа 2010

Информации недостаточно, чтобы дать какой-либо конкретный совет.Если дорогостоящее совпадение LIKE неизбежно, то единственное, что я вижу в данный момент, это:

В настоящее время этот процесс может занимать часы / дни в зависимости от количества ключевых слов в списке.ключевых слов для поиска.

Вы пытались кэшировать результаты запросов в таблице?Ключевое слово для ввода?

Поскольку я не верю, что весь набор данных, все ключевые слова могут измениться в одночасье.И поскольку они не меняются очень часто, имеет смысл просто сохранять результаты в дополнительной таблице, предварительно рассчитанной, чтобы будущие запросы по ключевому слову можно было разрешить через кеш, а не повторять записи 30Mil.Очевидно, что для таблицы кеша необходимо выполнить какое-то периодическое обслуживание: когда ключевые слова модифицируются / удаляются и когда списки модифицируются, записи в кэш-памяти должны обновляться заново.Чтобы упростить обновление, в таблице кэша также должен содержаться идентификатор исходных строк в таблице keyword_list, которые предоставили результаты.


В ОБНОВЛЕНИЕ : вставка данных вТаблица списка ключевых слов уже в нижнем регистре.Используйте дополнительную строку, если исходный случай необходим для дальнейшего использования.


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

select AD.id
from DICT, AD
where 
  DICT.word = :input_word and
  DICT.word_id = AD.word_id

DICT - это таблица со словами, а AD (аналог вашего keyword_list) со словами из рекламы.

По сути, проблему можно охарактеризовать как «полное сканирование таблицы» .Это довольно распространенная проблема, часто подчеркивающая плохой дизайн макета данных.Поиск в сети для получения дополнительной информации о том, что можно сделать. У SO тоже много записей .

1 голос
/ 24 апреля 2011

Мой совет - увеличить размер кэша до сотен гигабайт.Кидай железо в него.Если вы не можете построить кластер Беовульф или построить систему поиска пространства binAry.

1 голос
/ 27 августа 2010

Вы можете посмотреть индексирование Oracle Text .Он предназначен для поддержки того типа поиска в тексте, о котором вы говорите.

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