Thread: Gist indexing performance with cidr types

Hi

I'm trying to get a query to run fast enough for interactive use. I've gotten
some speed-up, but still not there. It is for a tool called IRRExplorer
(http://irrexplorer.nlnog.net/) that correlates IP routes between Internet
Route Registries and real-world routing information. We landed on PostgreSQL
largely due to indexing of the cidr type with gist indexing.

* Preliminaries:

The query is about getting data from this table:

irrexplorer=> \d routes
       Table "public.routes"
   Column   |  Type   | Modifiers
-----------+---------+-----------
  route     | cidr    | not null
  asn       | bigint  | not null
  source_id | integer | not null
Indexes:
     "unique_entry" UNIQUE CONSTRAINT, btree (route, asn, source_id)
     "route_gist" gist (route inet_ops)
Check constraints:
     "positive_asn" CHECK (asn > 0)
Foreign-key constraints:
     "routes_source_id_fkey" FOREIGN KEY (source_id) REFERENCES sources(id)

Complete DDL: https://github.com/job/irrexplorer/blob/master/data/schema.sql

Data set: 125 MB on disk, 2.3 million rows.

Running stock PostgreSQL 9.4.4 on Ubuntu 14.10 (hosted on VMWare on OS X)

Have done VACUUM, ANALYZE, and checked memory settings, and tried to increase
work_mem, but with no success. The issue seems cpu bound (100% cpu load during
query).


* Query

When a user inputs an AS number a simple match on the asn column will return
the stuff relevant. However, the interesting thing to display is
conflicting/rogue routes. This means matching routes with the && operator to
find all covered/covering routes. This would look something like this:

SELECT rv.route, rv.asn, rv.source
FROM routes_view rv
LEFT OUTER JOIN routes_view r ON (rv.route && r.route)
WHERE rv.route && r.route AND r.asn = %s

While this is fairly fast if the initial set of routes is relatively small
(<100) it runs with a second or so, but if the number of routes matching
the asn is large (>1000), it takes quite a while (+30 seconds). Explain
analyze link:

http://explain.depesz.com/s/dHqo

I am not terribly good at reading the output, but it seem most of the time is
actually spend on the bitmap scan for the gist index. It there another type of
indexing that would behave better here?

Since there often identical routes in the initial set of routes (from the AS number matching), I tried reducing the
initialset of matching routes: 
ORDER BY rv.route;

SELECT rv.route, rv.asn, rv.source
FROM
     (SELECT DISTINCT route FROM routes_view WHERE asn = %s) r
LEFT OUTER JOIN routes_view rv ON (r.route && rv.route)

This often cuts the set of initial matching routes by 25-50%, and cuts a
similar amount of time from the query time. Explain analyze link:

http://explain.depesz.com/s/kf13

I tried further reducing the routes to the minimal set:

WITH distinct_routes AS (SELECT DISTINCT route FROM routes_view WHERE asn = %s)
SELECT route FROM distinct_routes
EXCEPT
SELECT r1.route
FROM distinct_routes r1
     INNER JOIN distinct_routes r2 ON (r1.route << r2.route);

But typically only yields 10-20% reduction of the inital route set, and
adds query complexity (putting the above in a CTE/WITH seems to make the
query significantly slower for some reason).

The main issue seem to be with the gist bitmap index. Is there a better way to
approach this style of query?


     Best regards, Henrik

> I'm trying to get a query to run fast enough for interactive use. I've gotten
> some speed-up, but still not there. It is for a tool called IRRExplorer
> (http://irrexplorer.nlnog.net/) that correlates IP routes between Internet
> Route Registries and real-world routing information. We landed on PostgreSQL
> largely due to indexing of the cidr type with gist indexing.

It is nice to hear about someone making use of the feature.

> * Query
>
> When a user inputs an AS number a simple match on the asn column will return
> the stuff relevant. However, the interesting thing to display is
> conflicting/rogue routes. This means matching routes with the && operator to
> find all covered/covering routes. This would look something like this:
>
> SELECT rv.route, rv.asn, rv.source
> FROM routes_view rv
> LEFT OUTER JOIN routes_view r ON (rv.route && r.route)
> WHERE rv.route && r.route AND r.asn = %s

Why don't you just use INNER JOIN like this:

SELECT rv.route, rv.asn, rv.source
FROM routes_view rv
JOIN routes_view r ON rv.route && r.route
WHERE r.asn = %s

> While this is fairly fast if the initial set of routes is relatively small
> (<100) it runs with a second or so, but if the number of routes matching the
> asn is large (>1000), it takes quite a while (+30 seconds).Explain analyze
> link:
>
> http://explain.depesz.com/s/dHqo
>
> I am not terribly good at reading the output, but it seem most of the time is
> actually spend on the bitmap scan for the gist index. It there another type of
> indexing that would behave better here?

An index to the "asn" column would probably help to the outer side,
but more time seems to be consumed on the inner side.  Plain index
scan would probably be faster for it.  You can test it by setting
enable_bitmapscan to false.

The problem about bitmap index scan is selectivity estimation.  The
planner estimates a lot more rows would match the condition, so it
chooses bitmap index scan.  Selectivity estimation functions for inet
on PostgreSQL 9.4 just return some constants, so it is expected.  We
developed better ones for 9.5.  PostgreSQL 9.5 also supports index
only scans with GiST which can be even better than plain index scan.
Can you try 9.5 to see if they help?

Hi, thanks for the reply.

On Tue, 25 Aug 2015, Emre Hasegeli wrote:

>> I'm trying to get a query to run fast enough for interactive use. I've gotten
>> some speed-up, but still not there. It is for a tool called IRRExplorer
>> (http://irrexplorer.nlnog.net/) that correlates IP routes between Internet
>> Route Registries and real-world routing information.

>> We landed on PostgreSQL largely due to indexing of the cidr type with
>> gist indexing.
>
> It is nice to hear about someone making use of the feature.

Thanks to whoever made it. It is probably a niche-feature though.

>> SELECT rv.route, rv.asn, rv.source
>> FROM routes_view rv
>> LEFT OUTER JOIN routes_view r ON (rv.route && r.route)
>> WHERE rv.route && r.route AND r.asn = %s
>
> Why don't you just use INNER JOIN like this:
>
> SELECT rv.route, rv.asn, rv.source
> FROM routes_view rv
> JOIN routes_view r ON rv.route && r.route
> WHERE r.asn = %s

I probably have a habit of thinking in outer joins. The inner join turns
out to slightly slower though (but faster in planning), but it looks like
it depends on a dice roll by the planner (it does bitmap heap scan on
inner, and index scan on left outer).

>> I am not terribly good at reading the output, but it seem most of the time is
>> actually spend on the bitmap scan for the gist index. It there another type of
>> indexing that would behave better here?
>
> An index to the "asn" column would probably help to the outer side,

"select route from routes where asn = %s" takes .15-.2 seconds on my
laptop, so it isn't where the time is spend here.

> but more time seems to be consumed on the inner side.  Plain index
> scan would probably be faster for it.  You can test it by setting
> enable_bitmapscan to false.

This actually makes it go slower for inner join (31s -> 56s). Left outer
join is around the same.

> The problem about bitmap index scan is selectivity estimation.  The
> planner estimates a lot more rows would match the condition, so it
> chooses bitmap index scan.  Selectivity estimation functions for inet
> on PostgreSQL 9.4 just return some constants, so it is expected.  We
> developed better ones for 9.5.  PostgreSQL 9.5 also supports index
> only scans with GiST which can be even better than plain index scan.

OK, that is interesting.

> Can you try 9.5 to see if they help?

I'll try installing it and report back.


     Best regards, Henrik

  Henrik Thostrup Jensen <htj at nordu.net>
  Software Developer, NORDUnet

On Wed, 26 Aug 2015, Henrik Thostrup Jensen wrote:

>> Can you try 9.5 to see if they help?
>
> I'll try installing it and report back.

I upgraded to 9.5 (easier than expected) and ran vacuum analyze.

The query planner now chooses index scan for outer and inner join. This
seems to cut off roughly a second or so (31s -> 30s, and 17s->16s for when
using distint on initial route set).

Query:

EXPLAIN (ANALYZE, BUFFERS)
SELECT rv.route, rv.asn, rv.source FROM
     (SELECT DISTINCT route FROM routes_view WHERE asn = %s) r
INNER JOIN routes_view rv ON (r.route && rv.route)
ORDER BY rv.route;

Explain analyze: http://explain.depesz.com/s/L7kZ


9.5 also seems to fix the case with using CTE/WITH was actually slower.
The fastest I can currently do is this, which finds the minimal set of
covering routes before joining:

SET enable_bitmapscan = false;
EXPLAIN ANALYZE
WITH
distinct_routes AS (SELECT DISTINCT route FROM routes_view WHERE asn = %s),
minimal_routes  AS (SELECT route FROM distinct_routes
                     EXCEPT
                     SELECT r1.route
                     FROM distinct_routes r1 INNER JOIN distinct_routes r2 ON (r1.route << r2.route))
SELECT rv.route, rv.asn, rv.source
FROM routes_view rv
JOIN minimal_routes ON (rv.route <<= minimal_routes.route);

Explain analyze: http://explain.depesz.com/s/Plx4

The query planner chooses bitmap Index Scan for this query, which adds
around .5 second the query time, so it isn't that bad of a decision.

Unfortunately it still takes 15 seconds for my test case (a big network,
but still a factor 10 from the biggest).

Are the coverage operatons just that expensive?


     Best regards, Henrik

> Are the coverage operatons just that expensive?

They shouldn't be.  A similar query like yours works in 0.5 second on my laptop:

># create table inner_side as select i, ((random() * 255.5)::int::text || '.' || (random() * 255.5)::int::text || '.'
||(random() * 255.5)::int::text || '.' || (random() * 255.5)::int::text || '/' || (random() * 16 +
9)::int::text)::inet::cidras network from generate_series(1, 2300000) as i; 
> SELECT 2300000
>
># create table outer_side as select i, ((random() * 255.5)::int::text || '.' || (random() * 255.5)::int::text || '.'
||(random() * 255.5)::int::text || '.' || (random() * 255.5)::int::text || '/' || (random() * 16 +
9)::int::text)::inet::cidras network from generate_series(1, 732) as i; 
> SELECT 732
>
># create index on inner_side using gist(network inet_ops);
> CREATE INDEX
>
># analyze;
> ANALYZE
>
># explain analyze select * from outer_side join inner_side on outer_side.network && inner_side.network;
> QUERY PLAN
> ----------
> Nested Loop  (cost=0.41..563927.27 rows=137310 width=22) (actual time=0.115..474.103 rows=561272 loops=1)
>   ->  Seq Scan on outer_side  (cost=0.00..11.32 rows=732 width=11) (actual time=0.011..0.096 rows=732 loops=1)
>   ->  Index Scan using inner_side_network_idx on inner_side  (cost=0.41..540.38 rows=23000 width=11) (actual
time=0.031..0.553rows=767 loops=732) 
>         Index Cond: ((outer_side.network)::inet && (network)::inet)
> Planning time: 0.830 ms
> Execution time: 505.641 ms
> (6 rows)

Maybe, something we haven't expected about your dataset causes a
performance regression on the index.  Did you see anything relevant on
the server logs on index creation time?

On Wed, 26 Aug 2015, Emre Hasegeli wrote:

>> Are the coverage operatons just that expensive?
>
> They shouldn't be.  A similar query like yours works in 0.5 second on my laptop:
[snip]

I get the same from your testcase.

> Maybe, something we haven't expected about your dataset causes a
> performance regression on the index.  Did you see anything relevant on
> the server logs on index creation time?

I tried dropping and re-creating the index. The only log entry was for the
drop statement.

The distribution of the data is not uniform like the data set you produce.
Though I find it hard to believe that it would affect this as much.

select masklen(route), count(*) from routes group by masklen(route);

  masklen |  count
---------+---------
        8 |      47
        9 |      30
       10 |      84
       11 |     225
       12 |     580
       13 |    1163
       14 |    2401
       15 |    4530
       16 |   32253
       17 |   20350
       18 |   35583
       19 |   76307
       20 |  111913
       21 |  132807
       22 |  229578
       23 |  286986
       24 | 1149793

Rest is rather small, though with bumps at /32 and /48 (typical IPv6 prefix length).

Real-world address space is very fragmented, where as some is unused.

Then there is the mixed IPv6 and IPv4 data that might factor in.


I tried the approach from your benchmark, to try make a more isolated test
case:

irrexplorer=> SELECT DISTINCT route INTO hmm FROM routes_view WHERE asn = 2914;
SELECT 732

irrexplorer=> explain analyze select routes.route from routes join hmm on routes.route && hmm.route;
                                                                QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------
  Nested Loop  (cost=0.41..511914.27 rows=2558 width=7) (actual time=8.096..17209.778 rows=8127 loops=1)
    ->  Seq Scan on hmm  (cost=0.00..11.32 rows=732 width=7) (actual time=0.010..0.609 rows=732 loops=1)
    ->  Index Only Scan using route_gist on routes  (cost=0.41..470.32 rows=22900 width=7) (actual time=4.823..23.502
rows=11loops=732) 
          Index Cond: (route && (hmm.route)::inet)
          Heap Fetches: 0
  Planning time: 0.971 ms
  Execution time: 17210.627 ms
(7 rows)

The only difference in the query plan is that the above used an index
only, where as your test case used index scan (it did this for me as
well). I tried without index only scan:

irrexplorer=> set enable_indexonlyscan =false;
SET

                                                             QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------
  Nested Loop  (cost=0.41..571654.27 rows=2558 width=7) (actual time=6.406..15899.791 rows=8127 loops=1)
    ->  Seq Scan on hmm  (cost=0.00..11.32 rows=732 width=7) (actual time=0.011..0.615 rows=732 loops=1)
    ->  Index Scan using route_gist on routes  (cost=0.41..551.93 rows=22900 width=7) (actual time=4.490..21.712
rows=11loops=732) 
          Index Cond: ((route)::inet && (hmm.route)::inet)
  Planning time: 0.505 ms
  Execution time: 15900.669 ms
(6 rows)

Slight faster, but nothing significant. Something seems wonky.


     Best regards, Henrik

> Then there is the mixed IPv6 and IPv4 data that might factor in.

It shouldn't be the problem.  The index should separate them on the top level.

> I tried the approach from your benchmark, to try make a more isolated test
> case:

Can you try to isolate it even more by something like this:

select * from routes where route && 'a.b.c.d/e';

It would be easier to debug, if we can reproduce performance
regression like this.  It would also be helpful to check where the
time is spent.  Maybe "perf" on Linux would help, though I haven't
used it before.

On Wed, 26 Aug 2015, Emre Hasegeli wrote:

> Can you try to isolate it even more by something like this:

I tried some different bisection approaches:

-- base query (time ~19 seconds)
EXPLAIN (ANALYZE, BUFFERS)
SELECT rv.route, rv.asn, rv.source
FROM
     (SELECT DISTINCT route FROM routes_view WHERE asn = 2914 AND [ stuff here ]) r
     JOIN routes_view rv ON (r.route && rv.route);

SELECT DISTINCT route FROM routes_view WHERE asn = 2914;    -> 732 rows, 0.2 seconds

masklen(route) <= 20;   -> 356 rows, join time  9.2 seconds
masklen(route) > 20;    -> 376 rows, join time  9.1 seconds

family(route) = 6       ->  22 rows, join time  0.2 seconds
family(route) = 4       -> 710 rows, join time 18.1 seconds

route <= '154.0.0.0'    -> 362 rows, join time 9.2 seconds
route > '154.0.0.0'     -> 370 rows, join time 9.5 seconds

Nothing really interesting here though.


> select * from routes where route && 'a.b.c.d/e';
>
> It would be easier to debug, if we can reproduce performance
> regression like this.  It would also be helpful to check where the
> time is spent.  Maybe "perf" on Linux would help, though I haven't
> used it before.

Haven't used this before either (but seem like a nice tool). Output while
running the query:

Samples: 99K of event 'cpu-clock', Event count (approx.): 11396624870
   14.09%  postgres                         [.] inet_gist_consistent
   10.77%  postgres                         [.] 0x00000000000c05f7
   10.46%  postgres                         [.] FunctionCall5Coll
    5.68%  postgres                         [.] gistdentryinit
    5.57%  postgres                         [.] 0x00000000000c05c4
    4.62%  postgres                         [.] FunctionCall1Coll
    4.52%  postgres                         [.] MemoryContextReset
    4.25%  postgres                         [.] bitncmp
    3.32%  libc-2.19.so                     [.] __memcmp_sse4_1
    2.44%  postgres                         [.] 0x00000000000c08f9
    2.37%  postgres                         [.] 0x00000000000c0907
    2.27%  postgres                         [.] 0x00000000000c0682
    2.12%  postgres                         [.] pg_detoast_datum_packed
    1.86%  postgres                         [.] hash_search_with_hash_value
    1.40%  postgres                         [.] inet_gist_decompress
    1.09%  postgres                         [.] 0x00000000000c067e
    1.03%  postgres                         [.] 0x00000000000c047e
    0.77%  postgres                         [.] 0x00000000002f0e57
    0.75%  postgres                         [.] gistcheckpage

This seemed to stay reletively consistent throughout the query.


     Best regards, Henrik

  Henrik Thostrup Jensen <htj at nordu.net>
  Software Developer, NORDUnet

On Wed, 26 Aug 2015, Jeff Janes wrote:

> Any chance you can share the actual underlying data?

Sure. I added a snapshot to the repo:
https://github.com/job/irrexplorer/blob/master/data/irrexplorer_dump.sql.gz?raw=true

> I noticed it wasn't on github, but is that because it is proprietary, or
> just because you don't think it is interesting?

I hoped it wouldn't be this complicated :-).

BGP and IRR data is (mostly) public, but it changes constantly, so there
is little sense in putting in the repo, as it is not the authorative
source (we have a script to boostrap with instead).


> If you loop over the 732 rows yourself, issuing the simple query against each retrieved constant value:
>
> explain (analyze,buffers) select routes.route from routes where route && $1
>
> Does each one take about the same amount of time, or are there some outlier values which take much more time than the
others?

I wrote a small script to try this out. It queries for each route 20 times
to try and suppress the worst noise. I've sorted the results by time and
put it here: https://gist.github.com/htj/1817883f92a9cb17a4f8
(ignore the ntp timing issue causing a negative value)

Some observations:

- v6 is faster than v4 which is expected.

- The slowest prefixes by all seem to start bits '11'.
   However it is only by a factor of 1.5x which is not really significant


     Best regards, Henrik

  Henrik Thostrup Jensen <htj at nordu.net>
  Software Developer, NORDUnet

> Nothing really interesting here though.

I think the slowdown is not related with the key your searched for,
but the organisation of the index.  We have a simple structure for
the index keys.  Basically, common bits of the child nodes are stored
on the parent node.  It leads to not efficient indexes, where there
are too much values with the same prefix.  I couldn't quite understand
why it performs so bad, though.  You might have better luck with
ip4r extension [1] or creating an index using the range types like
this:

> # create type inetrange as range (subtype = inet);
> CREATE TYPE
>
> # create function cidr_to_range(cidr) returns inetrange language sql as 'select inetrange(set_masklen($1::inet, 0),
set_masklen(broadcast($1),0))'; 
> CREATE FUNCTION
>
> # create index on routes using gist ((cidr_to_range(route)));
> CREATE INDEX
>
> # explain analyze select * from routes where cidr_to_range(route) && cidr_to_range('160.75/16');
> QUERY PLAN
> ----------
> Bitmap Heap Scan on routes  (cost=864.50..18591.45 rows=21173 width=19) (actual time=7.249..7.258 rows=7 loops=1)
>   Recheck Cond: (inetrange(set_masklen((route)::inet, 0), set_masklen(broadcast((route)::inet), 0)) &&
'[160.75.0.0/0,160.75.255.255/0)'::inetrange)
>   Heap Blocks: exact=3
>   ->  Bitmap Index Scan on routes_cidr_to_range_idx  (cost=0.00..859.21 rows=21173 width=0) (actual time=7.242..7.242
rows=7loops=1) 
>         Index Cond: (inetrange(set_masklen((route)::inet, 0), set_masklen(broadcast((route)::inet), 0)) &&
'[160.75.0.0/0,160.75.255.255/0)'::inetrange)
> Planning time: 1.456 ms
> Execution time: 7.346 ms
> (7 rows)

I have examined them about the performance problem:

* It splits pages by IP family [2] a lot of times, but deleting IPv6
  rows from the table doesn't make it faster.
* It doesn't fail and do 50-50 split [3] as I expected.
* The previous posted version [4] of it works roughly twice faster,
  but it is still too slow.

[1] https://github.com/RhodiumToad/ip4r
[2] network_gist.c:705
[3] network_gist.c:754
[4] CAE2gYzzioHNxdZXyWz0waruJuw7wKpEJ-2xPTihjd6Rv8YJF_w@mail.gmail.com

Hi

On Thu, 27 Aug 2015, Emre Hasegeli wrote:

> I think the slowdown is not related with the key your searched for,
> but the organisation of the index.  We have a simple structure for
> the index keys.  Basically, common bits of the child nodes are stored
> on the parent node.  It leads to not efficient indexes, where there
> are too much values with the same prefix.  I couldn't quite understand
> why it performs so bad, though.

I can see the issue. Unfortunately IP space tends to be fragmented in some
ranges, and very sparse in other.

It is unfortunate that something to index IP prefixes doesn't handle BGP
and IRR data very well (the only largish "real" datasets with IP prefixes
I can think of).


> You might have better luck with ip4r extension [1] or creating an index
> using the range types like this:
[snip]

Using the range type index:

  Nested Loop  (cost=0.42..603902.92 rows=8396377 width=26) (actual time=0.514..662.500 rows=8047 loops=1)
    ->  Seq Scan on hmm  (cost=0.00..11.32 rows=732 width=7) (actual time=0.015..0.119 rows=732 loops=1)
    ->  Index Scan using routes_cidr_to_range_idx on routes  (cost=0.42..595.58 rows=22941 width=19) (actual
time=0.262..0.903rows=11 loops=732) 
          Index Cond: (inetrange(set_masklen((route)::inet, 0), set_masklen(broadcast((route)::inet), 0)) &&
inetrange(set_masklen((hmm.route)::inet,0), set_masklen(broadcast((hmm.route)::inet), 0))) 
  Planning time: 0.211 ms
  Execution time: 662.769 ms
(6 rows)

Boom. This is actually usefull.

It does take 70 seconds for the biggst network though. The index is also
rather large:

  public | routes_cidr_to_range_idx | index | htj   | routes  | 158 MB |

Table is 119MB data. The gist index was 99 MB.


     Best regards, Henrik

  Henrik Thostrup Jensen <htj at nordu.net>
  Software Developer, NORDUnet