Bitmapscan changes

Heikki Linnakangas <heikki@enterprisedb.com> writes:

The patch also adds support for candidate matches. An index scan can
indicate that the tuples it's returning are candidates, and the executor
will recheck the original scan quals of any candidate matches when the
tuple is fetched from heap.

This will not work, unless we change the planner --- the original quals
aren't necessarily there in some corner cases (partial indexes, if
memory serves).

The motivation for adding the support for candidate matches is that GIT
/ clustered indexes need it.

You need more than a vague reference to an unapplied patch to convince
me we ought to do this.

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

The patch also adds support for candidate matches. An index scan can
indicate that the tuples it's returning are candidates, and the executor
will recheck the original scan quals of any candidate matches when the
tuple is fetched from heap.

This will not work, unless we change the planner --- the original quals
aren't necessarily there in some corner cases (partial indexes, if
memory serves).

This is only for bitmap scans, which *do* always have the original quals
available in the executor (BitmapHeapScanState.bitmapqualorig).
That's because we have to recheck the original conditions when the
bitmap goes lossy.

To support candidate matches with the amgettuple API, that'll need to be
changed as well. And that will indeed involve more executor changes.

The motivation for adding the support for candidate matches is that GIT
/ clustered indexes need it.

You need more than a vague reference to an unapplied patch to convince
me we ought to do this.

With the unapplied GIT patch, the index doesn't store the index key of
every tuple. That has the consequence that when scanning, we get a bunch
of tids to a heap page, we know that some of the might match, but we
don't know which ones until the tuples are fetched from heap.

In a more distant future, range-encoded bitmap indexes will also produce
candidate matches. And as I mentioned, this is immediately useful when
doing bitmap ANDs large enough to go lossy.

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

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

This will not work, unless we change the planner --- the original quals
aren't necessarily there in some corner cases (partial indexes, if
memory serves).

This is only for bitmap scans, which *do* always have the original quals
available in the executor (BitmapHeapScanState.bitmapqualorig).
That's because we have to recheck the original conditions when the
bitmap goes lossy.

Yeah, but the index AM has to support regular indexscans too, and those
are not prepared for runtime lossiness determination; nor am I
particularly willing to add that.

With the unapplied GIT patch, the index doesn't store the index key of
every tuple.

I thought the design was to eliminate *duplicate* keys from the index.
Not to lose data.

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

This will not work, unless we change the planner --- the original quals
aren't necessarily there in some corner cases (partial indexes, if
memory serves).

This is only for bitmap scans, which *do* always have the original quals
available in the executor (BitmapHeapScanState.bitmapqualorig).
That's because we have to recheck the original conditions when the
bitmap goes lossy.

Yeah, but the index AM has to support regular indexscans too, and those
are not prepared for runtime lossiness determination; nor am I
particularly willing to add that.

Well, do you have an alternative suggestion?

With the unapplied GIT patch, the index doesn't store the index key of
every tuple.

I thought the design was to eliminate *duplicate* keys from the index.
Not to lose data.

The idea *isn't* to deal efficiently with duplicate keys. The bitmap
indexam is better suited for that.

The idea really is to lose information from the leaf index pages, in
favor of a drastically smaller index. On a completely clustered table,
the heap effectively is the leaf level of the index.

I'm glad we're having this conversation now. I'd really appreciate
review of the design. I've been posting updates every now and then,
asking for comments, but never got any. If you have suggestions, I'm all
ears and I still have some time left before feature freeze to make changes.

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

Heikki Linnakangas <heikki@enterprisedb.com> writes:

With the unapplied GIT patch, the index doesn't store the index key of
every tuple.

I thought the design was to eliminate *duplicate* keys from the index.
Not to lose data.

The idea really is to lose information from the leaf index pages, in
favor of a drastically smaller index. On a completely clustered table,
the heap effectively is the leaf level of the index.

I'm really dubious that this is an intelligent way to go. In the first
place, how will you keep the index sorted if you can't determine the
values of all the keys? It certainly seems that this would break the
ability to have a simple indexscan return sorted data, even if the index
itself doesn't get corrupted. In the second place, this seems to
forever kill the idea of indexscans that don't visit the heap --- not
that we have any near-term prospect of doing that, but I know a lot of
people remain interested in the idea.

The reason this catches me by surprise is that you've said several times
that you intended GIT to be something that could just be enabled
universally. If it's lossy then there's a much larger argument that not
everyone would want it.

regards, tom lane

Tom Lane wrote:

I'm really dubious that this is an intelligent way to go. In the first
place, how will you keep the index sorted if you can't determine the
values of all the keys? It certainly seems that this would break the
ability to have a simple indexscan return sorted data, even if the index
itself doesn't get corrupted.

That's indeed a very fundamental thing with the current design. The
index doesn't retain the complete order within heap pages. That
information is lost, again in favor of a smaller index size. It incurs a
significant CPU overhead, but on an I/O bound system that's a tradeoff
you want to make.

At the moment, I'm storing the offsets within the heap in a bitmap
attached to the index tuple. btgettuple fetches all the heap tuples
represented by the grouped index tuple, checks their visibility, sorts
them into index order, and returns them to the caller one at a time.
Thats ugly, API-wise, because it makes the indexam to actually go look
at the heap, which it shouldn't have to deal with.

Another approach I've been thinking of is to store a list of offsets, in
index order. That would avoid the problem of returning sorted data, and
reduce the CPU overhead incurred by sorting and scanning, at the cost of
much larger (but still much smaller than what we have now) index.

In the second place, this seems to
forever kill the idea of indexscans that don't visit the heap --- not
that we have any near-term prospect of doing that, but I know a lot of
people remain interested in the idea.

I'm certainly interested in that. It's not really needed for clustered
indexes, though. A well-clustered index is roughly one level shallower,
and the heap effectively is the leaf-level, therefore the amount of I/O
you need to fetch the index tuple + heap tuple, is roughly the same that
as fetching just the index tuple from a normal b-tree index.

On non-clustered indexes, index-only scans would of course still be useful.

The reason this catches me by surprise is that you've said several times
that you intended GIT to be something that could just be enabled
universally. If it's lossy then there's a much larger argument that not
everyone would want it.

Yeah, we can't just always enable it by default. While a clustered index
would degrade to a normal b-tree when the heap isn't clustered, you
would still not want to always enable the index clustering because of
the extra CPU overhead. That has become clear in the CPU bound tests
I've run.

I think we could still come up with some safe condiitions when we could
enable it by default, though. In particular, I've been thinking that if
you run CLUSTER on a table, you'd definitely want to use a clustered
index as well.

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

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

In the second place, this seems to
forever kill the idea of indexscans that don't visit the heap --- not
that we have any near-term prospect of doing that, but I know a lot of
people remain interested in the idea.

I'm certainly interested in that. It's not really needed for clustered
indexes, though. A well-clustered index is roughly one level shallower,
and the heap effectively is the leaf-level, therefore the amount of I/O
you need to fetch the index tuple + heap tuple, is roughly the same that
as fetching just the index tuple from a normal b-tree index.

That argument ignores the fact that the heap entries are likely to be
much wider than the index entries, due to having other columns in them.

I think we could still come up with some safe condiitions when we could
enable it by default, though.

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just how
much territory is going to be left for this between HOT and bitmap indexes?
I particularly dislike the idea of having the index AM reaching directly
into the heap --- we should be trying to get rid of that, not add more
cases.

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

In the second place, this seems to
forever kill the idea of indexscans that don't visit the heap --- not
that we have any near-term prospect of doing that, but I know a lot of
people remain interested in the idea.

I'm certainly interested in that. It's not really needed for clustered
indexes, though. A well-clustered index is roughly one level shallower,
and the heap effectively is the leaf-level, therefore the amount of I/O
you need to fetch the index tuple + heap tuple, is roughly the same that
as fetching just the index tuple from a normal b-tree index.

That argument ignores the fact that the heap entries are likely to be
much wider than the index entries, due to having other columns in them.

True, that's the "roughly" part. It does indeed depend on your schema.
As a data point, here's the index sizes (in pages) of a 140 warehouse
TPC-C database:

index name normal grouped % of normal size
--------------------------------------
i_customer 31984 29250 91.5%
i_orders 11519 11386 98.8%
pk_customer 11519 1346 11.6%
pk_district 6 2
pk_item 276 10 3.6%
pk_new_order 3458 42 1.2%
pk_order_line 153632 2993 1.9%
pk_orders 11519 191 1.7%
pk_stock 38389 2815 7.3%
pk_warehouse 8 2

The customer table is an example of pretty wide table, there's only ~12
tuples per page. pk_customer is still benefiting a lot. i_customer and
i_orders are not benefiting because the tables are not in the index
order. The orders-related indexes are seeing the most benefit, they
don't have many columns.

I think we could still come up with some safe condiitions when we could
enable it by default, though.

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just how
much territory is going to be left for this between HOT and bitmap indexes?

I don't see how HOT is overlapping with clustered indexes. On the
contrary, it makes clustered indexes work better, because it reduces the
amount of index inserts needed and helps to keep a table clustered.

The use cases for bitmap indexes and clustered indexes do overlap
somewhat. But clustered indexes have an edge because:
- there's no requirement of having only a small number of distinct values
- they support uniqueness checks
- you can efficiently have a mixture of grouped and non-grouped tuples,
if your table is only partly clustered

In general, clustered indexes are more suited for OLTP work than bitmap
indexes.

I particularly dislike the idea of having the index AM reaching directly
into the heap --- we should be trying to get rid of that, not add more
cases.

I agree. The right way would be to add support for partial ordering and
candidate matches to the indexam API, and move all the sorting etc.
ugliness out of the indexam. That's been on my TODO since the beginning.

If you're still not convinced that we want this at all, how would you
feel about the another approach I described? The one where the
in-heap-page order is stored in the index tuples, so there's no need for
sorting, at the cost of losing part of the I/O benefit.

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

Heikki Linnakangas wrote:

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

In the second place, this seems to
forever kill the idea of indexscans that don't visit the heap --- not
that we have any near-term prospect of doing that, but I know a lot of
people remain interested in the idea.

I'm certainly interested in that. It's not really needed for
clustered indexes, though. A well-clustered index is roughly one
level shallower, and the heap effectively is the leaf-level,
therefore the amount of I/O you need to fetch the index tuple + heap
tuple, is roughly the same that as fetching just the index tuple from
a normal b-tree index.

That argument ignores the fact that the heap entries are likely to be
much wider than the index entries, due to having other columns in them.

True, that's the "roughly" part. It does indeed depend on your schema.
As a data point, here's the index sizes (in pages) of a 140 warehouse
TPC-C database:

Ah, I see now that you didn't (necessarily) mean that the clustering
becomes inefficient at reducing the index size on wider tables, but that
there's much more heap pages than leaf pages in a normal index. That's
true, you might not want to use clustered index in that case, to allow
index-only scans. If we had that feature, that is.

Often, though, when using index-only scans, columns are added to the
index to allow them to be returned in an index-only scans. That narrows
the gap a bit.

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

On Mon, 2007-03-12 at 13:56 -0400, Tom Lane wrote:

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just
how much territory is going to be left for this between HOT and bitmap
indexes?

HOT and clustered indexes have considerable synergy. In many tests we've
got +20% performance with them acting together. Neither one achieves
this performance on their own, but together they work very well.

There is an overlap between clustered and bitmap indexes, but they come
at the problem from different ends of the scale. Bitmap indexes are
designed to cope well with highly non-unique data, while clustered
indexes optimise for unique or somewhat unique keys. The difference is
really bitmap for DW and clustered indexes for OLTP.

The ideas for bitmap indexes come from research and other RDBMS
implementations. Clustered indexes have also got external analogs - the
concepts are very similar to SQLServer Clustered Indexes and Teradata
Primary Indexes (Block Index structure), as well as being reasonably
close to Oracle's Index Organised Tables.

Clustered indexes offer a way to reduce index size to 1-5% of normal
b-tree sizes, yet still maintaining uniqueness checking capability. For
VLDB, that is a win for either OLTP or DW - think about a 1 TB index
coming down to 10-50 GB in size. The benefit is significant for most
tables over a ~1 GB in size through I/O reduction on leaf pages.

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

Simon Riggs wrote:

On Mon, 2007-03-12 at 13:56 -0400, Tom Lane wrote:

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just
how much territory is going to be left for this between HOT and bitmap
indexes?

HOT and clustered indexes have considerable synergy. In many tests we've
got +20% performance with them acting together. Neither one achieves
this performance on their own, but together they work very well.

To clarify, Simon is talking about DBT-2 tests we run in November.
Clustered indexes don't require HOT per se, but on TPC-C the performance
benefit comes from reducing the amount of I/O on the stock table and
index, and that's a table that gets updated at a steady rate. Without
HOT, the updates will disorganize the table and the performance gain you
get from clustered indexes vanishes after a while.

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

On Mon, 12 Mar 2007, Heikki Linnakangas wrote:

Here's a patch to change the amgetmulti API so that it's called only
once per scan, and the indexam adds *all* matching tuples at once to a
caller-supplied TIDBitmap. Per Tom's proposal in July 2006:
http://archives.postgresql.org/pgsql-hackers/2006-07/msg01233.php

I incorporated something like your change to gistnext(). This is much
better, for the reason Teodor mentions up thread.

The return type of gistnext() is int and it is possible that it could
overflow (on some platforms) now that there is no max_tids.

Thanks,

Gavin

Tom Lane wrote:

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just how
much territory is going to be left for this between HOT and bitmap indexes?

I'm in a awkward situation right now. I've done my best to describe the
use cases for clustered indexes. I know the patch needs refactoring,
I've refrained from making API changes and tried to keep all the
ugliness inside the b-tree, knowing that there's changes to the indexam
API coming from the bitmap index patch as well.

I've been seeking for comments on the design since November, knowing
that this is a non-trivial change. I have not wanted to spend too much
time polishing the patch, in case I need to rewrite it from scratch
because of some major design flaw or because someone comes up with a
much better idea.

It's frustrating to have the patch dismissed at this late stage on the
grounds of "it's not worth it". As I said in February, I have the time
to work on this, but if major changes are required to the current
design, I need to know.

Just to recap the general idea: reduce index size taking advantage of
clustering in the heap.

Clustered indexes have roughly the same performance effect and use cases
as clustered indexes on MS SQL Server, and Index-Organized-Tables on
Oracle, but the way I've implemented them is significantly different. On
other DBMSs, the index and heap are combined to a single b-tree
structure. The way I've implemented them is less invasive, there's no
changes to the heap for example, and it doesn't require moving live tuples.

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

Ühel kenal päeval, K, 2007-03-14 kell 10:22, kirjutas Heikki
Linnakangas:

Tom Lane wrote:

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just how
much territory is going to be left for this between HOT and bitmap indexes?

I'm in a awkward situation right now. I've done my best to describe the
use cases for clustered indexes.

...

Just to recap the general idea: reduce index size taking advantage of
clustering in the heap.

Clustered indexes have roughly the same performance effect and use cases
as clustered indexes on MS SQL Server, and Index-Organized-Tables on
Oracle, but the way I've implemented them is significantly different. On
other DBMSs, the index and heap are combined to a single b-tree
structure. The way I've implemented them is less invasive, there's no
changes to the heap for example, and it doesn't require moving live tuples.

Do you keep visibility info in the index ?

How does this info get updated when visibility data changes in the
heap ?

If there is no visibility data in index, then I can't see, how it gets
the same performance effect as Index-Organized-Tables, as lot of random
heap access is still needed.

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

Hannu Krosing wrote:

Ühel kenal päeval, K, 2007-03-14 kell 10:22, kirjutas Heikki
Linnakangas:

Tom Lane wrote:

At this point I'm feeling unconvinced that we want it at all. It's
sounding like a large increase in complexity (both implementation-wise
and in terms of API ugliness) for a fairly narrow use-case --- just how
much territory is going to be left for this between HOT and bitmap indexes?

I'm in a awkward situation right now. I've done my best to describe the
use cases for clustered indexes.

...

Just to recap the general idea: reduce index size taking advantage of
clustering in the heap.

This is what I suggest.

Provide a tarball of -head with the patch applied.

Provide a couple of use cases that can be run with explanation of how to
verify the use cases.

Allow the community to drive the inclusion by making it as easy as
possible to allow a proactive argument to take place by the people
actually using the product.

Proving that a user could and would use the feature is something that is
a very powerful argument.

Sincerely,

Joshua D. Drake

--

=== The PostgreSQL Company: Command Prompt, Inc. ===
Sales/Support: +1.503.667.4564 || 24x7/Emergency: +1.800.492.2240
Providing the most comprehensive PostgreSQL solutions since 1997
http://www.commandprompt.com/

Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
PostgreSQL Replication: http://www.commandprompt.com/products/

Joshua D. Drake wrote:

Allow the community to drive the inclusion by making it as easy as
possible to allow a proactive argument to take place by the people
actually using the product.

This seems to be a rather poor decision making process: "Are the users
happy with the new feature? If so, then apply the patch." It leads to
unmanageable code.

Which is why we don't do things that way. The code must fit within the
general architecture before application -- particularly if it's an
internal API change. That's what the review process is for.

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

Alvaro Herrera wrote:

Joshua D. Drake wrote:

Allow the community to drive the inclusion by making it as easy as
possible to allow a proactive argument to take place by the people
actually using the product.

This seems to be a rather poor decision making process: "Are the users
happy with the new feature? If so, then apply the patch." It leads to
unmanageable code.

Perhaps reading my message again is in order. I think it is pretty
obvious that the a user shouldn't determine if a patch should be applied.

My whole point was that if people are clamoring for the feature, it
could drive that feature to be more aggressively reviewed.

I can't even count how many times I see:

This seems like a corner case feature, I don't think we should add it.

So I am suggesting a way to insure that the feature is not considered
corner case. (if it is indeed not a corner case)

Sincerely,

Joshua D. Drake

--

=== The PostgreSQL Company: Command Prompt, Inc. ===
Sales/Support: +1.503.667.4564 || 24x7/Emergency: +1.800.492.2240
Providing the most comprehensive PostgreSQL solutions since 1997
http://www.commandprompt.com/

Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
PostgreSQL Replication: http://www.commandprompt.com/products/

Hannu Krosing wrote:

Ühel kenal päeval, K, 2007-03-14 kell 10:22, kirjutas Heikki
Linnakangas:

Clustered indexes have roughly the same performance effect and use cases
as clustered indexes on MS SQL Server, and Index-Organized-Tables on
Oracle, but the way I've implemented them is significantly different. On
other DBMSs, the index and heap are combined to a single b-tree
structure. The way I've implemented them is less invasive, there's no
changes to the heap for example, and it doesn't require moving live tuples.

Do you keep visibility info in the index ?

No.

If there is no visibility data in index, then I can't see, how it gets
the same performance effect as Index-Organized-Tables, as lot of random
heap access is still needed.

Let me illustrate the effect in the best case, with a table that
consists of just the key:

Normal b-tree:

Root -> leaf -> heap

aaa -> aaa -> aaa
bbb -> bbb
ccc -> ccc
ddd -> ddd -> ddd
eee -> eee
fff -> fff
ggg -> ggg -> ggg
hhh -> hhh
iii -> iii

Clustered b-tree:

Root -> heap

aaa -> aaa
bbb
ccc
ddd -> ddd
eee
fff
ggg -> ggg
hhh
iii

The index is much smaller, one level shallower in the best case. A
smaller index means that more of it fits in cache. If you're doing
random access through the index, that means that you need to do less I/O
because you don't need to fetch so many index pages. You need to access
the heap anyway for the visibility information, as you pointed out, but
the savings are coming from having to do less index I/O.

How close to the best case do you get in practice? It depends on your
schema, narrow tables or tables with wide keys gain the most, and on the
clusteredness of the table.

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

Alvaro Herrera wrote:

Which is why we don't do things that way. The code must fit within the
general architecture before application -- particularly if it's an
internal API change. That's what the review process is for.

Yes, of course. As I've said, I have the time to work on this, but I
need get the review process *started*. Otherwise I'll just tweak and
polish the patch for weeks, and end up with something that gets rejected
in the end anyway.

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