Index AM change proposals, redux

I am glad you have summarized this. The details of exactly what was
being proposed was too complex for me to understand before.

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

Tom Lane wrote:

I just finished looking through the various threads about index AM
changes that Bruce has been holding onto in the commit-fest queue.
There seem to be the following issues:

* Proposed change to have amgetmulti return its results by ORing bits
into a caller-supplied TIDBitmap, rather than the current interface
involving an intermediate TID array. The TID-array design was intended
to be agnostic about what would happen on either side of the API, but it
seems that it's really just equally inconvenient for everybody :-(.

Although the original motivation for this was to open a door for bitmap
indexes, it seems to me it's worth doing whether or not bitmap indexes
ever happen. It's logically simpler (only one amgetmulti call per scan)
and should save at least a few cycles. I recommend we just go ahead
with this.

* Proposed change to let both amgetnext and amgetmulti mark returned
tuples as "candidate matches", that is in need of rechecking of quals
against the real heap tuple. I had originally objected to this on
the grounds that it would require setup work that doesn't happen now,
but looking at the code I see that's wrong --- the setup work *does*
happen anyway, see indexqualorig. nodeIndexscan.c comments "The
indexqualorig expression is always initialized even though it will only
be used in some uncommon cases --- would be nice to improve that".
So this complaint is probably a red herring. I'm still a bit concerned
by the fact that the patch only tracks this on a page basis in the
amgetmulti case: if any of the tuples on a page are in-doubt then
everything on the page will have to be rechecked. Is that good enough?

A bigger issue is whether this is worth applying when nobody seems to be
working on either of the main uses for it (bitmap indexes and GIT
indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

* Proposed change to let amgetnext mark returned tuples as not
necessarily in order, requiring somebody downstream to sort them again.
I was pretty desperately unhappy with that because it required injection
of sorting knowledge into code that really shouldn't have anything to do
with it --- not least because not all indexscans even have a defined
ordering. Given that it is only needed for one particular possible
implementation of GIT, and Heikki was leaning away from that
implementation anyway at last report, I vote against considering this
any further.

* Proposed changes to refactor the TIDBitmap support to include a
concept of a "stream bitmap" being read from disk. (Not strictly an
index AM change, but closely related.) While this is clean and nice on
its own, it doesn't seem to have any use unless bitmap indexes happen.
If we leave the code sit it'll probably acquire bit rot, but I'm
disinclined to add a bunch of unused code, too. Thoughts?

* Proposed changes to allow amgetnext to return the actual index keys,
allowing certain types of "unindexable" quals to be checked without
having to fetch the heap entry. For example a LIKE condition could be
fully checked against the index entry. Since certain types of indexes
(GIN now, possibly hash in future) are incapable of doing this, there'd
need to be a way of marking index AMs (or perhaps individual indexes) as
able or not able to return their keys, so that the planner could know
whether quals could be pushed into the indexscan.

We don't have any actual submitted patch for this, but AFAIR everyone
agrees it's a good idea.

* Bitmap indexes themselves. As far as I can tell, this development
effort has stalled because of intractable problems with VACUUM.
Can anyone provide a status update on that?

* GIT (Grouped Index Tuple) indexes, which achieve index space savings
in btrees by having a single index tuple represent multiple heap tuples
(on a single heap page) containing a range of key values. I am not sure
what the development status is --- Heikki had submitted a completed
patch but there seemed to be agreement on making changes, and that's not
been done AFAIK. The really serious problem I've got with it is that
it'd foreclose the possibility of returning actual index keys from btree
indexes, thus basically killing the usefulness of that idea. I'm not
convinced it would offer enough gain to be worth paying that price.
Another issue is that we'd need to check how much of the use-case for
GIT has been taken over by HOT.

* "Thick" indexes containing copies of tuple visibility info. As far
as I'm concerned, this patch isn't going anywhere :-(. It's got the
same showstopper problem as retail vacuum and some of the earlier forms
of the HOT patch: it assumes that during tuple update or delete, it
can re-find the tuple's index entries by re-computing the indexed
expressions. That's just not reliable enough.

Is that a reasonable summary of where we are?

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

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

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

Tom Lane wrote:

* Proposed change to let both amgetnext and amgetmulti mark returned
tuples as "candidate matches", that is in need of rechecking of quals
against the real heap tuple. I had originally objected to this on
the grounds that it would require setup work that doesn't happen now,
but looking at the code I see that's wrong --- the setup work *does*
happen anyway, see indexqualorig. nodeIndexscan.c comments "The
indexqualorig expression is always initialized even though it will only
be used in some uncommon cases --- would be nice to improve that".
So this complaint is probably a red herring. I'm still a bit concerned
by the fact that the patch only tracks this on a page basis in the
amgetmulti case: if any of the tuples on a page are in-doubt then
everything on the page will have to be rechecked. Is that good enough?

I think it's good enough. If we wanted to track it on a per-tuple basis,
we'd need to store two bits per tuple, AFAICS, doubling the size of the
bitmaps.

A bigger issue is whether this is worth applying when nobody seems to be
working on either of the main uses for it (bitmap indexes and GIT
indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

It has some merit on its own. Consider the case where you bitmap AND a
lossy page and a non-lossy one. We currently make the result lossy,
because we can't know which tuples on the page match, and then we need
to recheck all tuples on that page. With the support for candidate
matches, we could instead keep the non-lossy version of the bitmap and
mark the matches as candidates.

In the very best case, we might even apply a further AND to the page,
which eliminates all the remaining candidate matches, and skip the heap
access of that page altogether.

* Proposed change to let amgetnext mark returned tuples as not
necessarily in order, requiring somebody downstream to sort them again.
I was pretty desperately unhappy with that because it required injection
of sorting knowledge into code that really shouldn't have anything to do
with it --- not least because not all indexscans even have a defined
ordering. Given that it is only needed for one particular possible
implementation of GIT, and Heikki was leaning away from that
implementation anyway at last report, I vote against considering this
any further.

Agreed, there's no use for that without GIT.

* Proposed changes to refactor the TIDBitmap support to include a
concept of a "stream bitmap" being read from disk. (Not strictly an
index AM change, but closely related.) While this is clean and nice on
its own, it doesn't seem to have any use unless bitmap indexes happen.
If we leave the code sit it'll probably acquire bit rot, but I'm
disinclined to add a bunch of unused code, too. Thoughts?

If the code is unused, it can easily bit rot even if it's in CVS. Let's
not apply it. The patch is out there if/when someone picks up the bitmap
index patch again.

* Proposed changes to allow amgetnext to return the actual index keys,
allowing certain types of "unindexable" quals to be checked without
having to fetch the heap entry. For example a LIKE condition could be
fully checked against the index entry. Since certain types of indexes
(GIN now, possibly hash in future) are incapable of doing this, there'd
need to be a way of marking index AMs (or perhaps individual indexes) as
able or not able to return their keys, so that the planner could know
whether quals could be pushed into the indexscan.

We don't have any actual submitted patch for this, but AFAIR everyone
agrees it's a good idea.

Agreed :-).

* GIT (Grouped Index Tuple) indexes, which achieve index space savings
in btrees by having a single index tuple represent multiple heap tuples
(on a single heap page) containing a range of key values. I am not sure
what the development status is --- Heikki had submitted a completed
patch but there seemed to be agreement on making changes, and that's not
been done AFAIK. The really serious problem I've got with it is that
it'd foreclose the possibility of returning actual index keys from btree
indexes, thus basically killing the usefulness of that idea. I'm not
convinced it would offer enough gain to be worth paying that price.
Another issue is that we'd need to check how much of the use-case for
GIT has been taken over by HOT.

I don't think there's much overlap with HOT. On the contrary, HOT makes
GIT much more useful, because GIT was very sensitive to the cluster
order of the heap, and HOT helps with that.

There is, however, a ton of overlap with index-only scans, and the
possibility to return keys from indexes, as you pointed out.

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

* Proposed changes to allow amgetnext to return the actual index keys,
allowing certain types of "unindexable" quals to be checked without
having to fetch the heap entry. For example a LIKE condition could be
fully checked against the index entry.

In the extreme we could build tuples and push them up several nodes -- even
including joins -- before fetching the rest of the attributes from the heap.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training!

* Proposed change to let both amgetnext and amgetmulti mark returned
tuples as "candidate matches", that is in need of rechecking of quals

indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

This is good way to eliminate awful operation '@@@' without performance loss.

* Proposed changes to allow amgetnext to return the actual index keys,
allowing certain types of "unindexable" quals to be checked without
having to fetch the heap entry. For example a LIKE condition could be
fully checked against the index entry. Since certain types of indexes
(GIN now, possibly hash in future) are incapable of doing this, there'd

GiST too, because type of storage may be differ from type to be indexed. The
same touches GIN too.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

* GIT (Grouped Index Tuple) indexes, which achieve index space savings
in btrees by having a single index tuple represent multiple heap

tuples

(on a single heap page) containing a range of key values. I am not

sure

what the development status is --- Heikki had submitted a completed
patch but there seemed to be agreement on making changes, and that's

not

been done AFAIK. The really serious problem I've got with it is that
it'd foreclose the possibility of returning actual index keys from

btree

indexes, thus basically killing the usefulness of that idea. I'm not
convinced it would offer enough gain to be worth paying that price.
Another issue is that we'd need to check how much of the use-case for
GIT has been taken over by HOT.

I do not see the serious problem ? The one key that is stored would
represent all tuples it points to. So the interface could eighter
be designed to allow skipping the key in one go, or return the same
key repeatedly. All that the second approach would need is return
the key and the heap tuple pointer in two different vars.

Andreas

"Zeugswetter Andreas OSB SD" <Andreas.Zeugswetter@s-itsolutions.at> writes:

... The really serious problem I've got with it is that
it'd foreclose the possibility of returning actual index keys from btree
indexes, thus basically killing the usefulness of that idea. I'm not
convinced it would offer enough gain to be worth paying that price.

I do not see the serious problem ? The one key that is stored would
represent all tuples it points to.

No, the entry represents a range of values for which the one key is the
lower bound. You don't know just what the keys are for the other
tuples, unless you go to the heap and look.

We could restrict GIT to only represent tuples with exactly the same
key, but that takes away a whole lot of its use-case (especially so
now that HOT is in there).

regards, tom lane

Teodor Sigaev <teodor@sigaev.ru> writes:

* Proposed change to let both amgetnext and amgetmulti mark returned
tuples as "candidate matches", that is in need of rechecking of quals
...
indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

This is good way to eliminate awful operation '@@@' without performance loss.

Oh yeah, that kluge :-(. Okay, that's probably a sufficient reason
all by itself.

* Proposed changes to allow amgetnext to return the actual index keys,
allowing certain types of "unindexable" quals to be checked without
having to fetch the heap entry. For example a LIKE condition could be
fully checked against the index entry. Since certain types of indexes
(GIN now, possibly hash in future) are incapable of doing this, there'd

GiST too, because type of storage may be differ from type to be indexed. The
same touches GIN too.

Is this the case for *all* GiST and GIN indexes, or might we need a
per-index (rather than per-AM) flag to tell whether the original keys
are available?

regards, tom lane

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

A bigger issue is whether this is worth applying when nobody seems to be
working on either of the main uses for it (bitmap indexes and GIT
indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

It has some merit on its own.

Yeah, and Teodor's point about cleaning up the @@@ hack pretty much
seals the deal for me.

Unless anyone has objections, I will review and apply Heikki's patch
http://archives.postgresql.org/pgsql-patches/2007-03/msg00163.php
which covers both the amgetmulti return-a-bitmap change and the
candidate-matches change. (Heiiki, you don't have a later version
of that do you?)

The remaining topics associated with index AMs are closed for this
commit fest, unless anyone has specific questions they want discussed
right now...

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

A bigger issue is whether this is worth applying when nobody seems to be
working on either of the main uses for it (bitmap indexes and GIT
indexes). There seemed to be some possible marginal use for it in GIST
indexes, but I'm not convinced that's a sufficient reason to complicate
the APIs.

It has some merit on its own.

Yeah, and Teodor's point about cleaning up the @@@ hack pretty much
seals the deal for me.

Unless anyone has objections, I will review and apply Heikki's patch
http://archives.postgresql.org/pgsql-patches/2007-03/msg00163.php
which covers both the amgetmulti return-a-bitmap change and the
candidate-matches change. (Heiiki, you don't have a later version
of that do you?)

The remaining topics associated with index AMs are closed for this
commit fest, unless anyone has specific questions they want discussed
right now...

OK, do you want the items moved to the next commit-fest, discarded, or
made into TODOs? And which ones? Or do you want to do it?

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

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

GiST too, because type of storage may be differ from type to be indexed. The
same touches GIN too.

Is this the case for *all* GiST and GIN indexes, or might we need a
per-index (rather than per-AM) flag to tell whether the original keys
are available?

Ughm. GiST and GIN are different here. For GiST it is clear that is per index
flag:
- rtree emulation over box stores original values
- rtree emulation over points or circles, btree_gist, ltree stores modified
original value which can be restored from index with call of specific
function
- tsvector opclass doesn't have this possibility at all
So, only rtree emulation over box is able to return original value from index.
For GIN index I know only one opclass where it's possible to get original value,
it's a wildspeed, but in any case that requires some transformation before.
However, it's possible to develop opclass for GIN which will be similar to
classic Btree, for indexing scalar values.

Both GIN and GiST make a call of transformation function before indexing value.
I suppose, there is no automatic way to set this flag even in case when type of
storage and type of indexing value are the same.

So, I see three variant:
- add flag in pg_am
- add flag to create operator class and by default it should point to
impossibility to get value from index. At least for GIN and GiST.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Bruce Momjian <bruce@momjian.us> writes:

Tom Lane wrote:

The remaining topics associated with index AMs are closed for this
commit fest, unless anyone has specific questions they want discussed
right now...

OK, do you want the items moved to the next commit-fest, discarded, or
made into TODOs? And which ones? Or do you want to do it?

TODOs for each of the open items I listed in my summary, please.
They aren't material for the next commit fest until someone does more
work.

regards, tom lane

Teodor Sigaev <teodor@sigaev.ru> writes:

Both GIN and GiST make a call of transformation function before indexing value.
I suppose, there is no automatic way to set this flag even in case when type of
storage and type of indexing value are the same.

So, I see three variant:
- add flag in pg_am
- add flag to create operator class and by default it should point to
impossibility to get value from index. At least for GIN and GiST.

Yeah, just as messy as I feared :-(. My inclination for the first pass
would be to just make it a per-AM flag in pg_am. We could always
complicate matters later.

(Of course, this is all hypothetical since no patch is on the
horizon...)

regards, tom lane

Yeah, just as messy as I feared :-(. My inclination for the first pass
would be to just make it a per-AM flag in pg_am. We could always
complicate matters later.

Agree, and the single existing suitable opclass hasn't operation marked with
RECHECK flag.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Tom Lane wrote:

Yeah, and Teodor's point about cleaning up the @@@ hack pretty much
seals the deal for me.

Note that we'll need to add candidate match support to the regular index
scan API as well for that.

Unless anyone has objections, I will review and apply Heikki's patch
http://archives.postgresql.org/pgsql-patches/2007-03/msg00163.php
which covers both the amgetmulti return-a-bitmap change and the
candidate-matches change.

Ok. Thank you!

(Heiiki, you don't have a later version of that do you?)

Nope.

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

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

Yeah, and Teodor's point about cleaning up the @@@ hack pretty much
seals the deal for me.

Note that we'll need to add candidate match support to the regular index
scan API as well for that.

[ confused... ] Thought you'd done that in this patch?

(Heiiki, you don't have a later version of that do you?)

Nope.

Going through my mailbox, I found Alexey Klyukin's update:
http://archives.postgresql.org/pgsql-patches/2007-06/msg00204.php
Did you look at his version at all?

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Note that we'll need to add candidate match support to the regular index
scan API as well for that.

[ confused... ] Thought you'd done that in this patch?

No, I only modified the bitmap scan API.

(Heiiki, you don't have a later version of that do you?)

Nope.

Going through my mailbox, I found Alexey Klyukin's update:
http://archives.postgresql.org/pgsql-patches/2007-06/msg00204.php
Did you look at his version at all?

Oh, I didn't remember that exists at all. It looks good at first glance,
though it's missing the doc changes of the original.

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

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

Note that we'll need to add candidate match support to the regular index
scan API as well for that.

[ confused... ] Thought you'd done that in this patch?

No, I only modified the bitmap scan API.

Okay. I applied what you'd done (with minor revisions), but we'll have
to fix up the regular indexscan API before anything can be done about
@@@. I'll take a look at that part tomorrow.

Teodor, do you have any thoughts about exactly how you'd fix @@@ ?
I suppose that the recheck-need is not really a property of specific
tuples, but of a particular query, for that case. Where would you
want to detect that?

regards, tom lane

... The really serious problem I've got with it is that
it'd foreclose the possibility of returning actual index keys from

btree

indexes, thus basically killing the usefulness of that idea. I'm

not

convinced it would offer enough gain to be worth paying that price.

I do not see the serious problem ? The one key that is stored would
represent all tuples it points to.

No, the entry represents a range of values for which the one key is

the

lower bound. You don't know just what the keys are for the other
tuples, unless you go to the heap and look.

Thanks for explaining. I think that idea stands in the way of future
improvements and should be dropped, yes.

We could restrict GIT to only represent tuples with exactly the same
key, but that takes away a whole lot of its use-case (especially so
now that HOT is in there).

Ok, I was forgetting pg's outstanding "partial index" feature.
In pg you will most likely exclude highly duplicate keys from the index.
Since other dbs don't have this feature, it is common to have highly
duplicate keys (millions) there (unless you use very ugly workarounds).

I agree that the possibility of returning actual index keys and
filtering
rows early has more merrit. It could also be used to skip forward, when
the
qual misses middle key columns.

I do still see compressing exactly equal keys (or exactly equal parts),
but not restricted to the same heap page, as a useful btree TODO
(especially for long non unique keys).
But it may really not be so important in pg.

Andreas

Teodor, do you have any thoughts about exactly how you'd fix @@@ ?
I suppose that the recheck-need is not really a property of specific
tuples, but of a particular query, for that case. Where would you
want to detect that?

tsquery may include restriction by weight of search terms: 'sea & port:A'. GIN
index doesn't store information about weights, so the only difference between @@
and @@@ is that @@@ is marked with RECHECK flag. I think, the better way is set
flag about required recheck by looking value from index, not for tsquery. It
gives to us more flexibility.

So, I planned to add pointer to bool to consistent method, so signature will be
bool consistent( bool check[], StrategyNumber n, Datum query, bool *needRecheck)

Returning value of needRecheck should be ignored for operation not marked by
RECHECK flag in opclass. needRecheck should be initialized to true before call
of consistent method to keep compatibility with old opclasses.

To define, is recheck needed or not, the better way is to check actually needed
values. For example, let tsquery is equal to
'foo | bar | qq:A' and tsvetor = 'foo:1,2,3 asdasdasd:4'. Obviously recheck is
not needed. So patch is close to trivial:

*** tsginidx.c.orig     2008-04-11 17:08:37.000000000 +0400
--- tsginidx.c  2008-04-11 17:18:45.000000000 +0400
***************
*** 109,114 ****
--- 109,115 ----
   {
         QueryItem  *frst;
         bool       *mapped_check;
+       bool       *needRecheck;
   } GinChkVal;

   static bool
***************
*** 116,121 ****
--- 117,125 ----
   {
         GinChkVal  *gcv = (GinChkVal *) checkval;

+       if ( val->weight )
+               *(gcv->needRecheck) = true;
+
         return gcv->mapped_check[((QueryItem *) val) - gcv->frst];
   }

***************
*** 144,149 ****
--- 148,155 ----

                 gcv.frst = item = GETQUERY(query);
                 gcv.mapped_check = (bool *) palloc(sizeof(bool) * query->size);
+               gcv.needRecheck = PG_GETARG_POINTER(3);
+               *(gcv.needRecheck) = false;

for (i = 0; i < query->size; i++)
if (item[i].type == QI_VAL)

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/