1

I know that index internally is B-tree or similar tree structure. Suppose index is built for 3 columns (a,b,c), I want Postgres to:

  1. find key [a=10, b=20, c=30] in that B-tree,
  2. scan next 10 entries and return them.

If the index has only one column the solution is obvious:

select * from table1
where a >= 10
order by a limit 10

But if there are more columns the solution becomes much more complex. For 2 columns:

select * from table1
where a > 10 or (a = 10 and b >= 20)
order by a, b limit 10

3 columns:

select * from table1
where a > 10 or (a = 10 and (b > 20 or b = 20 and c >= 30))
order by a, b, c limit 10

Note that query: 

select * from table1
where a >= 10 and b >= 20 and c >= 30
order by a, b, c limit 10

is incorrect, since it will filter out for example [a = 11, b = 10, c=1].

How can I tell Postgres that I want this operation?

And can I be sure that even for those complex queries for 2+ columns the optimizer will always understand that he should perform range-scan? Why?

Erwin Brandstetter
  • 605,456
  • 145
  • 1,078
  • 1,228
Yuri Yaryshev
  • 991
  • 6
  • 24

1 Answers1

3

Use ROW values for comparison:

SELECT *
FROM   table1
WHERE  (a,b,c) >= (10, 20, 30)
ORDER  BY a,b,c
LIMIT  10;

(Using >= to match your code, though your description suggests >. Either works.)

(a,b,c) is short notation for ROW(a,b,c), really.

And yes, Postgres understands that it can use a matching multicolumn B-tree index for this (unlike some other RDBMS - or so I have heard).

"Matching" means that all index expressions, their sequence and the associated order (ASC|DESC) are the same - or the sort order of the whole index row is perfectly inverted, so that Postgres can scan the index backwards at almost the same speed.
For the given example these indexes match:

(a ASC, b ASC, c ASC)
(a DESC, b DESC, c DESC)

But these do not:

(a ASC, b DESC, c ASC)
(a ASC, c ASC, b ASC)

Optimizing queries on a range of timestamps (two columns)

Related, with more explanation:

Erwin Brandstetter
  • 605,456
  • 145
  • 1,078
  • 1,228
  • Perfect answer. Hovewer I've encountered another problem: what if index is [a asc, b desc, c asc]. Can I use this cool syntax somehow in this case? – Yuri Yaryshev Apr 10 '19 at 16:58
  • New questions should go into new questions, not comments. But it's close enough, I added more to address that above. – Erwin Brandstetter Apr 10 '19 at 17:14
  • Agree. Moved another question here: https://stackoverflow.com/questions/55618108/enforcing-index-scan-for-multicolumn-comparison-non-uniform-index-column-order?noredirect=1#comment97929503_55618108 – Yuri Yaryshev Apr 10 '19 at 17:24