базы данных - эффективный поиск текста

Question

У меня есть таблица, которая содержит строки URL, т.е.

/A/B/C 
/C/E 
/C/B/A/R 

Каждая строка разбивается на лексемы, где разделитель в моем случае «/». Тогда я задаю целое значение для каждого маркера и поместить их в словарь (разные таблицы базы данных), то есть

A : 1 
B : 2 
C : 3 
E : 4 
D : 5 
G : 6 
R : 7 

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

3, 2 

, и я хотел бы найти следующие строки

/A/B/C 
/C/B/A/R 

Как сделать это эффективно. Под этим я подразумеваю, как создать надлежащую структуру базы данных.

Я использую PostgreSQL, решение должно хорошо работать для 2 миллионов строк в первой таблице.

Чтобы прояснить мой пример - мне нужно, чтобы оба «B» и «C» находились в URL-адресе. Также «B» и «C» могут встречаться в любом порядке в URL-адресе.

Мне нужен эффективный SELECT. INSERT не должен быть эффективным. Мне не нужно выполнять всю работу в SQL, если это ничего не изменит.

Заранее благодарен

Answer 1

Я не уверен, как это сделать, но я просто даю вам некоторую идею, которая может быть полезна. У вас уже есть начальная таблица. Вы обрабатываете и создаете таблицу токенов:

+------------+---------+ 
| TokenValue | TokenId | 
+------------+---------+ 
| A   |  1 | 
| B   |  2 | 
| C   |  3 | 
| E   |  4 | 
| D   |  5 | 
| G   |  6 | 
| R   |  7 | 
+------------+---------+ 

Это нормально для меня. Теперь я должен создать новую таблицу, в которой я бы сопоставлял исходную таблицу с токенами таблицы токенов (OrderedTokens). Что-то вроде:

+-------+---------+---------+ 
| UrlID | TokenId | AnOrder | 
+-------+---------+---------+ 
|  1 |  1 |  1 | 
|  1 |  2 |  2 | 
|  1 |  3 |  3 | 
|  2 |  5 |  1 | 
|  2 |  2 |  2 | 
|  2 |  1 |  3 | 
|  2 |  7 |  4 | 
|  3 |  3 |  1 | 
|  3 |  4 |  2 | 
+-------+---------+---------+ 

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

select string_agg(t.tokenValue, '/' order by ot.anOrder) as OriginalUrl 
from OrderedTokens as ot 
join tokens t on t.tokenId = ot.tokenId 
group by ot.urlId 

предыдущий запрос приведет:

+-------------+ 
| OriginalUrl | 
+-------------+ 
| A/B/C  | 
| D/B/A/R  | 
| C/E   | 
+-------------+ 

Таким образом, вы даже не нуждаются в вашей исходной таблицы больше. Если вы хотите получить Urls, которые имеют какой-либо из предусмотренных лексем идентификаторов (в данном случае B ИЛИ C), вы sould использовать это:

select string_agg(t.tokenValue, '/' order by ot.anOrder) as OriginalUrl 
from OrderedTokens as ot 
join Tokens t on t.tokenId = ot.tokenId 
group by urlid 
having count(case when ot.tokenId in (2, 3) then 1 end) > 0 

Это приводит к:

+-------------+ 
| OriginalUrl | 
+-------------+ 
| A/B/C  | => It has both B and C 
| D/B/A/R  | => It has only B 
| C/E   | => It has only C 
+-------------+ 

Теперь, если вы хочу получить все Urls, которые имеют ОБА идентификаторов, то попробуйте следующее:

select string_agg(t.tokenValue, '/' order by ot.anOrder) as OriginalUrl 
from OrderedTokens as ot 
join Tokens t on t.tokenId = ot.tokenId 
group by urlid 
having count(distinct case when ot.tokenId in (2, 3) then ot.tokenId end) = 2 

Добавить в count всех идентификаторах вы хотите отфильтровать, а затем равно, что подсчитать количество добавленных вами идентификаторов. Предыдущий запрос приведет к:

+-------------+ 
| OriginalUrl | 
+-------------+ 
| A/B/C  | => It has both B and C 
+-------------+ 

Забавно, что ни одно из предложенных нами решений не привело к ожидаемому результату. Итак, я неправильно понял ваши требования или ожидаемый результат, который вы указали неправильно?

Дайте мне знать, если это правильно.

Answer 2

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

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

SELECT DISTINCT 
    u.url 
FROM 
    urls u 
INNER JOIN 
    dictionary d 
ON 
    d.id IN (3, 2) 
    AND u.url ~ E'\\m' || d.url_component || E'\\m' 

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

Если вы хотите оптимизировать производительность запросов, вы можете создать ссылочную таблицу компонентов URL; это выглядело бы примерно так:

/A/B/C A 
/A/B/C B 
/A/B/C C 
/C/E  C 
/C/E  E 
/D/B/A/R D 
/D/B/A/R B 
/D/B/A/R A 
/D/B/A/R R 

Затем вы можете создать кластерный индекс в этой таблице в компоненте URL. Этот запрос будет быстро получать ваши результаты:

SELECT DISTINCT 
    u.full_url 
FROM 
    url_components u 
INNER JOIN 
    dictionary d 
ON 
    d.id IN (3, 2) 
    AND u.url_component = d.url_component 

В принципе, этот подход перемещает сложность запроса спереди. Если вы делаете несколько вставок, но много запросов к этим данным, то это подходит.

Создание этой таблицы компонентов URL является тривиальным, в зависимости от того, какие инструменты у вас имеются. Простой скрипт awk может работать через ваши записи 2M через минуту или две, а последующая копия обратно в базу данных также будет быстрой. Если вам нужно поддерживать обновления в реальном времени в этой таблице, я бы рекомендовал не-SQL-решение: независимо от того, какое кодирование вашего приложения может использовать регулярные выражения для анализа URL-адреса и вставки компонентов в таблицу компонентов. Если вы ограничены использованием базы данных, то триггер insert может выполнять ту же роль, но это будет более хрупкий подход.