Początkowo myślałem o łączeniu bocznym, jak w innych sugerowanych podejściach (na przykład ostatnie zapytanie Erwina Brandstettera, w którym używa on prostego int8 typ danych i proste indeksy), ale nie chciałem tego pisać w odpowiedzi, ponieważ myślałem, że nie jest to zbyt wydajne. Gdy próbujesz znaleźć wszystkie netblock zakresy, które obejmują dany zakres, indeks niewiele pomaga.
Tutaj powtórzę zapytanie Erwina Brandstettera:
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;
Jeśli masz indeks na netblock_details, tak:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
możesz szybko (w O(logN) ) znajdź punkt początkowy skanowania w netblock_details tabela - albo maksymalna wartość n.ip_min czyli mniej niż r.ip_min lub minimalny n.ip_max to więcej niż r.ip_max . Ale potem musisz zeskanować/odczytać resztę indeksu/tabeli i dla każdego wiersza wykonać drugą część sprawdzenia i odfiltrować większość wierszy.
Innymi słowy, ten indeks pomaga szybko znaleźć początkowy wiersz, który spełnia pierwsze kryteria wyszukiwania:n.ip_min <= r.ip_min , ale wtedy będziesz kontynuować odczytywanie wszystkich wierszy spełniających te kryteria i dla każdego takiego wiersza wykonaj drugie sprawdzenie n.ip_max >= r.ip_max . Średnio (jeśli dane mają równomierny rozkład) będziesz musiał przeczytać połowę wierszy netblock_details stół. Optymalizator może użyć indeksu do wyszukiwania n.ip_max >= r.ip_max najpierw, a potem zastosuj drugi filtr n.ip_min <= r.ip_min , ale nie możesz używać tego indeksu do jednoczesnego stosowania obu filtrów.
Wynik końcowy:dla każdego wiersza z routing_details przeczytamy połowę wierszy z netblock_details . 600K * 4M =2 400 000 000 000 wierszy. Jest 2 razy lepszy niż produkt kartezjański. Możesz zobaczyć ten numer (produkt kartezjański) na wyjściu EXPLAIN ANALYZE w pytaniu.
592,496 * 8,221,675 = 4,871,309,550,800
Nic dziwnego, że podczas próby zmaterializowania i posortowania zapytań zabrakło miejsca na dysku.
Ogólny proces wysokiego poziomu prowadzący do końcowego wyniku:
-
dołącz do dwóch stołów (nie znajdując jeszcze najlepszego dopasowania). W najgorszym przypadku jest to produkt kartezjański, w najlepszym obejmuje wszystkie zakresy od
netblock_detailsdla każdego zakresu odrouting_details. Powiedziałeś, że jest wiele wpisów wnetblock_detailsdla każdego wpisu wrouting_details, od 3 do około 10. Tak więc wynik tego połączenia może mieć ~6 mln wierszy (nie za dużo) -
uporządkuj/podziel wynik połączenia przez
routing_detailszakresy i dla każdego takiego zakresu znajdź najlepszy (najmniejszy) zakres obejmującynetblock_details.
Moim pomysłem jest odwrócenie zapytania. Zamiast szukać wszystkich obejmujących zakresy z większych netblock_details dla każdego wiersza z mniejszych routing_details tabela Proponuję znaleźć wszystkie mniejsze zakresy z mniejszych routing_details dla każdego wiersza z większego netblock_details .
Proces dwuetapowy
Dla każdego wiersza z większego netblock_details znajdź wszystkie zakresy z routing_details które znajdują się wewnątrz netblock zasięg.
W zapytaniach użyłbym następującego schematu. Dodałem klucz podstawowy ID do obu stołów.
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
Potrzebujemy indeksu na routing_details na (ip_min, ip_max) . Najważniejszą rzeczą tutaj jest indeks na ip_min . Posiadanie drugiej kolumny w indeksie pomaga, eliminując potrzebę wyszukiwania wartości ip_max; to nie pomaga w przeszukiwaniu drzewa.
Zwróć uwagę, że podzapytanie nie ma LIMIT . To nie jest jeszcze ostateczny wynik. To zapytanie powinno zwrócić ~6 mln wierszy. Zapisz ten wynik w tabeli tymczasowej. Dodaj indeks do tabeli tymczasowej na (r_ID, n_length, n_ID) . n_ID to znowu tylko usunięcie dodatkowych wyszukiwań. Potrzebujemy indeksu, aby uniknąć sortowania danych dla każdego r_ID .
Ostatni krok
Dla każdego wiersza z routing_details znajdź n_ID z najmniejszą n_length . Teraz możemy użyć sprzężenia bocznego w „właściwej” kolejności. Tutaj temp tabela jest wynikiem poprzedniego kroku z indeksem .
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
Tutaj podzapytanie powinno być wyszukiwaniem indeksu, a nie skanowaniem. Optymalizator powinien być wystarczająco sprytny, aby wykonać tylko wyszukiwanie i zwrócić pierwszy znaleziony wynik, ponieważ LIMIT 1 , więc będziesz miał 600K wyszukiwań indeksu w tabeli tymczasowej rzędu 6M.
Oryginalna odpowiedź (zatrzymam ją tylko dla diagramu zakresów):
Czy możesz „oszukiwać”?
Jeśli dobrze zrozumiałem Twoje zapytanie, dla każdego routing_details.range chcesz znaleźć najmniejszy netblock_details.range który obejmuje/jest większy niż routing_details.range .
Biorąc pod uwagę następujący przykład, gdzie r to zakres routingu i n1, ..., n8 są zakresami bloków sieci, poprawną odpowiedzią jest 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
Twoje zapytanie, które zajęło 14 godzin pokazuje, że skanowanie indeksu zajęło 6 ms, ale sortowanie według długości zakresu zajęło 80 ms.
Przy tego rodzaju wyszukiwaniu nie ma prostego porządkowania danych 1D. Używasz n.start razem z n.end i razem z n.length . Ale może twoje dane nie są tak ogólne, lub możesz zwrócić nieco inny wynik.
Na przykład, jeśli można było zwrócić n6 w rezultacie może działać znacznie szybciej. n6 to zakres obejmujący największy start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Możesz też wybrać n7 , który ma najmniejszy end :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Ten rodzaj wyszukiwania używałby prostego indeksu na n.start (lub n.end ) bez dodatkowego sortowania.
Drugie, zupełnie inne podejście. Jak duże/długie są zakresy? Jeśli są stosunkowo krótkie (kilka liczb), możesz spróbować zapisać je jako jawną listę liczb całkowitych zamiast zakresu. Na przykład zakres [5-8] będą przechowywane jako 4 wiersze:(5, 6, 7, 8) . Dzięki temu modelowi przechowywania może być łatwiej znaleźć punkty przecięcia zakresów.
