Inizialmente stavo pensando a un join laterale come in altri approcci suggeriti (ad esempio, l'ultima query di Erwin Brandstetter, dove usa il semplice int8 datatype e indici semplici), ma non volevo scriverlo nella risposta, perché pensavo che non fosse davvero efficiente. Quando provi a trovare tutti i netblock intervalli che coprono l'intervallo dato, un indice non aiuta molto.
Ripeterò la domanda di Erwin Brandstetter qui:
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;
Quando hai un indice su netblock_details, in questo modo:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
puoi velocemente (in O(logN) ) trova il punto di partenza della scansione in netblock_details tabella - il massimo n.ip_min che è inferiore a r.ip_min o il minimo n.ip_max che è più di r.ip_max . Ma poi devi scansionare/leggere il resto dell'indice/tabella e per ogni riga fare la seconda parte del controllo e filtrare la maggior parte delle righe.
In altre parole, questo indice aiuta a trovare velocemente la riga iniziale che soddisfa i primi criteri di ricerca:n.ip_min <= r.ip_min , ma poi continuerai a leggere tutte le righe che soddisfano questo criterio e per ciascuna di queste righe esegui il secondo controllo n.ip_max >= r.ip_max . In media (se i dati hanno una distribuzione uniforme) dovrai leggere metà delle righe del netblock_details tavolo. L'ottimizzatore può scegliere di utilizzare l'indice per cercare n.ip_max >= r.ip_max prima e poi applica il secondo filtro n.ip_min <= r.ip_min , ma non puoi utilizzare questo indice per applicare entrambi i filtri insieme.
Risultato finale:per ogni riga di routing_details leggeremo metà delle righe da netblock_details . 600K * 4M =2.400.000.000.000 di righe. È 2 volte migliore del prodotto cartesiano. Puoi vedere questo numero (prodotto cartesiano) nell'output di EXPLAIN ANALYZE nella domanda.
592,496 * 8,221,675 = 4,871,309,550,800
Non c'è da stupirsi che le tue query esauriscano lo spazio su disco quando cerchi di materializzarle e ordinarle.
Il processo generale di alto livello per arrivare al risultato finale:
-
unisciti a due tavoli (senza ancora trovare la migliore corrispondenza). Nel peggiore dei casi si tratta di un prodotto cartesiano, nel migliore dei casi copre tutte le gamme da
netblock_detailsper ogni intervallo darouting_details. Hai detto che ci sono più voci innetblock_detailsper ogni voce inrouting_details, qualsiasi cosa da 3 a circa 10. Quindi, il risultato di questo join potrebbe avere ~6 milioni di righe (non troppo) -
ordina/partiziona il risultato dell'unione in base a
routing_detailsintervalli e per ciascuno di questi intervalli trova l'intervallo di copertura migliore (più piccolo) danetblock_details.
La mia idea è di invertire la query. Invece di trovare tutti gli intervalli di copertura da netblock_details più grandi per ogni riga da routing_details più piccoli tabella Suggerisco di trovare tutti gli intervalli più piccoli da routing_details più piccoli per ogni riga da netblock_details più grandi .
Processo in due fasi
Per ogni riga da netblock_details più grandi trova tutti gli intervalli da routing_details che si trovano all'interno del netblock intervallo.
Userei il seguente schema nelle query. Ho aggiunto la chiave primaria ID ad entrambe le tabelle.
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
Abbiamo bisogno dell'indice su routing_details su (ip_min, ip_max) . La cosa principale qui è l'indice su ip_min . Avere una seconda colonna nell'indice aiuta eliminando la necessità di cercare il valore di ip_max; non aiuta nella ricerca ad albero.
Nota che la sottoquery laterale non ha LIMIT . Non è ancora il risultato finale. Questa query dovrebbe restituire circa 6 milioni di righe. Salva questo risultato in una tabella temporanea. Aggiungi un indice alla tabella temporanea su (r_ID, n_length, n_ID) . n_ID è ancora una volta solo per rimuovere le ricerche extra. Abbiamo bisogno di un indice, evita di ordinare i dati per ogni r_ID .
Passaggio finale
Per ogni riga di routing_details trova il n_ID con il più piccolo n_length . Ora possiamo usare l'unione laterale nell'ordine "corretto". Qui temp la tabella è il risultato del passaggio precedente con l'indice .
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
Qui la sottoquery dovrebbe essere una ricerca dell'indice, non una scansione. L'ottimizzatore dovrebbe essere abbastanza intelligente da eseguire solo la ricerca e restituire il primo risultato trovato a causa di LIMIT 1 , quindi avrai 600.000 ricerche di indice nella tabella temporanea di 6 milioni di righe.
Risposta originale (la terrò solo per il diagramma degli intervalli):
Puoi "barare"?
Se ho capito bene la tua domanda, per ogni routing_details.range vuoi trovare un netblock_details.range più piccolo che copre/è più grande di routing_details.range .
Dato il seguente esempio, dove r è l'intervallo di instradamento e n1, ..., n8 sono intervalli netblock, la risposta corretta è 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
La tua query che ha richiesto 14 ore mostra che la scansione dell'indice ha richiesto 6 ms, ma l'ordinamento per lunghezza dell'intervallo ha richiesto 80 ms.
Con questo tipo di ricerca non esiste un semplice ordinamento 1D dei dati. Stai usando n.start insieme a n.end e insieme a n.length . Ma forse i tuoi dati non sono così generici o va bene restituire un risultato leggermente diverso.
Ad esempio, se fosse OK restituire n6 di conseguenza, potrebbe funzionare molto più velocemente. n6 è l'intervallo di copertura con start più grande :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Oppure potresti scegliere n7 , che ha la end più piccola :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Questo tipo di ricerca utilizzerebbe un semplice indice su n.start (o n.end ) senza ulteriore ordinamento.
Un secondo approccio completamente diverso. Quanto sono grandi/lunghi gli intervalli? Se sono relativamente brevi (pochi numeri), puoi provare a memorizzarli come un elenco esplicito di numeri interi, invece di un intervallo. Ad esempio, range [5-8] verrebbe memorizzato come 4 righe:(5, 6, 7, 8) . Con questo modello di archiviazione potrebbe essere più facile trovare intersezioni di intervalli.
