Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I'm trying to extend PostgreSQL to index bit strings up to 1000 bits. (These bit strings are created by quantization of high-dimensional vectors, so for each dimension up to 4 bits are assigned). Insertions are rather infrequent, whereas searches are the mostly used operation. In a search, I would like to get all the rows that exactly match the bit string.

It looks like a perfect job for GIN (in combination with my own data type), or what do you think?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

In a search, I would like to get all the rows that exactly match the bit string.

Use a B-Tree index, the default type. I don't see a case for a GIN index here.

Up to 1000 bits result in up to 133 bytes (or slightly more) storage size on disk for a bit varying type.

SELECT pg_column_size(repeat('1', 1000)::varbit)  -- 133

Not that much. A plain B-Tree index should do. But maybe the column is big enough that the following tricks improve performance.

If a small part of the bitstring column is distinctive enough to narrow your search down to few hits, an index on an expression might give you better performance, because the smaller index can fit into RAM and is faster to process all around. Don't bother for small tables, the overhead would eat the benefit. But could make a big difference for big tables.


Given table:

CREATE TABLE tbl(id serial PRIMARY KEY, b_col varbit);

If the first 10 bit are enough to narrow down a search to a few hits, you could create an index on the expression b_col::bit(10). Casting to bin(n) truncates the bitstring to n bit.

CREATE INDEX tbl_b_col10_idx ON tbl (b_col::bit(10))

Then, instead of the query

SELECT * FROM tbl WHERE b_col = '1111011110111101'::varbit; -- 16 bit

You would use:

FROM   tbl
WHERE  b_col::bit(10) = '1111011110111101'::bit(10) -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- filter to exact match

Be aware that shorter values are padded with 0's to the right (least significant bits) when cast to bit(n).

In a real world application this starts to make sense with several 100s of bits. Test for the turning point.

Optimize further

Since most installations operate with a MAXALIGN of 8 bytes (64 bit OS) (more details here), your index size is the same for any data not exceeding 8 bytes. Effectively, per row:

 4 bytes item pointer
23 bytes for the tuple header
 1 byte padding for data alignment
   actual space for data
   padding to the nearest multiple of 8 bytes

Plus some minor overhead per page and index / table. Details in the manual or in this related answer on SO.

Therefore, you should be able to further optimize the above approach. Take the first 64 bit (or last or whatever is most distinctive and works for you), cast it to bigint and build an index on this expression.
Effectively, this is just a very fast and simple hash function, where the hash value also allows to look up ranges of values. Depending on exact requirements you could go one step further and use any (IMMUTABLE) hash function.

CREATE INDEX tbl_b_col64_idx ON tbl (b_col::bit(64)::bigint)

I cast twice (::bit(64)::bigint) for there is no cast defined between varbit and bigint. The query to go along with that:

FROM   tbl
WHERE  b_col::bit(64)::bigint = '1111011110111101'::bit(64)::bigint -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- narrow down to exact match

The resulting index should be just as big as the one in the first example, but queries should be considerably faster for three reasons:

  • The index typically returns much fewer hits (64 bit of information vs. 10 bit)

  • Postgres can work with integer arithmetic, which should be faster, even for a plain = operation. (Didn't test to verify that.)

  • The type integer has no overhead like varbit - 5 or 8 bytes. (In my installation 5 bytes for up to 960 bit, 8 bytes for more).
    Effectively, to keep the index at its minimum size, you can only pack 24 bit into a varbit index - compared to 64 bit of information for a bigint index.


In such a case CLUSTER should improve performance:

CLUSTER TABLE tbl USING tbl_b_col10_idx;

It's a one-time operation and has to be repeated at intervals of your design. Be sure to read the manual on CLUSTER if you want to use that. Or consider the alternative pg_repack. Details:

If the first 64 bit of your values are unique most of the time, CLUSTER will barely help, since the index scan will return a single row in most cases. If not, CLUSTER will help a lot. Consequently, the effect will be far greater for the first example with the less optimized index.

share|improve this answer
Thanks a lot for this detailed answer! That's great! –  navige Jan 31 '13 at 14:49
Effectively, my solution is similar to a hash index, just with a very fast and simple hash algorithm (the cast) and tailored to Postgres' index capabilities. –  Erwin Brandstetter Jan 31 '13 at 22:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.