Re: Bitmap index AM

Hello.

I've been working on bitmap index AM for some time.

The situation is --- in general it works, but there're some problems I cannot
fix myself. I've been using Teodor's scripts for concurrency tests (modified a
bit), unfortunately without success.

Anyway, here's the patch. I hope someone will look at it and comment it.

Some notes:
- I haven't tested amrkpos and restrpos functions, don't know how (I've been
trying to make planner choose merge join without luck);
- no space is freed during vacuums, I think I'll elaborate on this in
separate email;
- nothing done around cost estimation.

Waiting for feedback, thanks.

--

Victor Y. Yegorov

I've managed to fix all bugs I've met so far.
Attached is an updated patch.

Comments:
o README should be updated to reflect the changes I've done recently;

o I'm still haven't tested ammarkpos and amrestrpos functions --- planner is
choosing Nested Loop all the time and my knowledge of query tuning isn't
that good to force Merge Join usage;

o The main reason no space is freed during ambulkdelete is that that would
make inserts and updates really slow. It would take really small amount of
time to determine free slot in the List-of-CTIDs, but then I'd have to read
and check the majority of bitmap storage pages, as there is no easy way to
determine page where bit at given position belongs (or I don't see it at
the moment).

The cause --- page contains both, plain and compressed blocks. And the
number of tuples one page of bitmap storage covers may significantly vary,
thus I have to check each page to find the one where newly inserted tuple
should belong. And such search should be done for each value in the indexed
attributes domain.

But I'm willing to discuss any opinions and waiting for the feedback.
Maybe we can find a good compromise here.

Thanks!

--

Victor Y. Yegorov

Hi again.

Here's an updated patch, that fixes several bugs and is synced with HEAD.

--

Victor Y. Yegorov

This has been saved for the 8.2 release:

http://momjian.postgresql.org/cgi-bin/pgpatches_hold

---------------------------------------------------------------------------

Victor Yegorov wrote:
> Hi again.
>
> Here's an updated patch, that fixes several bugs and is synced with HEAD.
>
>
> --
>
> Victor Y. Yegorov

[ Attachment, skipping... ]

>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend

--
Bruce Momjian | http://candle.pha.pa.us
pgman(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

Victor Yegorov wrote:
> Hi again.
>
> Here's an updated patch, that fixes several bugs and is synced with HEAD.

Are you closer to submitting this patch for application?

--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce,

We have a bitmap index AM in Bizgres (on PG 8.1.3) that is functional and
achieves very worthwhile (10x+) performance and space objectives.

It is a large patch, and introduces the access method along with modifying
the appropriate executor nodes. The latter part was necessary because of
the need to bypass the in-memory bitmap index when an on-disk bitmap is
available.

Because this patch is large, how do you suggest we go through review? Also,
there is some further work that Jie is doing to support efficient
multi-column indexes that will simplify the code, so we're not quite ready
for patch submission.

- Luke

On 6/12/06 9:13 AM, "Bruce Momjian" <pgman(at)candle(dot)pha(dot)pa(dot)us> wrote:

> Victor Yegorov wrote:
>> Hi again.
>>
>> Here's an updated patch, that fixes several bugs and is synced with HEAD.
>
> Are you closer to submitting this patch for application?

Luke Lonergan wrote:
> Bruce,
>
> We have a bitmap index AM in Bizgres (on PG 8.1.3) that is functional and
> achieves very worthwhile (10x+) performance and space objectives.
>
> It is a large patch, and introduces the access method along with modifying
> the appropriate executor nodes. The latter part was necessary because of
> the need to bypass the in-memory bitmap index when an on-disk bitmap is
> available.
>
> Because this patch is large, how do you suggest we go through review? Also,
> there is some further work that Jie is doing to support efficient
> multi-column indexes that will simplify the code, so we're not quite ready
> for patch submission.

Well, post a URL of the patch, and keep working on it. When it is
ready, let us know.

--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +