Алгоритм нахождения самого длинного префикса

11

У меня есть две таблицы.

Первый - это таблица с префиксами

code name price
343  ek1   10
3435 nt     4
3432 ek2    2

Во-вторых, записи звонков с номерами телефонов

number        time
834353212     10
834321242     20
834312345     30

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

 number        code   ....
 834353212     3435
 834321242     3432
 834312345     343

Для числа 834353212 мы должны обрезать '8', а затем найти самый длинный код из таблицы префиксов, его 3435.
Мы всегда должны сначала сбрасывать '8', а префикс должен быть в начале.

Я решил эту задачу очень давно, очень плохо. Это был ужасный Perl-скрипт, который делает много запросов для каждой записи. Этот скрипт:

  1. Возьмите номер из таблицы звонков, сделайте подстроку от длины (число) до префикса 1 => $ в цикле

  2. Выполните запрос: выберите количество (*) из префиксов, где код, например, $ prefix

  3. Если count> 0, тогда возьмите первые префиксы и запишите в таблицу

Первая проблема - это количество запросов call_records * length(number). Вторая проблема - LIKEвыражения. Я боюсь, что это медленно.

Я попытался решить вторую проблему:

CREATE EXTENSION pg_trgm;
CREATE INDEX prefix_idx ON prefix USING gist (code gist_trgm_ops);

Это ускоряет каждый запрос, но не решает проблему в целом.

У меня есть 20k префиксов и 170K номер сейчас, и мое старое решение плохо. Похоже, мне нужно новое решение без петель.

Только один запрос для каждой записи о вызове или что-то вроде этого.

Корявин Иван
источник
2
Я не совсем уверен, если codeв первой таблице совпадает с префиксом позже. Не могли бы вы уточнить это? Также будет приветствоваться некоторая фиксация данных примера и желаемого результата (чтобы легче было следить за вашей проблемой).
Дезсо
Ага. Вы правы. Я забыл написать о «8». Спасибо.
Корявин Иван
2
префикс должен быть в начале, верно?
Дезсо
Да. Со второго места. 8 $ префикс $ цифры
Корявин Иван
Какова мощность ваших столов? 100к номеров? Сколько префиксов?
Эрвин Брандштеттер

Ответы:

21

Я предполагаю тип данных textдля соответствующих столбцов.

CREATE TABLE prefix (code text, name text, price int);
CREATE TABLE num (number text, time int);

«Простое» решение

SELECT DISTINCT ON (1)
       n.number, p.code
FROM   num n
JOIN   prefix p ON right(n.number, -1) LIKE (p.code || '%')
ORDER  BY n.number, p.code DESC;

Ключевые элементы:

DISTINCT ONявляется расширением Postgres стандарта SQL DISTINCT. Найдите подробное объяснение используемой техники запросов в этом связанном ответе на SO .
ORDER BY p.code DESCвыбирает самое длинное совпадение, потому что '1234'сортирует после '123'(в порядке возрастания).

Простая SQL Fiddle .

Без индекса запрос будет выполняться очень долго (не дожидаясь его завершения). Чтобы сделать это быстро, вам нужна поддержка индекса. Упомянутые вами индексы триграмм, предоставляемые дополнительным модулем, pg_trgmявляются хорошим кандидатом. Вы должны выбрать между GIN и GiST index. Первый символ чисел является просто шумом и может быть исключен из индекса, что делает его дополнительно функциональным индексом.
В моих тестах функциональный индекс GIN триграммы выиграл гонку за индекс GiST триграммы (как и ожидалось):

CREATE INDEX num_trgm_gin_idx ON num USING gin (right(number, -1) gin_trgm_ops);

Продвинутый dbfiddle здесь .

Все результаты теста получены из локальной тестовой установки Postgres 9.1 с сокращенной настройкой: номера 17k и коды 2k:

  • Общее время выполнения: 1719,552 мс (триграмма GiST)
  • Общее время выполнения: 912,329 мс (триграмма GIN)

Еще быстрее

Неудачная попытка с text_pattern_ops

Как только мы игнорируем отвлекающий первый шумовой символ, он сводится к базовому левому привязанному образцу. Поэтому я попробовал функциональный индекс B-дерева с классом оператораtext_pattern_ops (предполагая тип столбца text).

CREATE INDEX num_text_pattern_idx ON num(right(number, -1) text_pattern_ops);

Это отлично работает для прямых запросов с одним поисковым термином и делает индекс триграммы плохим в сравнении:

SELECT * FROM num WHERE right(number, -1) LIKE '2345%'
  • Общее время выполнения: 3,816 мс (trgm_gin_idx)
  • Общее время выполнения: 0,147 мс (text_pattern_idx)

Однако планировщик запросов не будет учитывать этот индекс для объединения двух таблиц. Я видел это ограничение раньше. У меня пока нет значимого объяснения этому.

Частичные / функциональные индексы B-дерева

Альтернатива - использовать проверки на равенство для частичных строк с частичными индексами. Это может быть использовано в JOIN.

Поскольку у нас обычно ограниченное количество different lengthsпрефиксов, мы можем построить решение, подобное представленному здесь, с частичными индексами.

Скажем, у нас есть префиксы от 1 до 5 символов. Создайте несколько частичных функциональных индексов, один для каждой отдельной длины префикса:

CREATE INDEX prefix_code_idx5 ON prefix(code) WHERE length(code) = 5;
CREATE INDEX prefix_code_idx4 ON prefix(code) WHERE length(code) = 4;
CREATE INDEX prefix_code_idx3 ON prefix(code) WHERE length(code) = 3;
CREATE INDEX prefix_code_idx2 ON prefix(code) WHERE length(code) = 2;
CREATE INDEX prefix_code_idx1 ON prefix(code) WHERE length(code) = 1;

Поскольку это частичные индексы, все они вместе чуть больше одного полного индекса.

Добавьте соответствующие индексы для чисел (с учетом начального шумового символа):

CREATE INDEX num_number_idx5 ON num(substring(number, 2, 5)) WHERE length(number) >= 6;
CREATE INDEX num_number_idx4 ON num(substring(number, 2, 4)) WHERE length(number) >= 5;
CREATE INDEX num_number_idx3 ON num(substring(number, 2, 3)) WHERE length(number) >= 4;
CREATE INDEX num_number_idx2 ON num(substring(number, 2, 2)) WHERE length(number) >= 3;
CREATE INDEX num_number_idx1 ON num(substring(number, 2, 1)) WHERE length(number) >= 2;

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

Если эта стоимость слишком высока для вас (важна производительность записи / слишком много операций записи / дискового пространства), вы можете пропустить эти индексы. Остальное все еще быстрее, если не так быстро, как могло бы быть ...

Если числа никогда не короче nсимволов, отбросьте лишние WHEREпредложения из некоторых или всех, а также отбросьте соответствующее WHEREпредложение из всех последующих запросов.

Рекурсивный CTE

После всех настроек я надеялся на очень элегантное решение с рекурсивным CTE :

WITH RECURSIVE cte AS (
   SELECT n.number, p.code, 4 AS len
   FROM   num n
   LEFT    JOIN prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5

   UNION ALL 
   SELECT c.number, p.code, len - 1
   FROM    cte c
   LEFT   JOIN prefix p
            ON  substring(number, 2, c.len) = p.code
            AND length(c.number) >= c.len+1  -- incl. noise character
            AND length(p.code) = c.len
   WHERE    c.len > 0
   AND    c.code IS NULL
   )
SELECT number, code
FROM   cte
WHERE  code IS NOT NULL;
  • Общее время выполнения: 1045,115 мс

Однако, хотя этот запрос не плохой - он работает примерно так же хорошо, как простая версия с индексом GIN триграммы - он не дает того, к чему я стремился. Рекурсивный термин планируется только один раз, поэтому он не может использовать лучшие индексы. Только нерекурсивный термин может.

СОЮЗ ВСЕХ

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

SELECT DISTINCT ON (1) number, code
FROM  (
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 4) = p.code
            AND length(n.number) >= 5
            AND length(p.code) = 4
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 3) = p.code
            AND length(n.number) >= 4
            AND length(p.code) = 3
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 2) = p.code
            AND length(n.number) >= 3
            AND length(p.code) = 2
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 1) = p.code
            AND length(n.number) >= 2
            AND length(p.code) = 1
   ) x
ORDER BY number, code DESC;
  • Общее время выполнения: 57,578 мс (!!)

Прорыв, наконец-то!

Функция SQL

Включение этого в функцию SQL устраняет накладные расходы на планирование запросов для повторного использования:

CREATE OR REPLACE FUNCTION f_longest_prefix()
  RETURNS TABLE (number text, code text) LANGUAGE sql AS
$func$
SELECT DISTINCT ON (1) number, code
FROM  (
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 4) = p.code
            AND length(n.number) >= 5
            AND length(p.code) = 4
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 3) = p.code
            AND length(n.number) >= 4
            AND length(p.code) = 3
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 2) = p.code
            AND length(n.number) >= 3
            AND length(p.code) = 2
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 1) = p.code
            AND length(n.number) >= 2
            AND length(p.code) = 1
   ) x
ORDER BY number, code DESC
$func$;

Вызов:

SELECT * FROM f_longest_prefix_sql();
  • Общее время выполнения: 17,138 мс (!!!)

Функция PL / pgSQL с динамическим SQL

Эта функция plpgsql очень похожа на рекурсивный CTE, описанный выше, но динамический SQL EXECUTEзаставляет запрос перепланироваться для каждой итерации. Теперь он использует все индивидуальные индексы.

Кроме того, это работает для любого диапазона длин префикса. Функция принимает два параметра для диапазона, но я подготовил его со DEFAULTзначениями, поэтому он работает и без явных параметров:

CREATE OR REPLACE FUNCTION f_longest_prefix2(_min int = 1, _max int = 5)
  RETURNS TABLE (number text, code text) LANGUAGE plpgsql AS
$func$
BEGIN
FOR i IN REVERSE _max .. _min LOOP  -- longer matches first
   RETURN QUERY EXECUTE '
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(n.number, 2, $1) = p.code
            AND length(n.number) >= $1+1  -- incl. noise character
            AND length(p.code) = $1'
   USING i;
END LOOP;
END
$func$;

Последний шаг не может быть легко включен в одну функцию. Либо просто назовите это так:

SELECT DISTINCT ON (1)
       number, code
FROM   f_longest_prefix_prefix2() x
ORDER  BY number, code DESC;
  • Общее время выполнения: 27,413 мс

Или используйте другую функцию SQL в качестве оболочки:

CREATE OR REPLACE FUNCTION f_longest_prefix3(_min int = 1, _max int = 5)
  RETURNS TABLE (number text, code text) LANGUAGE sql AS
$func$
SELECT DISTINCT ON (1)
       number, code
FROM   f_longest_prefix_prefix2($1, $2) x
ORDER  BY number, code DESC
$func$;

Вызов:

SELECT * FROM f_longest_prefix3();
  • Общее время выполнения: 37,622 мс

Немного медленнее из-за необходимости планирования. Но более универсальный, чем SQL и более короткий для более длинных префиксов.

Эрвин Брандштеттер
источник
Я все еще проверяю, но выглядит отлично! Ваша идея «поменяться» как у оператора - гениальна. Почему я был так глуп; (
Корявин Иван
5
Ничего себе! это довольно редактировать. Я хотел бы снова поднять голос.
swasheck
3
Я учусь на вашем удивительном ответе больше, чем за последние два года. 17-30 мс против нескольких часов в моем цикле? Это волшебство.
Корявин Иван
1
@KorjavinIvan: Ну, как документально подтверждено, я тестировал с уменьшенной настройкой 2k префиксов / 17k номеров. Но это должно очень хорошо масштабироваться, и мой тестовый компьютер был крошечным сервером. Таким образом, вы должны оставаться на втором месте в реальной жизни.
Эрвин Брандштеттер
1
Хороший ответ ... Знаете ли вы расширение префикса Дмитрия ? Не могли бы вы включить это в сравнение тестовых случаев?
MatheusOl
0

Строка S является префиксом строки T, если T находится между S и SZ, где Z лексикографически больше, чем любая другая строка (например, 99999999 с достаточным количеством 9, чтобы превысить максимально длинный номер телефона в наборе данных, или иногда 0xFF будет работать).

Самый длинный общий префикс для любого данного T также лексикографически максимален, поэтому простая группа по max и найдет его.

select n.number, max(p.code) 
from prefixes p
join numbers n 
on substring(n.number, 2, 255) between p.code and p.code || '99999999'
group by n.number

Если это происходит медленно, это, вероятно, связано с вычисленными выражениями, поэтому вы также можете попробовать материализовать p.code || '999999' в столбец таблицы кодов с собственным индексом и т. Д.

KWillets
источник