Ik dacht oorspronkelijk aan een laterale verbinding zoals bij andere voorgestelde benaderingen (bijvoorbeeld de laatste vraag van Erwin Brandstetter, waar hij eenvoudige int8 gebruikt datatype en eenvoudige indexen), maar wilde het niet in het antwoord schrijven, omdat ik dacht dat het niet echt efficiënt is. Wanneer u alle netblock probeert te vinden bereiken die het gegeven bereik dekken, helpt een index niet veel.
Ik herhaal de vraag van Erwin Brandstetter hier:
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;
Als je een index hebt op netblock_details, zoals dit:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
je kunt snel (in O(logN) ) vind het startpunt van de scan in de netblock_details tabel - ofwel de maximale n.ip_min dat is minder dan r.ip_min , of de minimale n.ip_max dat is meer dan r.ip_max . Maar dan moet je de rest van de index/tabel scannen/lezen en voor elke rij het tweede deel van de controle doen en de meeste rijen eruit filteren.
Met andere woorden, deze index helpt om snel de startrij te vinden die voldoet aan de eerste zoekcriteria:n.ip_min <= r.ip_min , maar dan ga je verder met het lezen van alle rijen die aan deze criteria voldoen en voer je voor elke rij de tweede controle uit n.ip_max >= r.ip_max . Gemiddeld (als de gegevens gelijkmatig zijn verdeeld) moet u de helft van de rijen van de netblock_details lezen tafel. Optimizer kan ervoor kiezen om index te gebruiken om n.ip_max >= r.ip_max te zoeken eerst en pas daarna het tweede filter toe n.ip_min <= r.ip_min , maar u kunt deze index niet gebruiken om beide filters samen toe te passen.
Eindresultaat:voor elke rij van routing_details we lezen de helft van de rijen van netblock_details . 600K * 4M =2.400.000.000.000 rijen. Het is 2 keer beter dan het Cartesiaanse product. U kunt dit nummer (Cartesiaans product) zien in de uitvoer van EXPLAIN ANALYZE bij de vraag.
592,496 * 8,221,675 = 4,871,309,550,800
Geen wonder dat uw zoekopdrachten onvoldoende schijfruimte hebben wanneer u dit probeert te realiseren en te sorteren.
Het algemene proces op hoog niveau om tot het eindresultaat te komen:
-
voeg twee tafels toe (zonder de beste match te vinden). In het ergste geval is het een Cartesiaans product, in het beste geval dekt het alle bereiken van
netblock_detailsvoor elk bereik vanrouting_details. Je zei dat er meerdere vermeldingen zijn innetblock_detailsvoor elk item inrouting_details, alles van 3 tot ongeveer 10. Het resultaat van deze samenvoeging kan dus ~6M rijen hebben (niet te veel) -
bestel/partitioneer het resultaat van de join door de
routing_detailsbereik en vind voor elk dergelijk bereik het beste (kleinste) bereik vannetblock_details.
Mijn idee is om de query om te keren. In plaats van alle dekkingsbereiken te vinden van grotere netblock_details voor elke rij van kleinere routing_details tabel Ik stel voor om alle kleinere bereiken te vinden van kleinere routing_details voor elke rij van grotere netblock_details .
Proces in twee stappen
Voor elke rij van grotere netblock_details vind alle bereiken van routing_details die zich in het netblock bevinden bereik.
Ik zou het volgende schema gebruiken in de query's. Ik heb primaire sleutel ID toegevoegd naar beide tafels.
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
We hebben index nodig op routing_details op (ip_min, ip_max) . Het belangrijkste hier is index op ip_min . Het hebben van een tweede kolom in de index helpt door de noodzaak te elimineren om de waarde van ip_max op te zoeken; het helpt niet bij het zoeken naar bomen.
Merk op dat de laterale subquery geen LIMIT . heeft . Het is nog niet het eindresultaat. Deze query zou ongeveer 6 miljoen rijen moeten opleveren. Sla dit resultaat op in een tijdelijke tabel.Voeg een index toe aan de tijdelijke tabel op (r_ID, n_length, n_ID) . n_ID is opnieuw alleen maar om extra zoekopdrachten te verwijderen. We hebben een index nodig, vermijd het sorteren van de gegevens voor elke r_ID .
Laatste stap
Voor elke rij van routing_details vind de n_ID met de kleinste n_length . Nu kunnen we de laterale verbinding in de "juiste" volgorde gebruiken. Hier temp tabel is het resultaat van de vorige stap met de index .
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
Hier moet een subquery een zoekactie van de index zijn, niet een scan. Optimizer zou slim genoeg moeten zijn om alleen te zoeken en het eerste gevonden resultaat te retourneren vanwege LIMIT 1 , dus je hebt 600K zoekacties van de index in de 6M rij-temptabel.
Origineel antwoord (ik bewaar het alleen voor het diagram van bereiken):
Kun je "vals spelen"?
Als ik uw vraag goed heb begrepen, voor elke routing_details.range je wilt een kleinste netblock_details.range . vinden dat dekt/is groter dan routing_details.range .
Gegeven het volgende voorbeeld, waarbij r is routeringsbereik en n1, ..., n8 zijn netblock-bereiken, het juiste antwoord is 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
Uw zoekopdracht die 14 uur duurde laat zien dat de indexscan 6 ms duurde, maar het sorteren op bereiklengte 80 ms.
Bij dit soort zoeken is er geen eenvoudige 1D-ordening van de gegevens. Je gebruikt n.start samen met n.end en samen met n.length . Maar misschien zijn uw gegevens niet zo algemeen, of is het oké om een iets ander resultaat terug te geven.
Als het bijvoorbeeld OK was om n6 . te retourneren daardoor zou het veel sneller kunnen werken. n6 is het dekkingsbereik met de grootste start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Of je zou kunnen gaan voor n7 , die het kleinste end . heeft :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Dit soort zoekopdracht zou een eenvoudige index gebruiken op n.start (of n.end ) zonder extra sorteren.
Een tweede, totaal andere benadering. Hoe groot/lang zijn de bereiken? Als ze relatief kort zijn (weinig getallen), kunt u proberen ze op te slaan als een expliciete lijst van gehele getallen, in plaats van een bereik. Bijvoorbeeld bereik [5-8] zou worden opgeslagen als 4 rijen:(5, 6, 7, 8) . Met dit opslagmodel is het misschien gemakkelijker om kruispunten van bereiken te vinden.