Determining if an IP is within an IPv4 CIDR Block

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

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.

StackExchange Database Administrators Q#171044, answer score: 5