Thread: Indirect indexes

I propose we introduce the concept of "indirect indexes".  I have a toy
implementation and before I go further with it, I'd like this assembly's
input on the general direction.

Indirect indexes are similar to regular indexes, except that instead of
carrying a heap TID as payload, they carry the value of the table's
primary key.  Because this is laid out on top of existing index support
code, values indexed by the PK can only be six bytes long (the length of
ItemPointerData); in other words, 281,474,976,710,656 rows are
supported, which should be sufficient for most use cases.[1]

A new flag is added to the index AM routine, indicating whether it can
support indirect indexes.  Initially, only the b-tree AM would support
indirect indexes, but I plan to develop support for GIN indirect soon
afterwards, which seems most valuable.

To create an indirect index, the command   CREATE INDIRECT INDEX
is used.  Currently this always uses the defined primary key index[2].

Implementation-wise, to find a value using an indirect index that index
is scanned first; this produces a PK value, which can be used to scan
the primary key index, the result of which is returned.

There are two big advantages to indirect indexes, both of which are
related to UPDATE's "write amplification":

1. UPDATE is faster.  Indirect indexes on column that are not modified  by the update do not need to be updated.
2. HOT can be used more frequently.  Columns indexed only by indirect  indexes do not need to be considered for whether
anupdate needs to  be non-HOT, so this further limits "write amplification".
 

The biggest downside is that in order to find out a heap tuple using the
index we need to descend two indexes (the indirect and the PK) instead
of one, so it's slower.  For many use cases the tradeoff is justified.

I measured the benefits with the current prototype implementation.  In
two separate schemas, I created a pgbench_accounts table, with 12
"filler" columns, and indexed them all; one schema used regular indexes,
the other used indirect indexes.  Filled them both to the equivalent of
scale 50, which results in a table of some 2171 MB; the 12 indexes are
282 MB each, and the PK index is 107 MB).  I then ran a pgbench with a
custom script that update a random one of those columns and leave the
others alone on both schemas (not simultaneously).  I ran 100k updates
for each case, 5 times:
 method  │   TPS: min / avg (stddev) / max   │        Duration: min / avg / max        │ avg_wal 
──────────┼───────────────────────────────────┼─────────────────────────────────────────┼─────────direct   │  601.2 /
1029.9( 371.9) / 1520.9 │ 00:01:05.76 / 00:01:48.58 / 00:02:46.39 │ 4841 MBindirect │ 2165.1 / 3081.6 ( 574.8) / 3616.4
│00:00:27.66 / 00:00:33.56 / 00:00:46.2  │ 1194 MB
 
(2 rows)

This is a pretty small test (not long enough for autovacuum to trigger
decently) but I think this should be compelling enough to present the
case.

Please discuss.

Implementation notes:

Executor-wise, we could have a distinct IndirectIndexScan node, or we
could just hide the second index scan inside a regular IndexScan.  I
think from a cleanliness POV there is no reason to have a separate node;
efficiency wise I think a separate node leads to less branches in the
code.  (In my toy patch I actually have the second indexscan hidden
inside a separate "ibtree" AM; not what I really propose for commit.)
Additionally, executor will have to keep track of the values in the PK
index so that they can be passed down on insertion to each indirect
index.

Planner-wise, I don't think we need to introduce a distinct indirect
index Path.  We can just let the cost estimator attach the true cost of
the two scans to a regular index scan path, and the correct executor
node is produced later if that index is chosen.

In relcache we'll need an additional bitmapset of columns indexed by
indirect indexes.  This is used so that heap_update can return an output
bitmapset of such columns that were not modified (this is computed by
HeapSatisfiesHOTandKeyUpdate).  The executor uses this to know when to
skip updating each indirect index.

Vacuuming presents an additional challenge: in order to remove index
items from an indirect index, it's critical to scan the PK index first
and collect the PK values that are being removed.  Then scan the
indirect index and remove any items that match the PK items removed.
This is a bit problematic because of the additional memory needed to 
store the array of PK values.  I haven't implemented this yet.


Items I haven't thought about yet:
* UNIQUE INDIRECT?  I think these should work, but require some tinkering.
* Deferred unique indexes?  See unique_key_recheck.
* CREATE INDEX CONCURRENTLY.


[1]  Eventually we can expand this to allow for "normal" datatypes, say
bigint, but that's likely to require a much bigger patch in order to
change IndexTuple to support it.  I would defer that project to a later
time.

[2] It is possible to extend the grammar to allow other UNIQUE indexes
to be used, if they are on top of NOT NULL columns.  This would allow to
extend existing production databases with a new column.  A proposed
syntax is  CREATE INDIRECT INDEX idx ON tab (a, b, c) REFERENCES some_unique_index [optional WHERE clause] ;
which Bison accepts.  I propose not to implement this yet.  However this
is an important item because it allows existing databases to simply add
an UNIQUE NOT NULL column to their existing big tables to take advantage
of the feature, without requiring a lengthy dump/reload of tables that
currently only have larger keys.

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

On 10/18/2016 11:28 AM, Alvaro Herrera wrote:

> Vacuuming presents an additional challenge: in order to remove index
> items from an indirect index, it's critical to scan the PK index first
> and collect the PK values that are being removed.  Then scan the
> indirect index and remove any items that match the PK items removed.
> This is a bit problematic because of the additional memory needed to
> store the array of PK values.  I haven't implemented this yet.

As a whole I think the idea is interesting but the above scares me. Are 
we trading initial performance gains for performance degradation through 
maintenance? Since autovacuum is an indeterminate launch we could have a 
situation where even a medium level updated laden table becomes a source 
of contentions for IO and memory resources. I don't know that we would 
see issues on modern bare metal but considering our implementation space 
is places like RDS and GCE now, this is a serious consideration.

Sincerely,

JD

-- 
Command Prompt, Inc.                  http://the.postgres.company/                        +1-503-667-4564
PostgreSQL Centered full stack support, consulting and development.
Everyone appreciates your honesty, until you are honest with them.

On 18 October 2016 at 21:41, Joshua D. Drake <jd@commandprompt.com> wrote:

> Are we
> trading initial performance gains for performance degradation through
> maintenance?

Eh? That's backwards, so No. The whole point of this is it avoids long
term degradation currently caused by non-HOT updates.

Normal UPDATEs that don't change PKs won't generate any changes to
VACUUM away, so only actions that remove PK values will cause anything
to be collected and removed from indexes.

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

On Tue, Oct 18, 2016 at 3:28 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
> I propose we introduce the concept of "indirect indexes".  I have a toy
> implementation and before I go further with it, I'd like this assembly's
> input on the general direction.
>
> Indirect indexes are similar to regular indexes, except that instead of
> carrying a heap TID as payload, they carry the value of the table's
> primary key.  Because this is laid out on top of existing index support
> code, values indexed by the PK can only be six bytes long (the length of
> ItemPointerData); in other words, 281,474,976,710,656 rows are
> supported, which should be sufficient for most use cases.[1]


You don't need that limitation (and vacuum will be simpler) if you add
the PK as another key, akin to:

CREATE INDIRECT INDEX idx ON tab (a, b, c);

turns into

CREATE INDEX idx ON tab (a, b, c, pk);

And is queried appropriately (using an index-only scan, extracting the
PK from the index tuple, and then querying the PK index to get the
tids).

In fact, I believe that can work with all index ams supporting index-only scans.

On 18 October 2016 at 22:04, Claudio Freire <klaussfreire@gmail.com> wrote:
> On Tue, Oct 18, 2016 at 3:28 PM, Alvaro Herrera
> <alvherre@2ndquadrant.com> wrote:
>> I propose we introduce the concept of "indirect indexes".  I have a toy
>> implementation and before I go further with it, I'd like this assembly's
>> input on the general direction.
>>
>> Indirect indexes are similar to regular indexes, except that instead of
>> carrying a heap TID as payload, they carry the value of the table's
>> primary key.  Because this is laid out on top of existing index support
>> code, values indexed by the PK can only be six bytes long (the length of
>> ItemPointerData); in other words, 281,474,976,710,656 rows are
>> supported, which should be sufficient for most use cases.[1]
>
>
> You don't need that limitation (and vacuum will be simpler) if you add
> the PK as another key, akin to:
>
> CREATE INDIRECT INDEX idx ON tab (a, b, c);
>
> turns into
>
> CREATE INDEX idx ON tab (a, b, c, pk);
>
> And is queried appropriately (using an index-only scan, extracting the
> PK from the index tuple, and then querying the PK index to get the
> tids).
>
> In fact, I believe that can work with all index ams supporting index-only scans.

But if you did that, an UPDATE of a b or c would cause a non-HOT
update, so would defeat the purpose of indirect indexes.

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

On Tue, Oct 18, 2016 at 5:48 PM, Simon Riggs <simon@2ndquadrant.com> wrote:
> On 18 October 2016 at 22:04, Claudio Freire <klaussfreire@gmail.com> wrote:
>> On Tue, Oct 18, 2016 at 3:28 PM, Alvaro Herrera
>> <alvherre@2ndquadrant.com> wrote:
>>> I propose we introduce the concept of "indirect indexes".  I have a toy
>>> implementation and before I go further with it, I'd like this assembly's
>>> input on the general direction.
>>>
>>> Indirect indexes are similar to regular indexes, except that instead of
>>> carrying a heap TID as payload, they carry the value of the table's
>>> primary key.  Because this is laid out on top of existing index support
>>> code, values indexed by the PK can only be six bytes long (the length of
>>> ItemPointerData); in other words, 281,474,976,710,656 rows are
>>> supported, which should be sufficient for most use cases.[1]
>>
>>
>> You don't need that limitation (and vacuum will be simpler) if you add
>> the PK as another key, akin to:
>>
>> CREATE INDIRECT INDEX idx ON tab (a, b, c);
>>
>> turns into
>>
>> CREATE INDEX idx ON tab (a, b, c, pk);
>>
>> And is queried appropriately (using an index-only scan, extracting the
>> PK from the index tuple, and then querying the PK index to get the
>> tids).
>>
>> In fact, I believe that can work with all index ams supporting index-only scans.
>
> But if you did that, an UPDATE of a b or c would cause a non-HOT
> update, so would defeat the purpose of indirect indexes.

I meant besides all the other work, omitting the tid from the index
(as only the PK matters), marking them indirect, and all that.

On 18 October 2016 at 23:46, Alexander Korotkov
<a.korotkov@postgrespro.ru> wrote:

> Then vacuum removes (0;1) from heap, reference to (0;1) from tbl_pk_idx.
> But how will it remove (1,1) tuple from tbl_val_indirect_idx?  Thus, before
> vacuuming tbl_val_indirect_idx we should know not only values of id which
> are being removed, but actually (id, val) pairs which are being removed.
> Should we collect those paris while scanning heap?  But we should also take
> into account that multiple heap tuples might have same (id, val) pair values
> (assuming there could be other columns being updated).  Therefore, we should
> take into account when last pair of particular (id, val) pair value was
> deleted from heap.  That would be very huge change to vacuum, may be even
> writing way more complex vacuum algorithm from scratch.  Probably, you see
> the better solution of this problem.

The best way to sum up the problem is to consider how we deal with
repeated updates to a single tuple that flip the value from A to B
then back to A then to B then A etc.. Any value in the index can point
to multiple versions of the same tuple and multiple index values can
point to the same tuple (PK value). This problem behaviour was already
known to me from Claudio's earlier analysis of WARM (thanks Claudio).

Yes, VACUUMing that is likely to be a complex issue, as you say. At
the moment I don't have a plan for that, but am not worried.

Indirect indexes produce less index entries in general than current,
so the problem is by-design much smaller than current situation.
Indirect indexes can support killed-tuple interface, so scanning the
index by users will result in natural index maintenance, further
reducing the problem.

So there will be a much reduced need for bulk maintenance. Bulk
maintainence of the index, when needed, can be performed by scanning
the whole table via the index, after the PK index has been vacuumed.
That can be optimized using an index-only scan of the PK to avoid
touching the heap, which should be effective since the VM has been so
recently refreshed. For correctness it would require the index blocks
to be locked against write while checking for removal, so bulk
collection of values to optimize the underlying index doesn't seem
useful. The index scan could also be further optimized by introducing
a visibility map for the index, which is something that would also
optimize normal index VACUUMs as well, but that is a later project and
not something for 10.x

At this stage, the discussion should be 1) can it work? 2) do we want
it? At present, I see that it can work and we just need to be careful
to measure the effectiveness of it to demonstrate that it really is a
better way of doing things in some cases. Indirect indexes are
definitely not a panacea for all problems, for me it is just another
option to add into the rich world of Postgres indexing. Getting
traction can be difficult if people don't understand the pros and cons
of the different index types, but I'm happy we have a wide spread of
knowledge now.

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

On Tue, Oct 18, 2016 at 2:28 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
> I propose we introduce the concept of "indirect indexes".  I have a toy
> implementation and before I go further with it, I'd like this assembly's
> input on the general direction.
>
> Indirect indexes are similar to regular indexes, except that instead of
> carrying a heap TID as payload, they carry the value of the table's
> primary key.  Because this is laid out on top of existing index support
> code, values indexed by the PK can only be six bytes long (the length of
> ItemPointerData); in other words, 281,474,976,710,656 rows are
> supported, which should be sufficient for most use cases.[1]

So, I think that this is a really promising direction, but also that
you should try very hard to try to get out from under this 6-byte PK
limitation.  That seems really ugly, and in practice it probably means
your PK is probably going to be limited to int4, which is kind of sad
since it leaves people using int8 or text PKs out in the cold.  I
believe Claudio Freire is on to something when he suggests storing the
PK in the index tuple; one could try to skip storing the TID, or
always store it as all-zeroes.  Simon objected that putting the PK
into the index tuple would disable HOT, but I don't think that's a
valid objection.  The whole point of an indirect index is that it
doesn't disable HOT, and the physical location within the index page
you stick the PK value doesn't have any impact on whether that's safe.

The VACUUM problems seem fairly serious.  It's true that these indexes
will be less subject to bloat, because they only need updating when
the PK or the indexed columns change, not when other indexed columns
change.  On the other hand, there's nothing to prevent a PK from being
recycled for an unrelated tuple.  We can guarantee that a TID won't be
recycled until all index references to the TID are gone, but there's
no such guarantee for a PK.  AFAICT, that would mean that an indirect
index would have to be viewed as unreliable: after looking up the PK,
you'd *always* have to recheck that it actually matched the index
qual.

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

On 19 October 2016 at 14:52, Robert Haas <robertmhaas@gmail.com> wrote:
> On Tue, Oct 18, 2016 at 2:28 PM, Alvaro Herrera
> <alvherre@2ndquadrant.com> wrote:
>> I propose we introduce the concept of "indirect indexes".  I have a toy
>> implementation and before I go further with it, I'd like this assembly's
>> input on the general direction.
>>
>> Indirect indexes are similar to regular indexes, except that instead of
>> carrying a heap TID as payload, they carry the value of the table's
>> primary key.  Because this is laid out on top of existing index support
>> code, values indexed by the PK can only be six bytes long (the length of
>> ItemPointerData); in other words, 281,474,976,710,656 rows are
>> supported, which should be sufficient for most use cases.[1]
>
> So, I think that this is a really promising direction, but also that
> you should try very hard to try to get out from under this 6-byte PK
> limitation.  That seems really ugly, and in practice it probably means
> your PK is probably going to be limited to int4, which is kind of sad
> since it leaves people using int8 or text PKs out in the cold.  I
> believe Claudio Freire is on to something when he suggests storing the
> PK in the index tuple; one could try to skip storing the TID, or
> always store it as all-zeroes.

The main problem IMV is GIN indexes. It's relatively easy to discuss
variable length PKs with btrees, but the GIN format is designed around
use of 6byte values, so expanding beyond that would require
significant redesign/reimplementation. That would be at least a year's
work for not much benefit, so cannot occur for the first release.

A limit 281 trillion rows means the row headers alone will be 9
Petabytes, before we even include block wastage and data payload per
row. So that is more than we'll need for a few years. Setting the max
sequence value to 281474976710656 should be easy enough.

> Simon objected that putting the PK
> into the index tuple would disable HOT, but I don't think that's a
> valid objection.

Just to be clear, that's not what I objected to. Claudio appeared to
be suggesting that an indirect index is the same thing as an index
with PK tacked onto the end, which I re-confirm is not the case since
doing that would not provide the primary objective of indirect
indexes.

> The whole point of an indirect index is that it
> doesn't disable HOT, and the physical location within the index page
> you stick the PK value doesn't have any impact on whether that's safe.

Agreed, though it does have an impact on the length of the index tuple
and thus the size and effectiveness of the index.

Perhaps its best to see the restriction to 6byte PKs as both the first
phase of implementation and an optimization, rather than an ugly wart.

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

On Wed, Oct 19, 2016 at 9:21 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> The main problem IMV is GIN indexes. It's relatively easy to discuss
> variable length PKs with btrees, but the GIN format is designed around
> use of 6byte values, so expanding beyond that would require
> significant redesign/reimplementation. That would be at least a year's
> work for not much benefit, so cannot occur for the first release.

That doesn't bother me.  We can add an amcanindirect flag or similar.

>> The whole point of an indirect index is that it
>> doesn't disable HOT, and the physical location within the index page
>> you stick the PK value doesn't have any impact on whether that's safe.
>
> Agreed, though it does have an impact on the length of the index tuple
> and thus the size and effectiveness of the index.
>
> Perhaps its best to see the restriction to 6byte PKs as both the first
> phase of implementation and an optimization, rather than an ugly wart.

Perhaps, but I'm not ready to rule out "ugly wart".

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

On Wed, Oct 19, 2016 at 07:23:28PM +0530, Pavan Deolasee wrote:
>     AFAICS, even without considering VACUUM, indirect indexes would be always
>     used with recheck.
>     As long as they don't contain visibility information.  When indirect
>     indexed column was updated, indirect index would refer same PK with
>     different index keys.
>     There is no direct link between indirect index tuple and heap tuple, only
>     logical link using PK.  Thus, you would anyway have to recheck.
> 
> 
> 
> I agree. Also, I think the recheck mechanism will have to be something like
> what I wrote for WARM i.e. only checking for index quals won't be enough and we
> would actually need to verify that the heap tuple satisfies the key in the
> indirect index. 

I personally would like to see how far we get with WARM before adding
this feature that requires a DBA to evaluate and enable it.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

On Wed, Oct 19, 2016 at 10:21 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
>> Simon objected that putting the PK
>> into the index tuple would disable HOT, but I don't think that's a
>> valid objection.
>
> Just to be clear, that's not what I objected to. Claudio appeared to
> be suggesting that an indirect index is the same thing as an index
> with PK tacked onto the end, which I re-confirm is not the case since
> doing that would not provide the primary objective of indirect
> indexes.

No, I was suggesting using the storage format of those indexes.
Perhaps I wasn't clear.

CREATE INDEX could be implemented entirely as the rewrite I mention, I
believe. But everything else can't, as you say.

On 19 October 2016 at 18:40, Bruce Momjian <bruce@momjian.us> wrote:
> On Wed, Oct 19, 2016 at 07:23:28PM +0530, Pavan Deolasee wrote:
>>     AFAICS, even without considering VACUUM, indirect indexes would be always
>>     used with recheck.
>>     As long as they don't contain visibility information.  When indirect
>>     indexed column was updated, indirect index would refer same PK with
>>     different index keys.
>>     There is no direct link between indirect index tuple and heap tuple, only
>>     logical link using PK.  Thus, you would anyway have to recheck.
>>
>>
>>
>> I agree. Also, I think the recheck mechanism will have to be something like
>> what I wrote for WARM i.e. only checking for index quals won't be enough and we
>> would actually need to verify that the heap tuple satisfies the key in the
>> indirect index.
>
> I personally would like to see how far we get with WARM before adding
> this feature that requires a DBA to evaluate and enable it.

Assuming WARM is accepted, that *might* be fine.

What we should ask is what is the difference between indirect indexes
and WARM and to what extent they overlap.

My current understanding is that WARM won't help you if you update
parts of a JSON document and/or use GIN indexes, but is effective
without needing to add a new index type and will be faster for
retrieval than indirect indexes.

So everybody please chirp in with benefits or comparisons.

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

On Wed, Oct 19, 2016 at 06:58:05PM +0200, Simon Riggs wrote:
> >> I agree. Also, I think the recheck mechanism will have to be something like
> >> what I wrote for WARM i.e. only checking for index quals won't be enough and we
> >> would actually need to verify that the heap tuple satisfies the key in the
> >> indirect index.
> >
> > I personally would like to see how far we get with WARM before adding
> > this feature that requires a DBA to evaluate and enable it.
> 
> Assuming WARM is accepted, that *might* be fine.

First, I love WARM because everyone gets the benefits by default.  For
example, a feature that improves performance by 10% but is only used by
1% of users has a usefulness of 0.1% --- at least that is how I think of
it.

> What we should ask is what is the difference between indirect indexes
> and WARM and to what extent they overlap.
> 
> My current understanding is that WARM won't help you if you update
> parts of a JSON document and/or use GIN indexes, but is effective
> without needing to add a new index type and will be faster for
> retrieval than indirect indexes.
> 
> So everybody please chirp in with benefits or comparisons.

I am not sure we have even explored all the limits of WARM with btree
indexes --- I haven't heard anyone talk about non-btree indexes yet.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

On Wed, Oct 19, 2016 at 2:04 PM, Bruce Momjian <bruce@momjian.us> wrote:
>> What we should ask is what is the difference between indirect indexes
>> and WARM and to what extent they overlap.
>>
>> My current understanding is that WARM won't help you if you update
>> parts of a JSON document and/or use GIN indexes, but is effective
>> without needing to add a new index type and will be faster for
>> retrieval than indirect indexes.
>>
>> So everybody please chirp in with benefits or comparisons.
>
> I am not sure we have even explored all the limits of WARM with btree
> indexes --- I haven't heard anyone talk about non-btree indexes yet.

AFAIK there's no fundamental reason why it wouldn't work for other
index ams, but it does require quite a bit of legwork to get
everything working there.

Alexander Korotkov wrote:

Hi,

> Thank you for your proposal.  One question about vacuum excites me most.

> Imagine another situation: PK column was not updated, but indirect indexed
> column was updated.
> Thus, for single heap tuple we would have single PK tuple and two indirect
> index tuples (correct me if I'm wrong).
> How are we going to delete old indirect index tuple?

Yeah, this is a tough question all right.

Another thing to note is that the initial heap tuple might be removed
via HOT page pruning, so it will not be there during vacuuming either;
there would only be a redirect line pointer.  So I don't think we can
rely on that to figure out an exact cleanup of the indirect index.

One possibility is to forget about vacuuming the index altogether.
Instead we can rely solely on the killtuple interface, that is, have
obsolete tuples be removed during index scanning.

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

On Wed, Oct 19, 2016 at 01:04:16PM -0400, Bruce Momjian wrote:
> On Wed, Oct 19, 2016 at 06:58:05PM +0200, Simon Riggs wrote:
> > >> I agree. Also, I think the recheck mechanism will have to be something like
> > >> what I wrote for WARM i.e. only checking for index quals won't be enough and we
> > >> would actually need to verify that the heap tuple satisfies the key in the
> > >> indirect index.
> > >
> > > I personally would like to see how far we get with WARM before adding
> > > this feature that requires a DBA to evaluate and enable it.
> > 
> > Assuming WARM is accepted, that *might* be fine.
> 
> First, I love WARM because everyone gets the benefits by default.  For
> example, a feature that improves performance by 10% but is only used by
> 1% of users has a usefulness of 0.1% --- at least that is how I think of
> it.

Just to clarify, if a feature improves performance by 1%, but is enabled
by default, that is 10x more useful across our entire user base as the
feature numbers listed above, 1% vs 0.1%.

Also, it seems indirect indexes would be useful for indexing columns
that are not updated frequently on tables that are updated frequently,
and whose primary key is not updated frequently.  That's quite a logic
problem for users to understand.

Also, if vacuum is difficult for indirect indexes, and also for WARM,
perhaps the vacuum problem can be solved for WARM and WARM can be used
in this case too.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

Bruce Momjian wrote:

> Just to clarify, if a feature improves performance by 1%, but is enabled
> by default, that is 10x more useful across our entire user base as the
> feature numbers listed above, 1% vs 0.1%.

Great.  But not all users are alike.  We have big profile users that
write blog posts that get echoed all over the world who would benefit
from things that perhaps other users would not benefit that much from.

> Also, it seems indirect indexes would be useful for indexing columns
> that are not updated frequently on tables that are updated frequently,
> and whose primary key is not updated frequently.  That's quite a logic
> problem for users to understand.

I don't think we should be optimizing only for dumb users.  In any case,
updating primary key values is very rare; some would say it never
happens.

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

On Thu, Oct 20, 2016 at 10:39:23AM -0300, Alvaro Herrera wrote:
> Bruce Momjian wrote:
> 
> > Just to clarify, if a feature improves performance by 1%, but is enabled
> > by default, that is 10x more useful across our entire user base as the
> > feature numbers listed above, 1% vs 0.1%.
> 
> Great.  But not all users are alike.  We have big profile users that
> write blog posts that get echoed all over the world who would benefit
> from things that perhaps other users would not benefit that much from.
> 
> > Also, it seems indirect indexes would be useful for indexing columns
> > that are not updated frequently on tables that are updated frequently,
> > and whose primary key is not updated frequently.  That's quite a logic
> > problem for users to understand.
> 
> I don't think we should be optimizing only for dumb users.  In any case,
> updating primary key values is very rare; some would say it never
> happens.

Uh, so we are writing the database for sophisticated users who write
blog posts who make us look bad?  Really?

My point is that we need to look at the entire user base, and look at
the adoption rates of features, and figure out how to maximize that. 

You are right that sophisticated users can hit roadblocks, and we need
to give them a solution that keeps them on Postgres.  However, if we can
solve the problem in a way that everyone benefits from by default (e.g.
WARM), why not implement that instead, or at least go as far as we can
with that before adding a feature that only sophisticated users will
know to enable.  (My "logic problem" above shows that only sophisticated
users will likely use indirect indexes.)

If we have to solve a vacuum problem with indirect indexes, and WARM
also is limited by the same vacuum problem, let's fix the vacuum problem
for WARM, which will be used by all users.

In summary, I need to know what problems indirect indexes fix that WARM
cannot, or eventually cannot if given the amount of engineering work we
would need to implement indirect indexes.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

On 10/20/2016 06:39 AM, Alvaro Herrera wrote:
> Bruce Momjian wrote:

>> Also, it seems indirect indexes would be useful for indexing columns
>> that are not updated frequently on tables that are updated frequently,
>> and whose primary key is not updated frequently.  That's quite a logic
>> problem for users to understand.
>
> I don't think we should be optimizing only for dumb users.  In any case,
> updating primary key values is very rare; some would say it never
> happens.

Just because a person doesn't understand a use case doesn't make them dumb.

That said would it be possible to make this index an extension (like 
rum?). Assuming of course we can get any required infrastructure changes 
done in a general way.

I do think the feature has merit.

JD


-- 
Command Prompt, Inc.                  http://the.postgres.company/                        +1-503-667-4564
PostgreSQL Centered full stack support, consulting and development.
Everyone appreciates your honesty, until you are honest with them.

Joshua D. Drake wrote:

> That said would it be possible to make this index an extension (like rum?).
> Assuming of course we can get any required infrastructure changes done in a
> general way.

Well, the patch I currently have creates a separate index AM called
"ibtree" which is an indirect btree that internally calls the regular
btree code -- pretty much what you propose.  I think it can work that
way, but it's not as efficient as it can be done if the feature is
incorporated into core.  There are things like obtaining the primary key
value from the indexed tuple: in my extension I simply do "heap_fetch"
to obtain the heap tuple, then heap_getattr() to obtain the values from
the primary key columns.  This works, but if instead the executor passes
the primary key values as parameters, I can save both those steps, which
are slow.

Now if we do incorporate the infrastructure changes in core in a general
way, which is what I am proposing, then the in-core provided btree AM
can do indirect indexes without any further extension.  The same
infrastructure changes can later provide support for GIN indexes.

> I do think the feature has merit.

Thanks.

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

On 20/10/16 14:29, Bruce Momjian wrote:
> On Wed, Oct 19, 2016 at 01:04:16PM -0400, Bruce Momjian wrote:
>> On Wed, Oct 19, 2016 at 06:58:05PM +0200, Simon Riggs wrote:
>>>>> I agree. Also, I think the recheck mechanism will have to be something like
>>>>> what I wrote for WARM i.e. only checking for index quals won't be enough and we
>>>>> would actually need to verify that the heap tuple satisfies the key in the
>>>>> indirect index.
>>>>
>>>> I personally would like to see how far we get with WARM before adding
>>>> this feature that requires a DBA to evaluate and enable it.
>>>
>>> Assuming WARM is accepted, that *might* be fine.
>>
>> First, I love WARM because everyone gets the benefits by default.  For
>> example, a feature that improves performance by 10% but is only used by
>> 1% of users has a usefulness of 0.1% --- at least that is how I think of
>> it.
> 
> Just to clarify, if a feature improves performance by 1%, but is enabled
> by default, that is 10x more useful across our entire user base as the
> feature numbers listed above, 1% vs 0.1%.
> 
> Also, it seems indirect indexes would be useful for indexing columns
> that are not updated frequently on tables that are updated frequently,
> and whose primary key is not updated frequently.  That's quite a logic
> problem for users to understand.
> 

Which covers like 99.9% of problematic cases I see on daily basis.

And by that logic we should not have indexes at all, they are not
automatically created and user needs to think about if they need them or
not.

Also helping user who does not have performance problem by 1% is very
different from helping user who has performance problem by 50% even if
she needs to think about the solution a bit.

WARM can do WARM update 50% of time, indirect index can do HOT update
100% of time (provided the column is not changed), I don't see why we
could not have both solutions.

That all being said, it would be interesting to hear Álvaro's thoughts
about which use-cases he expects indirect indexes to work better than WARM.

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

On Thu, Oct 20, 2016 at 05:14:51PM +0200, Petr Jelinek wrote:
> > Also, it seems indirect indexes would be useful for indexing columns
> > that are not updated frequently on tables that are updated frequently,
> > and whose primary key is not updated frequently.  That's quite a logic
> > problem for users to understand.
> > 
> 
> Which covers like 99.9% of problematic cases I see on daily basis.
> 
> And by that logic we should not have indexes at all, they are not
> automatically created and user needs to think about if they need them or
> not.

Do you have to resort to extreme statements to make your point?  The use
of indexes is clear to most users, while the use of indirect indexes
would not be, as I stated earlier.

> Also helping user who does not have performance problem by 1% is very
> different from helping user who has performance problem by 50% even if
> she needs to think about the solution a bit.
> 
> WARM can do WARM update 50% of time, indirect index can do HOT update
> 100% of time (provided the column is not changed), I don't see why we
> could not have both solutions.

We don't know enough about the limits of WARM to say it is limited to
50%.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

On Thu, Oct 20, 2016 at 12:14 PM, Petr Jelinek <petr@2ndquadrant.com> wrote:
> WARM can do WARM update 50% of time, indirect index can do HOT update
> 100% of time (provided the column is not changed), I don't see why we
> could not have both solutions.
>
> That all being said, it would be interesting to hear Álvaro's thoughts
> about which use-cases he expects indirect indexes to work better than WARM.

I'm not Alvaro, but it's quite evident that indirect indexes don't
need space on the same page to get the benefits of HOT update (even
though it wouldn't be HOT).

That's a big difference IMO.

That said, WARM isn't inherently limited to 50%, but it *is* limited
to HOT-like updates (new tuple is in the same page as the old), and
since in many cases that is a limiting factor for HOT updates, one can
expect WARM will be equally limited.

On 20/10/16 17:24, Bruce Momjian wrote:
> On Thu, Oct 20, 2016 at 05:14:51PM +0200, Petr Jelinek wrote:
>>> Also, it seems indirect indexes would be useful for indexing columns
>>> that are not updated frequently on tables that are updated frequently,
>>> and whose primary key is not updated frequently.  That's quite a logic
>>> problem for users to understand.
>>>
>>
>> Which covers like 99.9% of problematic cases I see on daily basis.
>>
>> And by that logic we should not have indexes at all, they are not
>> automatically created and user needs to think about if they need them or
>> not.
> 
> Do you have to resort to extreme statements to make your point?  The use
> of indexes is clear to most users, while the use of indirect indexes
> would not be, as I stated earlier.
> 

Not extreme statement just pointing flaw in that logic. People need to
understand same limitation for example when using most of current
trigger-based replication systems as they don't support pkey updates.
And no, many users don't know when to use indexes and which one is most
appropriate even though indexes have been here for decades.

The fact that some feature is not useful for everybody never stopped us
from adding it before, especially when it can be extremely useful to some.

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

On Thu, Oct 20, 2016 at 12:30 PM, Pavan Deolasee
<pavan.deolasee@gmail.com> wrote:
>
>
> On Thu, Oct 20, 2016 at 8:44 PM, Petr Jelinek <petr@2ndquadrant.com> wrote:
>>
>>
>>
>> WARM can do WARM update 50% of time, indirect index can do HOT update
>> 100% of time (provided the column is not changed), I don't see why we
>> could not have both solutions.
>>
>
> I think the reason why I restricted WARM to one update per chain, also
> applies to indirect index. For example, if a indirect column value is
> changed from 'a' to 'b' and back to 'a', there will be two pointers from 'a'
> to the PK and AFAICS that would lead to the same duplicate scan issue.
>
> We have a design to convert WARM chains back to HOT and that will increase
> the percentage of WARM updates much beyond 50%. I was waiting for feedback
> on the basic patch before putting in more efforts, but it went unnoticed
> last CF.

With indirect indexes, since you don't need to insert a tid, you can
just "insert on conflict do nothing" on the index.

On Thu, Oct 20, 2016 at 1:08 PM, Pavan Deolasee
<pavan.deolasee@gmail.com> wrote:
> On Thu, Oct 20, 2016 at 9:20 PM, Claudio Freire <klaussfreire@gmail.com>
> wrote:
>>
>>
>>
>> With indirect indexes, since you don't need to insert a tid, you can
>> just "insert on conflict do nothing" on the index.
>
>
> Would that work with non-unique indexes? Anyways, the point I was trying to
> make is that there are a similar technical challenges and we could solve it
> for WARM as well with your work for finding conflicting <key, tid> pairs and
> then not doing inserts. My thinking currently is that it will lead to other
> challenges, especially around vacuum, but I could be wrong.

Consider this:

Have a vacuum_cycle_id field in the metapage, with one bit reserved to
whether there's a vacuum in progress.

While there is a vacuum in progress on the index, all kinds of
modifications will look up the <key, pk> entry, and store the current
vacuum_cycle_id on the unused space for the tid pointer on the index
entry. When not, only new entries will be added (with the current
vacuum cycle id). So, during vacuum, indirect indexes incur a similar
cost to that of regular indexes, but only during vacuum.

When vacuuming, allocate 1/2 maintenance_work_mem for a bloom filter,
and increase all vacuum cycle ids (on the metapage) and mark a vacuum
in progress.

Scan the heap, add <key, pk> pairs of *non-dead* tuples to the bloom
filter. That's one BF per index, sadly, but bear with me.

Then scan the indexes. <key, pk> pairs *not* in the BF that have the
*old* vacuum cycle id get removed.

Clear the vacuum in progress flag on all indexes' metapage.

The only drawback here is that mwm dictates the amount of uncleanable
waste left on the indexes (BF false positives). Surely, the BF could
be replaced with an accurate set rather than an approximate one, but
that could require a lot of memory if keys are big, and a lot of scans
of the indexes. The BF trick bounds the amount of waste left while
minimizing work.

On 2016-10-18 20:04:32, Claudio Freire wrote:
> You don't need that limitation (and vacuum will be simpler) if you add
the PK as another key, akin to:>> CREATE INDIRECT INDEX idx ON tab (a, b, c);>> turns into>> CREATE INDEX idx ON tab
(a,b, c, pk);
 


I know I am late to this point but I wanted to present my mere user's 
point of view.

First I liked it, as does not introduce yet another syntax to learn. 
However, after following the discussion, I see that indirect indexes 
have their disadvantages/slowdowns as well. If adding "pk" to the end of 
the column list just converts the index to an indirect index, I am 
unable to use a direct index which might be better in certain cases.

So, from a "dumb" user's point of view, I wonder if PostgreSQL can make 
the right decision of direct/indirect reliably (which would be great). 
And if not, what would be the alternatives? Introducing CREATE DIRECT INDEX?

Cheers,
Sven

PS: I mot saying I would be affected by this but IIRC we have (..., pk) 
indexes in production which then would be converted to indirect ones. 
But I cannot tell whether indirect indexes would do good or harm there.

On 10/19/16 7:52 AM, Robert Haas wrote:
> So, I think that this is a really promising direction, but also that
> you should try very hard to try to get out from under this 6-byte PK
> limitation.  That seems really ugly, and in practice it probably means
> your PK is probably going to be limited to int4, which is kind of sad
> since it leaves people using int8 or text PKs out in the cold.

My impression is that int4 is by far the most popular PK type. Even if 
the initial implementation is limited to that I think it'd have a lot of 
potential.
-- 
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Experts in Analytics, Data Architecture and PostgreSQL
Data in Trouble? Get it in Treble! http://BlueTreble.com
855-TREBLE2 (855-873-2532)   mobile: 512-569-9461

On 10/21/16 2:48 PM, Sven R. Kunze wrote:
>
>> You don't need that limitation (and vacuum will be simpler) if you add
> the PK as another key, akin to:
>>
>> CREATE INDIRECT INDEX idx ON tab (a, b, c);
>>
>> turns into
>>
>> CREATE INDEX idx ON tab (a, b, c, pk);
>
>
> I know I am late to this point but I wanted to present my mere user's
> point of view.
>
> First I liked it, as does not introduce yet another syntax to learn.

I believe you mis-understood what Claudio was saying. He's not 
suggesting an index with the PK on the end magically becomes an indirect 
index; he was saying that a "simple" way to overcome the 6 byte index 
TID limitation would be to store the PK as part of the index key. He 
used existing DDL to illustrate that, but that was just for 
illustration, not how this would actually be implemented.
-- 
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Experts in Analytics, Data Architecture and PostgreSQL
Data in Trouble? Get it in Treble! http://BlueTreble.com
855-TREBLE2 (855-873-2532)   mobile: 512-569-9461

On 10/21/16 4:05 PM, Adam Brusselback wrote:
> My main point is that maybe the reason why most users use int4 pkeys
> (besides conventional wisdom) is because it gets the most support from
> features like this, and it may not be quite as skewed if that same
> support were given to other types.

I think it's a pretty safe bet that they're the most popular simply 
because serial means int4 and not int8. I bet a fair number of users 
don't even realize bigserial exists.
-- 
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Experts in Analytics, Data Architecture and PostgreSQL
Data in Trouble? Get it in Treble! http://BlueTreble.com
855-TREBLE2 (855-873-2532)   mobile: 512-569-9461

Robert Haas wrote:

> So, I think that this is a really promising direction, but also that
> you should try very hard to try to get out from under this 6-byte PK
> limitation.  That seems really ugly, and in practice it probably means
> your PK is probably going to be limited to int4, which is kind of sad
> since it leaves people using int8 or text PKs out in the cold.

I think we could just add a new type, unsigned 6 byte int, specifically
for this purpose.  Little in the way of operators, as it's pointless to
try to do arithmetic with object identifiers.  (It'd be similar to UUID
in spirit, but I wouldn't try to do anything too smart to generate them.)

> I believe Claudio Freire is on to something when he suggests storing
> the PK in the index tuple; one could try to skip storing the TID, or
> always store it as all-zeroes.

That bloats the index a bit.  But then, maybe that is fine ...

> The VACUUM problems seem fairly serious.  It's true that these indexes
> will be less subject to bloat, because they only need updating when
> the PK or the indexed columns change, not when other indexed columns
> change.  On the other hand, there's nothing to prevent a PK from being
> recycled for an unrelated tuple.  We can guarantee that a TID won't be
> recycled until all index references to the TID are gone, but there's
> no such guarantee for a PK.  AFAICT, that would mean that an indirect
> index would have to be viewed as unreliable: after looking up the PK,
> you'd *always* have to recheck that it actually matched the index
> qual.

Yes, recheck is always needed.

As for vacuum, I was thinking this morning that perhaps the answer to
that is just to not vacuum the index at all and instead rely on the
killtuple interface (which removes tuples during scan).  So we don't
need to spend precious maint_work_mem space on a large list of PK
values.

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

Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> Robert Haas wrote:
>> So, I think that this is a really promising direction, but also that
>> you should try very hard to try to get out from under this 6-byte PK
>> limitation.  That seems really ugly, and in practice it probably means
>> your PK is probably going to be limited to int4, which is kind of sad
>> since it leaves people using int8 or text PKs out in the cold.

> I think we could just add a new type, unsigned 6 byte int, specifically
> for this purpose.

I think that's a really bad idea, because after you've fixed this
hopefully-temporary limitation, we'll still be stuck carrying this
weird type forever.  Besides which, doesn't the existing TID type
already serve the purpose?
        regards, tom lane

On 21.10.2016 22:54, Jim Nasby wrote:
> On 10/21/16 2:48 PM, Sven R. Kunze wrote:
>>
>>> You don't need that limitation (and vacuum will be simpler) if you add
>> the PK as another key, akin to:
>>>
>>> CREATE INDIRECT INDEX idx ON tab (a, b, c);
>>>
>>> turns into
>>>
>>> CREATE INDEX idx ON tab (a, b, c, pk);
>>
>>
>> I know I am late to this point but I wanted to present my mere user's
>> point of view.
>>
>> First I liked it, as does not introduce yet another syntax to learn.
>
> I believe you mis-understood what Claudio was saying. He's not
> suggesting an index with the PK on the end magically becomes an indirect
> index; he was saying that a "simple" way to overcome the 6 byte index
> TID limitation would be to store the PK as part of the index key. He
> used existing DDL to illustrate that, but that was just for
> illustration, not how this would actually be implemented.

Alright. Thanks for clarifying. :)

Cheers,
Sven

Alvaro Herrera wrote:
> I propose we introduce the concept of "indirect indexes".

This is a WIP non-functional patch for indirect indexes.  I've been
distracted from working on it for some time already and will be off-line
for half this month yet, but since this was discussed and seems to be
considered a welcome idea, I am posting it for those who want to have a
look at what I'm doing.  This can write values to indirect indexes (only
btrees), but it cannot read values from them yet, so don't expect this
to work at all unless you are hoping to read index files using
pageinspect.  (If you do test this, be aware that "VACUUM FULL pg_class"
is a case that I know needs fixed.)

I think the most interesting change here is how
HeapSatisfiesHOTandKeyUpdate() has accomodated some additional code to
return a bitmapset of columns that are not modified by an update.

This implements a new command
  CREATE INDIRECT INDEX
which instructs the AM to create an index that stores primary key values
instead of CTID values.  I have not tried yet to remove the limitation
of only six bytes in the PK value.  The part of the patch I'm not
submitting just yet adds a flag to IndexInfo used by IndexPath, so that
when the index is selected by the planner, an IndirectIndexScan node is
created instead of a plain IndexScan.  This node knows how to invoke the
AM so that the PK values are extracted in a first step and the CTIDs are
extracted from the PK in a second step (IndirectIndexScan carries two
IndexScanDesc structs and two index RelationDescs, so it keeps both the
indirect index and the PK index open).

The part that generated the most discussion was vacuuming.  As I said
earlier, I think that instead of trying to shoehorn an index cleanup in
regular vacuum (and cause a terrible degradation of maintenance_work_mem
consumption, into optimizing which so much work has gone), these indexes
would rely on desultory cleanup instead through the "killtuple"
interface that causes index tuples to be removed during scan.  Timely
cleanup is not critical as it is with regular (direct) indexes, given
that CTIDs are not stored and thus tuple movement does not affect this
type of indexes.

This patch is considerably smaller than the toy patch I had, which
introduced a separate AM for "ibtree" -- that was duplicating a lot
of code and adding more code complexity, which becomes much simpler with
the approach in the current code; one thing I didn't like at all was the
fact that the ibtree routines were calling the "internal" btree
routines, which was not nice.  (Also, it would have meant having
duplicate operator family/class rows.)

I hope to be back at home to collaborate with the commitfest on Nov
14th.

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

Hi,

On 2016-11-01 01:43:31 -0300, Alvaro Herrera wrote:
> Alvaro Herrera wrote:
> > I propose we introduce the concept of "indirect indexes".
> 
> This is a WIP non-functional patch for indirect indexes.  I've been
> distracted from working on it for some time already and will be off-line
> for half this month yet, but since this was discussed and seems to be
> considered a welcome idea, I am posting it for those who want to have a
> look at what I'm doing.

I see that this patch has a CF entry, but I'm unclear what reviewer
ought to do at the current state?  There's a lot of stuff closer to
being committable in this fest...


Regards,

Andres

Haribabu Kommi wrote:

> Closed in 2016-11 commitfest with "returned with feedback" status.

What feedback?

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

On Fri, Oct 21, 2016 at 7:04 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
> Robert Haas wrote:
>> So, I think that this is a really promising direction, but also that
>> you should try very hard to try to get out from under this 6-byte PK
>> limitation.  That seems really ugly, and in practice it probably means
>> your PK is probably going to be limited to int4, which is kind of sad
>> since it leaves people using int8 or text PKs out in the cold.
>
> I think we could just add a new type, unsigned 6 byte int, specifically
> for this purpose.  Little in the way of operators, as it's pointless to
> try to do arithmetic with object identifiers.  (It'd be similar to UUID
> in spirit, but I wouldn't try to do anything too smart to generate them.)

Sure, we could do that, but that's just band-aiding over the fact that
the index page format isn't really what we want for a feature of this
type.

> Yes, recheck is always needed.
>
> As for vacuum, I was thinking this morning that perhaps the answer to
> that is just to not vacuum the index at all and instead rely on the
> killtuple interface (which removes tuples during scan).  So we don't
> need to spend precious maint_work_mem space on a large list of PK
> values.

I don't think that's going to fly.  Even if it's the case that
indirect indexes typically need less cleanup than regular indexes, the
idea that there's no command to force a full cleanup short of REINDEX
doesn't sit well with me.  It's not difficult to construct realistic
scenarios in which kill_prior_tuple is almost useless (e.g. values are
all marching forward).

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

On Thu, Oct 20, 2016 at 11:30 AM, Pavan Deolasee
<pavan.deolasee@gmail.com> wrote:
> We have a design to convert WARM chains back to HOT and that will increase
> the percentage of WARM updates much beyond 50%. I was waiting for feedback
> on the basic patch before putting in more efforts, but it went unnoticed
> last CF.

While you did sign up to review one patch in the last CF, the amount
of review you did for that patch is surely an order of magnitude less
than what WARM will require.  Maybe more than that.  I don't mean to
point the finger at you specifically -- there are lots of people
slinging patches into the CommitFest who aren't doing as much review
as their own patches will require.  I'm putting a lot of time into
reviewing patches this year, and basically none into writing my own,
but I still can't review every major patch that somebody submits.  I
can't even do committer review of all of those patches, let alone
first-round review.

Perhaps I ought to rank the things I review by descending order of
importance, in which case this arguably ought to be pretty high on the
list.  But I'd feel somewhat bad working on this instead of, say,
multivariate statistics or unique joins, which have been pending for a
lot longer.  Anyway, the point, not just to you but to everybody, is
that the review can't always be left to other people.  Some people
will review and not contribute any code, and that's great.  Some
people will contribute code but not review, and to the extent that we
can support that, it's also great.  But the giant backlog of
unreviewed patches which has accumulated shows that we have too many
people needing more review than they produce, and that is not great.

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

On Tue, Dec 13, 2016 at 11:11 PM, Pavan Deolasee
<pavan.deolasee@gmail.com> wrote:
> To be fair to myself, I did try to find patches with equal or more
> complexity. But most of them had (multiple) reviewers assigned and were
> being discussed for weeks and months. I did not think I could contribute
> positively to those discussions, mostly because meaningful review at that
> point would require much more in-depth knowledge of the area. So I picked
> couple of patches which did not have any reviewers. May be not the best
> decision, but I did what I thought was correct.

I'm a little tired right now because it's almost 2am here, so maybe I
should go to bed instead of writing emails when I might be excessively
grumpy, but I just don't buy this.  There are indeed a number of
patches which have provoked lots of discussion already, but there are
also many that have had virtually no review at all.  Many of the
parallel query patches fall into this category, and there are lots of
others.  CommitFest 2017-01 currently has 62 patches in the "Needs
Review" state, and it is just not the case that all 62 of those are
under active discussion and review.  I bet there are a dozen that have
had no replies at all and another dozen that have had only a handful
of fairly casual replies without any in-depth discussion.  Maybe more.

Now, I will agree that diving into a patch in an area that you've
never seen before can be challenging and intimidating.  But you're not
asking any less for your own patch.  You would like someone to dive
into your patch and figure it out, whether they know that area well or
not, and let's face it: most people don't.  I don't.  I've read the
email threads about WARM, but the concept hasn't sunk in for me yet.
I understand HOT and I understand the heap and indexes pretty well so
I'll figure it out eventually, but I don't have it figured out now and
that's only going to get solved if I go put in a bunch of time to go
learn.  I imagine virtually everyone is in the same position.
Similarly, I just spent a ton of time reviewing Amit Kapila's work on
hash indexes and I don't know a heck of a lot about hash indexes --
virtually nobody does, because that area has been largely ignored for
the last decade or so.  Yet if everybody uses that as an excuse, then
we don't get anywhere.

To put that another way, reviewing patches is hard, but we still have
to do it if we want to produce a quality release with good features.
If we don't do a good job reviewing and therefore don't commit things,
we'll have a disappointing release.  If we don't do a good job
reviewing but commit things anyway, then we'll have a horribly buggy
release.  If the patch we fail to review adequately happens to be
WARM, then those will very possibly be data-corrupting bugs, which are
particularly bad for our project's reputation for reliability.  Those
aren't good options, so we had better try to make sure that we do lots
of high-quality review of that patch and all the others.  If we can't
turn to the people who are writing the patches to help review them,
even though that's difficult, then I think that much-needed review
won't happen.

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

Here's a still-WIP patch that's a better candidate for inclusion.  In
this patch, I have created an executor node for indirect index scans.
This node is created whenever an indexscan path is chosen for an
indirect index.  The planner treats indirect indexes just like regular
indexes, except that they are explicitly excluded from index-only scans
and bitmap scans.

Indirect indexes are more costly to scan than regular indexes, because
of the need to scan the primary key index.  However, the fact that they
can be ignored for HOT considerations make them worthwhile in
update-heavy cases.

This patch only implements btree indirect indexes, but it is possible to
implement them with other index types too.  The btree case is probably
not terribly interesting in conjuncttion with Pavan's WARM, but on the
other hand it is expected that GIN indirect to remain useful.  I have
not implemented GIN indirect indexes yet, to keep the patch small; once
we have btree indirect indexes we can implement GIN, which should be
easy.

There are a few broken things yet, such as "REINDEX TABLE pg_class" and
some other operations specifically on pg_class.  This one in particular
breaks the regression tests, but that shouldn't be terribly difficult to
fix.  Other things I know about that need further work:

* The killtuple implementation is bogus: it may delete entries that are
visible to scans other than our own (in particular it may delete entries
that are being concurrently created, I think).

* We still pass PK values in scan->xs_ctup.t_self.  Shouldn't be
difficult to fix, if a bit invasive.

* Only one primary key column is supported.  Should be an easy fix if
the above is fixed.

* Fill in the UNIQUE_CHECK_INSERT_SINGLETON bits, to avoid duplicate
entries in the indirect index

* Figure out what's the deal with validate_index_heapscan

* Figure out if we need to apply ExecQual in IndirectIndexNext

* Verify whether NumOrderByKeys != 0 is necessary.  If so, test it.

* There's a probably bogus assertion in get_index_paths

* Better implementation of RelationGetPrimaryKey?  Maybe save PK in
relcache?


-- 
Álvaro Herrera                https://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

Alvaro Herrera wrote:

> There are a few broken things yet, such as "REINDEX TABLE pg_class" and
> some other operations specifically on pg_class.  This one in particular
> breaks the regression tests, but that shouldn't be terribly difficult to
> fix.

This version fixes this problem, so the regression tests now pass.
I fixed it by adding yet another index attribute bitmapset to
RelationData, so we keep track of "all indexed columns" separately from
"columns used by regular indexes" and "columns used by indirect
indexes".  A possible optimization is to remove the first list and just
keep "indirect" and "direct", and in the only case where we need all of
them, do a bms_union -- it's not performance-critical anyway.

-- 
Álvaro Herrera                https://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

Here's v3.  This one applies on top of the "interesting-attrs" patch I
sent a few hours ago:
https://www.postgresql.org/message-id/20161228232018.4hc66ndrzpz4g4wn@alvherre.pgsql
and contains a number of bugfixes that I discovered on my own (and which
therefore require no further explanation, since evidently no-one has
reviewed the patch yet).

One exception: in htup_details.h I changed the definition of
HeapTupleHeaderIsHeapOnly() so that it returns a true boolean rather
than a random bit in a wider integer.  Without this change, my compiler
complains when the result is passed as a bool argument into a function.

-- 
Álvaro Herrera                https://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

Attached is v4, which fixes a couple of relatively minor bugs.  There
are still things to tackle before this is committable, but coding review
of the new executor node would be welcome.

The big remaining item is still fitting the PK data in TIDs 6 bytes.
I've been looking at reworking the btree code to allow for an arbitrary
size; it doesn't look impossible although it's going to be rather
invasive.  Also, vacuuming: my answer continues to be that the killtuple
interface should be good enough, but it's possible to vacuum the index
separately from vacuuming the table anyway if you do a full scan and
check the PK tuples for each indirect tuple.

This patch implements killtuple: a scan that sees an indirect tuple not
returning anything from the heap marks the tuple as LP_DEAD.  Later,
when the page is about to be split, those tuples are removed.

I also have a note in the code about not inserting an indirect tuple
when an identical one already exists.  This is a correctness issue: we
return duplicated heap rows in certain cases.

-- 
Álvaro Herrera                https://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

On Fri, Dec 30, 2016 at 07:35:30PM -0300, Alvaro Herrera wrote:
> Attached is v4, which fixes a couple of relatively minor bugs.  There
> are still things to tackle before this is committable, but coding review
> of the new executor node would be welcome.
> 
> The big remaining item is still fitting the PK data in TIDs 6 bytes.
> I've been looking at reworking the btree code to allow for an arbitrary
> size; it doesn't look impossible although it's going to be rather
> invasive.  Also, vacuuming: my answer continues to be that the killtuple
> interface should be good enough, but it's possible to vacuum the index
> separately from vacuuming the table anyway if you do a full scan and
> check the PK tuples for each indirect tuple.
> 
> This patch implements killtuple: a scan that sees an indirect tuple not
> returning anything from the heap marks the tuple as LP_DEAD.  Later,
> when the page is about to be split, those tuples are removed.
> 
> I also have a note in the code about not inserting an indirect tuple
> when an identical one already exists.  This is a correctness issue: we
> return duplicated heap rows in certain cases.

I still question the value of this patch as it requires user
configuration vs. more aggressive HOT/WARM updates.

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

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +

On Sat, Dec 31, 2016 at 7:35 AM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
> Attached is v4, which fixes a couple of relatively minor bugs.  There
> are still things to tackle before this is committable, but coding review
> of the new executor node would be welcome.

Moved to CF 2017-03 because of a lack of reviews. The patch fails to
apply and needs a rebase, so it is marked as "waiting on author".
-- 
Michael

Hi Álvaro,

On 1/31/17 11:54 PM, Michael Paquier wrote:
> On Sat, Dec 31, 2016 at 7:35 AM, Alvaro Herrera
> <alvherre@2ndquadrant.com> wrote:
>> Attached is v4, which fixes a couple of relatively minor bugs.  There
>> are still things to tackle before this is committable, but coding review
>> of the new executor node would be welcome.
> 
> Moved to CF 2017-03 because of a lack of reviews. The patch fails to
> apply and needs a rebase, so it is marked as "waiting on author".

It looks like we need a rebase if it's going to attract any reviewers.

Might I suggest this patch is not complete enough to be in the last CF
for a release?  I know it's been around for a while, but it is a major
feature and the consensus and completeness do not seem to be there.

I would encourage you to move this to 2017-07.

Thanks,
-- 
-David
david@pgmasters.net