Re: Question about indexes

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> I don't think so. You are thinking only of exact-equality queries ---
> as soon as the WHERE clause describes a range of index entries, the
> readout wouldn't be sorted by ctid anyway.

But then even bitmap indexes would fail in that way too, or at least have a
lot of extra cost that would have to be taken into account based on the number
of values in the range.

> Combining indexes via a bitmap intermediate step (which is not really
> the same thing as bitmap indexes, IIUC) seems like a more robust
> approach than relying on the index entries to be in ctid order.

I would see that as the next step, But it seems to me it would be only a small
set of queries where it would really help enough to outweigh the extra work of
the sort. Whereas if the ctid is already pre-sorted then the extra cost is
fairly low. Sort of like the difference in cost between a merge join where
both sides have to be sorted and a merge join where both sides are pre-sorted.

> But if we did want to sort indexes that way, we could do it today,
> I think. The ctid is already stored in index entries (it is the
> "payload" remember...) and we could use it as a tiebreaker when
> determining insertion position. This doesn't have the problems that
> putting ctid into the user columns would do, because the system knows
> about that ctid as being special; the difficulty with ctid in the user
> columns is the code not knowing that it'd need to change on a tuple move.

That's exactly what I was thinking. I just don't know how badly it would
complicate the vacuum{,full}/cluster code and whether those are the only cases
to worry about.

Note that the space saving of bitmap indexes is still a substantial factor.
Using btree indexes the i/o costs of doing multiple index scans plus a table
scan of the relevant pages would still be quite substantial. So this doesn't
completely obviate the need for bitmap indexes, but I think it would remove a
lot of the pressure from people who just need them to handle a few select
queries.

--
greg