Объединение двух больших таблиц postgres с использованием int8range, не масштабирующихся хорошо

Ответ 1

Я думал первоначально о боковом соединении, как и в других предложенных подходах (например, последний запрос Эрвина Брандстретера, где он использует простой тип данных int8 и простые индексы), но не хотел писать его в ответ, потому что я думал, что это не очень эффективно. Когда вы пытаетесь найти все диапазоны netblock, которые покрывают заданный диапазон, индекс не очень помогает.

Я повторю запрос Erwin Brandstetter:

SELECT *  -- only select columns you need to make it faster
FROM   routing_details r
     , LATERAL (
   SELECT *
   FROM   netblock_details n
   WHERE  n.ip_min <= r.ip_min
   AND    n.ip_max >= r.ip_max
   ORDER  BY n.ip_max - n.ip_min
   LIMIT  1
   ) n;

Когда у вас есть индекс в netblock_details, например:

CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details 
(ip_min, ip_max DESC NULLS LAST);

вы можете быстро (в O(logN)) найти начальную точку сканирования в таблице netblock_details - либо максимум n.ip_min, который меньше, чем r.ip_min, либо минимальный n.ip_max, который больше, чем r.ip_max. Но тогда вам придется сканировать/читать остальную часть индекса/таблицы, а для каждой строки делать вторую часть проверки и фильтровать большинство строк.

Другими словами, этот индекс помогает быстро найти начальную строку, которая удовлетворяет первым критериям поиска: n.ip_min <= r.ip_min, но затем вы продолжите чтение всех строк, удовлетворяющих этим критериям, и для каждой такой строки выполните вторую проверку n.ip_max >= r.ip_max. В среднем (если данные имеют равномерное распределение), вам нужно будет прочитать половину строк таблицы netblock_details. Оптимизатор может сначала использовать индекс для поиска n.ip_max >= r.ip_max, а затем применить второй фильтр n.ip_min <= r.ip_min, но вы не можете использовать этот индекс для одновременного применения обоих фильтров.

Конечный результат: для каждой строки из routing_details мы будем читать половину строк из netblock_details. 600K * 4M = 2 400 000 000 000 строк. Это в 2 раза лучше, чем декартово произведение. Вы можете увидеть это число (декартово произведение) на выходе EXPLAIN ANALYZE в вопросе.

592,496 * 8,221,675 = 4,871,309,550,800

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

Общий процесс высокого уровня для достижения конечного результата:

• присоединяйтесь к двум таблицам (не найдя лучшего совпадения). В худшем случае это декартово произведение, в лучшем случае все покрытия охватывают от netblock_details для каждого диапазона от routing_details. Вы сказали, что в netblock_details есть несколько записей для каждой записи в routing_details, что угодно от 3 до 10. Таким образом, результат этого объединения может иметь ~ 6M строк (не слишком много)

• упорядочить/разделить результат объединения по диапазонам routing_details и для каждого такого диапазона найти наилучший (наименьший) диапазон покрытия от netblock_details.

Моя идея - отменить запрос. Вместо того, чтобы находить все диапазоны покрытия от большего netblock_details для каждой строки из меньшей таблицы routing_details, я предлагаю найти все меньшие диапазоны от меньшего routing_details для каждой строки от большего netblock_details.

Двухэтапный процесс

Для каждой строки из более крупного netblock_details найдите все диапазоны от routing_details, которые находятся внутри диапазона netblock.

Я бы использовал следующую схему в запросах. Я добавил первичный ключ ID в обе таблицы.

CREATE TABLE routing_details (
ID        int
,ip_min   int8
,ip_max   int8
,asn      text
,netblock text
);

CREATE TABLE netblock_details (
ID        int
,ip_min   int8
,ip_max   int8
,name     text
,country  text
,source   text
);

SELECT
    netblock_details.ID AS n_ID
    ,netblock_details.ip_max - netblock_details.ip_min AS n_length
    ,r.ID AS r_ID
FROM
    netblock_details
    INNER JOIN LATERAL
    (
        SELECT routing_details.ID
        FROM routing_details
        WHERE
            routing_details.ip_min >= netblock_details.ip_min
            AND routing_details.ip_min <= netblock_details.ip_max
            -- note how routing_details.ip_min is limited from both sides
            -- this would make it possible to scan only (hopefully) small
            -- portion of the table instead of full or half table
            AND routing_details.ip_max <= netblock_details.ip_max
            -- this clause ensures that the whole routing range
            -- is inside the netblock range
    ) AS r ON true

Нам нужен индекс на routing_details на (ip_min, ip_max). Главное здесь - индекс на ip_min. Наличие второго столбца в индексе помогает, устраняя необходимость выполнять поиск значения ip_max; это не помогает в поиске дерева.

Обратите внимание, что в боковом подзапросе нет LIMIT. Это еще не окончательный результат. Этот запрос должен возвращать строки ~ 6M. Сохраните этот результат во временной таблице. Добавьте индекс во временную таблицу на (r_ID, n_length, n_ID). n_ID снова просто удалить дополнительные запросы. Нам нужен индекс, чтобы избежать сортировки данных для каждого r_ID.

Заключительный шаг

Для каждой строки из routing_details найдите n_ID с наименьшим n_length. Теперь мы можем использовать боковое соединение в "правильном" порядке. Здесь temp таблица является результатом предыдущего шага с индексом.

SELECT
    routing_details.*
    ,t.n_ID
    ,netblock_details.*
FROM
    routing_details
    INNER JOIN LATERAL
    (
        SELECT temp.n_ID
        FROM temp
        WHERE temp.r_ID = routing_details.ID
        ORDER BY temp.n_length
        LIMIT 1
    ) AS t ON true
    INNER JOIN netblock_details ON netblock_details.ID = t.n_ID

Здесь в подзапросе должен быть поиск индекса, а не сканирование. Оптимизатор должен быть достаточно умным, чтобы выполнять поиск и возвращать первый найденный результат из-за LIMIT 1, поэтому у вас будет 600K запросов индекса в таблице темпов строки 6M.

Оригинальный ответ (я сохраню его только для диаграммы диапазонов):

Можете ли вы "обмануть"?

Если я правильно понял ваш запрос, для каждого routing_details.range вы хотите найти наименьший netblock_details.range, который покрывает/больше, чем routing_details.range.

В следующем примере, где r - диапазон маршрутизации, а n1, ..., n8 - диапазоны netblock, правильный ответ n5.

   |---|
   n1

     |------------------|
     n2

                           |---------------|
                           n3

                                          |-----|
                                          n4

                  |------------------|
                  n5

                     |--------------------------------------|
                     n6

        |---------------------------|
        n7

                      |-----|
                      n8

                      |------------|
                      r
                     start       end

n.start <= r.start AND n.end >= r.end
order by n.length
limit 1 

Ваш запрос который занял 14 часов, показывает, что сканирование индекса заняло 6 мс, но сортировка по длине диапазона заняла 80 мс.

При таком поиске нет простого 1D-упорядочения данных. Вы используете n.start вместе с n.end и вместе с n.length. Но, возможно, ваши данные не являются общими, или это нормально, чтобы вернуть несколько иной результат.

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

n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1 

Или вы можете пойти за n7, у которого самый маленький end:

n.start <= r.start AND n.end >= r.end
order by n.end
limit 1 

Этот вид поиска будет использовать простой индекс на n.start (или n.end) без дополнительной сортировки.

Второй, совершенно другой подход. Насколько большой/длинный диапазон? Если они относительно короткие (несколько чисел), вы можете попытаться сохранить их как явный список целых чисел, а не диапазон. Например, диапазон [5-8] будет сохранен как 4 строки: (5, 6, 7, 8). С этой моделью хранения может быть проще найти пересечения диапазонов.

Ответ 2

У меня нет действительно хорошего ответа для вас, потому что я не знаком с индексами gist, но я заинтересован, поэтому я немного посмотрел на ваш план объяснений. Выделялось пару вещей:

1) Ваш план использует объединение вложенного цикла, даже в примере 250K. После этого вы просматриваете большую таблицу и выполняете поиск на более мелкой. Это означает, что он делает 8 миллионов запросов индекса на меньшую таблицу, занимая более 148 секунд. Странно, что это значительно замедляется с увеличением размера таблицы routing_details_small. Как я уже сказал, я не знаком с индексами gist, но я бы экспериментировал с set enable_nestloop to false;, чтобы увидеть, можете ли вы заставить его выполнить какое-то сортированное объединение/хеш-соединение.

2) Различия выполняются в конце. Это занимает довольно небольшую часть времени (~ 11 секунд), но это также означает, что вы можете делать немного дополнительную работу. Похоже, что ядро ​​приносит результирующее количество записей вниз от более 1 миллиона до 250 К, поэтому я бы экспериментировал с этим раньше. Я не уверен, если вы получаете дубликаты, потому что в таблице routing_details_small есть несколько записей для netblock, или что таблица netblock_details имеет несколько совпадений для данного netblock. Если первое, вы можете присоединиться к подзапросу с уникальными сведениями о маршрутизации. Если последнее, попробуйте следующее:

3). Сопоставив предыдущие два наблюдения, вы можете попробовать выполнить частичное соединение (присоединение к подзапросу) из seq-сканирования на routing_details_small. Это должно привести только к сканированию индекса 600K. Что-то вроде (при условии postgres 9.4): SELECT * FROM routing_details_small r, LATERAL (SELECT * FROM netblock_details n WHERE r.range <@ n.range LIMIT 1) nb;

Ответ 3

Используйте LATERAL join (найдите наименьшее совпадение в строке в routing_details):

• В чем разница между LATERAL и подзапросом в PostgreSQL?

Конструкция текущего БД

Единственный актуальный индекс для этих запросов:

"idx_netblock_details_range" gist (range)

Другие индексы здесь неактуальны.

Query

SELECT *  -- only select columns you need to make it faster
FROM   routing_details r
     , LATERAL (
   SELECT *
   FROM   netblock_details n
   WHERE  n.range @> r.range
   ORDER  BY upper(n.range) - lower(n.range)
   LIMIT  1
   ) n

SQL Fiddle с более реалистичными тестовыми данными.

Как и в ваших исходных запросах, из результата удаляются строки из routing_details без какого-либо совпадения в netblock_details.

Производительность зависит от распределения данных. Это должно быть лучше со многими матчами. DISTINCT ON может выиграть всего лишь с несколькими мастями в строке в routing_details, но для большого сортировки ему нужно много work_mem. Сделайте большой объем запросов на 200 МБ. Используйте SET LOCAL в той же транзакции:

• Параметр конфигурации work_mem в PostgreSQL для Linux

Этот запрос не потребуется столько памяти сортировки. В отличие от DISTINCT ON, вы не должны видеть, как Postgres меняет на диск для сортировки с допустимой настройкой на уровне work_mem на полпути. В строке EXPLAIN ANALYZE нет такой строки:

Sort Method: external merge Disk: 155288kBудаp >

Упрощенная конструкция DB

Во втором взгляде я проверил упрощенную конструкцию с равными столбцами int8 для нижней и верхней границ вместо типов диапазонов и простого индекса btree:

CREATE TABLE routing_details (    -- SMALL table
   ip_min   int8
 , ip_max   int8
 , asn      text
 , netblock text
 );

CREATE  TABLE netblock_details (  -- BIG table
   ip_min   int8
 , ip_max   int8
 , name     text
 , country  text
 , source   text
 );

CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);

Сортировка второго столбца индекса DESC NULLS LAST необходима!

Query

SELECT *  -- only select columns you need to make it faster
FROM   routing_details r
     , LATERAL (
   SELECT *
   FROM   netblock_details n
   WHERE  n.ip_min <= r.ip_min
   AND    n.ip_max >= r.ip_max
   ORDER  BY n.ip_max - n.ip_min
   LIMIT  1
   ) n;

Такая же базовая техника. В моих тестах это было в 3 раза быстрее, чем первый подход. Но все еще недостаточно быстро для миллионов строк.

SQL Fiddle.

Подробное объяснение метода (примеры с индексами b-дерева, но принцип запроса аналогичен для индекса GiST):

• Оптимизировать запрос GROUP BY для получения последней записи на пользователя

И для варианта DISTINCT ON:

• Выберите первую строку в каждой группе GROUP BY?

Расширенное решение

Выше решения линейно строятся с номерами строк в routing_details, но ухудшаются с количеством совпадений в netblock_details. Наконец, он вернулся ко мне: мы решили это раньше на dba.SE с более сложным подходом, обеспечивающим в основном превосходную производительность:

• Может ли пространственный индекс помочь в запросе "диапазон по порядку"

frequency в связанном ответе играет роль ip_max - n.ip_min/upper(range) - lower(range) здесь.

Ответ 4

Я не знаю, выполняется ли это на реальных данных. Выбор кандидата сжимается во внутренний цикл, который мне кажется хорошим. При тестировании он дал два сканирования индекса (плюс один для анти-соединения), избегая окончательной сортировки/уникальности. Кажется, он дает эквивалентные результаты.

-- EXPLAIN ANALYZE
SELECT *
FROM routing_details r
JOIN netblock_details n ON r.range <@ n.range
        -- We want the smallest overlapping range
        -- Use "Not exists" to suppress overlapping ranges 
        -- that are larger than n
        -- (this should cause an antijoin)
WHERE NOT EXISTS(
        SELECT * FROM netblock_details nx
        WHERE  r.range <@ nx.range      -- should enclose r
        AND n.range <> nx.range         -- but differ from n
        AND (nx.range <@ n.range        -- and overlap n, or be larger
                OR upper(nx.range) - lower(nx.range) < upper(n.range) - lower(n.range)
                OR (upper(nx.range) - lower(nx.range) = upper(n.range) - lower(n.range) AND lower(nx.range) > lower(n.range) )
                )
        )
ORDER BY r.netblock
        -- not needed any more
        -- , upper(n.range) - lower(n.range)
        ;

UPDATE: (FWIW) в качестве бонуса, мой тестовый набор данных

CREATE Table routing_details
 ( asn          text
 , netblock     text
 , range        int8range
 );
-- Indexes:
CREATE INDEX idx_routing_details_netblock ON routing_details (netblock);
CREATE INDEX idx_routing_details_range ON routing_details USING gist(range) ;


CREATE    Table netblock_details
 ( range        int8range
 , name         text
 , country      text
 , source       text
 );
-- Indexes:
CREATE INDEX idx_netblock_details_range ON netblock_details USING gist(range);
        -- the smaller table
INSERT INTO routing_details(range,netblock)
SELECT int8range(gs, gs+13), 'block_' || gs::text
FROM generate_series(0,1000000, 11) gs
        ;

        -- the larger table
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+17), 'name_' || gs::text
FROM generate_series(0,1000000, 17) gs
        ;

INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+19), 'name_' || gs::text
FROM generate_series(0,1000000, 19) gs
        ;

INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+23), 'name_' || gs::text
FROM generate_series(0,1000000, 23) gs
        ;

VACUUM ANALYZE routing_details;
VACUUM ANALYZE netblock_details;