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

Search Discussions

  • Tom Lane at Mar 1, 2005 at 7:34 am

    "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
  • Mark L. Woodward at Mar 1, 2005 at 1:39 pm

    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 at Mar 1, 2005 at 6:11 pm

    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
  • Mark L. Woodward at Mar 1, 2005 at 6:40 pm

    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.
  • Tom Lane at Mar 1, 2005 at 6:59 pm

    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
  • Mark L. Woodward at Mar 1, 2005 at 7:52 pm
    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
  • Hannu Krosing at Mar 3, 2005 at 1:41 pm
    Ü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>
  • Mark L. Woodward at Mar 3, 2005 at 4:41 pm

    Ü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.
  • Pailloncy Jean-Gerard at Mar 4, 2005 at 8:39 am

    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
  • Neil Conway at Mar 4, 2005 at 9:47 am

    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
  • Mark L. Woodward at Mar 4, 2005 at 12:29 pm

    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.
  • Tom Lane at Mar 4, 2005 at 3:28 pm

    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
  • Mark L. Woodward at Mar 4, 2005 at 5:55 pm

    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.
  • Tom Lane at Mar 4, 2005 at 3:00 pm

    Neil Conway 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
  • Pailloncy Jean-Gerard at Mar 5, 2005 at 9:00 am

    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
  • Victor Y. Yegorov at Mar 1, 2005 at 5:53 pm

    * Tom Lane [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
  • Tom Lane at Mar 1, 2005 at 7:05 pm

    "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
  • Victor Y. Yegorov at Mar 1, 2005 at 7:52 pm

    * Tom Lane [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
  • Victor Y. Yegorov at Mar 4, 2005 at 11:03 pm
    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 the WHERE 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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppgsql-hackers @
categoriespostgresql
postedFeb 28, '05 at 7:50p
activeMar 5, '05 at 9:00a
posts20
users6
websitepostgresql.org...
irc#postgresql

People

Translate

site design / logo © 2021 Grokbase