4

What is the fastest way to determine if an IP is contained within a CIDR block?

At the moment, whenever I store a CIDR address I also create two columns for starting and ending ip addresses. The starting and ending ip addresses are indexed. If I want to see which network contains an address then I look where ip between start_ip and end_ip which seems less than desirable.

It occurs to me I can store the right shifted number and could match similarly shifted IP address (660510 in the case of @cidr)...

select @cidr, inet_aton(substring_index(@cidr,'/',1))>>(32-substring_index(@cidr,'/',-1));
+---------------+-----------------------------------------------------------------------------+
| @cidr         | inet_aton(substring_index(@cidr,'/',1))>>(32-substring_index(@cidr,'/',-1)) |
+---------------+-----------------------------------------------------------------------------+
| 10.20.30.0/24 |                                                                      660510 |
+---------------+-----------------------------------------------------------------------------+
1 row in set (0.00 sec)

set @ip:='10.20.30.40';
Query OK, 0 rows affected (0.00 sec)

select @ip, inet_aton(@ip)>>(32-substring_index(@cidr,'/',-1));
+-------------+----------------------------------------------------+
| @ip         | inet_aton(@ip)>>(32-substring_index(@cidr,'/',-1)) |
+-------------+----------------------------------------------------+
| 10.20.30.40 |                                             660510 |
+-------------+----------------------------------------------------+
1 row in set (0.00 sec)

In order to benefit from this in an indexed manner, I would need to know the subnet mask (the number of bits to shift). Otherwise, I'll either be systematically comparing bit shifts (i.e., blindly shift for each possible netmask (from 0 to 24 bits)).

I have other sources to optimize, but optimizing the IP2Location™ LITE IP-ASN Database found at http://lite.ip2location.com/database/ip-asn would be a proof of concept.

The table...

CREATE TABLE `ip2loc_asn` (
  `asn` bigint(20) DEFAULT NULL,
  `cidr` varchar(50) DEFAULT NULL,
  `start_ip` bigint(20) DEFAULT NULL,
  `end_ip` bigint(20) DEFAULT NULL,
  `name` varchar(250) DEFAULT NULL,
  KEY `ip2locasn_startip_endip` (`start_ip`,`end_ip`),
  KEY `asn` (`asn`),
  KEY `cidr` (`cidr`)
) ENGINE=MyISAM; -- table is recreated monthly, MyISAM is the perfect engine

Sample data...

select * from ip2loc_asn limit 10;
+-------+--------------+----------+----------+-------------------------------+
| asn   | cidr         | start_ip | end_ip   | name                          |
+-------+--------------+----------+----------+-------------------------------+
| 56203 | 1.0.4.0/24   | 16778240 | 16778495 | Big Red Group                 |
| 56203 | 1.0.5.0/24   | 16778496 | 16778751 | Big Red Group                 |  
| 56203 | 1.0.6.0/24   | 16778752 | 16779007 | Big Red Group                 |  
| 38803 | 1.0.7.0/24   | 16779008 | 16779263 | Goldenit Pty ltd Australia, A |  
| 18144 | 1.0.64.0/18  | 16793600 | 16809983 | Energia Communications,Inc.   |
|  9737 | 1.0.128.0/17 | 16809984 | 16842751 | TOT Public Company Limited    |
|  9737 | 1.0.128.0/18 | 16809984 | 16826367 | TOT Public Company Limited    |
|  9737 | 1.0.128.0/19 | 16809984 | 16818175 | TOT Public Company Limited    |
| 23969 | 1.0.128.0/24 | 16809984 | 16810239 | TOT Public Company Limited    |
| 23969 | 1.0.129.0/24 | 16810240 | 16810495 | TOT Public Company Limited    |
+-------+--------------+----------+----------+-------------------------------+
10 rows in set (0.00 sec)

Netmask ranges from 8 to 32 bits...

select min(substring_index(cidr,'/',-1)+0), max(substring_index(cidr,'/',-1)+0) from ip2loc_asn;
+-------------------------------------+-------------------------------------+
| min(substring_index(cidr,'/',-1)+0) | max(substring_index(cidr,'/',-1)+0) |
+-------------------------------------+-------------------------------------+
|                                   8 |                                  32 |
+-------------------------------------+-------------------------------------+
1 row in set (0.33 sec)

select * from ip2loc_asn where cidr like '%/8' limit 1;
+------+-----------+----------+----------+------------------------------+
| asn  | cidr      | start_ip | end_ip   | name                         |
+------+-----------+----------+----------+------------------------------+
| 3356 | 4.0.0.0/8 | 67108864 | 83886079 | Level 3 Communications, Inc. |
+------+-----------+----------+----------+------------------------------+
1 row in set (0.00 sec)

select * from ip2loc_asn where cidr like '%/32' limit 1;
+-------+---------------+-----------+-----------+------+
| asn   | cidr          | start_ip  | end_ip    | name |
+-------+---------------+-----------+-----------+------+
| 51964 | 57.72.27.1/32 | 961026817 | 961026817 |      |
+-------+---------------+-----------+-----------+------+
1 row in set (0.02 sec)

Current execution plan...

explain select * from ip2loc_asn where inet_aton('10.20.30.40') between start_ip and end_ip;
+----+-------------+------------+-------+--------------------------+--------------------------+---------+------+-------+-----------------------+
| id | select_type | table      | type  | possible_keys            | key                      | key_len | ref  | rows  | Extra                 |
+----+-------------+------------+-------+--------------------------+--------------------------+---------+------+-------+-----------------------+
|  1 | SIMPLE      | ip2loc_asn | range | ip2loc_asn_startip_endip | ip2loc_asn_startip_endip | 9       | NULL | 10006 | Using index condition |
+----+-------------+------------+-------+--------------------------+--------------------------+---------+------+-------+-----------------------+
1 row in set (0.00 sec)

My clumsy attempt...

mysql to3_reference> alter table ip2loc_asn add column shifted_netmask int(10) unsigned;
Query OK, 626695 rows affected (4.06 sec)
Records: 626695  Duplicates: 0  Warnings: 0

mysql to3_reference> update ip2loc_asn set shifted_netmask = start_ip>>(32-substring_index(cidr,'/',-1));
Query OK, 626695 rows affected (5.98 sec)
Rows matched: 626695  Changed: 626695  Warnings: 0

mysql to3_reference> alter table ip2loc_asn add key ip2loc_asn_shiftednetmask (shifted_netmask);
Query OK, 626695 rows affected (5.83 sec)
Records: 626695  Duplicates: 0  Warnings: 0

Old way:

select * from ip2loc_asn where inet_aton('8.8.8.0') between start_ip and end_ip;
+-------+------------+-----------------+--------------+-----------+-----------+------------------------------+
| asn   | cidr       | shifted_netmask | netmask_bits | start_ip  | end_ip    | name                         |
+-------+------------+-----------------+--------------+-----------+-----------+------------------------------+
|  3356 | 8.0.0.0/9  |              16 |            9 | 134217728 | 142606335 | Level 3 Communications, Inc. |
|  3356 | 8.0.0.0/8  |               8 |            8 | 134217728 | 150994943 | Level 3 Communications, Inc. |
| 15169 | 8.8.8.0/24 |          526344 |           24 | 134744064 | 134744319 | Google Inc.                  |
+-------+------------+-----------------+--------------+-----------+-----------+- -----------------------------+
3 rows in set (0.00 sec)

An approach using shifted_netmask (undesirable - I'm incurring a full table scan to discover the number of bits in the netmask)...

select * from ip2loc_asn where shifted_netmask = inet_aton('8.8.8.0')>>32-netmask_bits;
+-------+------------+-----------------+--------------+-----------+-----------+------------------------------+
| asn   | cidr       | shifted_netmask | netmask_bits | start_ip  | end_ip    | name                         |
+-------+------------+-----------------+--------------+-----------+-----------+------------------------------+
|  3356 | 8.0.0.0/8  |               8 |            8 | 134217728 | 150994943 | Level 3 Communications, Inc. |
|  3356 | 8.0.0.0/9  |              16 |            9 | 134217728 | 142606335 | Level 3 Communications, Inc. |
| 15169 | 8.8.8.0/24 |          526344 |           24 | 134744064 | 134744319 | Google Inc.                  |
+-------+------------+-----------------+--------------+-----------+-----------+------------------------------+
3 rows in set (0.64 sec)

The desired approach is similar to the last query minus the scan for netmask bits.

  • 1
    What about a spatial index? In the "space" of IP addresses, an IP address is a "point" and a CIDR block is a "line" between two such points, making an R-Tree index well suited for finding contains/within. dba.stackexchange.com/a/54143/11651 – Michael - sqlbot Apr 15 '17 at 11:53
2

PostgreSQL

As a side note PostgreSQL, does this off the shelf with cidr and inet types. And if you really want to make this job top-notch look into the ip4r

It occurs to me I can store the right shifted number and could match similarly shifted IP address (660510 in the case of @cidr)...

Good thinking, this is actually how PostgreSQL stores them internally. Easily done,

CREATE TABLE ip2loc_asn (
  asn    bigint,
  cidr   cidr,
  name   text
);
CREATE INDEX ON ip2loc_asn USING gist(cidr);

INSERT INTO ip2loc_asn(asn,cidr,name)
VALUES
    ( 56203,  '1.0.4.0/24'   , 'Big Red Group' ),
    ( 56203,  '1.0.5.0/24'   , 'Big Red Group' ),
    ( 56203,  '1.0.6.0/24'   , 'Big Red Group' ),
    ( 38803,  '1.0.7.0/24'   , 'Goldenit Pty ltd Australia, A' ),
    ( 18144,  '1.0.64.0/18'  , 'Energia Communications,Inc.'   ),
    (  9737,  '1.0.128.0/17' , 'TOT Public Company Limited'    ),
    (  9737,  '1.0.128.0/18' , 'TOT Public Company Limited'    ),
    (  9737,  '1.0.128.0/19' , 'TOT Public Company Limited'    ),
    ( 23969,  '1.0.128.0/24' , 'TOT Public Company Limited'    ),
    ( 23969,  '1.0.129.0/24' , 'TOT Public Company Limited'    );

Now we can query it with the network-type operators

test=# SELECT * FROM ip2loc_asn WHERE cidr >> '1.0.129.0';
  asn  |     cidr     |            name            
-------+--------------+----------------------------
  9737 | 1.0.128.0/17 | TOT Public Company Limited
  9737 | 1.0.128.0/18 | TOT Public Company Limited
  9737 | 1.0.128.0/19 | TOT Public Company Limited
 23969 | 1.0.129.0/24 | TOT Public Company Limited

This happens on the index too.

2

The main problem is that the optimizer has no knowledge whether there is one start-end pair that matches, or lots. So, any attempt attempt at optimization is stuck with a table scan, or at least a large range scan.

Which do you have to start with? IP addresses? Or CIDR blocks? I ask that because we may need to rearrange the data you are starting with so as to do lookups of the other efficiently.

In this , I explain how to build and maintain a table of all 2^32 (or the IPv6 equivalent) IP addresses. It uses only a start_ip column, and infers end_ip from the next row. This implies that all unassigned IP ranges must have a row in the table. (This is not a big burden, at most doubling the number of rows.) With that, virtually all operations are essentially O(1) -- that is, something like WHERE ip >= start_ip ORDER BY start_ip DESC LIMIT 1 gets the answer "immediately". No table scan, no range scan; nothing worse than a 'point query' (effectively). Note that it does not even need to test end_ip. Caveat: Overlapping ranges are not handled. Some applications (perhaps not yours) can be adapted to not need overlapping.

How to adapt that to CIDR? One way is to turn your table of CIDRs into my variant. You are familiar with how to do that; the main differences being the lack of end_ip and the addition of "un-owned" ranges. So, if you "start with" CIDRs and need to look up IPs, this is a possible answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.