Re: visualizing B-tree index coverage

"TJ O'Donnell" <tjo(at)acm(dot)org> writes:

> However, I am concerned that I must place the most selective column first in
> my index. I cannot tell, a priori, which column will be most selective. That
> depends on the nature of search, which can vary widely each time.

If you're always using > operators then perhaps you would be better off with
three separate indexes on <x>, <y>, and <z> rather than one on <x,y,z>. It
depends on your use case.

It's also possible you would be better off with a GiST index on the array
[x,y,z] and using the GiST indexable operators in contrib/intarray. However
there are disadvantages to these addons as well.

> Are you saying that if my first column is not selective, even though the
> remaining columns are, the planner may choose not to use the index after
> seeing that the first column is not very selective? That seems like an
> oversight, IMHO. Shouldn't the overall effect of using all the columns be
> considered before choosing not to use an index scan?

If your index is on <x,y,z> and you say x=? and y=? and z=? then it's best to
have x be the most selective column but it's only a question of degree. The
index will be useful in basically the same situations, it'll just perform
somewhat better.

On the other hand if your index is on <x,y,z> and you say "x>? and y=? and
z=?" then the remaining qualifications after x>? are useless. Postgres simply
cannot use them in the index lookup. If your index was on <y,z,x> then
Postgres can use it to go straight to the start of the records that match and
read them from the index until they stop matching.

Consider the analogous situation if you were using an index of a book. I tell
you to look up everything in the encylopedia that starts with a letter after
"p". And by the way the second letter has to be an "x" and the third letter a
"y". You will more or less have to skim through everything after "p" even
though you know the second and third letter because the matching entries will
be scattered throughout the remaining pages.

Actually that's not entirely true, you could check each letter after "p" and
look up specifically "qxy...", "rxy...", "sxy...", "txy...", etc right up to
"xzy...". But unfortunately that's just not something Postgres currently knows
how to do. Even then you can see that it's much less efficient than just
reading a contiguous section of records out in order.

--
greg