[PATCH] bitmap indexes

Hi.

This is a cleaned-up and rebased version of the bitmap index patch from
Gavin Sherry, later revised by Gianni Ciolli and Gabriele Bartolini, and
others including Daniel Bausch.

I've been working on this patch for a while, and have made some progress
towards (a) general fixing, and (b) a working VACUUM implementation (the
major remaining piece). Unfortunately, I've been busy moving house, and
the latter is not complete (and not in this patch).

I will continue working on the code, and I'll post updates. I expect to
have more to show in just a few days.

Nevertheless, I'm posting it for review now as I keep working. Given the
size and age of the patch, I would appreciate any comments, no matter
how nitpicky.

Thanks.

-- Abhijit

P.S. There are some brokennesses, marked with XXXes in the code. See
also http://www.postgresql.org/message-id/20081101000154.GO27872@fune
and bmi-perf-test.tar.gz in particular.

Hi Abhijit,

On 2013-09-14 23:44:24 +0530, Abhijit Menon-Sen wrote:
> I've been working on this patch for a while, and have made some progress
> towards (a) general fixing, and (b) a working VACUUM implementation (the
> major remaining piece). Unfortunately, I've been busy moving house, and
> the latter is not complete (and not in this patch).
>
> I will continue working on the code, and I'll post updates. I expect to
> have more to show in just a few days.
>
> Nevertheless, I'm posting it for review now as I keep working. Given the
> size and age of the patch, I would appreciate any comments, no matter
> how nitpicky.

It'd be nice if you could quickly sketch out the plan for vacuum, that
will make reviewing more useful and easier.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Sat, Sep 14, 2013 at 1:14 PM, Abhijit Menon-Sen <ams(at)2ndquadrant(dot)com> wrote:
> Hi.
>
> This is a cleaned-up and rebased version of the bitmap index patch from
> Gavin Sherry, later revised by Gianni Ciolli and Gabriele Bartolini, and
> others including Daniel Bausch.
>

Hi Abhijit,

Please, in the next update consider this messages i'm getting when
compiling with your patch.
"""
bitmapxlog.c: In function ‘bitmap_xlog_cleanup’:
bitmapxlog.c:658:32: warning: ‘reln’ may be used uninitialized in this
function [-Wuninitialized]
selfuncs.c: In function ‘bmcostestimate’:
selfuncs.c:7327:13: warning: unused variable ‘indexCorrelation’
[-Wunused-variable]
selfuncs.c:7326:15: warning: unused variable ‘indexSelectivity’
[-Wunused-variable]
selfuncs.c:7325:11: warning: unused variable ‘indexTotalCost’
[-Wunused-variable]
selfuncs.c:7324:11: warning: unused variable ‘indexStartupCost’
[-Wunused-variable]
"""

Also, there are 2 regression tests failing (attached regression.diffs)

And this error, when trying to generate docs
"""
openjade:bitmap.sgml:123:85:X: reference to non-existent ID
"SQL-CREATEINDEX-TITLE"
"""

And finally, i was excercising the feature in some ways and got a
crash when creating an index concurrently (attached
index_failure.txt), it wasn't just a crash i couldn't start up the
server again after it

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

Hi Jaime.

At 2013-09-15 23:32:11 -0500, jaime(at)2ndquadrant(dot)com wrote:
>
> bitmapxlog.c:658:32: warning: ‘reln’ may be used uninitialized in this
> function [-Wuninitialized]

I added an XXX comment about this one, will investigate and fix.

Will look into the other errors as well, many thanks for the report.

-- Abhijit

On Sat, Sep 14, 2013 at 11:14 AM, Abhijit Menon-Sen <ams(at)2ndquadrant(dot)com>wrote:

> Hi.
>
> This is a cleaned-up and rebased version of the bitmap index patch from
> Gavin Sherry, later revised by Gianni Ciolli and Gabriele Bartolini, and
> others including Daniel Bausch.
>
> I've been working on this patch for a while, and have made some progress
> towards (a) general fixing, and (b) a working VACUUM implementation (the
> major remaining piece). Unfortunately, I've been busy moving house, and
> the latter is not complete (and not in this patch).
>
> I will continue working on the code, and I'll post updates. I expect to
> have more to show in just a few days.
>
> Nevertheless, I'm posting it for review now as I keep working. Given the
> size and age of the patch, I would appreciate any comments, no matter
> how nitpicky.
>

Hi Abhijit,

I get wrong answers from this index sometimes. It seems to occur when the
position of the column within the index is not the same as its position
within the table. So I think that what is happening is somewhere the
offset into the list of table columns is misused to offset into the list of
index columns.

I didn't see any XXX notes that indicate this is a known problem.

create table foo as select
floor(random()*10) as a,
floor(random()*10) as b,
floor(random()*10) as c,
d
from generate_series(1,10000000) d;

vacuum ANALYZE;
create index on foo using bitmap (a);
create index on foo using bitmap (b);

select count(*) from foo where a=4;
1000173
select count(*) from foo where a+0=4;
1000173

select count(*) from foo where b=4;
0
select count(*) from foo where b+0=4;
999750

Cheers,

Jeff

At 2013-09-24 09:51:00 -0700, jeff(dot)janes(at)gmail(dot)com wrote:
>
> I get wrong answers from this index sometimes.

Thanks for the report and the test case. I'll investigate.

-- Abhijit

Hi,

Here are some quick items while skimming this patch. I am looking at
commit 6448de29d from your github repo, branch bmi.

What's with the pg_bitmapindex stuff in pg_namespace.h? It doesn't seem
to be used anywhere.

This led me to research how these indexes are stored. I note that what
we're doing here is to create another regular table and a btree index on
top of it, and those are the ones that actually store the index data.
This seems grotty and completely unlike the way we do things elsewhere
(compare GIN indexes which have rbtrees inside them). I think this
should be stored in separate forks, or separate kinds of pages
intermixed in the index's main fork.

I don't like that files are named bitmap.c/.h. We already have bitmap
scans, so having the generic concept (bitmap) show up as a file name is
confusing. To cite an example, see the name of the bmgetbitmap function
(which returns a TID bitmap from a bitmap index. How is that not
confusing?). I think I would be more comfortable with the files being
called "bmi" or maybe "bitmapidx", or something like that. (For sure do
not change the AM's name. I mean "CREATE INDEX .. USING bmi" would
suck.)

Not happy with (the contents of) src/include/access/bitmap.h. There's
way too much stuff in a single file. I think a three-file split would
work nicely: one for the AM routine declarations (bitmap.h), one for
xlog stuff (bitmap_xlog.h), one for internal routines and struct
declarations (bitmap_priv.h, bitmap_internals.h, or something like
that). Also, I think macros and structs should be defined in a narrow
scope as possible; for example, macros such as HEADER_SET_FILL_BIT_ON
should be defined in bitmaputil.c, not bitmap.h (that macro is missing
parens BTW). For macros that are defined in headers, it would be better
to have prefixes that scope them to bitmaps; for example IS_FILL_WORD
should maybe have a BM_ prefix or something similar.

I don't think it's necessary to renumber relopt_kind. Just stash the
new one at the end of the enum.

bmoptions's DESCR entry in pg_proc.h says "btree".

contrib/bmfuncs.c defines CHECK_PAGE_OFFSET_RANGE but doesn't seem to
use it anywhere.

same file defines CHECK_RELATION_BLOCK_RANGE using a bare { } block. Our
style is to have these multi-statement macros use do {} while (false).

#include lines in source files are normally alphabetically sorted. The
new code fails to meet this expectation in many places.

First four lines of _bitmap_init seem gratuitous ..

All those #ifdef DEBUG_BMI lines sprinkled all over the place look
pretty bad; they interrupt the indentation flow. I would suggest to
define a macro or some macros to emit debugging messages, which are
enabled or disabled in a single place depending on DEBUG_BMI. Something
simple such as DO_DB() in fd.c would suffice.

I don't like this comment one bit: /* misteriously, MemSet segfaults... :( */
I think that's probably a bug that should be investigated rather than
papered over.

I don't understand the cur_bmbuild thingy .. I think that stuff should
be passed down as arguments to whatever do the index build, instead of
being a magical global var that also signals failure to find hash
functions for some datatypes.

Above definition of BMBuildHashData there's a comment referring us to
execGrouping.c but I cannot understand what it refers to.

"block unfound"? In general I think it's poor style to spell out the
function name in error messages. I mean, ereport() already reports the
function name. Also, please don't split long error messages across
multiple lines; better to leave the line to run off the screen.

I'm unsure about distinguishing errors in the recovery routines that
raise ERROR from those that PANIC. I mean, they would both cause the
server to PANIC.

The bitmap_xlog_cleanup routine talks about an "uninitialized reln".
That's a large point about xlog recovery -- you don't have relations.
You only have relfilenodes. I think you need to shuffle some routines
so that they can work with only a relfilenode.

Generally, the xlog stuff needs a lot of comments.

A pgindent run would be beneficial.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 09/26/2013 12:20 AM, Alvaro Herrera wrote:

> This led me to research how these indexes are stored. I note that what
> we're doing here is to create another regular table and a btree index on
> top of it, and those are the ones that actually store the index data.
> This seems grotty and completely unlike the way we do things elsewhere
> (compare GIN indexes which have rbtrees inside them).

Perhaps you meant that GIN has B-tree inside. RBTree is in fact used by
GiST, but only as in-memory structure during the search - to get the
tuples sorted by distance.

// Antonin Houska (Tony)

At 2013-09-25 19:20:17 -0300, alvherre(at)2ndquadrant(dot)com wrote:
>
> Here are some quick items while skimming this patch.

Great, that gives me plenty to work on.

At this point, I think it's appropriate to mark this patch as returned
with feedback (which I will do), since the changes needed seem fairly
major. I'll submit a revised patch for the next commitfest.

Many thanks to everyone who tried the patch and commented.

-- Abhijit

On Wed, Sep 25, 2013 at 3:20 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>wrote:

> Hi,
>
> Here are some quick items while skimming this patch. I am looking at
> commit 6448de29d from your github repo, branch bmi.
>
> What's with the pg_bitmapindex stuff in pg_namespace.h? It doesn't seem
> to be used anywhere.
>
> This led me to research how these indexes are stored. I note that what
> we're doing here is to create another regular table and a btree index on
> top of it, and those are the ones that actually store the index data.
> This seems grotty and completely unlike the way we do things elsewhere
> (compare GIN indexes which have rbtrees inside them).

+1 on that. I don't know about grottiness, but it certainly seems like it
would deadlock like crazy. Which another product's bitmap indexes are
infamous for, but since we don't need to store visibility information in
our indexes, hopefully we can do better.

Cheers,

Jeff

At 2013-09-26 08:39:05 -0700, jeff(dot)janes(at)gmail(dot)com wrote:
>
> I don't know about grottiness, but it certainly seems like it would
> deadlock like crazy.

Hi Jeff.

I don't understand the deadlock scenario you're thinking of. Could you
explain, please?

-- Abhijit