Původně jsem uvažoval o bočním spojení jako v jiných navrhovaných přístupech (například poslední dotaz Erwina Brandstettera, kde používá jednoduchý int8 datový typ a jednoduché indexy), ale nechtěl jsem to psát do odpovědi, protože jsem si myslel, že to není opravdu efektivní. Když se pokusíte najít všechny netblock rozsahy, které pokrývají daný rozsah, index moc nepomůže.
Zopakuji zde dotaz 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;
Když máte index na netblock_details, takhle:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
můžete rychle (v O(logN) ) vyhledejte počáteční bod skenování v netblock_details tabulka - buď maximální n.ip_min to je méně než r.ip_min nebo minimální n.ip_max to je více než r.ip_max . Pak ale musíte naskenovat/přečíst zbytek indexu/tabulky a pro každý řádek provést druhou část kontroly a odfiltrovat většinu řádků.
Jinými slovy, tento index pomáhá rychle najít počáteční řádek, který splňuje první vyhledávací kritéria:n.ip_min <= r.ip_min , ale pak budete pokračovat ve čtení všech řádků, které splňují tato kritéria, a pro každý takový řádek proveďte druhou kontrolu n.ip_max >= r.ip_max . V průměru (pokud mají data rovnoměrné rozložení) budete muset přečíst polovinu řádků netblock_details stůl. Optimalizátor se může rozhodnout použít k vyhledávání index n.ip_max >= r.ip_max nejprve a poté použijte druhý filtr n.ip_min <= r.ip_min , ale tento index nemůžete použít k použití obou filtrů společně.
Konečný výsledek:pro každý řádek z routing_details přečteme polovinu řádků z netblock_details . 600K * 4M =2 400 000 000 000 řádků. Je 2krát lepší než kartézský produkt. Toto číslo (kartézský součin) můžete vidět ve výstupu EXPLAIN ANALYZE v otázce.
592,496 * 8,221,675 = 4,871,309,550,800
Není divu, že vašim dotazům dochází místo na disku, když se to pokoušíte zhmotnit a seřadit.
Celkový proces na vysoké úrovni pro dosažení konečného výsledku:
-
připojte se ke dvěma stolům (aniž byste zatím našli nejlepší shodu). V horším případě je to kartézský produkt, v lepším případě to všechno pokrývá rozsahy od
netblock_detailspro každý rozsah zrouting_details. Řekl jste, že vnetblock_detailsje více položek pro každý záznam vrouting_details, cokoliv od 3 do přibližně 10. Takže výsledek tohoto spojení by mohl mít ~6M řádků (ne příliš mnoho) -
objednejte/rozdělte výsledek spojení pomocí
routing_detailsrozsahy a pro každý takový rozsah najděte nejlepší (nejmenší) rozsah pokrytí znetblock_details.
Můj nápad je obrátit dotaz. Místo hledání všech pokrývajících rozsahů z větších netblock_details pro každý řádek z menších routing_details tabulka Doporučuji najít všechny menší rozsahy z menších routing_details pro každý řádek z větších netblock_details .
Dvoufázový proces
Pro každý řádek z větších netblock_details najít všechny rozsahy z routing_details které jsou uvnitř netblock rozsah.
V dotazech bych použil následující schéma. Přidal jsem primární klíč ID k oběma tabulkám.
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
Potřebujeme index na routing_details na (ip_min, ip_max) . Hlavní věc je zde index na ip_min . Mít druhý sloupec v indexu pomáhá tím, že odpadá nutnost vyhledávat hodnotu ip_max; to nepomůže při hledání stromu.
Všimněte si, že boční dílčí dotaz nemá LIMIT . Ještě to není konečný výsledek. Tento dotaz by měl vrátit ~6 milionů řádků. Uložte tento výsledek do dočasné tabulky. Přidejte index do dočasné tabulky na (r_ID, n_length, n_ID) . n_ID je opět jen odstranit další vyhledávání. Potřebujeme index a vyhneme se řazení dat pro každé r_ID .
Poslední krok
Pro každý řádek z routing_details vyhledejte n_ID s nejmenším n_length . Nyní můžeme použít boční spojení ve "správném" pořadí. Zde temp tabulka je výsledkem předchozího kroku s indexem .
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
Zde by měl být dílčí dotaz hledáním indexu, nikoli skenováním. Optimalizátor by měl být dostatečně chytrý, aby provedl pouze vyhledávání a vrátil první nalezený výsledek, protože LIMIT 1 , takže budete mít 600 000 hledání indexu v 6M řádkové dočasné tabulce.
Původní odpověď (nechám si ji jen pro diagram rozsahů):
Umíš "podvádět"?
Pokud jsem správně pochopil váš dotaz, pro každý routing_details.range chcete najít nejmenší netblock_details.range který pokrývá/je větší než routing_details.range .
V následujícím příkladu, kde r je směrovací rozsah a n1, ..., n8 jsou rozsahy netblock, správná odpověď je 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
Váš dotaz, který trval 14 hodin ukazuje, že indexové skenování trvalo 6 ms, ale řazení podle délky rozsahu trvalo 80 ms.
Při tomto druhu vyhledávání neexistuje jednoduché 1D řazení dat. Používáte n.start spolu s n.end a společně s n.length . Možná však vaše data nejsou tak obecná, nebo je v pořádku vrátit poněkud jiný výsledek.
Například pokud bylo v pořádku vrátit n6 ve výsledku by to mohlo fungovat mnohem rychleji. n6 je rozsah pokrytí, který má největší start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Nebo můžete zvolit n7 , který má nejmenší end :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Tento druh vyhledávání by používal jednoduchý index na n.start (nebo n.end ) bez dalšího třídění.
Druhý, zcela odlišný přístup. Jak velké/dlouhé jsou rozsahy? Pokud jsou relativně krátké (málo čísel), můžete je zkusit uložit jako explicitní seznam celých čísel namísto rozsahu. Například rozsah [5-8] bude uloženo jako 4 řádky:(5, 6, 7, 8) . S tímto modelem úložiště může být snadnější najít průsečíky rozsahů.