Thread: An inverted index using roaring bitmaps

On Mon, Jun 6, 2022 at 10:42 PM Chinmay Kanchi <cgkanchi@gmail.com> wrote:
> The simulated index in this case is outrageously fast, up to ~150x on the GROUP BY.

Couldn't you make a similar argument in favor of adding a B-Tree index
on "country"? This probably won't be effective in practice, but the
reasons for this have little to do with how a B-Tree index represents
TIDs. A GIN index can compress TIDs much more effectively, but the
same issues apply there.

The main reason why it won't work with a B-Tree is that indexes in
Postgres are not transactionally consistent structures, in general.
Whereas your cities_rb table is transactionally consistent (or perhaps
just simulates a transactionally consistent index). Maybe it could
work in cases where an index-only scan could be used, which is roughly
comparable to having a transactionally consistent index. But that
depends on having the visibility map set most or all heap pages
all-visible.

GIN indexes don't support index-only scans, and I don't see that
changing. So it's possible that just adding TID compression to B-Tree
indexes would significantly speedup this kind of query, just by making
low cardinality indexes much smaller. Though that's a hard project,
for many subtle reasons. This really amounts to building a bitmap
index, of the kind that are typically used for data warehousing, which
is something that has been discussed plenty of times on this list. GIN
indexes were really built for things like full-text search, not for
data warehousing.

B-Tree deduplication makes B-Tree indexes a lot smaller, but it tends
to "saturate" at about 3.5x smaller (relative to the same index with
deduplication disabled) once there are about 10 or so distinct keys
per row (the exception is indexes that happen to have huge keys, which
aren't very interesting). There are many B-Tree indexes (with typical
sized keys) that are similar in size to an "equivalent" GIN index --
the ability to compress TIDs isn't very valuable when you don't have
that many TIDs per key anyway. It's different when you have many TIDs
per key, of course. GIN indexes alone don't "saturate" at the same
point -- there is often a big size difference between low cardinality
and ultra low cardinality data. There are bound to be cases where not
having that level of space efficiency matters, especially with B-Tree
index-only scans that scan a significant fraction of the entire index,
or even the entire index.

-- 
Peter Geoghegan

On Tue, Jun 7, 2022 at 5:00 PM Chinmay Kanchi <cgkanchi@gmail.com> wrote:
> I personally don't think this is a great replacement for a BTree index - for one thing, it isn't really possible to
usethis approach beyond equality comparisons (for scalars) or "contains"-type operations for arrays (or tsvectors,
jsonb,etc).
 

Why not? A bitmap is just a way of representing TIDs, that is often
very space efficient once compression is applied. In principle a
bitmap index can do anything that a B-Tree index can do, at least for
SELECTs.

Bitmap indexes are considered totally distinct to B-Tree indexes in
some DB systems because the concurrency control characteristics (the
use of heavyweight locks to protect the logical contents of the
database) are very different . I think that this is because the index
structure itself is so dense that the only practical approach that's
compatible with 2PL style concurrency control (or versions to MVCC
based on 2PL) is to lock a large number of TIDs at the same time. This
can lead to deadlocks with even light concurrent modifications --
which would never happen with an equivalent B-Tree index. But the data
structure is nevertheless more similar than different.

I probably wouldn't want to have a technique like roaring bitmap
compression of TIDs get applied by default within Postgres B-Trees,
but the reasons for that are pretty subtle. I might still advocate
*optional* TID list compression in Postgres B-Trees, which might even
be something we'd end up calling a bitmap index, that would only be
recommended for use in data warehousing scenarios. Extreme TID list
compression isn't free -- it really isn't desirable when there are
many concurrent modifications to relatively few index pages, as is
common in OLTP applications. That's one important reason why bitmap
indexes are generally only used in data warehousing environments,
where the downside doesn't really matter, but the upside pays for
itself (usually a fact table will have several bitmap indexes that are
usually combined, not just one).

> We ultimately abandoned that project because of the difficulty of keeping the bitmaps in sync with changing data,
whichwould no longer be an issue, if this was built as an index.
 

I think that it would in fact still be an issue if this was built as
an index. There is a reason why the concurrency characteristics of
bitmap indexes make them unsuitable for OLTP apps, which seems
related. That wouldn't mean that it wouldn't still be worth it, but it
would definitely be a real downside with some workloads. B-Tree
deduplication is designed to have very little overhead with mixed
reads and writes, so it's a performance all-rounder that can still be
beaten by specialized techniques that come with their own downsides.

-- 
Peter Geoghegan