Skip site navigation (1) Skip section navigation (2)

Re: Efficiently searching for CIDRs containing an IP address

From: "David F(dot) Skoll" <dfs(at)roaringpenguin(dot)com>
To: pgsql-admin(at)postgresql(dot)org
Subject: Re: Efficiently searching for CIDRs containing an IP address
Date: 2009-05-29 20:44:25
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-admin
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...
WHERE iprangeIN('', ..., '');

-- 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 '' <<= 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: (''::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: (''::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

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.



In response to


pgsql-admin by date

Next:From: Justin CarreraDate: 2009-05-31 00:46:13
Subject: ruby connect
Previous:From: Tom LaneDate: 2009-05-29 15:35:43
Subject: Re: Efficiently searching for CIDRs containing an IP address

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group