Jag tänkte ursprungligen på en lateral sammanfogning som i andra föreslagna tillvägagångssätt (till exempel den sista frågan från Erwin Brandstetter, där han använder enkel int8 datatyp och enkla index), men ville inte skriva det i svaret, eftersom jag trodde att det inte är riktigt effektivt. När du försöker hitta alla netblock intervall som täcker det givna intervallet, hjälper ett index inte mycket.
Jag upprepar Erwin Brandstetters fråga här:
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;
När du har ett index på netblock_details, så här:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
du kan snabbt (i O(logN) ) hitta startpunkten för skanningen i netblock_details tabell - antingen det maximala n.ip_min som är mindre än r.ip_min , eller minsta n.ip_max det är mer än r.ip_max . Men sedan måste du skanna/läsa resten av indexet/tabellen och för varje rad göra den andra delen av kontrollen och filtrera bort de flesta raderna.
Med andra ord, detta index hjälper till att snabbt hitta startraden som uppfyller de första sökkriterierna:n.ip_min <= r.ip_min , men sedan kommer du att fortsätta läsa alla rader som uppfyller detta kriterium och för varje sådan rad utföra den andra kontrollen n.ip_max >= r.ip_max . I genomsnitt (om data har jämn fördelning) måste du läsa hälften av raderna i netblock_details tabell. Optimizer kan välja att använda index för att söka efter n.ip_max >= r.ip_max först och sedan tillämpa det andra filtret n.ip_min <= r.ip_min , men du kan inte använda det här indexet för att tillämpa båda filtren samtidigt.
Slutresultat:för varje rad från routing_details vi läser igenom hälften av raderna från netblock_details . 600K * 4M =2 400 000 000 000 rader. Det är 2 gånger bättre än kartesisk produkt. Du kan se detta nummer (kartesisk produkt) i utgången av EXPLAIN ANALYZE i frågan.
592,496 * 8,221,675 = 4,871,309,550,800
Inte konstigt att dina frågor får slut på diskutrymme när du försöker materialisera och sortera detta.
Den övergripande processen på hög nivå för att nå det slutliga resultatet:
-
gå med två bord (utan att hitta den bästa matchningen ännu). I värsta fall är det kartesisk produkt, i bästa fall täcker allt intervall från
netblock_detailsför varje intervall frånrouting_details. Du sa att det finns flera poster inetblock_detailsför varje post irouting_details, allt från 3 till runt 10. Så resultatet av denna koppling kan ha ~6 miljoner rader (inte för mycket) -
beställ/partitionera resultatet av anslutningen med
routing_detailsintervall och för varje sådant intervall hitta det bästa (minsta) täckande intervallet frånnetblock_details.
Min idé är att vända frågan. Istället för att hitta alla täckningsområden från större netblock_details för varje rad från mindre routing_details tabell Jag föreslår för att hitta alla mindre intervall från mindre routing_details för varje rad från större netblock_details .
Tvåstegsprocess
För varje rad från större netblock_details hitta alla intervall från routing_details som finns i netblock intervall.
Jag skulle använda följande schema i frågorna. Jag har lagt till primärnyckeln ID till båda borden.
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
Vi behöver index på routing_details på (ip_min, ip_max) . Huvudsaken här är index på ip_min . Att ha den andra kolumnen i indexet hjälper till att eliminera behovet av att söka efter värdet ip_max; det hjälper inte i trädsökningen.
Observera att den laterala underfrågan inte har LIMIT . Det är inte slutresultatet ännu. Den här frågan bör returnera ~6 miljoner rader. Spara detta resultat i en temporär tabell. Lägg till ett index i den temporära tabellen på (r_ID, n_length, n_ID) . n_ID är återigen bara att ta bort extra uppslagningar. Vi behöver ett index, undvik att sortera data för varje r_ID .
Sista steget
För varje rad från routing_details hitta n_ID med den minsta n_length . Nu kan vi använda sidofogen i "rätt" ordning. Här temp tabellen är resultatet av föregående steg med indexet .
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
Här bör underfrågan vara en sökning av indexet, inte skanning. Optimizer bör vara smart nog att bara söka och returnera det först hittade resultatet på grund av LIMIT 1 , så du kommer att ha 600 000 indexsökningar i 6M radtemptabell.
Ursprungligt svar (jag behåller det bara för diagrammet över intervall):
Kan du "fuska"?
Om jag förstod din fråga rätt, för varje routing_details.range du vill hitta en minsta netblock_details.range som täcker/är större än routing_details.range .
Med tanke på följande exempel, där r är routingområde och n1, ..., n8 är nätblockintervall, är det korrekta svaret 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
Din förfrågan som tog 14 timmar visar att indexskanningen tog 6ms, men att sortera efter intervalllängd tog 80ms.
Med denna typ av sökning finns det ingen enkel 1D-ordning av data. Du använder n.start tillsammans med n.end och tillsammans med n.length . Men kanske din data inte är så generisk, eller så är det OK att returnera ett något annorlunda resultat.
Till exempel, om det var OK att returnera n6 som ett resultat kan det fungera mycket snabbare. n6 är det täckande intervallet som har störst start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Eller så kan du välja n7 , som har minsta end :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Denna typ av sökning skulle använda enkelt index på n.start (eller n.end ) utan extra sortering.
Ett andra, helt annat tillvägagångssätt. Hur stora/långa är avstånden? Om de är relativt korta (få siffror) kan du försöka lagra dem som en explicit lista med heltal istället för ett intervall. Till exempel intervall [5-8] skulle lagras som 4 rader:(5, 6, 7, 8) . Med denna lagringsmodell kan det vara lättare att hitta skärningspunkter för intervall.