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

Я предполагаю тип данных 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 и более короткий для более длинных префиксов.

Эрвин Брандштеттер
источник

Я все еще проверяю, но выглядит отлично! Ваша идея «поменяться» как у оператора - гениальна. Почему я был так глуп; (

Корявин Иван

Ничего себе! это довольно редактировать. Я хотел бы снова поднять голос.

swasheck

Я учусь на вашем удивительном ответе больше, чем за последние два года. 17-30 мс против нескольких часов в моем цикле? Это волшебство.

Корявин Иван

@KorjavinIvan: Ну, как документально подтверждено, я тестировал с уменьшенной настройкой 2k префиксов / 17k номеров. Но это должно очень хорошо масштабироваться, и мой тестовый компьютер был крошечным сервером. Таким образом, вы должны оставаться на втором месте в реальной жизни.

Эрвин Брандштеттер

Хороший ответ ... Знаете ли вы расширение префикса Дмитрия ? Не могли бы вы включить это в сравнение тестовых случаев?

MatheusOl