Ich dachte ursprünglich an einen lateralen Join wie in anderen vorgeschlagenen Ansätzen (zum Beispiel die letzte Abfrage von Erwin Brandstetter, wo er einfaches int8 verwendet Datentyp und einfache Indizes), wollte es aber nicht in die Antwort schreiben, weil ich dachte, dass es nicht wirklich effizient ist. Wenn Sie versuchen, alle netblock zu finden Bereiche, die den angegebenen Bereich abdecken, hilft ein Index nicht viel.
Ich wiederhole hier die Frage von Erwin Brandstetter:
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;
Wenn Sie einen Index für netblock_details haben, etwa so:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
können Sie schnell (in O(logN) ) finden Sie den Startpunkt des Scans in den netblock_details Tabelle - entweder die maximale n.ip_min das ist kleiner als r.ip_min , oder das Minimum n.ip_max das ist mehr als r.ip_max . Aber dann müssen Sie den Rest des Indexes/der Tabelle scannen/lesen und für jede Zeile den zweiten Teil der Prüfung durchführen und die meisten Zeilen herausfiltern.
Mit anderen Worten, dieser Index hilft, schnell die Startzeile zu finden, die das erste Suchkriterium erfüllt:n.ip_min <= r.ip_min , aber dann lesen Sie weiter alle Zeilen, die dieses Kriterium erfüllen, und führen für jede solche Zeile die zweite Prüfung n.ip_max >= r.ip_max durch . Im Durchschnitt (wenn die Daten gleichmäßig verteilt sind) müssen Sie die Hälfte der Zeilen der netblock_details lesen Tisch. Der Optimierer kann den Index verwenden, um nach n.ip_max >= r.ip_max zu suchen zuerst und wenden Sie dann den zweiten Filter n.ip_min <= r.ip_min an , aber Sie können diesen Index nicht verwenden, um beide Filter zusammen anzuwenden.
Endergebnis:für jede Zeile von routing_details wir werden die Hälfte der Zeilen von netblock_details lesen . 600K * 4M =2.400.000.000.000 Zeilen. Es ist zweimal besser als das kartesische Produkt. Sie können diese Zahl (kartesisches Produkt) in der Ausgabe von EXPLAIN ANALYZE sehen in der Frage.
592,496 * 8,221,675 = 4,871,309,550,800
Kein Wunder, dass Ihren Abfragen der Speicherplatz ausgeht, wenn Sie versuchen, dies zu materialisieren und zu sortieren.
Der gesamte High-Level-Prozess, um zum Endergebnis zu gelangen:
-
sich zwei Tischen anschließen (ohne die beste Übereinstimmung noch zu finden). Im schlimmsten Fall handelt es sich um ein kartesisches Produkt, im besten Fall deckt es alle Bereiche von
netblock_detailsab für jeden Bereich vonrouting_details. Sie sagten, dass es mehrere Einträge innetblock_detailsgibt für jeden Eintrag inrouting_details, alles zwischen 3 und etwa 10. Das Ergebnis dieser Verknüpfung könnte also ~6 Millionen Zeilen haben (nicht zu viel) -
sortieren/partitionieren Sie das Ergebnis des Joins nach
routing_detailsBereiche und finde für jeden solchen Bereich den besten (kleinsten) abdeckenden Bereich ausnetblock_details.
Meine Idee ist, die Abfrage umzukehren. Anstatt alle abdeckenden Bereiche aus größeren netblock_details zu finden für jede Zeile von kleineren routing_details Tabelle schlage ich vor, alle kleineren Bereiche aus kleineren routing_details zu finden für jede Zeile von größeren netblock_details .
Zweistufiger Prozess
Für jede Zeile größerer netblock_details finden Sie alle Bereiche von routing_details die sich innerhalb des netblock befinden Bereich.
Ich würde das folgende Schema in den Abfragen verwenden. Ich habe den Primärschlüssel ID hinzugefügt zu beiden Tabellen.
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
Wir brauchen einen Index für routing_details auf (ip_min, ip_max) . Die Hauptsache hier ist der Index auf ip_min . Eine zweite Spalte im Index zu haben, hilft, indem die Suche nach dem Wert von ip_max entfällt; es hilft nicht bei der Baumsuche.
Beachten Sie, dass die laterale Unterabfrage kein LIMIT hat . Es ist noch nicht das Endergebnis. Diese Abfrage sollte ~6 Millionen Zeilen zurückgeben. Speichern Sie dieses Ergebnis in einer temporären Tabelle. Fügen Sie der temporären Tabelle einen Index für (r_ID, n_length, n_ID) hinzu . n_ID dient wiederum nur dazu, zusätzliche Lookups zu entfernen. Wir brauchen einen Index, vermeiden Sie das Sortieren der Daten für jede r_ID .
Letzter Schritt
Für jede Zeile von routing_details Suchen Sie die n_ID mit der kleinsten n_length . Jetzt können wir den seitlichen Join in der "richtigen" Reihenfolge verwenden. Hier temp Tabelle ist das Ergebnis des vorherigen Schritts mit dem 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 sollte die Unterabfrage eine Suche nach dem Index sein, nicht ein Scan. Der Optimierer sollte aufgrund von LIMIT 1 schlau genug sein, nur die Suche durchzuführen und das erste gefundene Ergebnis zurückzugeben , also haben Sie 600.000 Indexsuchen in einer temporären Tabelle mit 6 Millionen Zeilen.
Ursprüngliche Antwort (ich behalte es nur für das Bereichsdiagramm):
Kann man "betrügen"?
Wenn ich Ihre Abfrage richtig verstanden habe, für jede routing_details.range Sie möchten eine kleinste netblock_details.range finden die routing_details.range abdeckt/größer ist .
Im folgenden Beispiel, wobei r Routingbereich ist und n1, ..., n8 Netblock-Bereiche sind, ist die richtige Antwort 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
Ihre Abfrage, die 14 Stunden gedauert hat zeigt, dass der Indexscan 6 ms dauerte, aber das Sortieren nach Bereichslänge 80 ms dauerte.
Bei dieser Art der Suche gibt es keine einfache 1D-Ordnung der Daten. Sie verwenden n.start zusammen mit n.end und zusammen mit n.length . Aber vielleicht sind Ihre Daten nicht so generisch oder es ist in Ordnung, ein etwas anderes Ergebnis zurückzugeben.
Zum Beispiel, wenn es in Ordnung war, n6 zurückzugeben Infolgedessen könnte es viel schneller arbeiten. n6 ist der Abdeckungsbereich, der den größten start hat :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Oder Sie könnten sich für n7 entscheiden , die das kleinste end hat :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Diese Art der Suche würde einen einfachen Index auf n.start verwenden (oder n.end ) ohne zusätzliche Sortierung.
Ein zweiter, ganz anderer Ansatz. Wie groß/lang sind die Reichweiten? Wenn sie relativ kurz sind (wenige Zahlen), könnten Sie versuchen, sie als explizite Liste von Ganzzahlen statt als Bereich zu speichern. Beispiel:Bereich [5-8] würde als 4 Zeilen gespeichert werden:(5, 6, 7, 8) . Mit diesem Speichermodell ist es möglicherweise einfacher, Schnittpunkte von Bereichen zu finden.
