Je pensais à l'origine à une jointure latérale comme dans d'autres approches suggérées (par exemple, la dernière requête d'Erwin Brandstetter, où il utilise de simples int8 type de données et index simples), mais je ne voulais pas l'écrire dans la réponse, car je pensais que ce n'était pas vraiment efficace. Lorsque vous essayez de trouver tous les netblock plages qui couvrent la plage donnée, un index n'aide pas beaucoup.
Je vais répéter la requête d'Erwin Brandstetter ici :
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;
Lorsque vous avez un index sur netblock_details, comme ceci :
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
vous pouvez rapidement (en O(logN) ) trouver le point de départ de l'analyse dans le netblock_details table - soit le maximum n.ip_min qui est inférieur à r.ip_min , ou le minimum n.ip_max c'est plus que r.ip_max . Mais ensuite, vous devez parcourir/lire le reste de l'index/de la table et pour chaque ligne, effectuez la deuxième partie de la vérification et filtrez la plupart des lignes.
En d'autres termes, cet index permet de trouver rapidement la ligne de départ qui satisfait les premiers critères de recherche :n.ip_min <= r.ip_min , mais vous continuerez ensuite à lire toutes les lignes qui satisfont à ce critère et pour chacune de ces lignes, effectuez la deuxième vérification n.ip_max >= r.ip_max . En moyenne (si les données ont une distribution uniforme), vous devrez lire la moitié des lignes du netblock_details table. L'optimiseur peut choisir d'utiliser l'index pour rechercher n.ip_max >= r.ip_max d'abord puis appliquer le second filtre n.ip_min <= r.ip_min , mais vous ne pouvez pas utiliser cet index pour appliquer les deux filtres ensemble.
Résultat final :pour chaque ligne de routing_details nous lirons la moitié des lignes de netblock_details . 600K * 4M =2 400 000 000 000 lignes. C'est 2 fois mieux que le produit cartésien. Vous pouvez voir ce nombre (produit cartésien) dans la sortie de EXPLAIN ANALYZE dans la question.
592,496 * 8,221,675 = 4,871,309,550,800
Pas étonnant que vos requêtes manquent d'espace disque lorsque vous essayez de matérialiser et de trier cela.
Le processus global de haut niveau pour arriver au résultat final :
-
joindre deux tables (sans trouver la meilleure correspondance pour le moment). Dans le pire des cas, il s'agit d'un produit cartésien, dans le meilleur des cas, il couvre toutes les plages de
netblock_detailspour chaque plage derouting_details. Vous avez dit qu'il y avait plusieurs entrées dansnetblock_detailspour chaque entrée dansrouting_details, n'importe quoi de 3 à environ 10. Ainsi, le résultat de cette jointure pourrait avoir ~6 millions de lignes (pas trop) -
ordonner/partitionner le résultat de la jointure par les
routing_detailsplages et pour chacune de ces plages, trouvez la meilleure plage de couverture (la plus petite) à partir denetblock_details.
Mon idée est d'inverser la requête. Au lieu de trouver toutes les plages de couverture à partir de netblock_details plus grands pour chaque ligne de plus petits routing_details table que je suggère de trouver toutes les plages plus petites à partir de routing_details plus petits pour chaque ligne à partir de netblock_details plus grands .
Processus en deux étapes
Pour chaque ligne de netblock_details plus grand trouver toutes les plages de routing_details qui sont à l'intérieur du netblock plage.
J'utiliserais le schéma suivant dans les requêtes. J'ai ajouté la clé primaire ID aux deux tables.
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
Nous avons besoin d'un index sur routing_details sur (ip_min, ip_max) . L'essentiel ici est l'index sur ip_min . Avoir une deuxième colonne dans l'index aide en éliminant le besoin de rechercher la valeur de ip_max; cela n'aide pas dans la recherche arborescente.
Notez que la sous-requête latérale n'a pas LIMIT . Ce n'est pas encore le résultat final. Cette requête doit renvoyer environ 6 millions de lignes. Enregistrez ce résultat dans une table temporaire.Ajoutez un index à la table temporaire sur (r_ID, n_length, n_ID) . n_ID est à nouveau juste pour supprimer les recherches supplémentaires. Nous avons besoin d'un index, évitez de trier les données pour chaque r_ID .
Étape finale
Pour chaque ligne de routing_details trouver le n_ID avec le plus petit n_length . Nous pouvons maintenant utiliser la jointure latérale dans le "bon" ordre. Ici temp la table est le résultat de l'étape précédente avec l'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
Ici, la sous-requête doit être une recherche de l'index, pas une analyse. L'optimiseur doit être suffisamment intelligent pour effectuer uniquement la recherche et renvoyer le premier résultat trouvé en raison de LIMIT 1 , vous aurez donc 600 000 recherches d'index dans une table temporaire de 6 millions de lignes.
Réponse originale (je la garderai juste pour le schéma des gammes) :
Pouvez-vous "tricher" ?
Si j'ai bien compris votre requête, pour chaque routing_details.range vous voulez trouver un plus petit netblock_details.range qui couvre/est supérieur à routing_details.range .
Étant donné l'exemple suivant, où r est la plage de routage et n1, ..., n8 sont des plages netblock, la bonne réponse est 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
Votre requête qui a pris 14 heures montre que le balayage de l'index a pris 6 ms, mais que le tri par longueur de plage a pris 80 ms.
Avec ce type de recherche, il n'y a pas de simple classement 1D des données. Vous utilisez n.start avec n.end et avec n.length . Mais peut-être que vos données ne sont pas si génériques ou qu'il est acceptable de renvoyer un résultat quelque peu différent.
Par exemple, si c'était OK pour retourner n6 par conséquent, cela pourrait fonctionner beaucoup plus rapidement. n6 est la plage de couverture qui a le plus grand start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Ou, vous pouvez opter pour n7 , qui a le plus petit end :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Ce type de recherche utiliserait un index simple sur n.start (ou n.end ) sans tri supplémentaire.
Une deuxième approche complètement différente. Quelle est la taille/longueur des plages ? S'ils sont relativement courts (peu de nombres), vous pouvez essayer de les stocker sous la forme d'une liste explicite d'entiers, au lieu d'une plage. Par exemple, plage [5-8] serait stocké sur 4 lignes :(5, 6, 7, 8) . Avec ce modèle de stockage, il peut être plus facile de trouver des intersections de plages.
