On some other DBMS’s, bitmap indexes are often used for columns that have only a few distinct values. Boolean columns, status codes and such. Compared to normal B-tree indexes, bitmap indexes are very efficient at packing duplicates.
PostgreSQL doesn’t have bitmap indexes, but GIN is also very good at handling duplicates. The internal structure of a GIN index is actually quite similar to a bitmap index. It doesn’t pack items in a bitmap, but in the upcoming 9.4 version it uses so-called varbyte encoding, which in the best case uses only a single byte per indexed row. 2-3 bytes is typical. In earlier versions, each item was packed using 6 bytes, which is still a lot less than the per-tuple overhead of a B-tree index.
For example, let’s create a table with a column, and fill it with some test data:
postgres=# create table numbers (n int4, mod2 int4); CREATE TABLE postgres=# insert into numbers (n, mod2) select n, n % 2 from generate_series(1, 10000000) n; INSERT 0 10000000
To create a GIN index as a substitute for a regular B-tree index, use the btree_gin extension that comes with PostgreSQL:
postgres=# create extension btree_gin; CREATE EXTENSION postgres=# create index numbers_mod2 on numbers using gin (mod2); CREATE INDEX
For comparison, let’s also create a regular B-tree index on it:
postgres=# create index numbers_mod2_btree on numbers using btree (mod2); CREATE INDEX
And check the sizes of the indexes:
postgres=# \\\\di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+--------------------+-------+--------+---------+--------+-------------
public | numbers_mod2_btree | index | heikki | numbers | 214 MB |
public | numbers_mod2_gin | index | heikki | numbers | 10 MB |
(2 rows)
GIN is 20x smaller than a B-tree index!
The above was from a 9.4devel checkout. On 9.3, the GIN index takes 58 MB instead of 10 MB. That’s still a lot smaller than a B-tree, but 9.4 will really up the ante.
I only see one problem with this scheme – being able to use it hinges on actually being aware of all of this, as for example by stumbling upon this blog post. :-)
The btree_gin documentation is currently very hesitant in recommending btree_gin for anything other than serving as a thing to build on (for the relatively few people that might wish to author their own operator class).
And what are the projected performance gains from this? When would I use one over the other? Why would I ever use a btree?
This is interesting and all but it’s not really what bitmap indexes are for. The power of bitmaps is the ability to combine them. Postgres is able to do runtime bitmap conversions with which it can then do a BITMAP AND but the conversion is so costly that this is rarely useful. By storing the bitmaps rather than converting at runtime you can leverage pre-computation to get astounding query speeds when filtering against multiple bitmap-indexed columns. Without true bitmap indexes, Postgres is likely to remain forever ill-suited to data warehouse workloads.
100% in agreement with you. It will hopefully come out in the future, but why the wait, PG is so great, let’s make it greater.
What has always held us back from implementing bitmap indexes is that it requires columns that have few unique values, and are not updated frequently. We just can’t imagine this fits many workloads.
Each new index type must add something significant for important use cases, so Heikki is right to question whether we’ll need bitmaps.
The bitmap index patch that was being actively worked on was measured as having good performance up to 10-20,000 values. So it covers most cases of “category” type columns used in decision support applications.
Updates were definitely slower, though very large Fact tables in BI applications don’t generally have lots of updates.
Other news was pretty good, but we must retest.
Hopefully we’ll see some better measurements in the next dev cycle so we can judge this objectively, now that we have funding to look at this again.
It was Bruce who questioned whether we need bitmap indexes. My gut feeling is that we still do. GIN does a decent job at the same use cases, but it’s nowhere near as compact as a compressed bitmap would be (for certain data distributions, anyway).
We probably don’t need bitmap indexes as a whole new indexam, though. Just modify GIN internal page format (again) to store the items in a bitmap instead of the current compressed item list format. Operator classes require no changes.
Initially Oracle said bitmap indexes would only work for columns with a few number of values. However over time the experience was this was not true. Turned out you could use bitmap indexes and very variable data and get very good performance. I guess they tweaked the design over time. My suspicion is bitmap indexes also behave like a columnar database. They have good compression, you ran read time in from disk super fast and then AND them together. Also my understanding is bitmap indexes are kinda partitioned (which is a kinda index on a index) so you don’t actually always need to read in the full index before you can do some work. The myth of columns with only a few values has been busted by Oracle for a while now. I guess it applied in theory but didn’t work out in practice. Really looking forward to native parallel query in 9.4. Note SQL Server behaves the same as Postgres with bitmap indexes. For DW this is a really big deal.
Two words: data warehouse
GIN posting lists intersection was faster than runtime bitmap AND even before 9.4 . In 9.4 we have GIN fast scan. So, we need some benchmarks to estimate how is GIN in comparison with on-disk bitmap.
As for Oracle, bitmap indexes can be useful even for columns with a very large number of distinct values – it is the repetition of the same value that makes the space cost gain – see Richard Foote’s blog http://richardfoote.wordpress.com/2010/02/18/myth-bitmap-indexes-with-high-distinct-columns-blow-out/
Still with Oracle, bitmap indexes have trouble with concurrent inserts – and this is by design : all sessions that want to insert a row with the same value in the bitmap-indexed column will update the same index value, so contention/serialization is unavoidable. How do Pg GIN indexes handle this ?
GIN has very similar properties. The “number of distinct values” should be understood not as an absolute number, but as a fraction of the total number of rows. B-tree is better if every key is unique, but if you have on average, say, 5 rows per distinct value, GIN (or bitmap indexes) is much more compact. That is to say, if you have 10 million rows with 2 million distinct values, GIN might still be worthwhile because it’s more compact. Especially if the keys are long.
Internally, GIN consists of a B-tree index with one entry for every distinct key, and a list of rows that have that value attached to each entry. The “list of rows” is stored efficiently when there are a lot of rows, but if there is only one row per value, ie. every row is unique, it degenerates into an old-fashioned B-tree.
Even though GIN degenerates into a B-tree, if every value is unique the normal B-tree index is a better choice because it’s better optimized for concurrent updates. For example, we never remove entries from the GIN tree, even when there no rows left with that value. So if you continuously insert and delete rows with different values, the GIN index will grow indefinitely.
So, updating a GIN index is indeed more expensive than updating a B-tree. And there will be more contention, simply because the index is more compact so the contention is not as spread out, and also because updating the compressed posting lists is somewhat expensive.
Updates could probably be optimized to some extent, but no-one’s spent a lot of effort on it.
Could gin btree be used for sorting?
No. If you do something like:
select * from numbers order by mod2;
in the above example, it will do a sequential scan + sort, instead of scanning the index in order.
There’s no fundamental reason why a GIN index couldn’t be used for that, it just hasn’t been implemented. It’s not a very common use case, because there usually won’t be that many duplicates when you want to do an ORDER BY, or if there are, a scan + sort is often faster anyway. And if there aren’t many duplicates, you’ll probably just use a regular B-tree. But it sure would be nice to implement that for the sake of completeness, if nothing else. Patches are welcome :-).