5

I have a PostgreSQL table with, among the other, two columns named col1 and col2, both of integer type (there are around 10M rows in the table). I want to perform SQL queries like:

SELECT * FROM table WHERE col1 >= val1 AND col2 <= val2;

(for certain val1 and val2 that I know a query time).

If I put btree indices on col1 and col2 PostgreSQL tries to execute the query performing an index scan on one of the two columns and then filtering on the other. This means that in most cases it has to sweep through around half of the table, even when the number of matching rows is very little. Adding a multicolumn index is useless, because PostgreSQL can effectively use it only when at least one of the two columns is tested for equality.

One important assumption that I can make on the values, though, is that the two columns are monotonic one respect to the other. This means that 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.

This means that in line of principle the query execution could be sped up by performing an index scan on one of the two columns, filtering on the other and stopping the execution as soon as a non matching value is found on the second column. In this case the query would read just exactly the rows to be returned.

Is there any way to setup indices or whatever other invariant in PostgreSQL so that the query planner is able to detect this?

(of course the problem can be easily solved performing two queries, the first one to translate the inequality on col2 to an inequality on col1; I am asking if there is a way to avoid this workaround and let PostgreSQL manage the mess by itself)

  • 1
    "Adding a multicolumn index is useless" - are you sure? Did you test it? – a_horse_with_no_name Jan 24 '15 at 8:20
  • hmmm, I should probably read the whole question before answering. Why would you want to avoid the workaround? The issue here is that you know your data better than postgres knows it (how could pg be sure the two columns are going to be monotonically related tomorrow even if it can see that they are today?) – Jack Douglas Jan 24 '15 at 10:06
  • Also, you may like to read all the answers on this related question – Jack Douglas Jan 24 '15 at 10:20
  • 1
    @JackDouglas I have no real reasons to avoid the workaround, and that is actually what I am implementing. I just wanted to potentially learn something on databases that I do not know. – Giovanni Mascellani Jan 24 '15 at 17:44
3

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 >= val1 AND col2 <= 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>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)                                                                                                             │
│     ->  Limit  (cost=0.29..0.38 rows=1 width=4) (actual time=0.059..0.060 rows=1 loops=1)                                             │
│           ->  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 > 500))                                                                       │
│                 Heap Fetches: 1                                                                                                       │
│ Total runtime: 0.087 ms                                                                                                               │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
select min(foo) from t where foo>500;
┌─────┐
│ min │
├─────┤
│ 510 │
└─────┘
select min(bar) from t where foo=510;
┌──────┐
│ min  │
├──────┤
│ 1020 │
└──────┘
explain analyse select * from t where bar>=1020 and bar<= 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 >= 1020) AND (bar <= 1100))                                                                   │
│   ->  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 >= 1020) AND (bar <= 1100))                                                               │
│ Total runtime: 0.030 ms                                                                                             │
└─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
select * from t where bar>=1020 and bar<= 1100;
┌─────┬──────┐
│ foo │ bar  │
├─────┼──────┤
│ 510 │ 1020 │
│ 520 │ 1040 │
│ 530 │ 1060 │
│ 540 │ 1080 │
│ 550 │ 1100 │
└─────┴──────┘

clean up:

drop schema stack cascade;
  • Yeah, I know this can be done (and I already suggested that in the last parenthetical in my question). My question was really about the possibility to describe constraints that instructed PostgreSQL to do that by itself (and at this point the answer is probably "No, it cannot be done"). Thanks for the detailed answer anyway. – Giovanni Mascellani Jan 24 '15 at 17:05
  • I noticed that too late :) – Jack Douglas Jan 24 '15 at 17:41
  • Oh, I had not noticed the time progression of the things. – Giovanni Mascellani Jan 24 '15 at 17:43
  • you might be interested to know that ypercube suggested a simpler version of this answer in The Heap – Jack Douglas Jan 24 '15 at 20:14
  • 1
    @a_horse_with_no_name thanks. Those 3 blocks touched are all the rows with foo<=1100. If that foo condition doesn't restrict the matched rows much then most of the index is scanned even when the query ultimately returns the same number of rows (113). – Jack Douglas Jan 25 '15 at 14:42
1

Have you tried using ranges? Maythe the indexing methods for them (gist) can give you desired performance (for large datasets). Though gist indexes come with some tradeoffs (size, build-time, index-time for simple queries).

Some testing code:

create table t(id serial primary key, some_col text, foo numrange);

insert into t(some_col, foo) 
select 'foobar', numrange(10*g, 20*g, '[]') from generate_series(1,50000) g;

create index ix_foo_bar on t  using gist (foo) ;
analyze t;

And querying it:

explain (analyze, buffers, verbose)
select * 
from t 
where foo @> numrange(1020, 1100, '[]');
  • In my case ranges are not a viable alternative. I simplified the question supposing that the two columns are of integer type, but they are actually one integer type (the table primary key) and one floating-point type. I think this means that your suggestion cannot be implemented. Thanks anyway. – Giovanni Mascellani Jan 25 '15 at 18:19
  • @giomasce it doesn't necessarily mean that - a functional index could cast/round. eg if your fp values are between 0 and 1, and your integers between 0 and 1000, multiply by 1000 and round for the index. Obviously your query will have to do the same conversion as the index for it to be used. – Jack Douglas Jan 25 '15 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.