Hello.

I'd like to implement bitmap indexes and want your comments. Here is
an essence of what I've found regarding bitmaps for the last month.

Consider the following table So, the bitmap for attribute A will be the
with 1 attribute A(int2): following:
# | A Val | Bitmap(s)
----+--- -----+---------------
1 | 1 1 | 11011001 0111
2 | 1 2 | 00100100 1000
3 | 2 3 | 00000010 0000
4 | 1
5 | 1
6 | 2
7 | 3
8 | 1
9 | 2
10 | 1
11 | 1
12 | 1

Some points:
1) If some new value will be inserted (say, 4) at some point of time, a new
bitmap for it will be added. Same for NULLs (if atrribute has no NOT NULL
contraint) --- one more bitmap. Or should we restrict "NOT NULL" for
bitmap'ed attributes?;

2) Queries, like "where A = 1" or "where A != 2" will require only 1 scan of
the index, while "where A < 3" will require 2 stages: 1st create a
list of
values lesser then 3, 2nd --- do OR of all bitmaps for that values.
For high cardinality attributes, this can take a lot of time;

3) Each bitmap is only a bitmap, so there should be an array of
corresponding
ctids pointers. Maybe, some more arrays (pages, don't know).

For 2)nd --- there are techniques, allowing better performance for "A < 3"
queries via increased storage space (see here for details:
http://delab.csd.auth.gr/papers/ADBIS03mmnm.pdf) and increased reaction time
for simple queries. I don't know, if they should be implemented, may later.

The most tricky part will be combinig multiple index scans on several
attributes --- as Neil Conway said on #postrgesql, this will be tricky,
as some
modifications will be needed in the index scan api. I remember, Tom Lane
suggested on-disk bitmaps --- implementing bitmap index access method
would be of much use not only for bitmap indexes, I think.

WAH compressing method should be used for bitmaps (to my mind). Also,
there is
a method of reordering heap tuples for better compression of bitmaps, I
thought
it may be possible to implement it as some option to the existing CLUSTER
command, papers:
WAH: http://www-library.lbl.gov/docs/LBNL/496/26/PDF/LBNL-49626.pdf
CLUSTER: http://www.cse.ohio-state.edu/~hakan/publications/reordering.pdf

I'd like to hear from you, before starting to do something.

--

Victor

Search Discussions

  • Tom Lane at Jan 29, 2005 at 4:23 pm

    "Victor Y. Yegorov" <viy@mits.lv> writes:
    I remember, Tom Lane suggested on-disk bitmaps
    I have suggested no such thing, and in fact believe that the sort of
    index structure you are proposing would be of very little use. What
    I've been hoping to look into is *in memory* bitmaps used as an
    interface between index scans and the subsequent heap lookups.
    See eg this thread:
    http://archives.postgresql.org/pgsql-hackers/2004-10/msg00439.php
    particularly
    http://archives.postgresql.org/pgsql-hackers/2004-10/msg00668.php

    regards, tom lane
  • Victor Y. Yegorov at Jan 29, 2005 at 5:39 pm

    * Tom Lane [29.01.2005 18:24]:
    "Victor Y. Yegorov" <viy@mits.lv> writes:
    I remember, Tom Lane suggested on-disk bitmaps
    I have suggested no such thing, and in fact believe that the sort of
    index structure you are proposing would be of very little use.
    Why? I thought they would be useful for data warehouse databases.

    Maybe I said something "the wrong way", but what I'm trying to implement
    is exactly what is said about in the first link you've posted below:
    http://archives.postgresql.org/pgsql-hackers/2004-10/msg00439.php

    Or am I misunderstanding the point?

    What I've been hoping to look into is *in memory* bitmaps used as an
    interface between index scans and the subsequent heap lookups.
    Sorry, that was what I've been speaking of.

    Anyway, bitmap indexes API could be used for in-memory bitmaps you're speaking
    of.


    --

    Victor Y. Yegorov
  • Victor Y. Yegorov at Jan 29, 2005 at 5:41 pm

    * Pawe� Niewiadomski [29.01.2005 17:45]:
    I'd like to implement bitmap indexes and want your comments. Here is
    an essence of what I've found regarding bitmaps for the last month.
    Do you think it would be possible to work on it as a team?
    Yes, why not.

    But everything depends on the community, may bitmaps will be realized as a
    contrib or pgfoundry module. The only thing --- I don't know, if that is
    possible for indexes.


    --

    Victor Y. Yegorov
  • Mike Rylander at Jan 29, 2005 at 6:47 pm

    On Sat, 29 Jan 2005 19:41:20 +0200, Victor Y. Yegorov wrote:
    * Pawe� Niewiadomski [29.01.2005 17:45]:
    I'd like to implement bitmap indexes and want your comments. Here is
    an essence of what I've found regarding bitmaps for the last month.
    Do you think it would be possible to work on it as a team?
    Yes, why not.

    But everything depends on the community, may bitmaps will be realized as a
    contrib or pgfoundry module. The only thing --- I don't know, if that is
    possible for indexes.
    For on-disk bitmap indexes, yes. I don't see any reason this couldn't
    be done with GiST, perhaps even as a generalization of the index stuff
    in the int_array contrib module. But the bitmaps that Tom as been
    advocating, the ones used to join two index scans, will require a new
    planner Op.

    As a side note, wouldn't the in-memory bitmaps pretty much kill the
    need for multicolumn indexes? It seems that they would be able to
    join index scans on the same table, and then there would be no need
    for industrial strength cross-column correlation stats. The planner
    would be able to choose a multi index scan based on multiple single
    column stat entries and completely sidestep the need for precalculated
    cross-column correlations. Am I getting that right?

    --
    Mike Rylander
    mrylander@gmail.com
    GPLS -- PINES Development
    Database Developer
    http://open-ils.org
  • Dawid Kuroczko at Jan 29, 2005 at 7:21 pm

    On Sat, 29 Jan 2005 18:46:44 +0000, Mike Rylander wrote:
    As a side note, wouldn't the in-memory bitmaps pretty much kill the
    need for multicolumn indexes? It seems that they would be able to
    join index scans on the same table, and then there would be no need
    for industrial strength cross-column correlation stats. The planner
    would be able to choose a multi index scan based on multiple single
    column stat entries and completely sidestep the need for precalculated
    cross-column correlations. Am I getting that right?
    I'm not too sure of that. Lets imagine big table with two columns,
    a and b. If we use multicolumn index (a,b), the search must go through
    a tree, find a value, and from there find b value.

    With in-memory bitmap, the search would start with index a, all
    matching rows would form the bitmap; then the second search
    would go through b index, forming another bitmap. Which then
    would be ANDed with previous bitmap.
    If I am correct, in case of in-memory bitmap PostgreSQL would
    have to read more index tuples (the less unique values, the
    more tuples to read) which in majority of cases would mean
    more work than multicolumn index.

    However in-memory bitmap would speed up many other
    cases (think: OR), but multicolumn indexes are there to stay. :)

    Regards,
    Dawid
  • Victor Yegorov at Jan 29, 2005 at 7:55 pm

    * Dawid Kuroczko [29.01.2005 21:25]:

    With in-memory bitmap, the search would start with index a, all
    matching rows would form the bitmap; then the second search
    would go through b index, forming another bitmap. Which then
    would be ANDed with previous bitmap.
    Not only matching rows will form a bitmap, all rows should.

    And the physical order of rows in the table is important to form bitmap.


    --

    Victor Y. Yegorov
  • Dawid Kuroczko at Jan 29, 2005 at 7:57 pm

    On Sat, 29 Jan 2005 21:54:39 +0200, Victor Yegorov wrote:
    * Dawid Kuroczko [29.01.2005 21:25]:
    With in-memory bitmap, the search would start with index a, all
    matching rows would form the bitmap; then the second search
    would go through b index, forming another bitmap. Which then
    would be ANDed with previous bitmap.
    Not only matching rows will form a bitmap, all rows should.

    And the physical order of rows in the table is important to form bitmap.
    My mistake -- when I said "all matching rows would form the bitmap"
    I meant "all matching rows would form '1's in the bitmap". :)
    Gotta work on clarity of my messages.

    Regards,
    Dawid
  • Tom Lane at Jan 29, 2005 at 9:21 pm

    Mike Rylander writes:
    As a side note, wouldn't the in-memory bitmaps pretty much kill the
    need for multicolumn indexes? It seems that they would be able to
    join index scans on the same table, and then there would be no need
    for industrial strength cross-column correlation stats.
    No, because the ability to do it is not the same as the ability to
    predict in advance how many rows will result.

    regards, tom lane
  • Neil Conway at Jan 30, 2005 at 12:08 am

    Mike Rylander wrote:
    For on-disk bitmap indexes, yes. I don't see any reason this couldn't
    be done with GiST
    It might be possible to do it with GiST, but GiST is designed for
    implementing tree-structured indexes; I don't think it's the right tool
    for the job.

    -Neil
  • Mike Rylander at Jan 30, 2005 at 12:40 am

    On Sun, 30 Jan 2005 11:07:59 +1100, Neil Conway wrote:
    Mike Rylander wrote:
    For on-disk bitmap indexes, yes. I don't see any reason this couldn't
    be done with GiST
    It might be possible to do it with GiST, but GiST is designed for
    implementing tree-structured indexes; I don't think it's the right tool
    for the job.
    For the initial example where the index is implemented as a set of
    unique keys from the table and a bitmap for each key this would look a
    unique index, but with an extra datum at at each index node to hold
    the bitmap for that key. If implemented that way an augmented B-Tree
    structure would work fine. At least that's how I would imagine an
    on-disk bitmap index would work. I suppose that would make the index
    much more efficient for high-cardinality values, no?

    --
    Mike Rylander
    mrylander@gmail.com
    GPLS -- PINES Development
    Database Developer
    http://open-ils.org
  • Neil Conway at Jan 30, 2005 at 1:18 am

    Mike Rylander wrote:
    For the initial example where the index is implemented as a set of
    unique keys from the table and a bitmap for each key this would look a
    unique index, but with an extra datum at at each index node to hold
    the bitmap for that key. If implemented that way an augmented B-Tree
    structure would work fine. At least that's how I would imagine an
    on-disk bitmap index would work.
    It might _work_, I just don't see the point. Given an attribute of a
    heap relation that has N distinct values and T tuples, you need to store

    - N bitmaps, each of T bits (before compression)
    - T ctids
    - a way to map from a bit in one of the bitmaps to a heap tuple
    - a way to decide which bitmap(s) to use for a given index scan

    I don't see why it's a win to organize this data in a tree. Why not
    store the ctids in a simple array? You then know that bit K of any
    bitmap refers to entry K of the ctid array. You'd also need some meta
    data to figure out which bitmap to use for a given scankey, but it
    should be pretty easy to do that efficiently.

    -Neil
  • Mike Rylander at Jan 30, 2005 at 1:52 am

    On Sun, 30 Jan 2005 12:15:20 +1100, Neil Conway wrote:
    It might _work_, I just don't see the point. Given an attribute of a
    heap relation that has N distinct values and T tuples, you need to store

    - N bitmaps, each of T bits (before compression)
    - T ctids
    - a way to map from a bit in one of the bitmaps to a heap tuple
    - a way to decide which bitmap(s) to use for a given index scan

    I don't see why it's a win to organize this data in a tree. Why not
    store the ctids in a simple array? You then know that bit K of any
    bitmap refers to entry K of the ctid array. You'd also need some meta
    data to figure out which bitmap to use for a given scankey, but it
    should be pretty easy to do that efficiently.
    OK, I think it just clicked. I was seeing a tree for the initial
    lookup to find the right bitmaps to scan. Does that seem like to much
    overhead for the first step?

    So, pick the bitmap(s) based on the key, scan the bitmaps and combine
    them based on the WHERE condition combination type, and as you find
    matching bits you toss the ctids into a "matching" array. Then it's a
    fast ctid scan. That it? I'm very interested in this after reading a
    bit (heh he) about bitmap indexes. Here's how I'm visualizing it now:

    For a query like "SELECT * FROM table WHERE a IN (1,3)" ...

    Index on "table.a" looks like:

    bitmaps
    1 | 001001001001000
    2 | 100000010100001
    3 | 010110100010110

    ctids
    1 | {2,5,8,11}
    2 | {0,7,9,14}
    3 | {1,3,4,6,10,12,13}


    The index scan would do bitwise a OR on bitmaps 1 and 3, find the
    possition of the "1"s, jump to those possitions in the ctid array, and
    bounce to the heap for the value.


    --
    Mike Rylander
    mrylander@gmail.com
    GPLS -- PINES Development
    Database Developer
    http://open-ils.org
  • Jim C. Nasby at Jan 30, 2005 at 9:58 am

    On Sat, Jan 29, 2005 at 01:56:12PM +0200, Victor Y. Yegorov wrote:
    2) Queries, like "where A = 1" or "where A != 2" will require only 1 scan of
    the index, while "where A < 3" will require 2 stages: 1st create a
    list of
    values lesser then 3, 2nd --- do OR of all bitmaps for that values.
    For high cardinality attributes, this can take a lot of time;

    3) Each bitmap is only a bitmap, so there should be an array of
    corresponding
    ctids pointers. Maybe, some more arrays (pages, don't know).

    For 2)nd --- there are techniques, allowing better performance for "A < 3"
    queries via increased storage space (see here for details:
    http://delab.csd.auth.gr/papers/ADBIS03mmnm.pdf) and increased reaction time
    for simple queries. I don't know, if they should be implemented, may later.
    Sorry if this is in the PDF but I didn't want to read 17 pages to find
    out... for the example where 1 >= A >= 4, couldn't you just do NOT (A >=
    3)? Granted, in this example it wouldn't matter, but it would be faster
    to do this if you asked for A < 4. One downside is that you'd also have
    to consider the NULL bitmap, if the field is nullable.
    --
    Jim C. Nasby, Database Consultant decibel@decibel.org
    Give your computer some brain candy! www.distributed.net Team #1828

    Windows: "Where do you want to go today?"
    Linux: "Where do you want to go tomorrow?"
    FreeBSD: "Are you guys coming, or what?"
  • Pawel Niewiadomski at Jan 30, 2005 at 7:37 pm

    On Sat, 29 Jan 2005 18:46:44 +0000, Mike Rylander wrote :

    For on-disk bitmap indexes, yes. I don't see any reason this couldn't
    be done with GiST, perhaps even as a generalization of the index stuff
    in the int_array contrib module.
    I was thinking about playing with the core
    source of PostgreSQL and creating patches, GiST as I read
    has some limitations that I want to overcome. Speaking about
    my idea - I was thinking about implementing on-disk indexes, not in
    memory. I think having both of them would be great :-)

    --
    **Pawel Niewiadomski**, new()foo-baz.com, http://new.foo-baz.com/
    Virtual Qmail (http://v-q.foo-baz.com), qmail-patches (http://q-p.foo-baz.com)

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppgsql-hackers @
categoriespostgresql
postedJan 29, '05 at 11:56a
activeJan 30, '05 at 7:37p
posts15
users7
websitepostgresql.org...
irc#postgresql

People

Translate

site design / logo © 2022 Grokbase