Как я могу оптимизировать этот запрос LIKE JOIN?

Question

Этот запрос находит суффикс домена:

        SELECT
        DISTINCT ON ("companyDomain".id)
            "companyDomain".domain,
            "publicSuffix".suffix
        FROM
            "companyDomain"
        INNER JOIN
            "publicSuffix"
        ON
            REVERSE("companyDomain".domain) LIKE REVERSE("publicSuffix".suffix) || '%'
        ORDER BY
            "companyDomain".id, LENGTH("publicSuffix".suffix) DESC

Изменить: обратите внимание, что это также работает с поддоменами.

Вы можете поиграть с примером здесь и визуализируйте план с помощью pev . Я пробовал добавлять в таблицы закрывающие индексы, но в итоге планировщик запросов не использовал их. Также, возможно, есть другой запрос, который мог бы быть более эффективным?

Answer 1

Рассматривали ли вы использование индекса gin?

Я внес следующие изменения в ваш образец DML:

CREATE EXTENSION IF NOT EXISTS pg_trgm;
...
CREATE INDEX companyDomain_domain_reverse ON "companyDomain" USING gin (REVERSE(domain) gin_trgm_ops);
...
CREATE INDEX publicSuffix_suffix_reverse ON "publicSuffix" USING gin (REVERSE(suffix) gin_trgm_ops);

А вот план запроса:

+--------------------------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                                              |
+--------------------------------------------------------------------------------------------------------------------------------------------------------+
|Unique  (cost=40802.07..41004.44 rows=908 width=31) (actual time=98.229..98.356 rows=908 loops=1)                                                       |
|  ->  Sort  (cost=40802.07..40903.26 rows=40474 width=31) (actual time=98.228..98.264 rows=1006 loops=1)                                                |
|        Sort Key: "companyDomain".id, (length(("publicSuffix".suffix)::text)) DESC                                                                      |
|        Sort Method: quicksort  Memory: 103kB                                                                                                           |
|        ->  Nested Loop  (cost=0.05..37704.86 rows=40474 width=31) (actual time=1.655..97.976 rows=1006 loops=1)                                        |
|              ->  Seq Scan on "publicSuffix"  (cost=0.00..151.15 rows=8915 width=12) (actual time=0.011..0.728 rows=8915 loops=1)                       |
|              ->  Bitmap Heap Scan on "companyDomain"  (cost=0.05..4.15 rows=5 width=15) (actual time=0.010..0.010 rows=0 loops=8915)                   |
|                    Recheck Cond: (reverse((domain)::text) ~~ (reverse(("publicSuffix".suffix)::text) || '%'::text))                                    |
|                    Rows Removed by Index Recheck: 0                                                                                                    |
|                    Heap Blocks: exact=301                                                                                                              |
|                    ->  Bitmap Index Scan on companydomain_domain_reverse  (cost=0.00..0.05 rows=5 width=0) (actual time=0.010..0.010 rows=0 loops=8915)|
|                          Index Cond: (reverse((domain)::text) ~~ (reverse(("publicSuffix".suffix)::text) || '%'::text))                                |
|Planning Time: 0.150 ms                                                                                                                                 |
|Execution Time: 98.439 ms                                                                                                                               |
+--------------------------------------------------------------------------------------------------------------------------------------------------------+

В качестве бонуса - вам даже не нужно REVERSE() текст в индексе и в запросе:

create index companydomain_domain
    on "companyDomain" using gin(domain gin_trgm_ops);



SELECT DISTINCT ON ("companyDomain".id) "companyDomain".domain, "publicSuffix".suffix
FROM "companyDomain"
         INNER JOIN "publicSuffix" ON "companyDomain".domain LIKE '%' || "publicSuffix".suffix
ORDER BY "companyDomain".id, LENGTH("publicSuffix".suffix) DESC

Запрос занимает такое же количество времени и по-прежнему использует джин index:

+------------------------------------------------------------------------------------------------------------------------------------------------+
|QUERY PLAN                                                                                                                                      |
+------------------------------------------------------------------------------------------------------------------------------------------------+
|Unique  (cost=40556.91..40759.28 rows=908 width=31) (actual time=96.170..96.315 rows=908 loops=1)                                               |
|  ->  Sort  (cost=40556.91..40658.10 rows=40474 width=31) (actual time=96.169..96.209 rows=1006 loops=1)                                        |
|        Sort Key: "companyDomain".id, (length(("publicSuffix".suffix)::text)) DESC                                                              |
|        Sort Method: quicksort  Memory: 103kB                                                                                                   |
|        ->  Nested Loop  (cost=0.05..37459.70 rows=40474 width=31) (actual time=1.764..95.919 rows=1006 loops=1)                                |
|              ->  Seq Scan on "publicSuffix"  (cost=0.00..151.15 rows=8915 width=12) (actual time=0.009..0.711 rows=8915 loops=1)               |
|              ->  Bitmap Heap Scan on "companyDomain"  (cost=0.05..4.12 rows=5 width=15) (actual time=0.010..0.010 rows=0 loops=8915)           |
|                    Recheck Cond: ((domain)::text ~~ ('%'::text || ("publicSuffix".suffix)::text))                                              |
|                    Rows Removed by Index Recheck: 0                                                                                            |
|                    Heap Blocks: exact=301                                                                                                      |
|                    ->  Bitmap Index Scan on companydomain_domain  (cost=0.00..0.05 rows=5 width=0) (actual time=0.010..0.010 rows=0 loops=8915)|
|                          Index Cond: ((domain)::text ~~ ('%'::text || ("publicSuffix".suffix)::text))                                          |
|Planning Time: 0.132 ms                                                                                                                         |
|Execution Time: 96.393 ms                                                                                                                       |
+------------------------------------------------------------------------------------------------------------------------------------------------+

PS: Думаю, вам нужен только один из индексов - в данном случае: companyDomain_domain_reverse

Answer 2

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

Я предлагаю преобразовать домены / суффиксы в массивы, например

alter table "companyDomain" add column adomain text[];
update "companyDomain" set adomain = string_to_array(domain, '.');
create index idx_adom on "companyDomain" using gin (adomain array_ops);

alter table "publicSuffix" add column asuffix text[];
update "publicSuffix" set asuffix = string_to_array(ltrim(suffix, '.'), '.');
create index idx_asuffix on "publicSuffix" using gin (asuffix array_ops);

Давайте сравним эти запросы:

ostgres=# explain (analyze, verbose, buffers)
SELECT  DISTINCT ON ("companyDomain".id)
    "companyDomain".domain,
    "publicSuffix".suffix
FROM
    "companyDomain"
        INNER JOIN "publicSuffix" ON REVERSE("companyDomain".domain) LIKE REVERSE("publicSuffix".suffix) || '%'
ORDER BY "companyDomain".id, LENGTH("publicSuffix".suffix) DESC;
┌────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                                   QUERY PLAN                                                                   │
├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Unique  (cost=185738.35..185940.72 rows=908 width=31) (actual time=2364.720..2364.890 rows=908 loops=1)                                        │
│   Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, (length(("publicSuffix".suffix)::text))                           │
│   Buffers: shared hit=306                                                                                                                      │
│   ->  Sort  (cost=185738.35..185839.53 rows=40474 width=31) (actual time=2364.719..2364.764 rows=1006 loops=1)                                 │
│         Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, (length(("publicSuffix".suffix)::text))                     │
│         Sort Key: "companyDomain".id, (length(("publicSuffix".suffix)::text)) DESC                                                             │
│         Sort Method: quicksort  Memory: 103kB                                                                                                  │
│         Buffers: shared hit=306                                                                                                                │
│         ->  Nested Loop  (cost=0.00..182641.13 rows=40474 width=31) (actual time=22.735..2364.484 rows=1006 loops=1)                           │
│               Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, length(("publicSuffix".suffix)::text)                 │
│               Join Filter: (reverse(("companyDomain".domain)::text) ~~ (reverse(("publicSuffix".suffix)::text) || '%'::text))                  │
│               Rows Removed by Join Filter: 8093814                                                                                             │
│               Buffers: shared hit=306                                                                                                          │
│               ->  Seq Scan on public."publicSuffix"  (cost=0.00..377.15 rows=8915 width=12) (actual time=0.081..0.794 rows=8915 loops=1)       │
│                     Output: "publicSuffix".id, "publicSuffix".suffix, "publicSuffix".created_at, "publicSuffix".asuffix                        │
│                     Buffers: shared hit=288                                                                                                    │
│               ->  Materialize  (cost=0.00..31.62 rows=908 width=15) (actual time=0.001..0.036 rows=908 loops=8915)                             │
│                     Output: "companyDomain".domain, "companyDomain".id                                                                         │
│                     Buffers: shared hit=18                                                                                                     │
│                     ->  Seq Scan on public."companyDomain"  (cost=0.00..27.08 rows=908 width=15) (actual time=11.576..11.799 rows=908 loops=1) │
│                           Output: "companyDomain".domain, "companyDomain".id                                                                   │
│                           Buffers: shared hit=18                                                                                               │
│ Planning Time: 0.167 ms                                                                                                                        │
│ JIT:                                                                                                                                           │
│   Functions: 9                                                                                                                                 │
│   Options: Inlining false, Optimization false, Expressions true, Deforming true                                                                │
│   Timing: Generation 1.956 ms, Inlining 0.000 ms, Optimization 0.507 ms, Emission 10.878 ms, Total 13.341 ms                                   │
│ Execution Time: 2366.971 ms                                                                                                                    │
└────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Узкое место здесь, поскольку Я понимаю, Rows Removed by Join Filter: 8093814

Кажется, что PostgreSQL создает декартово соединение таблиц, а затем фильтрует его, используя условие ON:

select count(*) from "companyDomain", "publicSuffix";
---
8094820

Для обходного пути попробуйте использовать оператор массива :

postgres=# explain (analyze, verbose, buffers)
SELECT  DISTINCT ON ("companyDomain".id)
    "companyDomain".domain,
    "publicSuffix".suffix
FROM
    "companyDomain"
        INNER JOIN "publicSuffix" ON adomain @> asuffix
ORDER BY "companyDomain".id, LENGTH("publicSuffix".suffix) DESC;
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                                 QUERY PLAN                                                                  │
├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Unique  (cost=8310.60..8512.97 rows=908 width=31) (actual time=180.149..180.335 rows=908 loops=1)                                           │
│   Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, (length(("publicSuffix".suffix)::text))                        │
│   Buffers: shared hit=48986                                                                                                                 │
│   ->  Sort  (cost=8310.60..8411.78 rows=40474 width=31) (actual time=180.148..180.200 rows=1239 loops=1)                                    │
│         Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, (length(("publicSuffix".suffix)::text))                  │
│         Sort Key: "companyDomain".id, (length(("publicSuffix".suffix)::text)) DESC                                                          │
│         Sort Method: quicksort  Memory: 145kB                                                                                               │
│         Buffers: shared hit=48986                                                                                                           │
│         ->  Nested Loop  (cost=0.59..5213.39 rows=40474 width=31) (actual time=0.190..179.693 rows=1239 loops=1)                            │
│               Output: "companyDomain".domain, "publicSuffix".suffix, "companyDomain".id, length(("publicSuffix".suffix)::text)              │
│               Buffers: shared hit=48986                                                                                                     │
│               ->  Seq Scan on public."companyDomain"  (cost=0.00..27.08 rows=908 width=57) (actual time=0.015..0.098 rows=908 loops=1)      │
│                     Output: "companyDomain".id, "companyDomain".domain, "companyDomain".created_at, "companyDomain".adomain                 │
│                     Buffers: shared hit=18                                                                                                  │
│               ->  Bitmap Heap Scan on public."publicSuffix"  (cost=0.59..5.15 rows=45 width=54) (actual time=0.052..0.197 rows=1 loops=908) │
│                     Output: "publicSuffix".id, "publicSuffix".suffix, "publicSuffix".created_at, "publicSuffix".asuffix                     │
│                     Recheck Cond: ("companyDomain".adomain @> "publicSuffix".asuffix)                                                       │
│                     Rows Removed by Index Recheck: 572                                                                                      │
│                     Heap Blocks: exact=41510                                                                                                │
│                     Buffers: shared hit=48968                                                                                               │
│                     ->  Bitmap Index Scan on idx_asuffix  (cost=0.00..0.58 rows=45 width=0) (actual time=0.039..0.039 rows=573 loops=908)   │
│                           Index Cond: ("publicSuffix".asuffix <@ "companyDomain".adomain)                                                   │
│                           Buffers: shared hit=7458                                                                                          │
│ Planning Time: 0.189 ms                                                                                                                     │
│ Execution Time: 180.434 ms                                                                                                                  │
└─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Вероятно, это не слишком точно (например, aaa.bbb здесь равно bbb.aaa), но вы можете исправить это в предложении WHERE. В любом случае это будет быстрее.

А пока старые столбцы domain и suffix избыточны, потому что вы можете восстановить их из adomain/asuffix, используя array_to_string(anyarray, text [, text]) функцию .

В качестве альтернативы, чтобы избежать изменений в структуре таблиц, вы можете создать функциональные индексы на string_to_array(), а затем использовать его в фильтрах / объединениях.

Answer 3

Вам нужно совпадение типа

'something.google.com' like '%google.com'

Но вы знаете, что PostgreSQL не будет использовать для этого индекс, потому что строка шаблона начинается с подстановочного знака. Таким образом, вы меняете обе строки:

'moc.elgoog.gnihtemos' like 'moc.elgoog%'

и создаете индекс функции для REVERSE("companyDomain".domain).

Это очень хорошая идея, но PostgreSQL не использует ваш индекс. Это связано с тем, что СУБД не знает, что находится в ваших строках (поскольку это данные таблицы, и СУБД не будет сначала читать всю таблицу, чтобы добраться до плана). В худшем случае все обратные суффиксы будут начинаться с '%'. Если в этом случае СУБД решит выполнить go через индекс, это может стать очень медленным. Вы знаете, что суффиксы не заканчиваются на '%', но СУБД этого не делает и выбирает безопасный план (полное сканирование таблицы).

Это задокументировано здесь: https://www.postgresql.org/docs/9.2/indexes-types.html

Оптимизатор также может использовать индекс B-дерева для запросов, включающих операторы сопоставления с образцом LIKE и ~ , если образец является константой . ..

Я не вижу способа убедить PostgreSQL в том, что использование индекса безопасно. Например, AND REVERSE("publicSuffix".suffix) || '%' NOT LIKE '/%%' ESCCAPE '/' не помогает.

На мой взгляд, лучше всего использовать индексы для RIGHT(domain, 3) и RIGHT(suffix, 3), потому что мы знаем, что суффиксы, включая точку, должны быть длиной не менее трех символов . Это может сузить совпадения, чтобы их можно было использовать.

CREATE INDEX idx_publicSuffix_suffix3 ON "publicSuffix"(RIGHT(suffix, 3) varchar_pattern_ops, suffix);

CREATE INDEX idx_companyDomain_domain3 ON "companyDomain"(RIGHT(domain, 3) varchar_pattern_ops, id, domain);

SELECT DISTINCT ON (cd.id)
  cd.domain,
  ps.suffix
FROM "companyDomain" cd
JOIN "publicSuffix" ps ON cd.domain LIKE '%' || ps.suffix
                       AND RIGHT(cd.domain, 3) = RIGHT(ps.suffix, 3)
ORDER BY cd.id, LENGTH(ps.suffix) DESC;

Демо: https://www.db-fiddle.com/f/dPpVFWjpVJHYFnVut4k7wS/1

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
¦                                                                   QUERY PLAN                                                                                                     ¦
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
¦ Unique  (cost=1684.72..1685.71 rows=198 width=72) (actual time=165.676..165.882 rows=908 loops=1)                                                                                ¦
¦     Buffers: shared hit=4079                                                                                                                                                     ¦
¦     ->  Sort  (cost=1684.72..1685.22 rows=198 width=72) (actual time=165.675..165.723 rows=1006 loops=1)                                                                         ¦
¦           Sort Key: cd.id, (length((ps.suffix)::text)) DESC                                                                                                                      ¦
¦           Sort Method: quicksort Memory: 103kB                                                                                                                                   ¦
¦           Buffers: shared hit=4079                                                                                                                                               ¦
¦           ->  Merge Join  (cost=0.56..1677.17 rows=198 width=72) (actual time=0.090..165.222 rows=1006 loops=1)                                                                  ¦
¦                 Buffers: shared hit=4076                                                                                                                                         ¦
¦                 ->  Index Only Scan using idx_companydomain_domain3 on companyDomain cd  (cost=0.28..93.23 rows=1130 width=36) (actual time=0.018..0.429 rows=908 loops=1)       ¦
¦                       Heap Fetches: 908                                                                                                                                          ¦
¦                       Buffers: shared hit=109                                                                                                                                    ¦
¦                 ->  Materialize  (cost=0.28..602.89 rows=7006 width=32) (actual time=0.019..47.510 rows=390620 loops=1)                                                          ¦
¦                       Buffers: shared hit=3967                                                                                                                                   ¦
¦                       ->  Index Only Scan using idx_publicsuffix_suffix3 on publicSuffix ps  (cost=0.28..585.37 rows=7006 width=32) (actual time=0.015..2.798 rows=8354 loops=1) ¦
¦                             Heap Fetches: 8354                                                                                                                                   ¦
¦                             Buffers: shared hit=3967                                                                                                                             ¦
¦ Planning time: 0.471 ms                                                                                                                                                          ¦
¦ Execution time: 166.054 ms                                                                                                                                                       ¦
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Answer 4

Как насчет:

SELECT 
  DISTINCT ON ("companyDomain".id) "companyDomain".domain, 
  "publicSuffix".suffix 
FROM 
  "companyDomain" 
  INNER JOIN "publicSuffix" ON RIGHT(
    domain, 
    - POSITION('.' IN domain) + 1
  ) = "publicSuffix".suffix 
ORDER BY 
  "companyDomain".id, 
  LENGTH("publicSuffix".suffix) DESC;

Мы получаем позицию первого . в домене, затем используем отрицательное значение этого (+1, чтобы включить первое .), чтобы извлечь суффикс от RIGHT слева.

Похоже, он работает намного быстрее, от 2500 мс до 120 мс.

Live test