Re: Efficiently searching for CIDRs containing an IP address

I've done some experiments; here are my results for posterity and Google:

I installed the ip4r exension and created the following database:

CREATE TABLE ip4r_networks (
    iprange ip4r,
    satellite integer
);
CREATE INDEX foo2 ON ip4r_networks USING gist (iprange);

CREATE TABLE networks (
    iprange cidr,
    satellite integer
);
CREATE INDEX foo ON networks USING btree (iprange);

I then populated ip4r_networks and networks with 1.78 million rows of
randomly-generated CIDRs, ranging randomly from /16 networks to /32.

Typical queries (recall that for our application, we don't allow networks
"larger" than /8)

=============================================================================
-- A hack expanding an IP address into 25 nested CIDRs...
EXPLAIN ANALYZE SELECT * FROM networks
WHERE iprangeIN('43.45.67.89/32', ..., '43.0.0.0/8');

-- Cleaned-up EXPLAIN results:
Bitmap Heap Scan on networks  (cost=106.67..203.68 rows=25 width=11) (actual time=0.317..0.323 rows=2 loops=1)
   Recheck Cond: ((iprange)::inet = ANY (('{...}'::cidr[])::inet[]))
   ->  Bitmap Index Scan on foo  (cost=0.00..106.66 rows=25 width=0) (actual time=0.304..0.304 rows=2 loops=1)
         Index Cond: ((iprange)::inet = ANY (('{...}'::cidr[])::inet[]))
 Total runtime: 0.387 ms
=============================================================================
-- Using ip4r
EXPLAIN ANALYZE SELECT * FROM ip4r_networks WHERE '43.45.67.89' <<= iprange;

Bitmap Heap Scan on ip4r_networks  (cost=50.37..4450.33 rows=1780 width=12) (actual time=0.123..0.129 rows=2 loops=1)
   Recheck Cond: ('43.45.67.89'::ip4r <<= iprange)
   ->  Bitmap Index Scan on foo2  (cost=0.00..49.93 rows=1780 width=0) (actual time=0.109..0.109 rows=2 loops=1)
         Index Cond: ('43.45.67.89'::ip4r <<= iprange)
 Total runtime: 0.203 ms
=============================================================================

My results show that ip4r is consistently about twice as fast as the
hack that uses 25 nested CIDRs in an IN clause.  However, creating the
GiST index is much, much slower than creating the btree index.  And
the hack has acceptable performance, so we'll probably go with the
hack.

Note that the hack only works for the specific case of CIDRs.  It obviously
won't work for general IP ranges that might not be on CIDR boundaries.

Regards,

David.