Recuperación eficiente de registros de rango de IP superpuestos a través de un solo punto

Question

Tengo una tabla con millones de registros de rango de IP (inicio_num, final_num respectivamente) que necesito consultar a través de una sola dirección IP para devolver todos los intervalos que se superponen . La consulta es esencialmente:

SELECT start_num 
     , end_num 
     , other_data_col 
FROM ip_ranges 
WHERE :query_ip BETWEEN start_num and end_num; 

la tabla tiene 8 particiones rango en núm_inicial y tiene un índice compuesto local en (núm_inicial, END_NUM). Llámalo UNQ_RANGE_IDX. Las estadísticas se han recopilado en la tabla y el índice.

La consulta realiza un análisis de rango de índice en el índice UNQ_RANGE_IDX como se esperaba y, en algunos casos, funciona muy bien. Los casos en los que funciona bien se encuentran hacia la parte inferior del espacio de direcciones IP (es decir, algo así como 4.4.10.20) y el rendimiento es pobre cuando está en el extremo superior. (es decir, 200.2.2.2) Estoy seguro de que el problema reside en el hecho de que en el extremo inferior, el optimizador puede podar todas las particiones por encima de la que contiene los intervalos aplicables debido a la partición de rango en start_num que proporciona la información necesaria para ciruela pasa. Al consultar en el extremo superior del espectro de IP, no puede podar las particiones inferiores y, por lo tanto, incurre en la E/S de lectura de las particiones de índice adicionales. Esto se puede verificar mediante el número de CR_BUFFER_GETS al rastrear la ejecución.

En realidad, los rangos que satisfacen la consulta no estarán en ninguna partición, excepto aquella en la que está ubicado el query_ip o el inmediatamente debajo o arriba ya que el tamaño del rango no será mayor que una clase A y cada la partición cubre muchas clases A cada una. Puedo hacer que Oracle use esa información al especificarla en la cláusula where, pero ¿hay alguna manera de transmitir este tipo de información a Oracle a través de estadísticas, histogramas o un índice personalizado/de dominio? Parece que habría una solución/enfoque común para este tipo de problema al buscar intervalos de fechas que cubran una fecha específica también.

Estoy buscando soluciones que utilicen Oracle y su funcionalidad para abordar este problema, pero se agradecen otros tipos de soluciones. He pensado en un par de métodos fuera del alcance de Oracle que funcionarían, pero espero una mejor forma de indexación, recopilación de estadísticas o particiones que funcionen bien.

información solicitada:

CREATE TABLE IP_RANGES (
    START_NUM NUMBER NOT NULL, 
    END_NUM NUMBER NOT NULL, 
    OTHER  NUMBER NOT NULL, 
    CONSTRAINT START_LTE_END CHECK (START_NUM <= END_NUM) 
) 
PARTITION BY RANGE(START_NUM) 
(
    PARTITION part1 VALUES LESS THAN(1090519040) TABLESPACE USERS, 
    PARTITION part2 VALUES LESS THAN(1207959552) TABLESPACE USERS 
    ....<snip>.... 
    PARTITION part8 VALUES LESS THAN(MAXVALUE) TABLESPACE USERS 
); 

CREATE UNIQUE INDEX IP_RANGES_IDX ON IP_RANGES(START_NUM, END_NUM, OTHER) LOCAL NOLOGGING; 

ALTER TABLE IP_RANGES ADD CONSTRAINT PK_IP_RANGE 
PRIMARY KEY(START_NUM, END_NUM, OTHER) USING INDEX IP_RANGES_IDX; 

No hay nada especial acerca de los valores de corte seleccionados para las particiones de rango. Son simplemente direcciones de clase A donde el número de rangos por partición equivaldría a aproximadamente 1 millón de registros.

Answer 1

Te sugiero que conviertas tu mesa de 8 millones de filas en una mesa más grande. IP de Google (para mí, en este momento) está subiendo como

"66.102.011.104"

Puede almacenar un registro como "66.102.011" con la gama (s) respectiva que cae en. De hecho, almacena al menos un registro por cada "aaa.bbb.ccc". Probablemente terminará con una tabla tal vez cinco veces más grande, pero una que puede señalar el registro relevante con solo unos IO lógicos cada vez en lugar de los cientos/miles para un escaneo de partición.

Sospecho que cualquier dato que tenga va a estar un poco desactualdo de todos modos (como varias autoridades alrededor del mundo emiten/vuelven a emitir rangos), por lo que regenerar los ajustes para esa tabla sobre una base diaria/semanal no debería ser un gran problema

Answer 2

Tuve un problema similar en el pasado; la ventaja que tenía era que mis rangos eran distintos. Tengo varias tablas IP_RANGES, cada una para un contexto específico, y la más grande tiene aproximadamente 10 millones de registros, sin particiones.

Cada una de las tablas que tengo está indexada, con la clave primaria (END_NUM, START_NUM). También tengo un índice único en (START_NUM, END_NUM), pero no se usa en este caso.

Usando una dirección IP aleatoria (1234567890), su consulta toma aproximadamente 132k consistentes obtiene.

La siguiente consulta arroja entre 4-10 constantes obtiene (dependiendo de IP) en 10.2.0.4.

select * 
    from ip_ranges outr 
where :ip_addr between outr.num_start and outr.num_end 
    and outr.num_end = (select /*+ no_unnest */ 
           min(innr.num_end) 
          from ip_ranges innr 
          where innr.num_end >= :ip_addr); 
--------------------------------------------------------------------------------------------------- 
| Id | Operation      | Name    | Rows | Bytes | Cost (%CPU)| Time  | 
--------------------------------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT    |     |  1 | 70 |  6 (0)| 00:00:01 | 
|* 1 | INDEX RANGE SCAN    | IP_RANGES_PK  |  1 | 70 |  3 (0)| 00:00:01 | 
| 2 | SORT AGGREGATE    |     |  1 |  7 |   |   | 
| 3 | FIRST ROW     |     | 471K| 3223K|  3 (0)| 00:00:01 | 
|* 4 |  INDEX RANGE SCAN (MIN/MAX)| IP_RANGES_PK  | 471K| 3223K|  3 (0)| 00:00:01 | 
--------------------------------------------------------------------------------------------------- 

Predicate Information (identified by operation id): 
--------------------------------------------------- 

    1 - access("OUTR"."NUM_END"= (SELECT /*+ NO_UNNEST */ MIN("INNR"."NUM_END") FROM 
       "IP_RANGES" "INNR" WHERE "INNR"."NUM_END">=TO_NUMBER(:IP_ADDR)) AND 
       "OUTR"."NUM_START"<=TO_NUMBER(:IP_ADDR)) 
     filter("OUTR"."NUM_END">=TO_NUMBER(:IP_ADDR)) 
    4 - access("INNR"."NUM_END">=TO_NUMBER(:IP_ADDR)) 


Statistics 
---------------------------------------------------------- 
      0 recursive calls 
      0 db block gets 
      7 consistent gets 
      0 physical reads 
      0 redo size 
     968 bytes sent via SQL*Net to client 
     492 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

La sugerencia es NO_UNNEST clave; le dice a Oracle que ejecute esa subconsulta una vez, no una vez por cada fila, y le da una prueba de igualdad para que el índice la use en la consulta externa.

Answer 3

El problema que veo es el índice de particiones locales y, como dijiste, parece que Oracle no elimina la lista de particiones de manera eficiente. ¿Puedes probar con el índice global? El índice particionado local no se adapta bien a las consultas OLTP. En nuestro entorno, no usamos ningún índice particionado local.

Answer 4

¿Podría indicar si existen características uniformes u ordenadas de sus rangos de IP? Por ejemplo, normalmente esperaría que los rangos IP se encuentren en los límites de la potencia de 2. ¿Es ese el caso aquí, por lo que podemos suponer que todos los rangos tienen una máscara de red implícita que comienza con m unos seguidos por n ceros donde m + n = 32?

Si es así, debería haber una forma de explotar este conocimiento y "dar un paso" dentro de los rangos. ¿Sería posible agregar un índice en un valor calculado con el recuento de los bits enmascarados (0-32) o tal vez el tamaño del bloque (1 a 2^32)?

32 busca de las máscaras 0 a 32 utilizando solo el start_num sería más rápido que un escaneo usando BETWEEN start_num AND end_num.

Además, ¿ha considerado la aritmética de bits como un posible medio para buscar coincidencias (una vez más solo si los rangos representan trozos uniformemente posicionados en tamaños de potencia de 2).

Answer 5

Su partición existente no funciona, porque Oracle está accediendo a las particiones de índice local de la tabla por start_num, y tiene que verificar cada una donde podría haber una coincidencia.

Una solución diferente, suponiendo que ningún intervalo abarque una clase A, sería enumerar la partición por trunc(start_num/power(256,3)) - el primer octeto. Puede valer la pena dividirlo en una columna (rellenado mediante el desencadenador) y agregarlo como una columna de filtrado a su consulta.

Sus ~ 10m filas serían, suponiendo una distribución pareja, distribuidas en aproximadamente 40k filas, lo que podría ser mucho más rápido de leer.

---

Ejecuto el caso de uso que se describe a continuación, suponiendo que ningún rango abarca una red de clase A.

create table ip_ranges 
(start_num   number   not null, 
    end_num   number   not null, 
    start_first_octet number   not null, 
    ... 
    constraint start_lte_end check (start_num <= end_num), 
    constraint check_first_octet check (start_first_octet = trunc(start_num/16777216)) 
) 
partition by list (start_first_octet) 
(
partition p_0 values (0), 
partition p_1 values (1), 
partition p_2 values (2), 
... 
partition p_255 values (255) 
); 

-- run data population script, ordered by start_num, end_num 

create index ip_ranges_idx01 on ip_ranges (start_num, end_num) local; 

begin 
    dbms_stats.gather_table_stats (ownname => user, tabname => 'IP_RANGES', cascade => true); 
end; 
/

Uso de la consulta base anterior todavía se realiza mal, ya que es incapaz de hacer efectiva la eliminación de particiones:

---------------------------------------------------------------------------------------------------------------------- 
| Id | Operation       | Name   | Rows | Bytes | Cost (%CPU)| Time  | Pstart| Pstop | 
---------------------------------------------------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT     |     | 25464 | 1840K| 845 (1)| 00:00:05 |  |  | 
| 1 | PARTITION LIST ALL    |     | 25464 | 1840K| 845 (1)| 00:00:05 |  1 | 256 | 
| 2 | TABLE ACCESS BY LOCAL INDEX ROWID| IP_RANGES  | 25464 | 1840K| 845 (1)| 00:00:05 |  1 | 256 | 
|* 3 | INDEX RANGE SCAN    | IP_RANGES_IDX01 | 825 |  | 833 (1)| 00:00:05 |  1 | 256 | 
---------------------------------------------------------------------------------------------------------------------- 

Predicate Information (identified by operation id): 
--------------------------------------------------- 

    3 - access("END_NUM">=TO_NUMBER(:IP_ADDR) AND "START_NUM"<=TO_NUMBER(:IP_ADDR)) 
     filter("END_NUM">=TO_NUMBER(:IP_ADDR)) 


Statistics 
---------------------------------------------------------- 
     15 recursive calls 
      0 db block gets 
    141278 consistent gets 
     94469 physical reads 
      0 redo size 
     1040 bytes sent via SQL*Net to client 
     492 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

Sin embargo, si añadimos la condición para permitir que Oracle se concentre en una sola partición, hace una gran diferencia:

SQL> select * from ip_ranges 
    2 where :ip_addr between start_num and end_num 
    3  and start_first_octet = trunc(:ip_addr/power(256,3)); 

---------------------------------------------------------------------------------------------------------------------- 
| Id | Operation       | Name   | Rows | Bytes | Cost (%CPU)| Time  | Pstart| Pstop | 
---------------------------------------------------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT     |     | 183 | 13542 | 126 (2)| 00:00:01 |  |  | 
| 1 | PARTITION LIST SINGLE    |     | 183 | 13542 | 126 (2)| 00:00:01 | KEY | KEY | 
| 2 | TABLE ACCESS BY LOCAL INDEX ROWID| IP_RANGES  | 183 | 13542 | 126 (2)| 00:00:01 | KEY | KEY | 
|* 3 | INDEX RANGE SCAN    | IP_RANGES_IDX01 |  3 |  | 322 (1)| 00:00:02 | KEY | KEY | 
---------------------------------------------------------------------------------------------------------------------- 

Predicate Information (identified by operation id): 
--------------------------------------------------- 

    3 - access("END_NUM">=TO_NUMBER(:IP_ADDR) AND "START_NUM"<=TO_NUMBER(:IP_ADDR)) 
     filter("END_NUM">=TO_NUMBER(:IP_ADDR)) 


Statistics 
---------------------------------------------------------- 
     15 recursive calls 
      0 db block gets 
      7 consistent gets 
      0 physical reads 
      0 redo size 
     1040 bytes sent via SQL*Net to client 
     492 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

Answer 6

En primer lugar, ¿cuál es su requisito de rendimiento?

Sus particiones tienen un valor inicial definido y valores finales que se pueden determinar desde ALL_PARTITIONS (o codificados) y utilizados en una función (concepto a continuación pero deberá modificarla para avanzar una partición hacia adelante/atrás) .

continuación, debería ser capaz de código

SELECT * FROM ip_ranges 
WHERE :query_ip BETWEEN start_num and end_num 
AND start_num between get_part_start(:query_ip) and get_part_end(:query_ip); 

Cuáles deberían ser capaces de bloqueo hacia abajo a la partición (s) específico. Sin embargo, si, como sugiere, solo puede bloquearlo en tres de ocho particiones, eso todavía será un BIG scan. Estoy publicando otra respuesta más radical que puede ser más apropiada.

create or replace function get_part_start (i_val in number) 
           return number deterministic is 
    cursor c_1 is 
    select high_value from all_tab_partitions 
    where table_name = 'IP_RANGES' 
    order by table_owner, table_name; 
    type tab_char is table of varchar2(20) index by pls_integer; 
    type tab_num is table of number index by pls_integer; 
    t_char tab_char; 
    t_num tab_num; 
    v_ind number; 
begin 
    open c_1; 
    fetch c_1 bulk collect into t_char; 
    close c_1; 
    -- 
    for i in 1..t_char.last loop 
    IF t_char(i) != 'MAXVALUE' THEN 
     t_num(to_number(t_char(i))) := null; 
    END IF; 
    end loop; 
    -- 
    IF i_val > t_num.last then 
    return t_num.last; 
    ELSIF i_val < t_num.first then 
    return 0; 
    END IF; 
    v_ind := 0; 
    WHILE i_val >= t_num.next(v_ind) loop 
    v_ind := t_num.next(v_ind); 
    exit when v_ind is null; 
    END LOOP; 
    return v_ind; 
end; 
/