Re: [HACKERS] Bitmap index scans use of filters on available columns

[Jeff Janes]

On Sun, Nov 8, 2015 at 12:34 PM, Tom Lane  wrote:
> Jeff Janes  writes:
>> On Fri, Nov 6, 2015 at 7:15 PM, Tomas Vondra
>>  wrote:
>>> I've however also noticed that all the 'like' procedures are marked as not
>>> leak proof, which is a bit unfortunate because that's the example from
>>> Jeff's e-mail that started this thread.
>
>> Is there a reason they aren't leak proof?  I don't see that they have
>> side effects, or that they can throw errors.  What do they leak?
>
> Huh?
>
> regression=# select 'z' like '\';
> ERROR:  LIKE pattern must not end with escape character

Ah, I was only thinking of the pattern as a constant.  And there is no
way to declare a function leakproof on one input but not another.

Cheers,

Jeff


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tom Lane]

Jeff Janes  writes:
> On Fri, Nov 6, 2015 at 7:15 PM, Tomas Vondra
>  wrote:
>> I've however also noticed that all the 'like' procedures are marked as not
>> leak proof, which is a bit unfortunate because that's the example from
>> Jeff's e-mail that started this thread.

> Is there a reason they aren't leak proof?  I don't see that they have
> side effects, or that they can throw errors.  What do they leak?

Huh?

regression=# select 'z' like '\';
ERROR:  LIKE pattern must not end with escape character

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Jeff Janes]

On Fri, Nov 6, 2015 at 7:15 PM, Tomas Vondra
 wrote:
> Hi,
>
> On 11/07/2015 02:18 AM, Robert Haas wrote:
>>
>> On Fri, Nov 6, 2015 at 7:11 PM, Tomas Vondra
>>  wrote:

 I think LEAKPROOF is probably fine for this.  How would the new thing
 be different?
>>>
>>>
>>> I don't think so - AFAIK "leakproof" is about not revealing information
>>> about arguments, nothing more and nothing less. It does not say whether
>>> it's
>>> safe to evaluate on indexes, and I don't think we should extend the
>>> meaning
>>> in this direction.
>>
>>
>> That seems like a non-answer answer.
>
>
> I'm not claiming I have an answer, really. My knowledge of leakproof stuff
> is a bit shallow. Also, I had a few beers earlier today, which does not
> really improve the depth of knowledge on any topic except politics and
> football (aka soccer). So you may be perfectly right.
>
>> Clearly, if a function can leak information about it's arguments,
>> for example by throwing an error, we can't call it on tuples that
>> might not even be visible, or the behavior of the query might be
>> change. So any function that is not leakproof is also not safe for
>> this purpose.
>>
>> Now that doesn't rule out the possibility that the functions for
>> which this optimization is safe are a subset of the leakproof
>> functions - but offhand I don't see why that should be the case. The
>> index tuple is just a tuple, and the values it contains are just
>> datums, no more or less than in a heap tuple. There could be a reason
>> for concern here, but saying that it might not be "safe to evaluate
>> on indexes" just begs the question: WHY wouldn't that be safe?
>
>
> Ah. For some reason I thought the "division by zero" example is one of the
> non-safe cases, but now I see int4div is not marked as leakproof, so we
> couldn't push it to index anyway.
>
> I've however also noticed that all the 'like' procedures are marked as not
> leak proof, which is a bit unfortunate because that's the example from
> Jeff's e-mail that started this thread.

Is there a reason they aren't leak proof?  I don't see that they have
side effects, or that they can throw errors.  What do they leak?

Anyway, I just picked that for convenience.  One of the original
pieces that lead me on this quest had a range inclusion rather than a
LIKE.  I just thought that changing it to a LIKE made the data
generator simpler and easier to reason about, without changing the
fundamental principle.

Cheers,

Jeff


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Amit Kapila]

On Fri, Nov 6, 2015 at 10:28 AM, Kyotaro HORIGUCHI <
horiguchi.kyot...@lab.ntt.co.jp> wrote:
>
> Hello,
>
> At Fri, 6 Nov 2015 09:49:30 +0530, Amit Kapila 
wrote in 
> > Apart from other problems discussed, I think it could also lead to
> > a performance penality for the cases when the qual condition is
> > costly as evaluating such a qual against lot of dead rows would be a
> > time consuming operation.  I am not sure, but I think some of the
> > other well know databases might not have any such problems as
> > they store visibility info inside index due to which they don't need to
> > fetch the heap tuple for evaluating such quals.
>
> I was junst thinking of the same thing. Can we estimate the
> degree of the expected penalty using heap statistics? Of couse
> not so accurate though.
>

I think so. Information related to number of tuples inserted, updated,
hot-updated, deleted and so on is maintained and is shown by
pg_stat_all_tables.  By the way, whats your point here, do you mean to
say that we can estimate approximate penality and then decide whether
quals should be evaluated at index level?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tomas Vondra]

Hi,

On 11/07/2015 02:18 AM, Robert Haas wrote:

On Fri, Nov 6, 2015 at 7:11 PM, Tomas Vondra
 wrote:

I think LEAKPROOF is probably fine for this.  How would the new thing
be different?


I don't think so - AFAIK "leakproof" is about not revealing information
about arguments, nothing more and nothing less. It does not say whether it's
safe to evaluate on indexes, and I don't think we should extend the meaning
in this direction.


That seems like a non-answer answer.


I'm not claiming I have an answer, really. My knowledge of leakproof 
stuff is a bit shallow. Also, I had a few beers earlier today, which 
does not really improve the depth of knowledge on any topic except 
politics and football (aka soccer). So you may be perfectly right.



Clearly, if a function can leak information about it's arguments,
for example by throwing an error, we can't call it on tuples that
might not even be visible, or the behavior of the query might be
change. So any function that is not leakproof is also not safe for
this purpose.

Now that doesn't rule out the possibility that the functions for
which this optimization is safe are a subset of the leakproof
functions - but offhand I don't see why that should be the case. The
index tuple is just a tuple, and the values it contains are just
datums, no more or less than in a heap tuple. There could be a reason
for concern here, but saying that it might not be "safe to evaluate
on indexes" just begs the question: WHY wouldn't that be safe?


Ah. For some reason I thought the "division by zero" example is one of 
the non-safe cases, but now I see int4div is not marked as leakproof, so 
we couldn't push it to index anyway.


I've however also noticed that all the 'like' procedures are marked as 
not leak proof, which is a bit unfortunate because that's the example 
from Jeff's e-mail that started this thread.


regards

--
Tomas Vondra   http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Robert Haas]

On Fri, Nov 6, 2015 at 7:11 PM, Tomas Vondra
 wrote:
>> I think LEAKPROOF is probably fine for this.  How would the new thing
>> be different?
>
> I don't think so - AFAIK "leakproof" is about not revealing information
> about arguments, nothing more and nothing less. It does not say whether it's
> safe to evaluate on indexes, and I don't think we should extend the meaning
> in this direction.

That seems like a non-answer answer.

Clearly, if a function can leak information about it's arguments, for
example by throwing an error, we can't call it on tuples that might
not even be visible, or the behavior of the query might be change.  So
any function that is not leakproof is also not safe for this purpose.

Now that doesn't rule out the possibility that the functions for which
this optimization is safe are a subset of the leakproof functions -
but offhand I don't see why that should be the case.  The index tuple
is just a tuple, and the values it contains are just datums, no more
or less than in a heap tuple.  There could be a reason for concern
here, but saying that it might not be "safe to evaluate on indexes"
just begs the question: WHY wouldn't that be safe?

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tomas Vondra]

Hi,

On 11/05/2015 07:36 PM, Robert Haas wrote:

On Thu, Nov 5, 2015 at 1:29 PM, Tomas Vondra
 wrote:


But then again, can we come up with a way to distinguish operators that are
safe to evaluate on indexes - either automatic or manual? We already do that
with the indexable operators with explicitly listing them in the opclass,
and we also explicitly use the LEAKPROOF for a similar thing. I don't think
extending the opclass is a really good solution, but why not to invent
another *PROOF flag?


I think LEAKPROOF is probably fine for this.  How would the new thing
be different?


I don't think so - AFAIK "leakproof" is about not revealing information 
about arguments, nothing more and nothing less. It does not say whether 
it's safe to evaluate on indexes, and I don't think we should extend the 
meaning in this direction.


I find it perfectly plausible that there will be leakproof functions 
that can't be pushed to indexes, and that would not be possible with a 
single marker. Of course, "leakproof" may be a minimum requirement, but 
another marker is needed to actually enable pushing the function to index.


Of course, we may eventually realize that leakproof really is 
sufficient, and that we can push all leakproof functions to indexes. In 
that case we may deprecate the other marker and just use leakproof. But 
if we go just with leakproof and later find that we really need two 
markers because not all leakproof functions are not index-pushable, 
it'll be much harder to fix because it will cause performance 
regressions for the users (some of the expressions won't be pushed to 
indexes anymore).


But I think the marker is the last thing we need to worry about.

regards

--
Tomas Vondra   http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Kyotaro HORIGUCHI]

Hello,

At Fri, 6 Nov 2015 09:49:30 +0530, Amit Kapila  wrote 
in 
> Apart from other problems discussed, I think it could also lead to
> a performance penality for the cases when the qual condition is
> costly as evaluating such a qual against lot of dead rows would be a
> time consuming operation.  I am not sure, but I think some of the
> other well know databases might not have any such problems as
> they store visibility info inside index due to which they don't need to
> fetch the heap tuple for evaluating such quals.

I was junst thinking of the same thing. Can we estimate the
degree of the expected penalty using heap statistics? Of couse
not so accurate though.

regards,

-- 
Kyotaro Horiguchi
NTT Open Source Software Center



-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Amit Kapila]

On Thu, Nov 5, 2015 at 7:45 AM, Tomas Vondra 
wrote:

> Hi,
>
> On 11/04/2015 11:32 PM, Tom Lane wrote:
>
>> Jeff Janes  writes:
>>
>>> On Wed, Nov 4, 2015 at 7:14 AM, Tom Lane  wrote:
>>>
 You're missing my point: that is possible in an indexscan, but
 *not* in a bitmap indexscan, because the index AM APIs are
 totally different in the two cases. In a bitmap scan, nothing
 more than a TID bitmap is ever returned out to anyplace that
 could execute arbitrary expressions.

>>>
>> I had thought it must already be able to execute arbitrary
>>> expressions, due to the ability to already support user-defined
>>> btree ops (and ops of non-btree types in the case of other index
>>> types).
>>>
>>
>> No. An index AM is only expected to be able to evaluate clauses of
>> the form   , and the
>> key restriction there is that the operator is one that the AM has
>> volunteered to support. Well, actually, it's the opclass more than
>> the AM that determines this, but anyway it's not just some random
>> operator; more than likely, the AM and/or opclass has got special
>> logic about the operator.
>>
>
> Isn't that pretty much exactly the point made by Jeff and Simon, that
> index AM is currently only allowed to handle the indexable operators, i.e.
> operators that it can explicitly optimize (e.g. use to walk the btree and
> such), and completely ignores the other operators despite having all the
> columns in the index. Which means we'll have to do the heap fetch, which
> usually means a significant performance hit.
>
>
>> This also ties into Robert's point about evaluation of operators
>> against index entries for dead or invisible rows. Indexable operators
>> are much less likely than others to have unexpected side-effects.
>>
>
> I certainly understand there are cases that require care - like the
> leakproof thing pointed out by Robert for example. I don't immediately see
> why evaluation against dead rows would be a problem.
>
>
Apart from other problems discussed, I think it could also lead to
a performance penality for the cases when the qual condition is
costly as evaluating such a qual against lot of dead rows would be a
time consuming operation.  I am not sure, but I think some of the
other well know databases might not have any such problems as
they store visibility info inside index due to which they don't need to
fetch the heap tuple for evaluating such quals.



With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Robert Haas]

On Thu, Nov 5, 2015 at 1:29 PM, Tomas Vondra
 wrote:
>> Well, one thing is that you might leak information about
>> already-deleted rows, which could be a security vulnerability, or more
>> mundanely cause a function to error out when there are no actually
>> visible rows that could trigger such an error.  It would be surprising
>> if you could add a CHECK(b != 0) constraint to a table, query it for
>> rows where a/b>1, and get a division by zero error.
>
> Yes, I guess we don't have this problem when evaluating the expression on
> heap because we get to check visibility first, and after moving the
> expression to the index we can't do that.

Right.

> But then again, can we come up with a way to distinguish operators that are
> safe to evaluate on indexes - either automatic or manual? We already do that
> with the indexable operators with explicitly listing them in the opclass,
> and we also explicitly use the LEAKPROOF for a similar thing. I don't think
> extending the opclass is a really good solution, but why not to invent
> another *PROOF flag?

I think LEAKPROOF is probably fine for this.  How would the new thing
be different?

> But that is about heap, and we're discussing indexes here, right? I don't
> think you can break the index descriptor like this, because otherwise we'd
> already have problems with that.

Oh, right.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tomas Vondra]

Hi,

On 11/05/2015 06:51 PM, Robert Haas wrote:

On Wed, Nov 4, 2015 at 9:15 PM, Tomas Vondra
 wrote:

I certainly understand there are cases that require care - like the
leakproof thing pointed out by Robert for example. I don't immediately see
why evaluation against dead rows would be a problem.


Well, one thing is that you might leak information about
already-deleted rows, which could be a security vulnerability, or more
mundanely cause a function to error out when there are no actually
visible rows that could trigger such an error.  It would be surprising
if you could add a CHECK(b != 0) constraint to a table, query it for
rows where a/b>1, and get a division by zero error.


Yes, I guess we don't have this problem when evaluating the expression 
on heap because we get to check visibility first, and after moving the 
expression to the index we can't do that.


But then again, can we come up with a way to distinguish operators that 
are safe to evaluate on indexes - either automatic or manual? We already 
do that with the indexable operators with explicitly listing them in the 
opclass, and we also explicitly use the LEAKPROOF for a similar thing. I 
don't think extending the opclass is a really good solution, but why not 
to invent another *PROOF flag?




But I think it's even worse: I believe there can be dead rows in the
heap whose tuple descriptor doesn't even match the current
pg_attribute contents.  Consider BEGIN; ALTER TABLE ... ADD COLUMN ...
int8; INSERT ...; ROLLBACK; ALTER TABLE .. ADD COLUMN .. text; SELECT
...  If the SELECT tries to decode one of the tuples added by the
failed transaction considering the new column as text when the dead
tuples in question had it as an int8, I suspect that you can crash the
server.  Nothing good will happen, anyway.


But that is about heap, and we're discussing indexes here, right? I 
don't think you can break the index descriptor like this, because 
otherwise we'd already have problems with that.


regards

--
Tomas Vondra  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Robert Haas]

On Wed, Nov 4, 2015 at 9:15 PM, Tomas Vondra
 wrote:
> I certainly understand there are cases that require care - like the
> leakproof thing pointed out by Robert for example. I don't immediately see
> why evaluation against dead rows would be a problem.

Well, one thing is that you might leak information about
already-deleted rows, which could be a security vulnerability, or more
mundanely cause a function to error out when there are no actually
visible rows that could trigger such an error.  It would be surprising
if you could add a CHECK(b != 0) constraint to a table, query it for
rows where a/b>1, and get a division by zero error.

But I think it's even worse: I believe there can be dead rows in the
heap whose tuple descriptor doesn't even match the current
pg_attribute contents.  Consider BEGIN; ALTER TABLE ... ADD COLUMN ...
int8; INSERT ...; ROLLBACK; ALTER TABLE .. ADD COLUMN .. text; SELECT
...  If the SELECT tries to decode one of the tuples added by the
failed transaction considering the new column as text when the dead
tuples in question had it as an int8, I suspect that you can crash the
server.  Nothing good will happen, anyway.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tomas Vondra]

Hi,

On 11/04/2015 11:32 PM, Tom Lane wrote:

Jeff Janes  writes:

On Wed, Nov 4, 2015 at 7:14 AM, Tom Lane  wrote:

You're missing my point: that is possible in an indexscan, but
*not* in a bitmap indexscan, because the index AM APIs are
totally different in the two cases. In a bitmap scan, nothing
more than a TID bitmap is ever returned out to anyplace that
could execute arbitrary expressions.



I had thought it must already be able to execute arbitrary
expressions, due to the ability to already support user-defined
btree ops (and ops of non-btree types in the case of other index
types).


No. An index AM is only expected to be able to evaluate clauses of
the form   , and the
key restriction there is that the operator is one that the AM has
volunteered to support. Well, actually, it's the opclass more than
the AM that determines this, but anyway it's not just some random
operator; more than likely, the AM and/or opclass has got special
logic about the operator.


Isn't that pretty much exactly the point made by Jeff and Simon, that 
index AM is currently only allowed to handle the indexable operators, 
i.e. operators that it can explicitly optimize (e.g. use to walk the 
btree and such), and completely ignores the other operators despite 
having all the columns in the index. Which means we'll have to do the 
heap fetch, which usually means a significant performance hit.




This also ties into Robert's point about evaluation of operators
against index entries for dead or invisible rows. Indexable operators
are much less likely than others to have unexpected side-effects.


I certainly understand there are cases that require care - like the 
leakproof thing pointed out by Robert for example. I don't immediately 
see why evaluation against dead rows would be a problem.


But maybe we can derive a set of rules required from the operators? Say 
only those marked as leakproof when RLS is enabled on the table, and 
perhaps additional things.


A "bruteforce" way would be to extend each index AM with every possible 
operator, but that's not quite manageable I guess. But why couldn't we 
provide a generic infrastructure that would allow filtering "safe" 
expressions and validating them on an index tuple?



kind regards

--
Tomas Vondra  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tom Lane]

Jeff Janes  writes:
> On Wed, Nov 4, 2015 at 7:14 AM, Tom Lane  wrote:
>> You're missing my point: that is possible in an indexscan, but *not* in a
>> bitmap indexscan, because the index AM APIs are totally different in the
>> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
>> returned out to anyplace that could execute arbitrary expressions.

> I had thought it must already be able to execute arbitrary
> expressions, due to the ability to already support user-defined btree
> ops (and ops of non-btree types in the case of other index types).

No.  An index AM is only expected to be able to evaluate clauses of
the form   , and the key
restriction there is that the operator is one that the AM has volunteered
to support.  Well, actually, it's the opclass more than the AM that
determines this, but anyway it's not just some random operator; more than
likely, the AM and/or opclass has got special logic about the operator.

This also ties into Robert's point about evaluation of operators against
index entries for dead or invisible rows.  Indexable operators are much
less likely than others to have unexpected side-effects.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Jeff Janes]

On Wed, Nov 4, 2015 at 7:14 AM, Tom Lane  wrote:
> Simon Riggs  writes:
>> On 4 November 2015 at 15:54, Tom Lane  wrote:
>> We generate this plan
>>  Index Scan using f_x_y_idx on f  (cost=0.42..26075.71 rows=209 width=37)
>>Index Cond: (x = 5)
>>Filter: (y ~~ '%abc%'::text)
>
>> So it should be possible to do the Filter condition on the BitmapIndexScan.
>
> You're missing my point: that is possible in an indexscan, but *not* in a
> bitmap indexscan, because the index AM APIs are totally different in the
> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
> returned out to anyplace that could execute arbitrary expressions.

I had thought it must already be able to execute arbitrary
expressions, due to the ability to already support user-defined btree
ops (and ops of non-btree types in the case of other index types).
Does that only require a restricted execution environment?


> In the case at hand, the planner should have considered a plan of this
> shape as well.  Presumably it concluded it was more expensive than using
> the bitmap approach.  Jeff might try "set enable_bitmapscan = 0" and
> compare the estimated and actual costs.

It is a simplified test case, I can get it to do about anything I want
by tweaking the size, selectivity, columns selected, and cache warmth.

My understanding is that the normal (not index-only) index scan, which
is thought to be slower and actually is slower with a hot cache, also
applies the filter on the heap tuple, not the index tuple.  But since
it only matters much for large queries and large queries tend to
prefer bitmaps, I was less interested in that case.  And bitmaps can
feed into BitmapAnd, which is very helpful in avoiding index-creep
where every query gets a new index tailored for it.  I think we are
missing a trick here that could apply to lots of situations.

Cheers,

Jeff


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Robert Haas]

On Wed, Nov 4, 2015 at 10:59 AM, Tom Lane  wrote:
> Simon Riggs  writes:
>> On 4 November 2015 at 16:14, Tom Lane  wrote:
>>> You're missing my point: that is possible in an indexscan, but *not* in a
>>> bitmap indexscan, because the index AM APIs are totally different in the
>>> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
>>> returned out to anyplace that could execute arbitrary expressions.
>
>> Still misunderstanding each other... sorry about that
>
>> If a btree can Filter y like that on an IndexScan, then it can also apply
>> that Filter on y when it is looking through rows before it adds them to the
>> bitmap.
>
> btree applies no such filter in either case.  "Filter" conditions are
> applied outside the index AM --- and yes, I will resist any proposal to
> relocate that responsibility.

I don't understand what you're arguing against here - as Simon I think
correctly points out, there seems to be a substantial performance
improvement possible here.  It's not so much that we would apply the
Filter conditions outside the index AM as that we would have two kinds
of Index Quals that could be enforced by the index AM.  Some quals
(such as x = 5) could be enforced by scanning only the relevant
portion of the index, while others (such as y like '%abc%') don't
abridge the portion of the index that needs to be scanned, but could
disqualify some index tuples before we go to the trouble of hitting
the heap.

The problem I see is this might involve testing quals against an index
tuple when the corresponding heap tuple isn't visible.  This probably
isn't safe except for leakproof quals, and there might be some other
problems as well.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Simon Riggs]

On 4 November 2015 at 16:59, Tom Lane  wrote:

> Simon Riggs  writes:
> > On 4 November 2015 at 16:14, Tom Lane  wrote:
> >> You're missing my point: that is possible in an indexscan, but *not* in
> a
> >> bitmap indexscan, because the index AM APIs are totally different in the
> >> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
> >> returned out to anyplace that could execute arbitrary expressions.
>
> > Still misunderstanding each other... sorry about that
>
> > If a btree can Filter y like that on an IndexScan, then it can also apply
> > that Filter on y when it is looking through rows before it adds them to
> the
> > bitmap.
>
> btree applies no such filter in either case.  "Filter" conditions are
> applied outside the index AM --- and yes, I will resist any proposal to
> relocate that responsibility.
>

I don't think anyone has argued that point, yet, we just don't have enough
info to agree yet.

As Jeff said in his OP, "Is there a fundamental reason the filter on y is
not being applied to
the index scan, rather than the heap scan?", which still stands.

Why would you resist? And/Or Why is that important?

-- 
Simon Riggshttp://www.2ndQuadrant.com/

PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tom Lane]

Simon Riggs  writes:
> On 4 November 2015 at 16:14, Tom Lane  wrote:
>> You're missing my point: that is possible in an indexscan, but *not* in a
>> bitmap indexscan, because the index AM APIs are totally different in the
>> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
>> returned out to anyplace that could execute arbitrary expressions.

> Still misunderstanding each other... sorry about that

> If a btree can Filter y like that on an IndexScan, then it can also apply
> that Filter on y when it is looking through rows before it adds them to the
> bitmap.

btree applies no such filter in either case.  "Filter" conditions are
applied outside the index AM --- and yes, I will resist any proposal to
relocate that responsibility.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Simon Riggs]

On 4 November 2015 at 16:14, Tom Lane  wrote:

> Simon Riggs  writes:
> > On 4 November 2015 at 15:54, Tom Lane  wrote:
> > We generate this plan
> >  Index Scan using f_x_y_idx on f  (cost=0.42..26075.71 rows=209 width=37)
> >Index Cond: (x = 5)
> >Filter: (y ~~ '%abc%'::text)
>
> > So it should be possible to do the Filter condition on the
> BitmapIndexScan.
>
> You're missing my point: that is possible in an indexscan, but *not* in a
> bitmap indexscan, because the index AM APIs are totally different in the
> two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
> returned out to anyplace that could execute arbitrary expressions.
>

Still misunderstanding each other... sorry about that

If a btree can Filter y like that on an IndexScan, then it can also apply
that Filter on y when it is looking through rows before it adds them to the
bitmap.

I completely understand that it cannot return the value (of y) via the
bitmap.

We should be able to get a plan like this

explain select * from f where x=5 and y like '%abc%';

  QUERY PLAN

--
 Bitmap Heap Scan on f  (cost=382.67..9314.72 rows=1 width=37)
   ->  Bitmap Index Scan on f_x_y_idx  (cost=0.00..382.67 rows=10433
width=0)
 Index Cond: (x = 5)
>>  Filter: (y ~~ '%abc%'::text)

if the bitmap stays non-lossy.

I see that plannodes.h says
"In a BitmapIndexScan plan node, the targetlist and qual fields are not
used and are always NIL. "
but it doesn't say why.

Why can't the BitmapIndexScan execute arbitrary expressions? (or What did
you mean by that phrase?)

-- 
Simon Riggshttp://www.2ndQuadrant.com/

PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tom Lane]

Simon Riggs  writes:
> On 4 November 2015 at 15:54, Tom Lane  wrote:
> We generate this plan
>  Index Scan using f_x_y_idx on f  (cost=0.42..26075.71 rows=209 width=37)
>Index Cond: (x = 5)
>Filter: (y ~~ '%abc%'::text)

> So it should be possible to do the Filter condition on the BitmapIndexScan.

You're missing my point: that is possible in an indexscan, but *not* in a
bitmap indexscan, because the index AM APIs are totally different in the
two cases.  In a bitmap scan, nothing more than a TID bitmap is ever
returned out to anyplace that could execute arbitrary expressions.

In the case at hand, the planner should have considered a plan of this
shape as well.  Presumably it concluded it was more expensive than using
the bitmap approach.  Jeff might try "set enable_bitmapscan = 0" and
compare the estimated and actual costs.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Simon Riggs]

On 4 November 2015 at 15:54, Tom Lane  wrote:

> Nicolas Barbier  writes:
> > 2015-11-04 Antonin Houska :
> >> (see expand_indexqual_opclause()), I'm not sure any kind of expansion is
> >> possible for '%abc%' which would result in a b-tree searchable
> condition.
>
> > I think the question is not about using the b-tree for checking the
> > condition, but about just retrieving the value for y from the index,
> > and just using that to check the condition before fetching the
> > corresponding tuple from the heap.
>
> Bitmap index scans only return TID bitmaps, not index tuples; indeed
> the underlying index may not store anything recognizable as tuples.
>

Agreed, though the OP's question was asking why a Filter condition can't be
added to a BitmapIndexScan, so that non-qualifying rows can be excluded
from the TID bitmap it generates.

We generate this plan

postgres=# explain select * from f where x=5 and y like '%abc%';

QUERY PLAN

--

 Index Scan using f_x_y_idx on f  (cost=0.42..26075.71 rows=209 width=37)
   Index Cond: (x = 5)
   Filter: (y ~~ '%abc%'::text)

So it should be possible to do the Filter condition on the BitmapIndexScan.

-- 
Simon Riggshttp://www.2ndQuadrant.com/

PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Tom Lane]

Nicolas Barbier  writes:
> 2015-11-04 Antonin Houska :
>> (see expand_indexqual_opclause()), I'm not sure any kind of expansion is
>> possible for '%abc%' which would result in a b-tree searchable condition.

> I think the question is not about using the b-tree for checking the
> condition, but about just retrieving the value for y from the index,
> and just using that to check the condition before fetching the
> corresponding tuple from the heap.

Bitmap index scans only return TID bitmaps, not index tuples; indeed
the underlying index may not store anything recognizable as tuples.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Nicolas Barbier]

2015-11-04 Antonin Houska :

> While prefix expression
>
> y like 'abc%'
>
> can be converted to
>
> y >= 'abc'
>
> (see expand_indexqual_opclause()), I'm not sure any kind of expansion is
> possible for '%abc%' which would result in a b-tree searchable condition.

I think the question is not about using the b-tree for checking the
condition, but about just retrieving the value for y from the index,
and just using that to check the condition before fetching the
corresponding tuple from the heap.

Nicolas

-- 
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index scans use of filters on available columns

[Antonin Houska]

While prefix expression

y like 'abc%'

can be converted to

y >= 'abc'

(see expand_indexqual_opclause()), I'm not sure any kind of expansion is
possible for '%abc%' which would result in a b-tree searchable condition.

Jeff Janes  wrote:

> Is there a fundamental reason the filter on y is not being applied to
> the index scan, rather than the heap scan?

-- 
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] Bitmap index scans use of filters on available columns

[Jeff Janes]

create table f as select (random()*100)::int as x, md5(random()::text)
as y from generate_series(1,100);

create index on f (x, y);
analyze verbose f; --dont vacuum

explain select * from f where x=5 and y like '%abc%';

  QUERY PLAN
--
 Bitmap Heap Scan on f  (cost=382.67..9314.72 rows=1 width=37)
   Recheck Cond: (x = 5)
   Filter: (y ~~ '%abc%'::text)
   ->  Bitmap Index Scan on f_x_y_idx  (cost=0.00..382.67 rows=10433 width=0)
 Index Cond: (x = 5)

Is there a fundamental reason the filter on y is not being applied to
the index scan, rather than the heap scan?  Should this be a to-do
item?  This could avoid a lot of heap block reads, and also might
prevent the bitmap from overflowing work_mem and turning lossy.

Cheers,

Jeff


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] bitmap-index-scan faster than seq-scan on full-table-scan (gin index)

[Jesper Krogh]

On 2010-05-31 22:09, Tom Lane wrote:

Jesper Krogh  writes:
   

Conceptually searching for the "full dataset" would always be fastest
solved by a seq-scan. The query planner enforces this so much, so not
even "enable_seqscan=off" can convince it to to something else.
...
Would it be possible to implement the "Filtering" using the gin-index and
a subsequent visibillity-check as on the index-scan?
 

You're failing to make any sense whatsoever.  If you're reading the full
dataset, there is no filter condition.  If there is a potentially
indexable filter condition, the planner will certainly consider that.
   

Yes, you're totally right on that (about making sense).

But that is because of the "simplified" use-case described. A more elaborate
description ..
I have a table with has a set of colums attached to it typically
used for "sorting" these columns may also be inferred on the table
by a typical join condition and a document that is fts-indexed.
So the actual use-case is that people query for:

"give me the 1000 most recent documents matching "

Term may in some cases be hugely trivial, only filtering away 0.001% of the
dataset resulting in a "index-scan on a btree date index" filtering on the
tsvector column for ".

Term may also be something really specific only returning a single
or a few documents and just pushing a post-sorting to get the ordering.

But in the case where the query-planner falls over to a "index-scan"
on one of the btree-indices it ends up reading over from the TOAST data.

Will the planner consider doing the index-scan(forward or backwards)
on a btree-index and filter using a gin-index instead of filtering directly
on the tuple-data?
(I haven't been able to enforce an query-plan that looks like that).


Personally I think the issue here has got more to do with the
non-immutability of the single-argument form of to_tsquery, which means
it gets re-evaluated at every row during a seqscan.  Do your results
change if you work with to_tsquery('english', ...)  (or whatever your
default TS config is)?
   


It is english..  and yes it did indeed change the results. So the 
expensive case

dropped from ~60s to ~28s and the cheap case from ~7.3s to ~4.3s, that
is quite surprising that such "small" change can have that huge impact. The
single-argument version should be forbidden.

But the performance ratio between the two cases is still the same.

The test was actually run with the preliminary gincostestimate-patch from
Oleg Bartunov so the actual cost estimates match way better now, but that
should not impact the actual runtime.

Thanks

--
Jesper

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] bitmap-index-scan faster than seq-scan on full-table-scan (gin index)

[Tom Lane]

Jesper Krogh  writes:
> Conceptually searching for the "full dataset" would always be fastest
> solved by a seq-scan. The query planner enforces this so much, so not
> even "enable_seqscan=off" can convince it to to something else.
> ...
> Would it be possible to implement the "Filtering" using the gin-index and
> a subsequent visibillity-check as on the index-scan?

You're failing to make any sense whatsoever.  If you're reading the full
dataset, there is no filter condition.  If there is a potentially
indexable filter condition, the planner will certainly consider that.

Personally I think the issue here has got more to do with the
non-immutability of the single-argument form of to_tsquery, which means
it gets re-evaluated at every row during a seqscan.  Do your results
change if you work with to_tsquery('english', ...)  (or whatever your
default TS config is)?

regards, tom lane

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] bitmap-index-scan faster than seq-scan on full-table-scan (gin index)

[Jesper Krogh]

Hi.

The test data a set of generated terms using this perl-script
http://shrek.krogh.cc/~jesper/build-test.pl
and http://shrek.krogh.cc/~jesper/words.txt

I have generated a test dataset with an average tsvector length of
around 250 and 200.000 tuples in the dataset.

Conceptually searching for the "full dataset" would always be fastest
solved by a seq-scan. The query planner enforces this so much, so not
even "enable_seqscan=off" can convince it to to something else. So in
the next two explain analyze I compare a query searching 99% of the
table up with a seqscan. The 98% case is enforced to be a 
"bitmap-index-scan"
I would expect the runtime of the seqscan to be shortest and the 
bitmap-index-scan
to be quite a lot larger, due to "random access" and the fact that the 
index-data

also needs to be read in from disk.

Bot runs are run with a freshly started postgresql backend and
"echo 3 > /proc/sys/vm/drop_caches" so the os caching should not come 
into play.


ftstest=# EXPLAIN ANALYZE select id from ftstest where body_fts @@ 
to_tsquery('commonterm98');
 QUERY 
PLAN


 Bitmap Heap Scan on ftstest  (cost=6579.81..992733.57 rows=195976 
width=4) (actual time=4813.258..7081.277 rows=195976 loops=1)

   Recheck Cond: (body_fts @@ to_tsquery('commonterm98'::text))
   ->  Bitmap Index Scan on ftstest_gist_idx  (cost=0.00..6530.82 
rows=195976 width=0) (actual time=4787.513..4787.513 rows=195976 loops=1)

 Index Cond: (body_fts @@ to_tsquery('commonterm98'::text))
 Total runtime: 7389.346 ms
(5 rows)

ftstest=# set enable_bitmapscan = off;
WARNING:  terminating connection because of crash of another server process
DETAIL:  The postmaster has commanded this server process to roll back 
the current transaction and exit, because another server process exited 
abnormally and possibly corrupted shared memory.
HINT:  In a moment you should be able to reconnect to the database and 
repeat your command.

server closed the connection unexpectedly
This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Succeeded.
ftstest=# set enable_bitmapscan = off;
SET
ftstest=# EXPLAIN ANALYZE select id from ftstest where body_fts @@ 
to_tsquery('commonterm98');

  QUERY PLAN
--
 Seq Scan on ftstest  (cost=0.00..1006314.00 rows=195976 width=4) 
(actual time=96.077..60092.080 rows=195976 loops=1)

   Filter: (body_fts @@ to_tsquery('commonterm98'::text))
 Total runtime: 60436.556 ms
(3 rows)

So searching the full table via a bitmap-index-scan is actually 9 times
cheaper than a seq-scan.  (same on 9.0b1 and 8.4).

Digging more into it reveals that the body_fts tsvector is indeed needed for
the "filter" in the SeqScan. The tsvector data is stored in a TOAST 
table and

the in the bitmap-index-scan case it only needs to read in the main table
for checking visibillity. In the end it translates to reading in 1.4GB of
TOAST-data vs. reading in 34MB of table data.

Thinking a bit, then I dont think this is a particular rare case, 
allthough the
ratio between the tables may be a real cornercase. The ratio is not 1:33 
in the
dataset that looks like the production dataset, but more 1:10, but in 
all cases
in "production" there would be a much higher cache-hit ratio on the 
gin-index
and the main table pages than on the TOAST table, so even with a ratio 
of 1:1

there most likely would be a real-world benefit.

Would it be possible to implement the "Filtering" using the gin-index and
a subsequent visibillity-check as on the index-scan?

The same end up being the case for queries ordered by btree indexes and
"filtered" by gin-indexes.

Jesper
--
Jesper

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index - first look

[Gianni Ciolli]

On Fri, Nov 07, 2008 at 03:56:25PM +0300, Teodor Sigaev wrote:
> After looking at additional heap and b-tree index placed in 
> pg_bitmapindex namespace...
>
> Additional heap contains unique values and page's number with offset 
> number in bitmap index, b-tree index contains tuples with the same values 
> and ItemPointer to heap's row. So, heap is an unnecessary step - b-tree 
> index should store ItemPointer to the bitmap index directly.

Hi Teodor,

B-tree points to LOVItem (heap's row) because the LOVItem contains
some vector metadata, plus the last two words of the actual bitmap
vector, last_compword and last_word; they are stored there because
they will be changing in most cases.

Let me explain with an example; let BM_WORD_SIZE be 2, so that we have
16 bits per word.

Suppose that the size of vector is N, with k = N % 16 > 0, that is, up
to now max(tidnum) == N.

Then if we (non-HOT) update a row, or if we insert a row, then that
row will have tidnum = N' > N, so that the corresponding vector will
need to be "enlarged" by N'-N bits.

In the case

N' % 16 == N % 16

then we will have to update the last word, which will be locate in the
LOVItem in last_word, without scanning BMV pages.

Another case which is dealt at LOVItem level is when

N' % 16 > N % 16
and 
last_compword is compressed
and
last_word can merge with last_compword in a single word

(e.g. if last_compword is the compressed word representing M 1's, and
if last_word is a word of 1's, then they will merge in the single
compressed word representing M+1 1's).

I agree that this is more complicated than the abstract model of
bitmap indexes; we kept this design, which came from the author of the
previous version of the patch, because it seems likely to be an useful
optimization.

Thank you for your comments (also for the useful remarks on the
catalog);

best regards,
Dr. Gianni Ciolli - 2ndQuadrant Italia
PostgreSQL Training, Services and Support
[EMAIL PROTECTED] | www.2ndquadrant.it


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index - first look

[Teodor Sigaev]

Additional heap contains unique values and page's number with offset 
number in bitmap index, b-tree index contains tuples with the same values 
and ItemPointer to heap's row. So, heap is an unnecessary step - b-tree 
index should store ItemPointer to the bitmap index directly.

B-tree points to LOVItem (heap's row) because the LOVItem contains
some vector metadata, plus the last two words of the actual bitmap
vector, last_compword and last_word; they are stored there because
they will be changing in most cases.



I'm talking about pg_bitmapindex.pg_bm_OID tables - they contain distinct values 
from indexed table and pair of (blockNumber, offsetNumber), which is exactly 
ItemPointerData. I suppose, that pair points somewhere in bitmap index. In other 
hand, tuple of index 'pg_bitmapindex.pg_bm_OID_idx' contains the same distinct 
values and ItemPointer pointed to row in corresponding pg_bitmapindex.pg_bm_OID 
table.


Why doesn't ItemPointer in pg_bitmapindex.pg_bm_OID_idx point into bitmap index 
file?


Actually, you don't need a pg_bitmapindex.pg_bm_OID tables at all - the same 
data could be stored in pg_bitmapindex.pg_bm_OID_idx itself. But this is not a 
strong objection, just an a optimization.


BTW, see comments near index_getnext():
 * Note: caller must check scan->xs_recheck, and perform rechecking of the
 * scan keys if required.  We do not do that here because we don't have
 * enough information to do it efficiently in the general case.

Although it's not true for b-tree now, but it may change.



--
Teodor Sigaev   E-mail: [EMAIL PROTECTED]
   WWW: http://www.sigaev.ru/

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index - first look

[Vladimir Sitnikov]

Could you please put more comments on the index build procedure?

I guess it strongly relies on the fact the block number increases as tuples
are returned from "heap scan", doesn't it? However, thanks to synchronized
scans the order of tuples could be a little bit different.

I found no evidence of  "build index" being able to add tid # 10 after it
has created the bitmap for tids 1000...2000. As far as I understand it never
tries to update words that were written during index creation.

That particular  "if (_blockno != buf->hot_buffer_block) {"  in
buf_add_tid_with_fill looks to be a wrong thing for me -- I believe it is a
way to often (it will try to sync the buffer after each 300/8=~40 bytes
since there are no more than 300 tuples on a single page)
I would not flush the bitmap every data block, but I would keep "hot buffer"
as a temporary view (uncompressed) of the bitmap being build. So as tuples
come, we either set the bit directry in the "hot buffer" (if it covers the
relevant tid range) or flush that view to the bitmap (merging, and splitting
the bitmap where it is required) and repoint the window so it starts with
block of tid that triggered flushing. Does that make sense?


Regards,
Vladimir Sitnikov

Re: [HACKERS] Bitmap index - first look

[Teodor Sigaev]

After looking at additional heap and b-tree index placed in pg_bitmapindex 
namespace...


Additional heap contains unique values and page's number with offset number in 
bitmap index, b-tree index contains tuples with the same values and ItemPointer 
to heap's row. So, heap is an unnecessary step - b-tree index should store 
ItemPointer to the bitmap index directly.


--
Teodor Sigaev   E-mail: [EMAIL PROTECTED]
   WWW: http://www.sigaev.ru/

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index - first look

[Vladimir Sitnikov]

One more point on pg_am:  amsearchnull is equal to "f"  however the index
stores and could find nulls perfectly.

Regards,
Vladimir Sitnikov

[HACKERS] Bitmap index - first look

[Teodor Sigaev]

http://archives.postgresql.org/message-id/[EMAIL PROTECTED]

1) Sometimes index doesn't find all matching rows:
postgres=# SELECT * FROM qq WHERE t ='asd';
 i |  t
---+-
 2 | asd
 1 | asd
 2 | asd
(3 rows)
postgres=# SET enable_seqscan=off;
SET
postgres=# SELECT * FROM qq WHERE t ='asd';
 i |  t
---+-
 2 | asd
(1 row)

How to reproduce:
DROP TABLE IF EXISTS qq;
CREATE TABLE qq ( i int, t text );
INSERT INTO qq VALUES (1, 'qwe');
INSERT INTO qq VALUES (2, 'asd');
CREATE INDEX qqidx ON qq USING bitmap (i,t);
INSERT INTO qq VALUES (1, 'asd');
INSERT INTO qq VALUES (2, 'asd');
SELECT * FROM qq;
SELECT * FROM qq WHERE t ='asd';
SET enable_seqscan=off;
SELECT * FROM qq WHERE t ='asd';

2) Why is pg_am.amstrategies set to 5 while index supports only equal operation?

3) Typo in bmbulkdelete:
/* allocate stats if first time through, else re-use existing struct */
if (result == NULL)
  result = (IndexBulkDeleteResult *)
  palloc0(sizeof(IndexBulkDeleteResult));

result = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));

'result' is allocated twice.

4) Bitmap index is marked with pg_am.amcanorder = 'f', so you don't need to 
support ammarkpos/amrestrpos - see

http://archives.postgresql.org/pgsql-hackers/2008-10/msg00862.php




--
Teodor Sigaev   E-mail: [EMAIL PROTECTED]
   WWW: http://www.sigaev.ru/

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Bitmap index thoughts (another segfault)

[Gavin Sherry]

On Sat, 7 Apr 2007, Mark Kirkwood wrote:

> Mark Kirkwood wrote:
> bitmap=# SELECT count(*) FROM bitmaptest
> WHERE val1 in (1,7)
> AND val0 IN (4,3)
> ;
>
> ERROR:  XX000: unknown stream type 2
> LOCATION:  stream_add_node, tidbitmap.c:1033

Thanks. Turned out to be a typo in stream_add_node()! I'll post a new
patch soon. Thanks for the test kit and your testing!

Gavin

---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index thoughts (another segfault)

[Gavin Sherry]

> I'm seeing a segfault on a size TPC-H size 10 database. The patch and
> code are:
> - bitmap patch from 12 Mar
> - 8.3 dev from 27 Mar

Thanks Mark. I tracked this down. I'll post a new patch soon.

Gavin

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

Re: [HACKERS] Bitmap index thoughts (another segfault)

[Mark Kirkwood]

Mark Kirkwood wrote:
I'm seeing a segfault on a size TPC-H size 10 database. The patch and 
code are:

- bitmap patch from 12 Mar
- 8.3 dev from 27 Mar


SELECT count(distinct(o_orderkey))
FROM orders orders_alias
WHERE o_orderpriority IN ('1-URGENT', '3-MEDIUM') AND o_orderstatus='P';

(gdb) bt
#0  0x in ?? ()
#1  0x08155eb5 in bitmap_stream_free (opaque=0x84e4070) at tidbitmap.c:1336
#2  0x08142914 in ExecEndBitmapHeapScan (node=0x8405548)
at nodeBitmapHeapscan.c:463
#3  0x0813789a in ExecutorEnd (queryDesc=0x83ed948) at execMain.c:992
#4  0x081134ef in PortalCleanup (portal=0x83ee018) at portalcmds.c:302
#5  0x0823e2d2 in PortalDrop (portal=0x83ee018, isTopCommit=0 '\0')
at portalmem.c:382
#6  0x081b2182 in exec_simple_query (
query_string=0x83a8018 "SELECT count(distinct(o_orderkey))\nFROM 
orders orders_alias\nWHERE o_orderpriority IN ('1-URGENT', '3-MEDIUM') 
AND o_orderstatus='P';") at postgres.c:964

#7  0x081b4350 in PostgresMain (argc=4, argv=0x833a638,
username=0x833a610 "postgres") at postgres.c:3488
#8  0x0818faab in ServerLoop () at postmaster.c:2985
#9  0x081911b1 in PostmasterMain (argc=1, argv=0xbfbfec30) at 
postmaster.c:967

#10 0x08153592 in main (argc=1, argv=0xbfbfec30) at main.c:188



Not a SIGSEGV but another stream related issue:

bitmap=# \d bitmaptest;
  Table "public.bitmaptest"
 Column |  Type   | Modifiers
+-+---
 id | integer | not null
 val0   | integer |
 val1   | integer |
 val2   | integer |
 fil| text|
Indexes:
"bitmaptest_id" btree (id)
"bitmaptest_val0" bitmap (val0)
"bitmaptest_val1" bitmap (val1)
"bitmaptest_val2" bitmap (val2)
bitmap=# SELECT count(*) FROM bitmaptest
   WHERE val1 in (1,7)
   AND val0 IN (4,3)
   ;

ERROR:  XX000: unknown stream type 2
LOCATION:  stream_add_node, tidbitmap.c:1033

I could not reproduce this with the TPC-H dataset, so here's a link to 
the files to generate this one:

http://homepages.paradise.net.nz/markir/download/bizgres/bitmaptest.tar.gz

Cheers

Mark

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
  choose an index scan if your joining column's datatypes do not
  match

Re: [HACKERS] Bitmap index thoughts (another segfault)

[Mark Kirkwood]

I'm seeing a segfault on a size TPC-H size 10 database. The patch and 
code are:

- bitmap patch from 12 Mar
- 8.3 dev from 27 Mar


SELECT count(distinct(o_orderkey))
FROM orders orders_alias
WHERE o_orderpriority IN ('1-URGENT', '3-MEDIUM') AND o_orderstatus='P';

(gdb) bt
#0  0x in ?? ()
#1  0x08155eb5 in bitmap_stream_free (opaque=0x84e4070) at tidbitmap.c:1336
#2  0x08142914 in ExecEndBitmapHeapScan (node=0x8405548)
at nodeBitmapHeapscan.c:463
#3  0x0813789a in ExecutorEnd (queryDesc=0x83ed948) at execMain.c:992
#4  0x081134ef in PortalCleanup (portal=0x83ee018) at portalcmds.c:302
#5  0x0823e2d2 in PortalDrop (portal=0x83ee018, isTopCommit=0 '\0')
at portalmem.c:382
#6  0x081b2182 in exec_simple_query (
query_string=0x83a8018 "SELECT count(distinct(o_orderkey))\nFROM 
orders orders_alias\nWHERE o_orderpriority IN ('1-URGENT', '3-MEDIUM') 
AND o_orderstatus='P';") at postgres.c:964

#7  0x081b4350 in PostgresMain (argc=4, argv=0x833a638,
username=0x833a610 "postgres") at postgres.c:3488
#8  0x0818faab in ServerLoop () at postmaster.c:2985
#9  0x081911b1 in PostmasterMain (argc=1, argv=0xbfbfec30) at 
postmaster.c:967

#10 0x08153592 in main (argc=1, argv=0xbfbfec30) at main.c:188



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

Re: [HACKERS] Bitmap index stuff

[Gavin Sherry]

On Mon, 26 Feb 2007, Heikki Linnakangas wrote:

> Hi,
>
> How are you doing with the bitmap indexes?

I need to send of a patch fixing the last bug you pointed out. The code
needs a merge of HEAD.

>
> I've been trying to get my head around the patch a couple of times to
> add the vacuum support, but no matter how simple I try to keep it, I
> just always seem to get stuck.
>
> It looks like vacuum support would need:
>
> - something similar to read_words, let's call it iterate_set_bits, that
> returns each set bit from a bitmap vector, keeping the buffer locked
> over calls.
> - ability to clear the bit returned by iterate_set_bits. If normal index
> scans also used this, the same functions could be used to support the
> kill_prior_tuple thingie.

Okay.

>
> The above also needs to be able to recompress a page if it gets
> fragmented by repeated setting and clearing of bits.

Yes.

> I still feel that the data structures are unnecessarily complex. In
> particular, I'd like to get rid of the special-cased last_word and
> last_comp_word in the lov item. Perhaps we could instead embed a normal,
> but smaller, BMBitmapData structure in the lov item, and just add a
> length field to that?

I'm not sure that this really simplifies the code. I agree things could be
simpler though.

>
> You have a lot of code to support efficient building of a bitmap index.
> I know you've worked hard on that, but do we really need all that? How
> did the bitmap build work in the previous versions of the patch, and how
> much faster is the current approach?

I included details on a previous email, I thought. Basically, in cases
where the data is distributed as follows:

1 1 1 1 1 1 1  2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 ...

We're very fast in both versions. If the data is distributed as:

1 2 3 4 5 6  1 2 3 4 5 6

In the original version(s), we were terribly slow (in my test, 7 times
slower than btree). Considering the kind of data sets bitmap suits, this
made bitmap unusable. With the rewrite, we're much faster (in my test,
faster than btree).

The test case was: a table with 600M rows with 100,000 distinct keys to be
indexed.

> BTW: It occured to me that since we're piggybacking on b-tree's strategy
> numbers, comparison operators etc, conceivably we could also use any
> other indexam. For example, a bitmap GiST would be pretty funky. We'll
> probably leave that for future versions, but have you given that any
> thought?

True. I haven't given it any thought though. Interesting... I'd have to
think of some interesting data sets which would suit the capabilities
(operators) we have with GiST.

Thanks,

Gavin

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

[HACKERS] Bitmap index stuff

[Heikki Linnakangas]

Hi,

How are you doing with the bitmap indexes?

I've been trying to get my head around the patch a couple of times to 
add the vacuum support, but no matter how simple I try to keep it, I 
just always seem to get stuck.


It looks like vacuum support would need:

- something similar to read_words, let's call it iterate_set_bits, that 
returns each set bit from a bitmap vector, keeping the buffer locked 
over calls.
- ability to clear the bit returned by iterate_set_bits. If normal index 
scans also used this, the same functions could be used to support the 
kill_prior_tuple thingie.


The above also needs to be able to recompress a page if it gets 
fragmented by repeated setting and clearing of bits.


I still feel that the data structures are unnecessarily complex. In 
particular, I'd like to get rid of the special-cased last_word and 
last_comp_word in the lov item. Perhaps we could instead embed a normal, 
but smaller, BMBitmapData structure in the lov item, and just add a 
length field to that?


You have a lot of code to support efficient building of a bitmap index. 
I know you've worked hard on that, but do we really need all that? How 
did the bitmap build work in the previous versions of the patch, and how 
much faster is the current approach?


BTW: It occured to me that since we're piggybacking on b-tree's strategy 
numbers, comparison operators etc, conceivably we could also use any 
other indexam. For example, a bitmap GiST would be pretty funky. We'll 
probably leave that for future versions, but have you given that any 
thought?


--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

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

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

On Thu, 8 Feb 2007, Heikki Linnakangas wrote:

> Gavin Sherry wrote:
> > I will update the code tomorrow. The focus will be cleaning up the
> > executor modifications. Please look else where for now.
>
> I'm getting a segfault with this test script:
>
> 
> CREATE TABLE bmtest (i int);
>
> INSERT INTO bmtest SELECT 1 FROM generate_series(1,10) a;
> INSERT INTO bmtest SELECT 10 FROM generate_series(1,100) a;
> DELETE FROM bmtest WHERE i = 1;
> VACUUM bmtest;
>
> CREATE INDEX i_bmtest ON bmtest USING bitmap (i);
>
> INSERT INTO bmtest SELECT 10 FROM generate_series(1,10) a;
> 
>

Hmm... this triggers a bug in the newly rewritten update code I think.
I'll post a fix soon.

Thanks for testing!

Gavin

---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

Gavin Sherry wrote:

I will update the code tomorrow. The focus will be cleaning up the
executor modifications. Please look else where for now.


I'm getting a segfault with this test script:


CREATE TABLE bmtest (i int);

INSERT INTO bmtest SELECT 1 FROM generate_series(1,10) a;
INSERT INTO bmtest SELECT 10 FROM generate_series(1,100) a;
DELETE FROM bmtest WHERE i = 1;
VACUUM bmtest;

CREATE INDEX i_bmtest ON bmtest USING bitmap (i);

INSERT INTO bmtest SELECT 10 FROM generate_series(1,10) a;



--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 5: don't forget to increase your free space map settings

Re: [HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

Gavin Sherry wrote:

On Thu, 1 Feb 2007, Bruce Momjian wrote:


Where are we on this patch?  Does it have performance tests to show
where it is beneificial?  Is it ready to be reviewed?


Here's an updated patch:

http://www.alcove.com.au/~swm/bitmap-2007-02-02.patch

In this patch, I rewrote the index build system. It was fast before for
well clustered data but for poorly clustered data, it was very slow. Now,
it is pretty good for each distribution type.

I have various test cases but the one which showed bitmap a poor light was
a table of 600M rows. The key to the table had a cardinality of 100,000.
When the table was loaded with keys clustered, the build time was 1000
seconds with bitmap (2200 with btree). With poorly clustered data (e.g.,
the index key was (1, 2, 3, ..., 6000, 1, 2, 3, ...)), the build time for
bitmap was 14000 seconds!

So, I rewrote this to compress data using HRL encoding (the same scheme we
use in the bitmap AM itself). Now, clustered data is just as fast and
unclustered data is 2000 seconds.

The select performance at a cardinality of 100,000 is similar to btree but
faster with lower cardinalities.

Jie also contributed a rewrite of the WAL code to this patch. Not only is
the code faster now, but it handles the notion of incomplete actions --
like btree and friends do. The executor code still needs some work from me
-- Jie and I have dirtied things up while experimenting -- but we would
really like some review of the code so that this can get squared away
well before the approach of 8.3 feature freeze.

One of the major deficiencies remaining is the lack of VACUUM support.
Heikki put his hand up for this and I'm holding him to it! ;-)


Thanks :). I'll take a look at it.

I'm a bit worried that vacuuming can get complicated if an index is in 
fact an index + a heap + a btree. To remove empty lov items and the 
entries in the auxiliary heap and b-tree, you need to:


1. Memorize empty lov-items
2. Scan the heap, and mark the heap tuples corresponding the empty 
lov-items as dead

3. Scan the b-tree, removing pointers to dead heap tuples
4. Remove dead heap tuples
5. Remove empty lov-items

Maybe it's possible to call the existing vacuuming code recursively, but 
it feels quite horrible.


--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
  choose an index scan if your joining column's datatypes do not
  match

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

On Thu, 1 Feb 2007, Bruce Momjian wrote:

>
> Where are we on this patch?  Does it have performance tests to show
> where it is beneificial?  Is it ready to be reviewed?

Here's an updated patch:

http://www.alcove.com.au/~swm/bitmap-2007-02-02.patch

In this patch, I rewrote the index build system. It was fast before for
well clustered data but for poorly clustered data, it was very slow. Now,
it is pretty good for each distribution type.

I have various test cases but the one which showed bitmap a poor light was
a table of 600M rows. The key to the table had a cardinality of 100,000.
When the table was loaded with keys clustered, the build time was 1000
seconds with bitmap (2200 with btree). With poorly clustered data (e.g.,
the index key was (1, 2, 3, ..., 6000, 1, 2, 3, ...)), the build time for
bitmap was 14000 seconds!

So, I rewrote this to compress data using HRL encoding (the same scheme we
use in the bitmap AM itself). Now, clustered data is just as fast and
unclustered data is 2000 seconds.

The select performance at a cardinality of 100,000 is similar to btree but
faster with lower cardinalities.

Jie also contributed a rewrite of the WAL code to this patch. Not only is
the code faster now, but it handles the notion of incomplete actions --
like btree and friends do. The executor code still needs some work from me
-- Jie and I have dirtied things up while experimenting -- but we would
really like some review of the code so that this can get squared away
well before the approach of 8.3 feature freeze.

One of the major deficiencies remaining is the lack of VACUUM support.
Heikki put his hand up for this and I'm holding him to it! ;-)

I will update the code tomorrow. The focus will be cleaning up the
executor modifications. Please look else where for now.

Thanks,

Gavin

---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

On Thu, 1 Feb 2007, Bruce Momjian wrote:

>
> Where are we on this patch?  Does it have performance tests to show
> where it is beneificial?  Is it ready to be reviewed?

I've got an updated patch which adds significant performance improvements
for worse case data distributions. It also contains a rewrite of the WAL
code to handle incomplete actions.

I haven't worked on the stuff discussed below with Heikki. It's a lot of
work and probably more suitable for a second generation.

I've just got to finish testing the merge of Tom's operator family stuff
and then I'll send off the patch and performance figures.

Thanks,

Gavin

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index thoughts

[Bruce Momjian]

Where are we on this patch?  Does it have performance tests to show
where it is beneificial?  Is it ready to be reviewed?

---

Heikki Linnakangas wrote:
> I've been skimming through the bitmap index patch...
> 
> A scan needs to access at least five pages:
> 
> 1. B-tree index (root+others, depending on depth)
> 2. The auxiliary heap page
> 3. bitmap index meta page
> 4. LOV page
> 5. bitmap page
> 
> That seems like a lot of indirection. A high startup cost is probably ok 
> for typical bitmap index use cases and most of the needed pages should 
> stay in memory, but could we simplify this? Why do we need the auxiliary 
> heap, couldn't we just store the blk+offset of the LOV item directly in 
> the b-tree index item?
> 
> And instead of having separate LOV pages that store a number of LOV 
> items, how about storing each LOV item on a page of it's own, and using 
> the rest of the page to store the last chunk of the bitmap. That would 
> eliminate one page access, but more importantly, maybe we could then get 
> rid of all the bm_last_* attributes in BMLOVItemData that complicate the 
> patch quite a bit, while preserving the performance.
> 
> -- 
>Heikki Linnakangas
>EnterpriseDB   http://www.enterprisedb.com
> 
> ---(end of broadcast)---
> TIP 5: don't forget to increase your free space map settings

-- 
  Bruce Momjian   [EMAIL PROTECTED]
  EnterpriseDBhttp://www.enterprisedb.com

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

---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index thoughts

[Jie Zhang]

On 12/27/06 3:16 AM, "Gavin Sherry" <[EMAIL PROTECTED]> wrote:

> On Wed, 27 Dec 2006, Heikki Linnakangas wrote:
> 
>> Jie Zhang wrote:
>>> The "bitmap data segment" sounds good in terms of space. The problem is that
>>> one bitmap is likely to occupy more pages than before, which may hurt the
>>> query performance.
>> 
>> We could have segments of say 1/5 of page. When a bitmap grows larger
>> than that, the bitmap would be moved to a page of its own. That way we
>> wouldn't get unnecessary fragmentation with large bitmaps, but small
>> bitmaps would be stored efficiently.
> 
> Yes.

I see. This sounds good. I will think more about this.

Thanks,
Jie



---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

Re: [HACKERS] Bitmap index thoughts

[Jie Zhang]

On 12/27/06 3:10 AM, "Gavin Sherry" <[EMAIL PROTECTED]> wrote:

> On Wed, 27 Dec 2006, Heikki Linnakangas wrote:
> 
>> Gavin Sherry wrote:
>>> On Tue, 26 Dec 2006, Heikki Linnakangas wrote:
 for typical bitmap index use cases and most of the needed pages should
 stay in memory, but could we simplify this? Why do we need the auxiliary
 heap, couldn't we just store the blk+offset of the LOV item directly in
 the b-tree index item?
>>> 
>>> The problem is, the b-tree code is very much tied to the heap. I don't
>>> want to modify the b-tree code to make bitmap indexes work (better).
>>> What's really tempting is to just manage our own balanced tree within the
>>> bitmap index file(s) itself. It would start from the metapage and simply
>>> spill to other 'special' index pages when necessary. The problem is, we do
>>> not have b-tree code generic enough that it would allow us to do this
>>> trivially -- consider concurrency and WAL in particular, which we
>>> currently get for free. I guess this is why I've been ignoring this issue
>>> :-).
>> 
>> Maybe we could reuse the code in ginbtree.c. Looks like Teodor & Oleg
>> had the same problem :).
>> 
>> Modifying the nbtree code doesn't seem that difficult either. AFAICS,
>> the only places where the heap is from within nbtree code is in index
>> building and uniqueness checks.
> 
> I'll take a look and think about it.
> 

I will take a look at it as well. I would also like to add eventually the
values for bm_last_tid_location in all bitmap page to the lov heap.
Combining this with the attribute values, we can easily jump into a specific
bitmap page. This will be useful during vacuuming and insertion after
vacuuming -- we can jump into a page to modify a bit. I am not sure if this
will affect the use of the btree code without the heap. But if we can get
rid of the lov heap, that would be great.

>> 
 And instead of having separate LOV pages that store a number of LOV
 items, how about storing each LOV item on a page of it's own, and using
 the rest of the page to store the last chunk of the bitmap. That would
 eliminate one page access, but more importantly, maybe we could then get
 rid of all the bm_last_* attributes in BMLOVItemData that complicate the
 patch quite a bit, while preserving the performance.
>>> 
>>> That's an interesting approach. We would still need a concept of
>>> last_word, at the very least, and probably last_comp_word for convenience.
>> 
>> Why?
> 
> The two last words of the bitmap vector, stored in the LOV item, provide a
> few things: they buffer the addition of new matches in the vector and they
> ease the calculation of the current position of the end of the vector.
> Jie, do you want to add more?
> 
> I think we could do this differently by calculating everything based on
> the other data stored in the lov item and data page (last_tid_location and
> num_hrl_words_used, from memory). But, I'm not sure. Jie?

Sure. When appending a new bit into an existing bitmap, the last two words
are needed to compute new HRL words, and they are the only words affected by
this new appending bit. So we need a way to know these two words easily.
Like Gavin said, separating them from other words is for convenience.

Also, we won't be able to get rid of bm_last_setbit. We need bm_last_setbit
to tell us how many zeros are there between two bit 1s. There is no other
way to know this.

Thanks,
Jie



---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index thoughts

[Simon Riggs]

On Wed, 2006-12-27 at 22:16 +1100, Gavin Sherry wrote:

> > But actually I'm not convinced we need to worry about efficient storage
> > of small bitmaps at all. The typical use case for bitmap indexes is
> > large tables with small number of distinct values, and the problem
> > doesn't really arise in that scenario. Let's keep it simple for now, we
> > can enhance it in later releases.
> 
> The scenario I'm concerned about is where a sales data base, say, has
> 100,000 products. However, only 500 or 1000 products are popular. They
> dominate, say >99% of the sales. The other 99,900 products consume a
> little bit over 8K each for very little benefit :-(.
> 
> This is pretty contrived but it seem real world enough...

Well, that seems to me to be the typical case. It's called a Zipf
Distribution and applies to categorical data everywhere. 

The main question is how you design your database.  We might think of
indexing the product group (a higher level of the Product Dimension),
since these tend to have a low number of values but these may have been
normalised (or "placed into a Dimension table"). This might leave you
with only the ProductId values in the large Fact table, which as Gavin
points out, may be sparsely populated.  

Another idea might to store the first N heap pointers in the auxiliary
heap, rather than allocating them a whole page for the first value. That
would be even more space efficient than allocating a fixed size part of
a page. At least that would provide some utility for that part of the
storage mechanism.

However, I think Heikki's KISG approach seems good for now. The
infrequent values will probably be infrequently accessed, so we may
never need to read them at all (wishful thinking?).

If we can get something ready for commit soon, that will leave lots of
time before 8.3 freeze to measure where things can be further improved
in terms of space and performance.

-- 
  Simon Riggs 
  EnterpriseDB   http://www.enterprisedb.com



---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[mark]

On Wed, Dec 27, 2006 at 03:42:36PM +, Heikki Linnakangas wrote:
> >I wonder what would happen if somebody implemented automatic index
> >exclusion conditions after use of an INDEX proved to be in the realm
> >of the worst case scenario? :-)
> I'm sorry, I don't understand that sentence...

I was joking about a rather magical automatic INDEX restriction
modifier. For example, if the index becomes large enough to matter
(100 Mbytes?) and any single key takes up more than, say, 20% of the
index, it might be cool if it would automatically add the value to
the restriction list, and prune the now wasted index records.

Sorry for inserting a silly joke in a serious discussion... :-)

Cheers,
mark

-- 
[EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] 
__
.  .  _  ._  . .   .__.  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/|_ |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
   and in the darkness bind them...

   http://mark.mielke.cc/


---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

[EMAIL PROTECTED] wrote:

On Wed, Dec 27, 2006 at 10:16:54PM +1100, Gavin Sherry wrote:

On Wed, 27 Dec 2006, Heikki Linnakangas wrote:

But actually I'm not convinced we need to worry about efficient storage
of small bitmaps at all. The typical use case for bitmap indexes is
large tables with small number of distinct values, and the problem
doesn't really arise in that scenario. Let's keep it simple for now, we
can enhance it in later releases.

The scenario I'm concerned about is where a sales data base, say, has
100,000 products. However, only 500 or 1000 products are popular. They
dominate, say >99% of the sales. The other 99,900 products consume a
little bit over 8K each for very little benefit :-(.
This is pretty contrived but it seem real world enough...


Seems like a good candidate for CREATE INDEX WHERE :-)


Yeah, that was my first thought as well. However, in Gavin's example it 
would be a nightmare to manually update the list popular products, and 
recreate the index when it changes.


Something clever inside bitmap indexam would clearly be better.

But even in that scenario, 99000*8k pages ~= 750 megabytes of wasted 
space might still be acceptable. Or not.



I wonder what would happen if somebody implemented automatic index
exclusion conditions after use of an INDEX proved to be in the realm
of the worst case scenario? :-)


I'm sorry, I don't understand that sentence...

--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

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

Re: [HACKERS] Bitmap index thoughts

[mark]

On Wed, Dec 27, 2006 at 10:16:54PM +1100, Gavin Sherry wrote:
> On Wed, 27 Dec 2006, Heikki Linnakangas wrote:
> > But actually I'm not convinced we need to worry about efficient storage
> > of small bitmaps at all. The typical use case for bitmap indexes is
> > large tables with small number of distinct values, and the problem
> > doesn't really arise in that scenario. Let's keep it simple for now, we
> > can enhance it in later releases.
> The scenario I'm concerned about is where a sales data base, say, has
> 100,000 products. However, only 500 or 1000 products are popular. They
> dominate, say >99% of the sales. The other 99,900 products consume a
> little bit over 8K each for very little benefit :-(.
> This is pretty contrived but it seem real world enough...

Seems like a good candidate for CREATE INDEX WHERE :-)

I wonder what would happen if somebody implemented automatic index
exclusion conditions after use of an INDEX proved to be in the realm
of the worst case scenario? :-)

Cheers,
mark

-- 
[EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] 
__
.  .  _  ._  . .   .__.  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/|_ |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
   and in the darkness bind them...

   http://mark.mielke.cc/


---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

On Wed, 27 Dec 2006, Heikki Linnakangas wrote:

> Jie Zhang wrote:
> > The "bitmap data segment" sounds good in terms of space. The problem is that
> > one bitmap is likely to occupy more pages than before, which may hurt the
> > query performance.
>
> We could have segments of say 1/5 of page. When a bitmap grows larger
> than that, the bitmap would be moved to a page of its own. That way we
> wouldn't get unnecessary fragmentation with large bitmaps, but small
> bitmaps would be stored efficiently.

Yes.

>
> > I have been thinking along the lines of increasing the
> > number of last bitmap words stored in each LOV item, but not to occupy one
> > page. This may prevent some cases Gavin indicated here, but not all.
>
> That sounds like more special cases and complexity. I like the segment
> idea more.
>
> But actually I'm not convinced we need to worry about efficient storage
> of small bitmaps at all. The typical use case for bitmap indexes is
> large tables with small number of distinct values, and the problem
> doesn't really arise in that scenario. Let's keep it simple for now, we
> can enhance it in later releases.

The scenario I'm concerned about is where a sales data base, say, has
100,000 products. However, only 500 or 1000 products are popular. They
dominate, say >99% of the sales. The other 99,900 products consume a
little bit over 8K each for very little benefit :-(.

This is pretty contrived but it seem real world enough...

Gavin

---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

On Wed, 27 Dec 2006, Heikki Linnakangas wrote:

> Gavin Sherry wrote:
> > On Tue, 26 Dec 2006, Heikki Linnakangas wrote:
> >> for typical bitmap index use cases and most of the needed pages should
> >> stay in memory, but could we simplify this? Why do we need the auxiliary
> >> heap, couldn't we just store the blk+offset of the LOV item directly in
> >> the b-tree index item?
> >
> > The problem is, the b-tree code is very much tied to the heap. I don't
> > want to modify the b-tree code to make bitmap indexes work (better).
> > What's really tempting is to just manage our own balanced tree within the
> > bitmap index file(s) itself. It would start from the metapage and simply
> > spill to other 'special' index pages when necessary. The problem is, we do
> > not have b-tree code generic enough that it would allow us to do this
> > trivially -- consider concurrency and WAL in particular, which we
> > currently get for free. I guess this is why I've been ignoring this issue
> > :-).
>
> Maybe we could reuse the code in ginbtree.c. Looks like Teodor & Oleg
> had the same problem :).
>
> Modifying the nbtree code doesn't seem that difficult either. AFAICS,
> the only places where the heap is from within nbtree code is in index
> building and uniqueness checks.

I'll take a look and think about it.

>
> >> And instead of having separate LOV pages that store a number of LOV
> >> items, how about storing each LOV item on a page of it's own, and using
> >> the rest of the page to store the last chunk of the bitmap. That would
> >> eliminate one page access, but more importantly, maybe we could then get
> >> rid of all the bm_last_* attributes in BMLOVItemData that complicate the
> >> patch quite a bit, while preserving the performance.
> >
> > That's an interesting approach. We would still need a concept of
> > last_word, at the very least, and probably last_comp_word for convenience.
>
> Why?

The two last words of the bitmap vector, stored in the LOV item, provide a
few things: they buffer the addition of new matches in the vector and they
ease the calculation of the current position of the end of the vector.
Jie, do you want to add more?

I think we could do this differently by calculating everything based on
the other data stored in the lov item and data page (last_tid_location and
num_hrl_words_used, from memory). But, I'm not sure. Jie?

Thanks,

Gavin

---(end of broadcast)---
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

Re: [HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

Jie Zhang wrote:

The "bitmap data segment" sounds good in terms of space. The problem is that
one bitmap is likely to occupy more pages than before, which may hurt the
query performance. 


We could have segments of say 1/5 of page. When a bitmap grows larger 
than that, the bitmap would be moved to a page of its own. That way we 
wouldn't get unnecessary fragmentation with large bitmaps, but small 
bitmaps would be stored efficiently.



I have been thinking along the lines of increasing the
number of last bitmap words stored in each LOV item, but not to occupy one
page. This may prevent some cases Gavin indicated here, but not all.


That sounds like more special cases and complexity. I like the segment 
idea more.


But actually I'm not convinced we need to worry about efficient storage 
of small bitmaps at all. The typical use case for bitmap indexes is 
large tables with small number of distinct values, and the problem 
doesn't really arise in that scenario. Let's keep it simple for now, we 
can enhance it in later releases.


--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 4: Have you searched our list archives?

  http://archives.postgresql.org

Re: [HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

Gavin Sherry wrote:

On Tue, 26 Dec 2006, Heikki Linnakangas wrote:

for typical bitmap index use cases and most of the needed pages should
stay in memory, but could we simplify this? Why do we need the auxiliary
heap, couldn't we just store the blk+offset of the LOV item directly in
the b-tree index item?


The problem is, the b-tree code is very much tied to the heap. I don't
want to modify the b-tree code to make bitmap indexes work (better).
What's really tempting is to just manage our own balanced tree within the
bitmap index file(s) itself. It would start from the metapage and simply
spill to other 'special' index pages when necessary. The problem is, we do
not have b-tree code generic enough that it would allow us to do this
trivially -- consider concurrency and WAL in particular, which we
currently get for free. I guess this is why I've been ignoring this issue
:-).


Maybe we could reuse the code in ginbtree.c. Looks like Teodor & Oleg 
had the same problem :).


Modifying the nbtree code doesn't seem that difficult either. AFAICS, 
the only places where the heap is from within nbtree code is in index 
building and uniqueness checks.



And instead of having separate LOV pages that store a number of LOV
items, how about storing each LOV item on a page of it's own, and using
the rest of the page to store the last chunk of the bitmap. That would
eliminate one page access, but more importantly, maybe we could then get
rid of all the bm_last_* attributes in BMLOVItemData that complicate the
patch quite a bit, while preserving the performance.


That's an interesting approach. We would still need a concept of
last_word, at the very least, and probably last_comp_word for convenience.


Why?


PS: Another versio of the patch shall be forthcoming shortly. I've been
working on compressing the data in memory during CREATE INDEX instead of
just managing arrays of TIDs in memory as we did previously. The array of
TIDs works great for well clustered data but it stinks for poorly
clustered data as we approach maintenance_word_mem and have to swap a lot.


Ok, sounds good.

--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index thoughts

[Jie Zhang]

>> And instead of having separate LOV pages that store a number of LOV
>> items, how about storing each LOV item on a page of it's own, and using
>> the rest of the page to store the last chunk of the bitmap. That would
>> eliminate one page access, but more importantly, maybe we could then get
>> rid of all the bm_last_* attributes in BMLOVItemData that complicate the
>> patch quite a bit, while preserving the performance.
> 
> That's an interesting approach. We would still need a concept of
> last_word, at the very least, and probably last_comp_word for convenience.
> Your idea doesn't require any extra space, either, which is good.
> Something I've been working through is the idea of a 'bitmap data
> segment'. Currently, we store the HRL compressed bitmap data to the extent
> of the page. That is, sizeof(BMBitmap) is as close to BLCKSZ as we can
> make it. The problem is that we may have some bitmaps where a few values
> occur only a small number of times and are well clustered at the beginning
> of the heap. In that circumstance, we use a whole page to store a small
> number of words and the free space cannot be used by any other vector.
> Now, say a segment was some fraction the size of BLCKSZ, we use less space
> for those vectors with few tuples in the heap. Just an idea...

The "bitmap data segment" sounds good in terms of space. The problem is that
one bitmap is likely to occupy more pages than before, which may hurt the
query performance. I have been thinking along the lines of increasing the
number of last bitmap words stored in each LOV item, but not to occupy one
page. This may prevent some cases Gavin indicated here, but not all.

Thanks,
Jie



---(end of broadcast)---
TIP 4: Have you searched our list archives?

   http://archives.postgresql.org

Re: [HACKERS] Bitmap index thoughts

[Gavin Sherry]

Hey Heikki,

On Tue, 26 Dec 2006, Heikki Linnakangas wrote:

> I've been skimming through the bitmap index patch...
>
> A scan needs to access at least five pages:
>
> 1. B-tree index (root+others, depending on depth)
> 2. The auxiliary heap page
> 3. bitmap index meta page
> 4. LOV page
> 5. bitmap page
>
> That seems like a lot of indirection. A high startup cost is probably ok

You're right, this is excessive and it was something I'd hoped to have
ripped out, but...

> for typical bitmap index use cases and most of the needed pages should
> stay in memory, but could we simplify this? Why do we need the auxiliary
> heap, couldn't we just store the blk+offset of the LOV item directly in
> the b-tree index item?

The problem is, the b-tree code is very much tied to the heap. I don't
want to modify the b-tree code to make bitmap indexes work (better).
What's really tempting is to just manage our own balanced tree within the
bitmap index file(s) itself. It would start from the metapage and simply
spill to other 'special' index pages when necessary. The problem is, we do
not have b-tree code generic enough that it would allow us to do this
trivially -- consider concurrency and WAL in particular, which we
currently get for free. I guess this is why I've been ignoring this issue
:-).

> And instead of having separate LOV pages that store a number of LOV
> items, how about storing each LOV item on a page of it's own, and using
> the rest of the page to store the last chunk of the bitmap. That would
> eliminate one page access, but more importantly, maybe we could then get
> rid of all the bm_last_* attributes in BMLOVItemData that complicate the
> patch quite a bit, while preserving the performance.

That's an interesting approach. We would still need a concept of
last_word, at the very least, and probably last_comp_word for convenience.
Your idea doesn't require any extra space, either, which is good.
Something I've been working through is the idea of a 'bitmap data
segment'. Currently, we store the HRL compressed bitmap data to the extent
of the page. That is, sizeof(BMBitmap) is as close to BLCKSZ as we can
make it. The problem is that we may have some bitmaps where a few values
occur only a small number of times and are well clustered at the beginning
of the heap. In that circumstance, we use a whole page to store a small
number of words and the free space cannot be used by any other vector.
Now, say a segment was some fraction the size of BLCKSZ, we use less space
for those vectors with few tuples in the heap. Just an idea...

Thanks,

Gavin

PS: Another versio of the patch shall be forthcoming shortly. I've been
working on compressing the data in memory during CREATE INDEX instead of
just managing arrays of TIDs in memory as we did previously. The array of
TIDs works great for well clustered data but it stinks for poorly
clustered data as we approach maintenance_word_mem and have to swap a lot.

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

[HACKERS] Bitmap index thoughts

[Heikki Linnakangas]

I've been skimming through the bitmap index patch...

A scan needs to access at least five pages:

1. B-tree index (root+others, depending on depth)
2. The auxiliary heap page
3. bitmap index meta page
4. LOV page
5. bitmap page

That seems like a lot of indirection. A high startup cost is probably ok 
for typical bitmap index use cases and most of the needed pages should 
stay in memory, but could we simplify this? Why do we need the auxiliary 
heap, couldn't we just store the blk+offset of the LOV item directly in 
the b-tree index item?


And instead of having separate LOV pages that store a number of LOV 
items, how about storing each LOV item on a page of it's own, and using 
the rest of the page to store the last chunk of the bitmap. That would 
eliminate one page access, but more importantly, maybe we could then get 
rid of all the bm_last_* attributes in BMLOVItemData that complicate the 
patch quite a bit, while preserving the performance.


--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 5: don't forget to increase your free space map settings

Re: [HACKERS] Bitmap index status

[Bruce Momjian]

Gavin Sherry wrote:
> On Wed, 18 Oct 2006, Heikki Linnakangas wrote:
> 
> > Hi,
> >
> > I don't want to harass you :), but what's the status with the bitmap
> > index code? Is there something I can do to help?
> >
> 
> Hi Heikki,
> 
> The streaming is implemented, as are range queries. I need to bring it up
> to HEAD and back-patch to bizgres since... it's not diverged fairly
> significantly from that code base.
> 
> Two outstanding items are handling vacuum and I was considering having a
> bitmap selectivity function but I haven't really looked into it.
> 
> Once I bring it up to HEAD I'll post.

Code promises for this feature have been unreliable in the past.  :-(

-- 
  Bruce Momjian   [EMAIL PROTECTED]
  EnterpriseDBhttp://www.enterprisedb.com

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

---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index status

[Gavin Sherry]

On Wed, 18 Oct 2006, Heikki Linnakangas wrote:

> Hi,
>
> I don't want to harass you :), but what's the status with the bitmap
> index code? Is there something I can do to help?
>

Hi Heikki,

The streaming is implemented, as are range queries. I need to bring it up
to HEAD and back-patch to bizgres since... it's not diverged fairly
significantly from that code base.

Two outstanding items are handling vacuum and I was considering having a
bitmap selectivity function but I haven't really looked into it.

Once I bring it up to HEAD I'll post.

Thanks,

Gavin


---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

Re: [HACKERS] Bitmap index status

[Jie Zhang]

On 10/18/06 2:41 AM, "Heikki Linnakangas" <[EMAIL PROTECTED]> wrote:

> Hi,
> 
> I don't want to harass you :), but what's the status with the bitmap
> index code? Is there something I can do to help?

Not at all. We will send you the new patch soon. Your comments are most
appreciated.

Thanks,
Jie



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

[HACKERS] Bitmap index status

[Heikki Linnakangas]

Hi,

I don't want to harass you :), but what's the status with the bitmap 
index code? Is there something I can do to help?


--
  Heikki Linnakangas
  EnterpriseDB   http://www.enterprisedb.com

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
  choose an index scan if your joining column's datatypes do not
  match

Re: [HACKERS] Bitmap index status

[Mark Wong]

Luke Lonergan wrote:

Mark,

On 9/25/06 11:32 AM, "Mark Wong" <[EMAIL PROTECTED]> wrote:


Yeah, basically gather as many stats as I can to accurately profile the
overall system performance.  I thought it would be appropriate to use a
TPC-H based workload as one measuring stick to use for bitmap indexes.


Note that the TPC-H queries don't follow the typical good use case for
bitmap indexes.  You'd like to see queries that use multiple AND and OR
clauses, otherwise there may be no benefit.


Oh right, people keep telling me that and it keeps going in one ear and 
out the other...



Also, DBT-3/TPC-H on Postgres right now does not benefit from indices
overall.  The planner has limitations WRT selectivity estimates and other
limitations that cause it to choose index access poorly for the query
workload.  We have two new features coming (for 8.3) that fix this, but for
now we find that indexes are a net loss, in some queries a huge loss.


Great, I'll keep my eye for those. :)


If you look at the whitepaper that Ayush Parashar published, he uses the
TPC-H data with some targeted queries that showcase the best use-cases for
bitmap index.


Mark

---(end of broadcast)---
TIP 4: Have you searched our list archives?

  http://archives.postgresql.org

Re: [HACKERS] Bitmap index status

[Gavin Sherry]

On Tue, 26 Sep 2006, Heikki Linnakangas wrote:

> Looks a bit better now, though I think you need to think more about the
> encapsulation of the structs. More detailed comments below.
>
> Jie Zhang wrote:
> > Essentially, we want to have a stream bitmap object that has an iterator,
> > which will be able to iterate through the bitmaps. The BitmapIndexscan,
> > BitmapAnd, BitmapOr will be executed once and return a streamp bitmap or a
> > hash bitmap. The BitmapHeapscan then calls tbm_iterate() to iterate
> > through
> > the bitmaps.
> >
> > The StreamBitmap structure will look like below.
> >
> > struct StreamBitmap {
> > NodeTag type; /* to make it a valid Node */
> > PagetableEntry entry; /* a page of tids in this stream bitmap */
> >
> > /* the iterator function */
> > void (*next)(StreamBitmap*);
> > Node* state; /* store how this stream bitmap generated,
> > and all necessary information to
> > obtain the next stream bitmap. */
> > };
>
> I'd suggest making state just a (void *). It's private to the producer
> of the bitmap, and I don't see a reason to expose it. I assume that the
> next-function fills in the PageTableEntry with the next set of tids.
>
> > Two new state objects will look like below. At the same time, we introduce
> > three new node types: T_StreamBitmapAND, T_StreamBitmapOR,
> > And T_StreamBitmapIndex, to define different states.
> >
> > /*
> > * Stores the necessary information for iterating through the stream
> > bitmaps
> > * generated by nodeBitmapAnd or nodeBitmapOr.
> > */
> > struct StreamBitmapOp {
> > NodeTag type; /* handles T_StreamBitmapAND and T_StreamBitmapOR */
> > List* bitmaps;
> > };
>
> AFAICS, this struct is private to tidbitmap.c, where the new
> stream-enabled tbm_intersect etc. functions are defined. Also, I don't
> see a reason why it needs to by a valid Node.

Well, making it a valid nodes makes it easy to identify (IsA) and gives us
access to copy/equal frameworks. I do think that it is best to bury this
in the bitmap code however.

> > * Stores some necessary information for iterating through the stream
> > * bitmaps generated by nodeBitmapIndexscan.
> > */
> > struct StreamBitmapIndex {
> > NodeTag type; /* handle T_StreamBitmapIndex */
> > IndexScanDesc scan;
> > BlockNumber nextBlockNo;/* next block no to be read */
> > };
>
> Where would this struct be defined? I think different index access
> methods might want to have different kind of states. The struct above
> assumes that the position of an index scan is always represented by the
> nextBlockNo. That seems to be the right thing for the bitmap indexam, so
> this struct is fine for StreamBitmaps returned by bmgetbitmap, but not
> necessary for others.

right.

>
> > Then we will have the iterator functions like the following:
> >
> > ...
> >
> > void StreamBitmapIndexNext(StreamBitmap* node) {
> > StreamBitmapIndex* sbi = (StreamBitmapIndex*) node->state;
> > amgetbitmap(sbi->scan, NULL, sbi->nextBlockNo);
> > }
>
> This means that the amgetbitmap function would still be called many
> times in each scan.  What would amgetbitmap return? A new StreamBitmap
> on each call?
>
> I'd like to see just one call to amgetbitmap. It would a) fill in the
> hash bitmap passed to it, b) return a new hash bitmap, or c) return a
> new StreamBitmap, with a indexam specific next-function that returns the
> tids one page at a time. I think we'll also need some kind of a
> destructor in StreamBitmap that's called by the consumer of the bitmap
> after it's done with it.

Right, I agree. I am working on this now.

Thanks,

gavin

---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index status

[Heikki Linnakangas]

Looks a bit better now, though I think you need to think more about the 
encapsulation of the structs. More detailed comments below.


Jie Zhang wrote:

Essentially, we want to have a stream bitmap object that has an iterator,
which will be able to iterate through the bitmaps. The BitmapIndexscan,
BitmapAnd, BitmapOr will be executed once and return a streamp bitmap or a
hash bitmap. The BitmapHeapscan then calls tbm_iterate() to iterate 
through

the bitmaps.

The StreamBitmap structure will look like below.

struct StreamBitmap {
NodeTag type; /* to make it a valid Node */
PagetableEntry entry; /* a page of tids in this stream bitmap */

/* the iterator function */
void (*next)(StreamBitmap*);
Node* state; /* store how this stream bitmap generated,
and all necessary information to
obtain the next stream bitmap. */
};


I'd suggest making state just a (void *). It's private to the producer 
of the bitmap, and I don't see a reason to expose it. I assume that the 
next-function fills in the PageTableEntry with the next set of tids.



Two new state objects will look like below. At the same time, we introduce
three new node types: T_StreamBitmapAND, T_StreamBitmapOR,
And T_StreamBitmapIndex, to define different states.

/*
* Stores the necessary information for iterating through the stream 
bitmaps

* generated by nodeBitmapAnd or nodeBitmapOr.
*/
struct StreamBitmapOp {
NodeTag type; /* handles T_StreamBitmapAND and T_StreamBitmapOR */
List* bitmaps;
};


AFAICS, this struct is private to tidbitmap.c, where the new 
stream-enabled tbm_intersect etc. functions are defined. Also, I don't 
see a reason why it needs to by a valid Node.



/*
* Stores some necessary information for iterating through the stream
* bitmaps generated by nodeBitmapIndexscan.
*/
struct StreamBitmapIndex {
NodeTag type; /* handle T_StreamBitmapIndex */
IndexScanDesc scan;
BlockNumber nextBlockNo;/* next block no to be read */
};


Where would this struct be defined? I think different index access 
methods might want to have different kind of states. The struct above 
assumes that the position of an index scan is always represented by the 
nextBlockNo. That seems to be the right thing for the bitmap indexam, so 
this struct is fine for StreamBitmaps returned by bmgetbitmap, but not 
necessary for others.



Then we will have the iterator functions like the following:

...

void StreamBitmapIndexNext(StreamBitmap* node) {
StreamBitmapIndex* sbi = (StreamBitmapIndex*) node->state;
amgetbitmap(sbi->scan, NULL, sbi->nextBlockNo);
}


This means that the amgetbitmap function would still be called many 
times in each scan.  What would amgetbitmap return? A new StreamBitmap 
on each call?


I'd like to see just one call to amgetbitmap. It would a) fill in the 
hash bitmap passed to it, b) return a new hash bitmap, or c) return a 
new StreamBitmap, with a indexam specific next-function that returns the 
tids one page at a time. I think we'll also need some kind of a 
destructor in StreamBitmap that's called by the consumer of the bitmap 
after it's done with it.


--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
  choose an index scan if your joining column's datatypes do not
  match

Re: [HACKERS] Bitmap index status

[Luke Lonergan]

Mark,

On 9/25/06 11:32 AM, "Mark Wong" <[EMAIL PROTECTED]> wrote:

> Yeah, basically gather as many stats as I can to accurately profile the
> overall system performance.  I thought it would be appropriate to use a
> TPC-H based workload as one measuring stick to use for bitmap indexes.

Note that the TPC-H queries don't follow the typical good use case for
bitmap indexes.  You'd like to see queries that use multiple AND and OR
clauses, otherwise there may be no benefit.

Also, DBT-3/TPC-H on Postgres right now does not benefit from indices
overall.  The planner has limitations WRT selectivity estimates and other
limitations that cause it to choose index access poorly for the query
workload.  We have two new features coming (for 8.3) that fix this, but for
now we find that indexes are a net loss, in some queries a huge loss.

If you look at the whitepaper that Ayush Parashar published, he uses the
TPC-H data with some targeted queries that showcase the best use-cases for
bitmap index.

- Luke 



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

Re: [HACKERS] Bitmap index status

[Mark Wong]

Hi Jie,

Yeah, basically gather as many stats as I can to accurately profile the 
overall system performance.  I thought it would be appropriate to use a 
TPC-H based workload as one measuring stick to use for bitmap indexes.


Mark

Jie Zhang wrote:

Hi Mark,

Thanks for doing the test. I checked out the link you provided below. I am a
little confused about the goal of these tests. Do you plan to test the
overall performance of postgreSQL on handling TPC-H queries?

Thanks,
Jie

On 9/22/06 3:45 PM, "Mark Wong" <[EMAIL PROTECTED]> wrote:


Jie Zhang wrote:

Hi Heikki and all,

I just sent the latest bitmap index patch to the list. I am not sure if
there is any size limit for this mailing list. If you have received my
previous email, please let me know.

Hi Jie,

I know I said I was going to get testing on this months ago but I've
been juggling between 3 systems due to disk failures and other hardware
configuration issues.  Anyways, I've take a baseline run of only the
power test using a 1GB database with the patch 09-17 patch against a
snapshot of pgsql from 2006-09-17:

http://dbt.osdl.org/dbt/dbt3testing/results/dev8-007/2/

Do you think the 1GB scale factor will be sufficient for testing as it
will certainly be faster?  Do you think testing with just a power test
will be sufficient for now?  I really don't have a good reason why I
didn't run a throughput test other than to save time. :)  I also wanted
to get your opinion again on which indexes we will want to try first.

Thanks,
Mark



---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
  choose an index scan if your joining column's datatypes do not
  match

Re: [HACKERS] Bitmap index status

[Jie Zhang]

Hi Mark,

Thanks for doing the test. I checked out the link you provided below. I am a
little confused about the goal of these tests. Do you plan to test the
overall performance of postgreSQL on handling TPC-H queries?

Thanks,
Jie

On 9/22/06 3:45 PM, "Mark Wong" <[EMAIL PROTECTED]> wrote:

> Jie Zhang wrote:
>> Hi Heikki and all,
>> 
>> I just sent the latest bitmap index patch to the list. I am not sure if
>> there is any size limit for this mailing list. If you have received my
>> previous email, please let me know.
> 
> Hi Jie,
> 
> I know I said I was going to get testing on this months ago but I've
> been juggling between 3 systems due to disk failures and other hardware
> configuration issues.  Anyways, I've take a baseline run of only the
> power test using a 1GB database with the patch 09-17 patch against a
> snapshot of pgsql from 2006-09-17:
> 
> http://dbt.osdl.org/dbt/dbt3testing/results/dev8-007/2/
> 
> Do you think the 1GB scale factor will be sufficient for testing as it
> will certainly be faster?  Do you think testing with just a power test
> will be sufficient for now?  I really don't have a good reason why I
> didn't run a throughput test other than to save time. :)  I also wanted
> to get your opinion again on which indexes we will want to try first.
> 
> Thanks,
> Mark
> 



---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

Re: [HACKERS] Bitmap index status

[Jie Zhang]

Gavin & Heikki,

>> 
>> The handling of stream and hash bitmaps looks pretty complicated to me.
>> All the bitmap-related nodes have logic to handle both types slightly
>> differently. It all seems to come down to that if a subnode (or
>> amgetbitmap in a bitmap index scan node) returns a StreamBitmap, the
>> caller needs to call the subnode many times, until it returns a NULL.
>> With a HashBitmap, the caller only calls the subnode once.
>> 
>> I think amgetbitmap should be called just once per index scan, and it
>> should return either a hash bitmap or a stream bitmap. The same applies
>> to all the executor nodes that return bitmaps, they would only return a
>> single HashBitmap or StreamBitmap, and the upper node would call
>> tbm_iterate repeatedly on that.
>> 
>> StreamBitmap would contain a callback (filled by the indexam) that
>> tbm_iterate would call to fill the next TBMIterateResult.
> 
> Right, this was the approach taken by an earlier version of the patch I
> had worked on. It was significantly uglified by the need to keep the index
> state around and to be careful about what amrescan might do behind out
> back. I will, however, introduce the idea again because it makes the code
> much cleaner and more logical, as you seem to suggest.
> 

I have been thinking about this approach some more. I do agree that this is
more attractive now. The following includes some more detailed design.
Please let me know if you have any comments. (My apologies to Gavin. You
talked to me about this approach before. But you introduced some on-disk
bitmap specific code into the tidbitmap.c, which prevented me from looking
more in this direction.)

Essentially, we want to have a stream bitmap object that has an iterator,
which will be able to iterate through the bitmaps. The BitmapIndexscan,
BitmapAnd, BitmapOr will be executed once and return a streamp bitmap or a
hash bitmap. The BitmapHeapscan then calls tbm_iterate() to iterate through
the bitmaps.

The StreamBitmap structure will look like below.

struct StreamBitmap {
NodeTag   type;   /* to make it a valid Node */
PagetableEntryentry;  /* a page of tids in this stream bitmap */

/* the iterator function */
void(*next)(StreamBitmap*);
Node*   state;/* store how this stream bitmap generated,
 and all necessary information to
 obtain the next stream bitmap. */
};

Two new state objects will look like below. At the same time, we introduce
three new node types: T_StreamBitmapAND, T_StreamBitmapOR,
And T_StreamBitmapIndex, to define different states.

/*
 * Stores the necessary information for iterating through the stream bitmaps
 * generated by nodeBitmapAnd or nodeBitmapOr.
 */
struct StreamBitmapOp {
NodeTag type;  /* handles T_StreamBitmapAND and T_StreamBitmapOR */
List*   bitmaps;
};

/*
 * Stores some necessary information for iterating through the stream
 * bitmaps generated by nodeBitmapIndexscan.
 */
struct StreamBitmapIndex {
NodeTag type; /* handle T_StreamBitmapIndex */
IndexScanDescscan;
BlockNumbernextBlockNo;/* next block no to be read */
};

Then we will have the iterator functions like the following:

void StreamBitmapAndNext(StreamBitmap* node) {
  tbm_intersect_stream(((StreampBitmapOp*) node->state)->bitmaps, node);
}

void StreamBitmapOrNext(StreamBitmap* node) {
  tbm_union_stream(((StreampBitmapOp*) node->state)->bitmaps, node);
}

void StreamBitmapIndexNext(StreamBitmap* node) {
  StreamBitmapIndex* sbi = (StreamBitmapIndex*) node->state;
  amgetbitmap(sbi->scan, NULL, sbi->nextBlockNo);
}

What do you think?

Thanks,
Jie



---(end of broadcast)---
TIP 4: Have you searched our list archives?

   http://archives.postgresql.org

Re: [HACKERS] Bitmap index status

[Mark Wong]

Jie Zhang wrote:

Hi Heikki and all,

I just sent the latest bitmap index patch to the list. I am not sure if
there is any size limit for this mailing list. If you have received my
previous email, please let me know.


Hi Jie,

I know I said I was going to get testing on this months ago but I've 
been juggling between 3 systems due to disk failures and other hardware 
configuration issues.  Anyways, I've take a baseline run of only the 
power test using a 1GB database with the patch 09-17 patch against a 
snapshot of pgsql from 2006-09-17:


http://dbt.osdl.org/dbt/dbt3testing/results/dev8-007/2/

Do you think the 1GB scale factor will be sufficient for testing as it 
will certainly be faster?  Do you think testing with just a power test 
will be sufficient for now?  I really don't have a good reason why I 
didn't run a throughput test other than to save time. :)  I also wanted 
to get your opinion again on which indexes we will want to try first.


Thanks,
Mark

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index status

[Jie Zhang]

On 9/19/06 5:15 AM, "Gavin Sherry" <[EMAIL PROTECTED]> wrote:

> On Tue, 19 Sep 2006, Heikki Linnakangas wrote:
> 
>> Jie Zhang wrote:
>>> Hi Heikki and all,
>>> 
>>> Please find the latest bitmap index patch in the attachment. This patch is
>>> generated against the postgresql cvs head.
>>> 
>> 
>> Thanks.
>> 
>> The handling of stream and hash bitmaps looks pretty complicated to me.
>> All the bitmap-related nodes have logic to handle both types slightly
>> differently. It all seems to come down to that if a subnode (or
>> amgetbitmap in a bitmap index scan node) returns a StreamBitmap, the
>> caller needs to call the subnode many times, until it returns a NULL.
>> With a HashBitmap, the caller only calls the subnode once.
>> 
>> I think amgetbitmap should be called just once per index scan, and it
>> should return either a hash bitmap or a stream bitmap. The same applies
>> to all the executor nodes that return bitmaps, they would only return a
>> single HashBitmap or StreamBitmap, and the upper node would call
>> tbm_iterate repeatedly on that.
>> 
>> StreamBitmap would contain a callback (filled by the indexam) that
>> tbm_iterate would call to fill the next TBMIterateResult.
> 
> Right, this was the approach taken by an earlier version of the patch I
> had worked on. It was significantly uglified by the need to keep the index
> state around and to be careful about what amrescan might do behind out
> back. I will, however, introduce the idea again because it makes the code
> much cleaner and more logical, as you seem to suggest.

I will think about this approach. But I am not quite convinced that this
approach will be simpler and cleaner than the above approach. :-)

Thanks,
Jie



---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

Re: [HACKERS] Bitmap index status

[Gavin Sherry]

On Tue, 19 Sep 2006, Heikki Linnakangas wrote:

> Jie Zhang wrote:
> > Hi Heikki and all,
> >
> > Please find the latest bitmap index patch in the attachment. This patch is
> > generated against the postgresql cvs head.
> >
>
> Thanks.
>
> The handling of stream and hash bitmaps looks pretty complicated to me.
> All the bitmap-related nodes have logic to handle both types slightly
> differently. It all seems to come down to that if a subnode (or
> amgetbitmap in a bitmap index scan node) returns a StreamBitmap, the
> caller needs to call the subnode many times, until it returns a NULL.
> With a HashBitmap, the caller only calls the subnode once.
>
> I think amgetbitmap should be called just once per index scan, and it
> should return either a hash bitmap or a stream bitmap. The same applies
> to all the executor nodes that return bitmaps, they would only return a
> single HashBitmap or StreamBitmap, and the upper node would call
> tbm_iterate repeatedly on that.
>
> StreamBitmap would contain a callback (filled by the indexam) that
> tbm_iterate would call to fill the next TBMIterateResult.

Right, this was the approach taken by an earlier version of the patch I
had worked on. It was significantly uglified by the need to keep the index
state around and to be careful about what amrescan might do behind out
back. I will, however, introduce the idea again because it makes the code
much cleaner and more logical, as you seem to suggest.

Thanks,

Gavin

---(end of broadcast)---
TIP 4: Have you searched our list archives?

   http://archives.postgresql.org

Re: [HACKERS] Bitmap index status

[Heikki Linnakangas]

Jie Zhang wrote:

Hi Heikki and all,

Please find the latest bitmap index patch in the attachment. This patch is
generated against the postgresql cvs head.
  


Thanks.

The handling of stream and hash bitmaps looks pretty complicated to me. 
All the bitmap-related nodes have logic to handle both types slightly 
differently. It all seems to come down to that if a subnode (or 
amgetbitmap in a bitmap index scan node) returns a StreamBitmap, the 
caller needs to call the subnode many times, until it returns a NULL. 
With a HashBitmap, the caller only calls the subnode once.


I think amgetbitmap should be called just once per index scan, and it 
should return either a hash bitmap or a stream bitmap. The same applies 
to all the executor nodes that return bitmaps, they would only return a 
single HashBitmap or StreamBitmap, and the upper node would call 
tbm_iterate repeatedly on that.


StreamBitmap would contain a callback (filled by the indexam) that 
tbm_iterate would call to fill the next TBMIterateResult.


I would also move the code to AND and OR together different types of 
bitmaps to tidbitmap.c, so that BitmapAnd and BitmapOr nodes wouldn't 
need to care about different types either.


tbm_intersect and tbm_union with two HashBitmaps would work like they do 
now. Calling tbm_intersect or tbm_union with two StreamBitmaps would 
return a new StreamBitmap object that would pull results from the two 
argument StreamBitmaps page at a time and AND or OR them together. 
Combining a HashBitmap and a StreamBitmap would wrap the HashBitmap with 
a new StreamBitmap that pulls the entries from the HashBitmap page at a 
time.


What do you think? Would you like me to help implementing the above?


This patch includes code style changes, bug fixes, and the stream bitmap
implementation. I have also fixed the problems mentioned in Heikki's email.
  


It seems you fixed the race condition in inserttuple by holding a write 
lock on the metapage while you find/create the lov item. While correct, 
isn't that pretty bad for concurrency? I realize that the main use case 
for bitmap indexes is large data warehouses where you don't do 
concurrent updates, but still...


--
 Heikki Linnakangas
 EnterpriseDB   http://www.enterprisedb.com


---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index status

[Jie Zhang]

Hi Heikki and all,

I just sent the latest bitmap index patch to the list. I am not sure if
there is any size limit for this mailing list. If you have received my
previous email, please let me know.

Thanks,
Jie

On 9/12/06 2:43 AM, "Heikki Linnakangas" <[EMAIL PROTECTED]> wrote:

> Hi,
> 
> What's the status of the bitmap index patch? Have you worked on it since
> the last posted patch
> (http://archives.postgresql.org/pgsql-patches/2006-08/msg3.php)?
> 
> I've started to review it, to get it into CVS early in the 8.3 cycle. I
> just want to make sure that I'm working on the latest version.
> 
> Beside the issues already discussed, I found two minor bugs:
> * pg_am says that bitmap am supports unique indexes, while it doesn't.
> Second,
> * race condition in _bitmap_inserttuple if two backends try to insert
> the same, new value. If they both find that there's no lov item for the
> key, and try to create one, one backend will get a duplicate key error
> on the lov index.
> 
> Also, vacuum actually does a reindex, which seems awfully wasteful. That
> needs to be looked at.



---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

Re: [HACKERS] Bitmap index status

[Jie Zhang]

Hi Heikki,

Gavin and I are trying to merge our changes together this week. We will post
a new patch by the end of this week. This patch will include some style
fixes, bug fixes, and the stream bitmap implementation.

I will look into the problems you have mentioned in this email. Yes, vacuum
currently does a reindex now. Gavin and I just talked about this yesterday.
We are looking into ways to improve this. One way is not to do reindex for
each vacuum. We maintain a list of updated tids along with the bitmap index.
Only when this list goes to a certain point, vacuum will re-build the index.

Thanks,
Jie

On 9/12/06 2:43 AM, "Heikki Linnakangas" <[EMAIL PROTECTED]> wrote:

> Hi,
> 
> What's the status of the bitmap index patch? Have you worked on it since
> the last posted patch
> (http://archives.postgresql.org/pgsql-patches/2006-08/msg3.php)?
> 
> I've started to review it, to get it into CVS early in the 8.3 cycle. I
> just want to make sure that I'm working on the latest version.
> 
> Beside the issues already discussed, I found two minor bugs:
> * pg_am says that bitmap am supports unique indexes, while it doesn't.
> Second,
> * race condition in _bitmap_inserttuple if two backends try to insert
> the same, new value. If they both find that there's no lov item for the
> key, and try to create one, one backend will get a duplicate key error
> on the lov index.
> 
> Also, vacuum actually does a reindex, which seems awfully wasteful. That
> needs to be looked at.



---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index status

[Tom Lane]

Heikki Linnakangas <[EMAIL PROTECTED]> writes:
> What's the status of the bitmap index patch? Have you worked on it since 
> the last posted patch 
> (http://archives.postgresql.org/pgsql-patches/2006-08/msg3.php)?

Gavin and Jie have made major changes since that version (or at least
they'd better have something to show for the month since then ;-)).
I wouldn't recommend reviewing the patch until they post something
current ...

> Also, vacuum actually does a reindex, which seems awfully wasteful. That 
> needs to be looked at.

Yikes.  I imagine they've not tried to do anything about that; if you
want to help, maybe you could take that subproblem?

regards, tom lane

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

[HACKERS] Bitmap index status

[Heikki Linnakangas]

Hi,

What's the status of the bitmap index patch? Have you worked on it since 
the last posted patch 
(http://archives.postgresql.org/pgsql-patches/2006-08/msg3.php)?


I've started to review it, to get it into CVS early in the 8.3 cycle. I 
just want to make sure that I'm working on the latest version.


Beside the issues already discussed, I found two minor bugs:
* pg_am says that bitmap am supports unique indexes, while it doesn't. 
Second,
* race condition in _bitmap_inserttuple if two backends try to insert 
the same, new value. If they both find that there's no lov item for the 
key, and try to create one, one backend will get a duplicate key error 
on the lov index.


Also, vacuum actually does a reindex, which seems awfully wasteful. That 
needs to be looked at.


--
 Heikki Linnakangas
 EnterpriseDB   http://www.enterprisedb.com


---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

  http://www.postgresql.org/docs/faq

Re: [HACKERS] Bitmap index

[Patrick B Kelly]

On Nov 22, 2004, at 2:57 AM, Pawe Niewiadomski wrote:
Hello,
I saw discussion about bitmap indexes few weeks ago. I wonder if
any of you is working on it (in secret)? I will be chosing subject
of my master thesis and thougth about implementing bitmap indexes.
--
**PaweÅ Niewiadomski**, new()foo-baz.com, http://new.foo-baz.com/
PodrÄcznik Administratora Systemu Linux:  http://sag.foo-baz.com/
PodrÄcznik Programisty Systemu Linux: http://lpg.foo-baz.com/
Virtual Qmail (http://v-q.foo-baz.com), qmail-patches 
(http://q-p.foo-baz.com)

---(end of 
broadcast)---
TIP 7: don't forget to increase your free space map settings


I have been looking into this myself but have not had the time to 
attack it. If you are going to pick this up and run with it, please let 
me know how I can help. This would be a great feature to have for data 
warehousing.

Patrick B. Kelly
--
  http://patrickbkelly.org
---(end of broadcast)---
TIP 6: Have you searched our list archives?
  http://archives.postgresql.org

Re: [HACKERS] Bitmap index

[Yann Michel]

Hi,

On Fri, Nov 26, 2004 at 10:25:41AM -, Pawel Niewiadomski wrote:
> 
> My promoter accepted the subject. I'm waiting for an official acceptance
> of the subject. Until then I would want to get familiar with PostgreSQL
> internals and bitmap index implementations. I will appreciate 
> any links to online papers, books that could help me.

That sounds nice! I thought of implementing it as part of my master
thesis next year so I already started reading about bitmap indexing and
so on. A nice start is possibly "Hector Garcia-Mollina" "Database
Implementation". 

Regards,
Yann

---(end of broadcast)---
TIP 4: Don't 'kill -9' the postmaster

Re: [HACKERS] Bitmap index

[Pawel Niewiadomski]

On Wed, 24 Nov 2004 19:26:41 +1100, Neil Conway <[EMAIL PROTECTED]> wrote :

> On Mon, 2004-11-22 at 07:57 +, PaweX Niewiadomski wrote:
> > I saw discussion about bitmap indexes few weeks ago. I wonder if
> > any of you is working on it (in secret)?
> 
> For what it's worth, I don't know of anyone working on them.
> 
> > I will be chosing subject
> > of my master thesis and thougth about implementing bitmap indexes.
> 
> No objection here :)

My promoter accepted the subject. I'm waiting for an official acceptance
of the subject. Until then I would want to get familiar with PostgreSQL
internals and bitmap index implementations. I will appreciate 
any links to online papers, books that could help me.

-- 
**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)


---(end of broadcast)---
TIP 9: the planner will ignore your desire to choose an index scan if your
  joining column's datatypes do not match

Re: [HACKERS] Bitmap index

[Neil Conway]

On Mon, 2004-11-22 at 07:57 +, PaweX Niewiadomski wrote:
> I saw discussion about bitmap indexes few weeks ago. I wonder if
> any of you is working on it (in secret)?

For what it's worth, I don't know of anyone working on them.

> I will be chosing subject
> of my master thesis and thougth about implementing bitmap indexes.

No objection here :)

-Neil



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

[HACKERS] Bitmap index

[Pawe³ Niewiadomski]

Hello,
I saw discussion about bitmap indexes few weeks ago. I wonder if
any of you is working on it (in secret)? I will be chosing subject
of my master thesis and thougth about implementing bitmap indexes.

-- 
**Paweł Niewiadomski**, new()foo-baz.com, http://new.foo-baz.com/
Podręcznik Administratora Systemu Linux:  http://sag.foo-baz.com/
Podręcznik Programisty Systemu Linux: http://lpg.foo-baz.com/
Virtual Qmail (http://v-q.foo-baz.com), qmail-patches (http://q-p.foo-baz.com)


---(end of broadcast)---
TIP 7: don't forget to increase your free space map settings

[HACKERS] Bitmap index

[Hans-Jürgen Schönig]

Hello ...

I remember that somebody was working on some sort of bitmap index some 
time ago (maybe 1 year or two).
Does anybody know if there is some sort of half-ready code or so around?
Does anybody know if there is somebody working on that?

	Regards,

		Hans

--
Cybertec Geschwinde u Schoenig
Schoengrabern 134, A-2020 Hollabrunn, Austria
Tel: +43/2952/30706 or +43/664/233 90 75
www.cybertec.at, www.postgresql.at, kernel.cybertec.at
---(end of broadcast)---
TIP 7: don't forget to increase your free space map settings

Re: [HACKERS] BITMAP Index support (and other DSS info.)

[Sailesh Krishnamurthy]

> "Shahbaz" == Shahbaz Chaudhary <[EMAIL PROTECTED]> writes:

Shahbaz> There are bound to be people in the academia (grad
Shahbaz> students, professors of CS, etc.) on this mailing list,
Shahbaz> yet I see few RDBMS courses using postgresql as an
Shahbaz> example.  If people still have connections to
Shahbaz> universities, it would seem that inviting researchers to
Shahbaz> use PGSQL for their experiments will quickly make it
Shahbaz> comparable to Oracle/etc.  This would be specifically

At Berkeley, PostgreSQL is used for projects in the upper division
undergraduate database systems class. At least it was used this past
Fall, and we plan to use it in the Spring as well (I will be
TA'ng). The projects involved using pg as a back-end and a small
buffer replacement policy assignment.

http://www-inst.eecs.berkeley.edu/~cs186/

In addition, we (the database systems research group) are using the
PostgreSQL code base (7.2.1) to build TelegraphCQ, our new system to
process continuous queries over data streams. Preliminary paper here:

http://www.cs.berkeley.edu/~franklin/Papers/TCQcidr03.pdf

No, it's not really close to a release yet ... :-)

-- 
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh

---(end of broadcast)---
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])

[HACKERS] BITMAP Index support (and other DSS info.)

[Shahbaz Chaudhary]

Hi all,
I've recently started using Postgresql and am impressed with how
complete an RDBMS system it really is.  It seems that while some
corporations may balk at using it for day to day operational use,
bringing in PGSQL for a more niche use will allow many professionals to
see its potential.

One such niche market is decision support systems (DSS).  Doing
something like Sybase IQ on PGSQL (bitmap/bitwise index) would greatly
help exposure.  I noticed that adding BITMAP index is not only on the
TODO list but has also been discussed quite a bit in the past.  I'm not
sure if any one has seen this
http://www.it.iitb.ernet.in/~rvijay/dbms/proj/ , a bitmap index
implementation using GiST!  I, my self, run a DB (about 2 GIG and
growing) with over ten million rows...and the need to be responsive
enough to be used on the web.  This would be great.

I haven't seen this in any of the mailing lists, a new book "PostgreSQL"
by Korry Douglas (comes out in februrary '03)
(http://www.amazon.com/exec/obidos/tg/detail/-/0735712573/qid=1041197382
/sr=1-8/ref=sr_1_8/104-4850283-3895915?v=glance&s=books)  which explains
the internals of PostgreSQL ...good for people who would like to
contribute to this project but haven't done hardcore C/C++ programming
since college (like myself).

There are bound to be people in the academia (grad students, professors
of CS, etc.) on this mailing list, yet I see few RDBMS courses using
postgresql as an example.  If people still have connections to
universities, it would seem that inviting researchers to use PGSQL for
their experiments will quickly make it comparable to Oracle/etc.  This
would be specifically helpful for adding capabilities that are not
considered top priority (time-series DBs...I work in a fiancial firm and
trust me when I say that they spend HUGE amounts of money on software
that does nothing more than what postgresql developers could add:
ordered set of tuples, link to data streams, memory based tables, etc.)

Any way, I hope this isn't considered off-topic :).

Shahbaz C.


---(end of broadcast)---
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

Re: [HACKERS] Bitmap index

[Nathan Myers]

On Mon, Dec 04, 2000 at 04:28:47PM +0100, [EMAIL PROTECTED] wrote:
> 
> on other RDBMS (Oracle,etc...),there is an index called bitmap index
> that greatly improve performance compared to btree index for boolean
> value (such as for a sex value,it's either M or F),i would like to
> know if such index will be implemented inside PostgreSQL.

Yes, please do send in your implementation for review.

Nathan Myers
[EMAIL PROTECTED]

[HACKERS] Bitmap index

[pejac]

Hi,

on other RDBMS (Oracle,etc...),there is an index called bitmap index that
greatly improve performance compared to btree index for boolean value
(such as for a sex value,it's either M or F),i would like to know if such
index will be implemented inside PostgreSQL.

Best regards,

PEJAC Pascal

[HACKERS] Bitmap index

[pejac]

Hi,

on other RDBMS (Oracle,etc...),there is an index called bitmap index that
greatly improve performance compared to btree index for boolean value
(such as for a sex value,it's either M or F),i would like to know if such
index will be implemented inside PostgreSQL.

[HACKERS] Bitmap index

[pejac]

Hello,

Please , excuse me for my bad english.

One question on bitmaps index. In them Commercial data bases (oracle DB2),
Let bitmap type index is supported.This index is used for fields of type sex or 
Boolean generally, would be it(he)
supported in postgres??? If not is foreseen it??? 

Best regards

PEJAC Pascal