Take advantage of monotonic columns in PostreSQL
if in a row col1 is greater then or equal two col1 in another row, then the same relation is valid between the two corresponding col2 entries


In which case you can reformulate your query to look like:

SELECT * FROM table WHERE col2 &gt;= val1 AND col2 &lt;= val2;


because you can find the lower bound for col2 from the lower bound for col1, like this:

schema:

create schema stack;
set search_path=stack;
--
create table t(foo integer, bar integer);
insert into t(foo,bar) select 10*g, 20*g from generate_series(1,100000) g;
create index on t(foo);
create index on t(bar);


method:


explain analyse select min(foo) from t where foo&gt;500; -- assuming val1=500

  
  ┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                              QUERY PLAN                                                               │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Result  (cost=0.38..0.39 rows=1 width=0) (actual time=0.063..0.064 rows=1 loops=1)                                                    │
│   InitPlan 1 (returns $0)                                                                                                             │
│     -&gt;  Limit  (cost=0.29..0.38 rows=1 width=4) (actual time=0.059..0.060 rows=1 loops=1)                                             │
│           -&gt;  Index Only Scan using t_foo_idx on t  (cost=0.29..2803.63 rows=33167 width=4) (actual time=0.058..0.058 rows=1 loops=1) │
│                 Index Cond: ((foo IS NOT NULL) AND (foo &gt; 500))                                                                       │
│                 Heap Fetches: 1                                                                                                       │
│ Total runtime: 0.087 ms                                                                                                               │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

  
  select min(foo) from t where foo&gt;500;

  
  ┌─────┐
│ min │
├─────┤
│ 510 │
└─────┘

  
  select min(bar) from t where foo=510;

  
  ┌──────┐
│ min  │
├──────┤
│ 1020 │
└──────┘

  
  explain analyse select * from t where bar&gt;=1020 and bar&lt;= 1100; -- assuming val2=1100

  
  ┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                     QUERY PLAN                                                      │
├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Bitmap Heap Scan on t  (cost=13.42..485.00 rows=500 width=8) (actual time=0.011..0.013 rows=5 loops=1)              │
│   Recheck Cond: ((bar &gt;= 1020) AND (bar &lt;= 1100))                                                                   │
│   -&gt;  Bitmap Index Scan on t_bar_idx  (cost=0.00..13.29 rows=500 width=0) (actual time=0.008..0.008 rows=5 loops=1) │
│         Index Cond: ((bar &gt;= 1020) AND (bar &lt;= 1100))                                                               │
│ Total runtime: 0.030 ms                                                                                             │
└─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

  
  select * from t where bar&gt;=1020 and bar&lt;= 1100;

  
  ┌─────┬──────┐
│ foo │ bar  │
├─────┼──────┤
│ 510 │ 1020 │
│ 520 │ 1040 │
│ 530 │ 1060 │
│ 540 │ 1080 │
│ 550 │ 1100 │
└─────┴──────┘



clean up:

drop schema stack cascade;