PostgreSQL 9.4: Index Only Used For Lower INET Ranges

Question

For some reason queries on the high range of are extremely slow and queries on the low range are extremely fast.

My index is an adapted version of the answer in Optimizing queries on a range of timestamps (two columns): CREATE INDEX idx_ip_range_inversed ON ip_range_domains(low, high); but it only works for low ranges for some reason.

Table

CREATE TABLE IF NOT EXISTS ip_range_domains (
  ip_range_domain_id     BIGSERIAL PRIMARY KEY,
  domain_id              BIGINT REFERENCES domains                        NOT NULL,
  source_type_id         INTEGER REFERENCES source_types                  NOT NULL,
  low                    INET                                             NOT NULL,
  high                   INET                                             NOT NULL,
  auto_high_conf         BOOLEAN                                          NOT NULL   DEFAULT FALSE,
  invalidation_reason_id INTEGER REFERENCES invalidation_reasons                     DEFAULT NULL,
  invalidated_at         TIMESTAMP WITHOUT TIME ZONE                                 DEFAULT NULL,
  created_at             TIMESTAMP WITHOUT TIME ZONE                      NOT NULL   DEFAULT current_timestamp
);
CREATE INDEX domain_id_btree ON ip_range_domains (domain_id);
CREATE INDEX idx_ip_range_inversed ON ip_range_domains(low, high);

This is fast:

=> EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM ip_range_domains WHERE '8.8.8.8'::INET BETWEEN low AND high;
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on ip_range_domains  (cost=25411.02..278369.96 rows=948529 width=55) (actual time=61.514..61.567 rows=55 loops=1)
   Recheck Cond: (('8.8.8.8'::inet >= low) AND ('8.8.8.8'::inet <= high))
   Heap Blocks: exact=23
   Buffers: shared hit=3613
   ->  Bitmap Index Scan on idx_ip_range_inversed  (cost=0.00..25173.89 rows=948529 width=0) (actual time=61.493..61.493 rows=55 loops=1)
         Index Cond: (('8.8.8.8'::inet >= low) AND ('8.8.8.8'::inet <= high))
         Buffers: shared hit=3590
 Planning time: 0.537 ms
 Execution time: 61.631 ms

This is slow:

=> EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM ip_range_domains WHERE '200.8.8.8'::INET BETWEEN low AND high;
                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on ip_range_domains  (cost=0.00..586084.02 rows=1016801 width=55) (actual time=14090.840..21951.343 rows=1 loops=1)
   Filter: (('200.8.8.8'::inet >= low) AND ('200.8.8.8'::inet <= high))
   Rows Removed by Filter: 23156868
   Buffers: shared hit=21232 read=217499
 Planning time: 0.111 ms
 Execution time: 21951.376 ms

After a bit of manual investigation I found that 74.181.234.146 uses the index but 74.181.234.147 does not. Interestingly, as I get higher, the queries that use the index start taking 600-700ms. Perhaps that's just an issue of finding the data on disk. That's an acceptable response time but faster would be better.

=> EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM ip_range_domains WHERE '74.181.234.146'::INET BETWEEN low AND high;
                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on ip_range_domains  (cost=256258.42..580278.67 rows=5685950 width=55) (actual time=593.066..593.068 rows=3 loops=1)
   Recheck Cond: (('74.181.234.146'::inet >= low) AND ('74.181.234.146'::inet <= high))
   Heap Blocks: exact=3
   Buffers: shared hit=38630
   ->  Bitmap Index Scan on idx_ip_range_inversed  (cost=0.00..254836.93 rows=5685950 width=0) (actual time=593.057..593.057 rows=3 loops=1)
         Index Cond: (('74.181.234.146'::inet >= low) AND ('74.181.234.146'::inet <= high))
         Buffers: shared hit=38627
 Planning time: 0.108 ms
 Execution time: 593.094 ms

Lowest query that doesn't use an index:

=> EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM ip_range_domains WHERE '74.181.234.147'::INET BETWEEN low AND high;
                                                         QUERY PLAN                                                          
-----------------------------------------------------------------------------------------------------------------------------
 Seq Scan on ip_range_domains  (cost=0.00..586084.02 rows=5685950 width=55) (actual time=5723.461..21914.826 rows=3 loops=1)
   Filter: (('74.181.234.147'::inet >= low) AND ('74.181.234.147'::inet <= high))
   Rows Removed by Filter: 23156866
   Buffers: shared hit=21864 read=216867
 Planning time: 0.108 ms
 Execution time: 21914.850 ms

Version:

=> SELECT version();

                                                    version                                                    
---------------------------------------------------------------------------------------------------------------
 PostgreSQL 9.4.4 on x86_64-unknown-linux-gnu, compiled by gcc (GCC) 4.8.2 20140120 (Red Hat 4.8.2-16), 64-bit

Answer 1

Your statistics are way off. The planner thinks it's going to retrieve 948529, 1016801, 5685950 and 5685950 rows, respectively, when infact it retrieves 55, 1, 3 and 3.

In the second example, that is why it's preferring a seqscan (I am guessing it expects to have about 5e+6 values in the table and 1e+6, being 20% of the entire table, is not worth an index scan).

What you need is increasing the statistics target on the two columns (ALTER TABLE ip_range_domains ALTER COLUMN high SET STATISTICS 1000) and run ANALYZE ip_range_domains. This will give the planner a much better idea of the data contained in this table (specifically, the two columns you are filtering on). Try playing with different values (10000 is the maximum).

The decision the planner needs to make is that between a sequential scan of a table, where each individual read is quite cheap (not least because the OS can prefetch that for you, but also because of the mechanics of the storage medium), and a random read (which is believed to be much more expensive because of... well, random, unpredictable reading pattern).

If the planner's conclusion is it will have to read 30% of the index to come up with 20% of the table, which it will all have to retrieve using random fetches, that is simply just too costly, so it will prefer a full sequential scan.