Estaba pensando originalmente en una unión lateral como en otros enfoques sugeridos (por ejemplo, la última consulta de Erwin Brandstetter, donde usa int8 simple tipo de datos e índices simples), pero no quería escribirlo en la respuesta, porque pensé que no es realmente eficiente. Cuando intentas encontrar todos los netblock rangos que cubren el rango dado, un índice no ayuda mucho.
Repetiré la consulta de Erwin Brandstetter aquí:
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;
Cuando tenga un índice en netblock_details, así:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
puede rápidamente (en O(logN) ) encuentre el punto de inicio del escaneo en netblock_details tabla - ya sea el máximo n.ip_min eso es menos que r.ip_min , o el mínimo n.ip_max eso es más que r.ip_max . Pero luego debe escanear/leer el resto del índice/tabla y para cada fila hacer la segunda parte de la verificación y filtrar la mayoría de las filas.
En otras palabras, este índice ayuda a encontrar rápidamente la fila inicial que satisface los primeros criterios de búsqueda:n.ip_min <= r.ip_min , pero luego continuará leyendo todas las filas que cumplan con este criterio y para cada una de esas filas realice la segunda verificación n.ip_max >= r.ip_max . En promedio (si los datos tienen una distribución uniforme), tendrá que leer la mitad de las filas de netblock_details mesa. Optimizer puede optar por utilizar el índice para buscar n.ip_max >= r.ip_max primero y luego aplicar el segundo filtro n.ip_min <= r.ip_min , pero no puede usar este índice para aplicar ambos filtros juntos.
Resultado final:para cada fila de routing_details leeremos la mitad de las filas de netblock_details . 600K * 4M =2,400,000,000,000 filas. Es 2 veces mejor que el producto cartesiano. Puede ver este número (producto cartesiano) en la salida de EXPLAIN ANALYZE en la pregunta
592,496 * 8,221,675 = 4,871,309,550,800
No es de extrañar que sus consultas se queden sin espacio en disco cuando intentan materializar y ordenar esto.
El proceso general de alto nivel para llegar al resultado final:
-
unir dos tablas (sin encontrar la mejor coincidencia todavía). En el peor de los casos, es un producto cartesiano, en el mejor de los casos, cubre todos los rangos de
netblock_detailspara cada rango derouting_details. Dijiste que hay varias entradas ennetblock_detailspara cada entrada enrouting_details, desde 3 hasta alrededor de 10. Por lo tanto, el resultado de esta unión podría tener ~6 millones de filas (no demasiadas) -
ordenar/particionar el resultado de la unión por
routing_detailsrangos y para cada uno de esos rangos encuentre el mejor rango de cobertura (el más pequeño) denetblock_details.
Mi idea es invertir la consulta. En lugar de encontrar todos los rangos de cobertura de netblock_details más grandes para cada fila de routing_details más pequeños tabla sugiero encontrar todos los rangos más pequeños de routing_details más pequeños para cada fila de netblock_details más grande .
Proceso de dos pasos
Para cada fila de mayor netblock_details encuentra todos los rangos de routing_details que están dentro del netblock rango.
Usaría el siguiente esquema en las consultas. He agregado la clave principal ID a ambas mesas.
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
Necesitamos índice en routing_details en (ip_min, ip_max) . Lo principal aquí es el índice en ip_min . Tener una segunda columna en el índice ayuda a eliminar la necesidad de buscar el valor de ip_max; no ayuda en la búsqueda del árbol.
Tenga en cuenta que la subconsulta lateral no tiene LIMIT . Todavía no es el resultado final. Esta consulta debería devolver ~6 millones de filas. Guarde este resultado en una tabla temporal. Agregue un índice a la tabla temporal en (r_ID, n_length, n_ID) . n_ID es nuevamente solo para eliminar búsquedas adicionales. Necesitamos un índice, evite ordenar los datos para cada r_ID .
Paso final
Para cada fila de routing_details encuentra el n_ID con el menor n_length . Ahora podemos usar la unión lateral en el orden "adecuado". Aquí temp la tabla es el resultado del paso anterior con el índice .
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
Aquí la subconsulta debe ser una búsqueda del índice, no un escaneo. El optimizador debe ser lo suficientemente inteligente como para hacer solo la búsqueda y devolver el primer resultado encontrado debido a LIMIT 1 , por lo que tendrá 600 000 búsquedas de índice en una tabla temporal de 6 millones de filas.
Respuesta original (la guardaré solo para el diagrama de rangos):
¿Puedes "hacer trampa"?
Si entendí tu consulta correctamente, para cada routing_details.range desea encontrar un netblock_details.range más pequeño que cubre/es más grande que routing_details.range .
Dado el siguiente ejemplo, donde r es el rango de enrutamiento y n1, ..., n8 son rangos de netblock, la respuesta correcta es 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
Su consulta que tomó 14 horas muestra que el escaneo de índice tomó 6 ms, pero ordenar por longitud de rango tomó 80 ms.
Con este tipo de búsqueda no existe una ordenación 1D simple de los datos. Estás usando n.start junto con n.end y junto con n.length . Pero, tal vez sus datos no sean tan genéricos, o está bien devolver un resultado algo diferente.
Por ejemplo, si estaba bien devolver n6 como resultado, podría funcionar mucho más rápido. n6 es el rango de cobertura que tiene mayor start :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
O bien, podría optar por n7 , que tiene el end más pequeño :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Este tipo de búsqueda usaría un índice simple en n.start (o n.end ) sin clasificación adicional.
Un segundo enfoque completamente diferente. ¿Qué tan grandes/largos son los rangos? Si son relativamente cortos (pocos números), podría intentar almacenarlos como una lista explícita de enteros, en lugar de un rango. Por ejemplo, rango [5-8] se almacenaría como 4 filas:(5, 6, 7, 8) . Con este modelo de almacenamiento, puede ser más fácil encontrar intersecciones de rangos.
