Thread: bitmap AM design

Here's the design of bitmap AM I'm planning to implement. I've discussed it
with Neil, but I'm willing to get more feedback on it.


There are going to be 1 metapage, 1 list of CTIDs (LOC), one list
of attribute values (LOV, including attributes for multi-column indexes) and a
bitmap for each entry in the LOV. Metapage will contain pointers to the LOC,
LOV will always start at page-1 and is organized as a 1-way chained list.

Neil suggested a very good way how to handle updates. Of course, it's not
necessary to strictly follow tuple layout in the table's heap, as I wanted
to do initially. All that's needed, is that bit positions in bitmaps would
be tied with CTID positions in LOC.
So, we can do simple insert (generally, that's how MVCC works for tuple
updates): when some tuple is updated, new CTID is added to the LOC and each
bitmap is extended by 1 bit.
On the other side (as Neil pointed), after VACUUM, we need to do some
maintenance of bitmap index to avoid situations when index contains duplicate
entries (in LOC and bitmaps) for the same CTID (value before marking tuple for
reuse and after actually reusing it). So far, the fastest way would be
recreating index, because the whole index designed for faster search/insert
operations and lacks effective reverse mapping (CTID->bit position->bit value)
functionality.

List of CTIDs is organized into an array of extents. Each extent has 2**i
pages ('i' is extent number in array). All pages for extent are allocated at
once, ensuring their IDs are sequential. So, we need to store only
BufferNumber of the first page in extent. LOC pages contain array of
ItemPointerData, it's size is detected at compile time. So, CTID for given bit
position can be obtained via only one ReadBuffer() call.

LOV pages store arrays of value-descriptors, each descriptor has a pointer to
the head of value's bitmap. Bitmaps are organized as 1-way chained list,
bitmap contents is compressed using Word-Aligned Hybryd method (similar to
RLE).
Neil suggested the other way of organizing bitmap storage: all bits for
given position are stored in one page (if it lacks space, new page is added
"at the bootom"), so we'll have a 2-dimensional bitmap storage.
This reduces amount of page reads during index scan, but for low-cardinality
indexes, we'll waste a lot of space per page, if each CTIDs slice is stored in
one page. On the other hand, it'll be hard to extend bitmap if we'll store
several CTID slices per page and some new value will be inserted (i.e. CTID
slice needs to be increased).

At the moment, I would implement the easiest method -- equality encoding (as
it's called in papers, bitmap per value). Neil's suggested techniques are
called range encoding. Josh Berkus on the irc suggested implementing several
encoding schemes as an option to the "create index" sql command.
What do you think?

I haven't looked at planner/executor yet.


If you have some questions, please, ask. Also, I'd like to tell that this is
my first time coding for PostgreSQL, thus I may use incorrect terminology.
Also, it takes much time to write anything, for the same  reason. And yes,
I would really appreciate all kind of criticism on this design.

I've started to implement AM, I need to register am* functions, what OIDs
should use to register them in include/catalog/pg_proc.h?


Waiting for your feedback.


-- 

Victor Y. Yegorov

"Victor Y. Yegorov" <viy@mits.lv> writes:
> Neil suggested a very good way how to handle updates. Of course, it's not
> necessary to strictly follow tuple layout in the table's heap, as I wanted
> to do initially. All that's needed, is that bit positions in bitmaps would
> be tied with CTID positions in LOC.
> So, we can do simple insert (generally, that's how MVCC works for tuple
> updates): when some tuple is updated, new CTID is added to the LOC and each
> bitmap is extended by 1 bit.

The other stuff you mentioned implies that an insertion therefore
requires exclusive lock on the index (because you may have to relocate
everything in sight to add one more CTID slot).

> On the other side (as Neil pointed), after VACUUM, we need to do some
> maintenance of bitmap index to avoid situations when index contains duplicate
> entries (in LOC and bitmaps) for the same CTID (value before marking tuple for
> reuse and after actually reusing it). So far, the fastest way would be
> recreating index,

I can't believe you are seriously suggesting that it's OK to force every
VACUUM to rebuild the index from scratch.  We already get far too many
complaints about the time needed for VACUUM.

I don't think we really need any more fundamentally nonconcurrent index
types :-(

> I've started to implement AM, I need to register am* functions, what OIDs
> should use to register them in include/catalog/pg_proc.h?

Anything the unused_oids script reports as free.
        regards, tom lane

> I don't think we really need any more fundamentally nonconcurrent index
> types :-(
>

Tom, I posted a message about a week ago (I forget the name) about a
persistent reference index, sort of like CTID, but basically a table
lookup. The idea is to simulate a structure that ISAM sort of techniques
can work in PostgreSQL.

Victor had emailed me and basically said he needed a similar sort of thing
for this bitmap index.

Eliminating the bitmap index issue for a moment, how hard would it be to
create a reference table like index? I'm sure given that construct, the
bitmap index becomes easier to construct.

* Tom Lane <tgl@sss.pgh.pa.us> [01.03.2005 09:37]:
> The other stuff you mentioned implies that an insertion therefore
> requires exclusive lock on the index (because you may have to relocate
> everything in sight to add one more CTID slot).

No, exclusive lock on index is worst thing to do.

All lists (list of ctids, bitmaps) will only grow, no data will be deleted, as
deletes will require relocation and possibly exclusive lock on the index.

Extending lists will need only a short-term exclusive locks on the pages in
the tails of each list.


> I can't believe you are seriously suggesting that it's OK to force every
> VACUUM to rebuild the index from scratch.  We already get far too many
> complaints about the time needed for VACUUM.
> 
> I don't think we really need any more fundamentally nonconcurrent index
> types :-(

Well, I misunderstood the purpose of ambulkdelete function, my fault.

Of course, no index rebuild will take place, instead, only flags in the
list of CTIDs will be updated for deleted tuples.


I have counter question for you: you've mentioned, that you want bitmaps in
the 8.1. What kind of bitmaps you were speaking about? On-disk bitmaps (this
is how I call new index access method I'm working on) or in-memory bitmaps,
as in here http://archives.postgresql.org/pgsql-hackers/2005-01/msg01001.php


Thanks for your reply.


-- 

Victor Y. Yegorov

pgsql@mohawksoft.com writes:
> Tom, I posted a message about a week ago (I forget the name) about a
> persistent reference index, sort of like CTID, but basically a table
> lookup. The idea is to simulate a structure that ISAM sort of techniques
> can work in PostgreSQL.

> Eliminating the bitmap index issue for a moment, how hard would it be to
> create a reference table like index?

I didn't see the point.  You cannot actually use CTID that way (at least
not without fundamentally redesigning our MVCC machinery) and anything
else you might come up with is effectively just a random unique ID that
has to be mapped through an index to find the row.  I don't see the
advantage compared to any ordinary application-defined primary key.
        regards, tom lane

> pgsql@mohawksoft.com writes:
>> Tom, I posted a message about a week ago (I forget the name) about a
>> persistent reference index, sort of like CTID, but basically a table
>> lookup. The idea is to simulate a structure that ISAM sort of techniques
>> can work in PostgreSQL.
>
>> Eliminating the bitmap index issue for a moment, how hard would it be to
>> create a reference table like index?
>
> I didn't see the point.  You cannot actually use CTID that way (at least
> not without fundamentally redesigning our MVCC machinery) and anything
> else you might come up with is effectively just a random unique ID that
> has to be mapped through an index to find the row.  I don't see the
> advantage compared to any ordinary application-defined primary key.

I have a search engine product which does use primary key based number.
The search engine also uses an external bitmap index. Here is the process:

Parse incoming text into discrete words.
Look up each word and retrieve its bitmap.
Combine all the bitmaps using the appropriate logical functions (AND, OR,
etc)
list out all the "1s" from the bitmaps as an entry into a table which
points to the primary key number.
Find all the records in the database with all the primary keys, sometimes
hundreds or thousands of entries in a "WHERE IN (...)" clause.
Now, after I've done all this logical work getting document numbers, I
have to do an index lookup for each one (or, god forbid, a full table
scan!)
This can be a long process, longer than actually doing the text search
with the bitmaps in the first place.

A "persistent reference" index would be like almost any other index except
that as new items are added to a table a new entry is added to the end of
the index. When a row is updated, its CTID is updated in the table. When
you run vacuum, you just update the CTID in the table as if it were any
other index. When you delete an item, you clear the CDID value of the
table entry. You can do "VACUUM COMPRESS INDEX myindex" which will
re-order and compact the persistent reference.

I know from a purely SQL standpoint, it sounds whacky, but from a VAR or
consultants point of view, it can really increase performance of some
products. That last "WHERE IN" clause of my search engine can take several
tens of seconds to run, but the actual search engine only took 0.03
seconds to find the documents. A persistent reference system would
eliminate tens ro thousands of index lookups per search query.

pgsql@mohawksoft.com writes:
> A "persistent reference" index would be like almost any other index except
> that as new items are added to a table a new entry is added to the end of
> the index. When a row is updated, its CTID is updated in the table.

This *does not work* under MVCC: it can't cope with referencing
multiple simultaneously existing versions of a row.  In general, any
index design that includes the words "update in place" can be rejected
out of hand.

In any case I still fail to see the advantage compared to an ordinary
serial primary key.  You could have made your bitmaps reference the
serial numbers directly, instead of an intermediate table.  (Either way
still fails to handle MVCC updates, unless the indexable attributes
cannot be changed by updates; but the intermediate table isn't helping
or hurting that.)

A bitmap that indexes CTIDs directly could work, because it doesn't need
to update any entries in-place when a table row is updated.  I didn't
care for the details of Victor's design because (a) the intermediate
list of CTIDs looks bulky and (b) it seemed to require a lot of data
shuffling to cope with growth of the table.  But in principle it would
work.
        regards, tom lane

"Victor Y. Yegorov" <viy@mits.lv> writes:
> All lists (list of ctids, bitmaps) will only grow, no data will be
> deleted, as deletes will require relocation and possibly exclusive
> lock on the index.
> Extending lists will need only a short-term exclusive locks on the pages in
> the tails of each list.

Hmm, you seem to be envisioning that these are actually lists, not
arrays --- that is, to find the N'th page in a list requires traversing
list links starting at the first page.  That doesn't sound workable.
If you can't access all the entries in roughly constant time then the
thing is going to have problems with big tables.

> I have counter question for you: you've mentioned, that you want bitmaps in
> the 8.1. What kind of bitmaps you were speaking about?

In-memory is what I intend to work on.
        regards, tom lane

OK, lets step back a bit and see if there is a solution that fits what we
think we need and PostgreSQL.

Lets talk about FTSS, its something I can discuss easily. It is a two
stage system with an indexer and a server. Only the data to be indexed is
in the database, all the FTSS data structures are in external files.

The indexer creates a number of data structures.
A table of document references, one entry per document.
A table of words parsed, one word per entry
A table of compressed bitmaps, one (or more) bitmap(s) per word.

The relation of bits in the word bitmaps is one bit per document as
ordered by the document table, i.e. if bit 5 is set high, then the fith
document is selected.

(Let's not discuss phrase analysis at this point.)

When the indexer runs, it executes a query that produces a set of results.
Each result has a document reference which is stored in the FTSS document
table.
The results are parsed out as discrete words, new words are added to the
word table, previously used word's reference counts are incremented.
A bitmap is created for each new word.
The bit of the current document is set to "1."
This procedure runs for each record in the query.

The server runs as follows:
accepts an HTTP request for search
Parses out the discrete words.
The word is found in the word table.
The word's bitmap is retrieved from the bitmap table.
A series of logical functions are performed on the retrieved bitmaps.
The resulting bitmap contains all the relevant documents in the form of
bits correlating to offsets into the document reference table.
The list of document references is returned to the database and found
using a "WHERE IN" clause.

Now, it occurs to me that if my document reference table can refer to
something other than an indexed primary key, I can save a lot of index
processing time in PostgreSQL if I can have a "safe" analogy to CTID.

I should be able to "know" more about a particular row (document) being
referenced, because I have already been through the table once.

I need to be able to "know" which rows are newer than my FTSS index so I
can search those rows more dynamically. I currently do this by saving the
highest value during indexing.



> pgsql@mohawksoft.com writes:
>> A "persistent reference" index would be like almost any other index
>> except
>> that as new items are added to a table a new entry is added to the end
>> of
>> the index. When a row is updated, its CTID is updated in the table.
>
> This *does not work* under MVCC: it can't cope with referencing
> multiple simultaneously existing versions of a row.  In general, any
> index design that includes the words "update in place" can be rejected
> out of hand.
>
> In any case I still fail to see the advantage compared to an ordinary
> serial primary key.  You could have made your bitmaps reference the
> serial numbers directly, instead of an intermediate table.  (Either way
> still fails to handle MVCC updates, unless the indexable attributes
> cannot be changed by updates; but the intermediate table isn't helping
> or hurting that.)
>
> A bitmap that indexes CTIDs directly could work, because it doesn't need
> to update any entries in-place when a table row is updated.  I didn't
> care for the details of Victor's design because (a) the intermediate
> list of CTIDs looks bulky and (b) it seemed to require a lot of data
> shuffling to cope with growth of the table.  But in principle it would
> work.
>
>             regards, tom lane
>

* Tom Lane <tgl@sss.pgh.pa.us> [01.03.2005 21:07]:
> Hmm, you seem to be envisioning that these are actually lists, not
> arrays --- that is, to find the N'th page in a list requires traversing
> list links starting at the first page.  That doesn't sound workable.
> If you can't access all the entries in roughly constant time then the
> thing is going to have problems with big tables.

Bitmaps are arays, you're right. But they are only accessed either when data
is inserted and gets added to the end (there're direct pointers to the last
page in each bitmap in the list of values), or during index scan. Scanning
index implies visiting all pages that forms the bitmap.

After scanning the bitmaps (and performing all logical operations as
requested), we end up with bit positions and need to return CTID from the
list, that resides in the given position in the list-of-CTIDs (yes, it's
actually one huge array, that occupies many pages).

List-of-CTIDs is organized into extents, each extent contains a known number
of pages and all pages for the extent are allocated sequentially. ID of the
first page of each extent is stored in the metapage. Also, it is known at
compile time how many CTIDs can be stored into one page. Given all that, it is
possible to compute ID of the page and CTID offset inside that page by CTID
offset, obtained at bitmap scan step.
Each extent has 2,4,8,16,32,etc. pages, so the metapage has enough space to
store an array of ID's for the first page of each extent.

Updating list-of-CTIDs is also "cheap" operation, as direct reference to the
last page in the list-of-CTIDs is stored in metapage.

The only list, that have drawbacks you've mentioned, is list-of-values. But,
as it contains only attributes' related data and pointers to start page of
corresponding bitmap, there won't be many pages in this list.


Maybe, there are some more insufficiencies I've missed?


-- 

Victor Y. Yegorov

Ühel kenal päeval (teisipäev, 1. märts 2005, 14:54-0500), kirjutas
pgsql@mohawksoft.com:
> Now, it occurs to me that if my document reference table can refer to
> something other than an indexed primary key, I can save a lot of index
> processing time in PostgreSQL if I can have a "safe" analogy to CTID.

I guess you could work on making hash indexes better (for concurrent
access).

'a "safe" analogy to CTID' looks remarkably like hash index

--
Hannu Krosing <hannu@tm.ee>

> Ühel kenal päeval (teisipäev, 1. märts 2005, 14:54-0500), kirjutas
> pgsql@mohawksoft.com:
>> Now, it occurs to me that if my document reference table can refer to
>> something other than an indexed primary key, I can save a lot of index
>> processing time in PostgreSQL if I can have a "safe" analogy to CTID.
>
> I guess you could work on making hash indexes better (for concurrent
> access).
>
> 'a "safe" analogy to CTID' looks remarkably like hash index
>

Yes, I agree, but I don't particularly like linear hash models without the
ability to adjust the initial table size estimates. Also, hash tables
without access to the hash function typically have a lot of collision,
specifically, I am dubious of "generic" hash functions having an optimally
dispersed behavior.

Le 2 mars 05, à 21:17, Hannu Krosing a écrit :

> Ühel kenal päeval (teisipäev, 1. märts 2005, 14:54-0500), kirjutas
> pgsql@mohawksoft.com:
>> Now, it occurs to me that if my document reference table can refer to
>> something other than an indexed primary key, I can save a lot of index
>> processing time in PostgreSQL if I can have a "safe" analogy to CTID.
>
> I guess you could work on making hash indexes better (for concurrent
> access).
You should have a look to this thread
http://archives.postgresql.org/pgsql-hackers/2005-02/msg00263.php

Take a look at this paper about "lock-free parallel hash table"
http://www.cs.rug.nl/~wim/mechver/hashtable/

> 'a "safe" analogy to CTID' looks remarkably like hash index
>
> --
> Hannu Krosing <hannu@tm.ee>

Cordialement,
Jean-Gérard Pailloncy

Pailloncy Jean-Gerard wrote:
> You should have a look to this thread
> http://archives.postgresql.org/pgsql-hackers/2005-02/msg00263.php
> 
> Take a look at this paper about "lock-free parallel hash table"
> http://www.cs.rug.nl/~wim/mechver/hashtable/

Is this relevant? Hash indexes are on-disk data structures, so ISTM 
lock-free algorithms aren't really applicable.

(BTW, is poor concurrency really the biggest issue with hash indexes? If 
so, there is some low-hanging fruit that I noticed a few years ago, but 
never got around to fixing: _hash_doinsert() write-locks the hash 
metapage on every insertion merely to increment a tuple counter. This 
could be improved by just acquiring the lock with probability 1/k, and 
incrementing the counter k times -- or some similar statistical 
approximation. IMHO there are bigger issues with hash indexes, like the 
lack of WAL safety, the very slow index build times, and their 
relatively poor performance -- i.e. no better than btree for any 
workload I've seen. If someone wants to step up to the plate and fix 
some of that, I'll improve hash index concurrency -- any takers? :-) )

-Neil

> Pailloncy Jean-Gerard wrote:
>> You should have a look to this thread
>> http://archives.postgresql.org/pgsql-hackers/2005-02/msg00263.php
>>
>> Take a look at this paper about "lock-free parallel hash table"
>> http://www.cs.rug.nl/~wim/mechver/hashtable/
>
> Is this relevant? Hash indexes are on-disk data structures, so ISTM
> lock-free algorithms aren't really applicable.
>
> (BTW, is poor concurrency really the biggest issue with hash indexes? If
> so, there is some low-hanging fruit that I noticed a few years ago, but
> never got around to fixing: _hash_doinsert() write-locks the hash
> metapage on every insertion merely to increment a tuple counter. This
> could be improved by just acquiring the lock with probability 1/k, and
> incrementing the counter k times -- or some similar statistical
> approximation. IMHO there are bigger issues with hash indexes, like the
> lack of WAL safety, the very slow index build times, and their
> relatively poor performance -- i.e. no better than btree for any
> workload I've seen. If someone wants to step up to the plate and fix
> some of that, I'll improve hash index concurrency -- any takers? :-) )
>

As always, I'd love to have the time to do this stuff, but as always, I'm
not in the position to spend any time on it. It's frustrating.

Anyway, IMHO, hash indexes would be dramatically improved if you could
specify your own hashing function and declare initial table size. If you
could do that, and work on an assumption that the hashing index was for
fairly static data, it could handle many needs. As it stands, hash indexes
are virtually useless.

Neil Conway <neilc@samurai.com> writes:
> (BTW, is poor concurrency really the biggest issue with hash indexes? If 
> so, there is some low-hanging fruit that I noticed a few years ago, but 
> never got around to fixing: _hash_doinsert() write-locks the hash 
> metapage on every insertion merely to increment a tuple counter. 

Given the short amount of time that lock is held, this wouldn't
win anything worth noticing.  Also, it's not "merely" to increment a
counter --- the counter drives decisions about whether to split buckets,
so any decrease in accuracy would lead directly to losses in overall
performance.

The lack of WAL support is a much bigger issue.
        regards, tom lane

pgsql@mohawksoft.com writes:
> Anyway, IMHO, hash indexes would be dramatically improved if you could
> specify your own hashing function

That's called a custom operator class.

> and declare initial table size.

It would be interesting to see if setting up the hashtable with about
the right number of buckets initially would make CREATE INDEX enough
faster to be a win ... but that doesn't mean I want to make the user
deal with it.  We could probably hack hashbuild() to estimate the
size of the parent table using the same code that the planner is now
using (ie, actual size in pages times a possibly-dead-reckoning rows
per page estimate).
        regards, tom lane

> pgsql@mohawksoft.com writes:
>> Anyway, IMHO, hash indexes would be dramatically improved if you could
>> specify your own hashing function
>
> That's called a custom operator class.

Would I also be able to query the bucket size and all that?

>
>> and declare initial table size.
>
> It would be interesting to see if setting up the hashtable with about
> the right number of buckets initially would make CREATE INDEX enough
> faster to be a win ... but that doesn't mean I want to make the user
> deal with it.  We could probably hack hashbuild() to estimate the
> size of the parent table using the same code that the planner is now
> using (ie, actual size in pages times a possibly-dead-reckoning rows
> per page estimate).
>

I know a linear hash is different than a classic simple hash table, but a
classic simple hash table has some great advantages at the expense of disk
space. IMHO being able to use the hash index in a way that is more of the
classic theoretical hash table and use the linear behavor if the table
grows beyond initial estimates I think would be a big win. It could
actually get to a 1:1 operation data retrieval on properly estimated
tables.

Estimations are a great idea, something like first prime after 2*NROWS
(with a GUC limit, I guess) would probably make hash indexes the fastest
most disk hogging index around.

Some more thoughts and questions.

The main idea above bitmaps is narrowing some data sets' possible values to
"yes" and "no" (i.e. 1 and 0) and then organize the data in the series of
bits, where bit's position determines values to consider. In the cases, where
several indexed attributes are used in WHERE clause, it's possible to do
logical AND/OR on bitmaps before returning any results to the caller. For
large tables with high number of low-cardinality attributes using bitmaps can
result in certain speed-up.

For on-disk bitmaps I'm working on, each value of each indexed attribute has
it's own bitmap (i.e. series of bits, with bits set to 1 for rows with
corresponding fields having value of that bitmap). Scanning the bitmap, we end
up with an array of "1-bits' positions" and need to convert those positions to
CTIDs, as executor is expecting. So, index should also keep a CTID table, that
corresponds to the bitmap's data. This CTID table will be the same for all
bitmap indexes, created for one table, thus having 2 bitmap indexes will mean
you're wasting some amount of disk space, storing absolutely identical data.
So, to save space, we have 2 possibilities:
1) create a new relkind for the CTID table (maybe used not only for on-disk  bitmaps);
2) make all "create index ... using bitmap" statements actually create/extend  existing bitmap index. This also
implies,that planner/executor should  try using multicolumn bitmap index when at least one indexed field is  present in
theWHERE clause.
 

I'm working on the 2nd case, because 1st one requires more work not only in
the access method + executor + planner area. It is also possible to keep
things as is and make a note in the documentation, that it is better to have 1
multicolumn bitmap index, then several single column ones, and that planner
will still use multicolumn index even if not all columns are involved.

Any comments/ideas here?


After implementing bitmap index access method, it'll be necessary to teach
planner and executor to use multicolumn bitmaps for any number of
scan-attributes. Also, I cannot say in what circumstances planner should
prefer bitmap scan to seqscan; I thought of cases, when it estimates return
set being about 60% of the relation. What community has to say here?


Also, as Tom is planning to work on in-memory bitmaps (maybe something is
done already, don't know), I thought that it can be possible to cooperate.
As I have no clue at the moment how in-memory bitmaps are going to work, is it
possible to hear from you some draft of the forthcoming implementation?
And what prerequisites would be required to join both bitmaps somehow?

Waiting for your thoughts/comments.


-- 

Victor Y. Yegorov

> Pailloncy Jean-Gerard wrote:
>> You should have a look to this thread
>> http://archives.postgresql.org/pgsql-hackers/2005-02/msg00263.php
>> Take a look at this paper about "lock-free parallel hash table"
>> http://www.cs.rug.nl/~wim/mechver/hashtable/
>
> Is this relevant? Hash indexes are on-disk data structures, so ISTM
> lock-free algorithms aren't really applicable.
No. Sorry for the misunderstanding.

Cordialement,
Jean-Gérard Pailloncy