代码之家 › 专栏 › 技术社区 › RC.

通过单点高效检索重叠的IP范围记录

database-design oracle database sql

RC. · 技术社区 · 14 年前

我有一个包含数百万条IP范围记录(分别是start\u num和end\u num)的表,我需要通过单个IP地址查询这些记录,以便返回与该点重叠的所有范围。查询基本上是:

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

该表在start\ num上有8个范围分区,在(start\ num,end\ num)上有一个本地复合索引。称之为UNQ\u RANGE\u IDX。统计数据已收集在表格和索引上。

查询按预期对UNQ\u range\u IDX索引执行索引范围扫描,在某些情况下执行得非常好。它性能良好的情况是在IP地址空间的底部(例如4.4.10.20),而在高端时性能较差。(即200.2.2.2)我确信问题出在这样一个事实上:在低端,优化器可以删减包含适用范围的分区之上的所有分区,这是因为start\ num上的范围分区提供了删减所需的信息。当在IP频谱的顶端进行查询时,它不能修剪较低的分区,因此它会导致读取额外索引分区的I/O。这可以通过跟踪执行时获得的cru缓冲区的数量来验证。

我正在寻找使用Oracle及其功能来解决这个问题的解决方案,但其他类型的解决方案是值得赞赏的。我已经想到了一些在Oracle范围之外的方法可以工作,但是我希望有一种更好的索引、统计数据收集或分区方法可以做到这一点。

请求的信息:

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;

为范围分区选择的截止值没有什么特别之处。它们只是一个类地址,其中每个分区的范围数相当于大约1M条记录。

6 回复 | 直到 14 年前

Gary Myers 14 年前

我建议你把800万行的桌子改大一点。谷歌的IP(对我来说,目前)即将成为

您可以将一条记录存储为“66.102.011”,其中包含相应的范围。事实上,你的商店至少 “一个记录一个”aaa.bbb.ccc公司". 您可能会得到一个可能是5倍大的表,但是您可以通过每次只使用几个逻辑IOs而不是分区扫描的成百上千个IOs来锁定相关记录。

我怀疑你所有的数据都会有点过时(因为世界各地的权威机构都会发布/重新发布范围),所以每天/每周重新生成该表的调整应该不是什么大问题。

Adam Musch 14 年前

我在过去也遇到过类似的问题;我的优势是我的范围很明显。我有几个IP_RANGES表,每个表对应一个特定的上下文,最大的是大约1000万条记录,没有分区。

我拥有的每个表都是索引组织的,主键是(endnum,START NUM)。我还有一个唯一的索引(START\u NUM,END\u NUM),但在本例中没有使用它。

使用一个随机的IP地址(1234567890),您的查询需要大约132k的时间。

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

最重要的提示是 ;它告诉Oracle运行该子查询一次,而不是每行运行一次,并为要在外部查询中使用的索引提供相等性测试。

Baski 14 年前

ErikE Russ Cam 14 年前

请说明你们的IP范围是否有统一或有序的特征?例如,我通常希望IP范围位于2次方边界上。这里就是这种情况,所以我们可以假设所有范围都有一个隐式的网络掩码,以米一个接一个 n

如果是这样的话,就应该有一种方法来利用这些知识并“逐步”进入范围。有没有可能在一个计算值上添加一个索引,其中包含屏蔽位的计数(0-32)或者块大小(1到2^32)?

32只使用start\u num从掩码0到32的寻道比使用start\u num和end\u num之间的扫描要快。

另外,您是否考虑过位算法作为检查匹配的可能方法(同样,仅当范围表示大小为2的幂次方的均匀位置块时)。

Gary Myers 14 年前

首先,你的表现要求是什么?

您的分区有一个明确的起始值和结束值,可以从所有的分区(或硬编码)中确定,并在函数中使用(下面的概念,但您需要修改它以向前/向后移动一个分区)。

然后您应该能够编写代码

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);

它应该能够锁定到特定的分区。但是,如果如您所建议的,您只能将它锁定为八个分区中的三个分区,那么这仍然是一个大的扫描。我正在发布另一个更激进的答案,可能更合适。

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;
/

Adam Musch 14 年前

您现有的分区不起作用,因为Oracle正在通过start\ num访问表的本地索引分区,并且必须检查每个分区中可能存在匹配项的地方。

另一种解决方案是,假设没有范围跨越类A,则按分区列出 trunc(start_num / power(256,3)) --第一个八位组。将它分解成一列(通过触发器填充)并将其作为筛选列添加到查询中可能是值得的。

假设分布均匀,那么您的~10m行将被分散成大约40k行,这可能会更快地通读。

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;
/

----------------------------------------------------------------------------------------------------------------------
| 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

但是,如果我们添加了允许Oracle将注意力集中在单个分区上的条件,则会产生巨大的差异:

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