If I'm reading this article correctly, one can create an index on t(col1, col2) and use it to speed up lookups for col1. Storage and CPU-wise, I assume that having such a combined index is more efficient than having two indexes. From this perspective, how does PostgreSQL build a map of the indexed data in a way that allows such single-column queries? In other words, what algorithms and/or data structures enable that?


No map needs to be built.

A multi-column index can be thought of as a list that is ordered as follows:

 col1 | col2
    1 |    1   \
    1 |    3    \--> for all entries with col1 = 1, sort by col2
    1 |    4    /
    1 |   42   /
    3 |    1   \
    3 |    2    \
    3 |    2     |--> for all entries with col1 = 3, sort by col2
    3 |    5    /
    3 |   12   /
    4 |    2
    4 |    7

Now an index can be used if all the values you want to scan lie next to each other in the index.

Now if you want to find the rows WHERE col1 = 42, you find them right next to each other in the index. So the index can be used for such a condition.

It is different for the condition WHERE col2 = 1. Here the index cannot be used, because the entries with col2 = 1 are spread all over the index.

  • So basically PostgreSQL doesn't allow to look up by col2 if index is on (col1, col2)? – d33tah Nov 14 '19 at 23:42
  • That has nothing to do with "allow". It just cannot be used effectively. Look at the list I sketched in my answer. How can you use a list that is sorted in this way to find all entries with col2 = 1? There is no way but to read the whole list. Then you might as well scan the whole table. So using the index offers no advantage. – Laurenz Albe Nov 15 '19 at 7:19
  • Okay, thanks. Sounds like I misunderstood the documentation and having an index on (col1, col2) will also optimize queries by col1, but not by col2 then, leaving them as seq_scan. No idea where I got the misunderstanding from. – d33tah Nov 15 '19 at 11:03

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.