Subject: Re: Expanding HOT updates for expression and partial indexes

From: "Burd, Greg" <[email-masked]>
Date: Thu, 13 Feb 2025 18:46:18 +0000

Attached find an updated patchset v5 that is an evolution of v4.

Changes v4 to v5 are:
* replaced GUC with table reloption called "expression_checks" (open to other name ideas)
* minimal documentation updates to README.HOT to address changes
* avoid, when possible, the expensive path that requires evaluating an estate using bitmaps
* determines the set of summarized indexes requiring updates, only updates those
* more tests in heap_hot_updates.sql (perhaps too many...)
* rebased to master, formatted, and make check-world passes

More comments in context below...

-greg

> On Feb 11, 2025, at 4:18 PM, Matthias van de Meent <[email-masked]> wrote:
>
>
> On Mon, 10 Feb 2025 at 20:11, Burd, Greg <[email-masked]> wrote:
>>> On Feb 10, 2025, at 12:17 PM, Matthias van de Meent <[email-masked]> wrote:
>>>
>>>>
>>>> I have a few concerns with the patch, things I’d greatly appreciate your thoughts on:
>>>>
>>>> First, I pass an EState along the update path to enable running the checks in heapam, this works but leaves me feeling as if I violated separation of concerns. If there is a better way to do this let me know or if you think the cost of creating one in the execIndexing.c ExecIndexesRequiringUpdates() is okay that’s another possibility.
>>>
>>> I think that doesn't have to be bad.
>>
>> Meaning that the approach I’ve taken is okay with you?
>
> If you mean "passing EState down through the AM so we can check if we
> really need HOT updates", then Yes, that's OK. I don't think the basic
> idea (executing the projections to check for differences) is bad per
> se, however I do think we may need more design work on the exact shape
> of how ExecIndexesRequiringUpdates() receives its information (which
> includes the EState).
>
> E.g. we could pass an opaquely typed pointer that's passed from the
> executor state through the table_update method into this
> ExecIndexesRequiringUpdates(). That opaque struct would then contain
> the important information for index update state checking, so that the
> AM can't realistically break things without bypassing the separation
> of concerns, and doesn't have to know about any executor nodes.

I'm open to this idea and will attempt an implementation in v6, ideas welcome.

>>>> Third, there is overhead to this patch, it is no longer a single simple bitmap test to choose HOT or not in heap_update().
>>>
>>> Why can't it mostly be that simple in simple cases?
>>
>> It can remain that simple in the cases you mention.  In relcache the hot blocking attributes are nearly the same, only the summarizing attributes are removed.  The first test then in heap_update() is for overlap with the modified set.  When there is none, the update will proceed on the HOT path.
>>
>> The presence of a summarizing index is determined in ExecIndexesRequiringUpdates() in execIndexing.c, so a slightly longer code path but not much new overhead.
>
> Yes, but that's only determined at an index-by-index level, rather
> than determined all at once, and that's real bad when you have
> hundreds of indexes to go through (however unlikely it might be, I've
> heard of cases where there are 1000s of indexes on one table). So, I
> prefer limiting any O(n_indexes) operations to only the most critical
> cases.

This makes sense, and I agree that avoiding O(n_indexes) operations is a good goal when possible.

>>> I mean, it's clear that "updated indexed column's value == non-HOT
>>> update". And that to determine whether an updated *projected* column's
>>> value (i.e., expression index column's value) was actually updated we
>>> need to calculate the previous and current index value, thus execute
>>> the projection twice. But why would we have significant additional
>>> overhead if there are no expression indexes, or when we can know by
>>> bitmap overlap that the only interesting cases are summarizing
>>> indexes?
>>
>> You’re right, there’s not a lot of new overhead in that case except what happens in ExecIndexesRequiringUpdates() to scan over the list of IndexInfo.  It is really only when there are many expressions/predicates requiring examination that there is any significant cost to this approach AFAICT (but if you see something please point it out).
>
> See the attached approach. Evaluation of the expressions only has to
> happen if there are any HOT-blocking attributes which are exclusively
> hot-blockingly indexed through expressions, so if the updated
> attribute numbers are a subset of hotblockingexprattrs. (substitute
> hotblocking with summarizing for the summarizing approach)

I believe I've incorporated the gist of your idea in this v5 patch, let me know if I missed something.

>>> I would've implemented this with (1) two new bitmaps, one each for
>>> normal and summarizing indexes, each containing which columns are
>>> exclusively used in expression indexes (and which should thus be used
>>> to trigger the (comparatively) expensive recalculation).
>>
>> That was one where I started, over time that became harder to work as the bitmaps contain the union of index attributes for the table not per-column.
>
> I think it's fairly easy to create, though.
>
>> Now there is one bitmap to cover the broadest case and then a function to find the modified set of indexes where each is examined against bitmaps that contain only attributes specific to the index in question.  This helped in cases where there were both expression and non-expression indexes on the same attribute.
>
> Fair, but do we care about one expression index on (attr1->>'data')'s
> value *not* changing when an index on (attr1) exists and attr1 has
> changed? That index on att1 would block HOT updates regardless of the
> (lack of) changes to the (att1->>'data') index, so doing those
> expensive calculations seems quite wasteful.

Agreed, when both a non-expression and an expression index exist on the same attribute then the expression checks are unnecessary and should be avoided.  In this v5 patchset this case becomes two checks of bitmaps (first hot_attrs, then exclusively exp_attrs) before proceeding with a non-HOT update.

> So, in my opinion, we should also keep track of those attributes only
> included in expressions of indexes, and that's fairly easy: see
> attached prototype.diff.txt (might need some work, the patch was
> drafted on v16's codebase, but the idea is clear).

Thank you for your patch, I've included and expanded it.

> The resulting %exprattrs bitmap contains attributes that are used only
> in expressions of those index types.
>
>>> The "new" output of these expression
>>> evaluations would be stored to be used later as index datums, reducing
>>> the number of per-expression evaluations down to 2 at most, rather
>>> than 2+1 when the index needs an insertion but the expression itself
>>> wasn't updated.
>>
>> Not reforming the new index tuples is also an interesting optimization.  I wonder how that can be passed from within heapam’s call into a function in execIndexing up into nodeModifiyTable and back down into execIndexing and on to the index access method?  I’ll have to think about that, ideas welcome.
>
> Note that index tuple forming happens only in the index AM, it's the
> Datum construction (i.e. projection from attributes/tuple to indexed
> value) that I'd like to deduplicate. Though looking at the current
> code, I don't think it's reasonable to have that as a requirement for
> this work. It'd be a nice-to-have for sure, but not as requirement.

Agreed that it's a nice-to-have, but not a priority.

>>> Do you have any documentation on the approaches used, and the specific
>>> differences between v3 and v4? I don't see much of that in your
>>> initial mail, and the patches themselves also don't show much of that
>>> in their details. I'd like at least some documentation of the new
>>> behaviour in src/backend/access/heap/README.HOT at some point before
>>> this got marked as RFC in the commitfest app, though preferably sooner
>>> rather than later.
>>
>> Good point, I should have updated README.HOT with the initial patchset.  I’ll jump on that and update ASAP.
>
> Thanks in advance.
>
> Kind regards,
>
> Matthias van de Meent
> Neon (https://neon.tech)
> <prototype.diff.txt>

---

From: Matthias van de Meent <[email-masked]>
Date: Sat, 15 Feb 2025 11:49:47 +0100

> * rebased to master, formatted, and make check-world passes

Thank you for the update. Below some comments, in no particular order.

-----

I'm not a fan of how you replaced TU_UpdateIndexes with a bitmap. It
seems unergonomic and a waste of performance.

In HEAD, we don't do any expensive computations for the fast path of
"indexed attribute updated" - at most we do the bitmap compare and
then set a pointer. With this patch, the way we signal that is by
allocating a bitmap of size O(n_indexes). That's potentially quite
expensive (given 1000s of indexes), and definitely more expensive than
only a pointer assignment.
In HEAD, we have a clear indication of which classes of indexes to
update, with TU_UpdateIndexes. With this patch, we have to derive that
from the (lack of) bits in the bitmap that might be output by the
table_update procedure.

I think we can do with an additional parameter for which indexes would
be updated (or store that info in the parameter which also will hold
EState et al). I think it's cheaper that way, too - only when
update_indexes could be TU_SUMMARIZING we might need the exact
information for which indexes to insert new tuples into, and it only
really needs to be sized to the number of summarizing indexes (usually
small/nonexistent, but potentially huge).

-----

I think your patch design came from trying to include at least two
distinct optimizations:
  1) to make the HOT-or-not check include whether the expressions of
indexes were updated, and
  2) to only insert index tuples into indexes that got updated values
when table_tuple_update returns update_indexes=TU_Summarizing.

While they touch similar code (clearly seen here), I think those
should be implemented in different patches. For (1), the current API
surface is good enough when the EState is passed down. For (2), you'll
indeed also need an additional argument we can use to fill with the
right summarizing indexes, but I don't think that can nor should
replace the function of TU_UpdateIndexes.

If you agree with my observation of those being distinct
optimizations, could you split this patch into parts (but still within
the same series) so that these are separately reviewable?

-----

I notice that ExecIndexesRequiringUpdates() does work on all indexes,
rather than just indexes relevant to this exact phase of checking. I
think that is a waste of time, so if we sort the indexes in order of
[hotblocking without expressions, hotblocking with expressions,
summarizing], then (with stored start/end indexes) we can save time in
cases where there are comparatively few of the types we're not going
to look at.

As an extreme example: we shouldn't do the (comparatively) expensive
work evaluating expressions to determine which of 1000s of summarizing
indexes has been updated when we're still not sure if we can apply HOT
at all.

(Sidenote: Though, arguably, we could be smarter by skipping index
insertions into unmodified summarizing indexes altogether regardless
of HOT status, as long as the update is on the same page - but that's
getting ahead of ourselves and not relevant to this discussion.)

-----

I noticed you've disabled any passing of "HOT or not" in the
simple_update cases, and have done away with the various checks that
are in place to prevent corruption. I don't think that's a great idea,
it's quite likely to cause bugs.

-----

You're extracting type info from the opclass, to use in
datum_image_eq(). Couldn't you instead use the index relation's
TupleDesc and its stored attribute information instead? That saves us
from having to do further catalog lookups during execution. I'm also
fairly sure that that information is supposed to be a more accurate
representation of attributes' expression output types than the
opclass' type information (though, they probably should match).

-----

The operations applied in ExecIndexesRequiringUpdates partially
duplicate those done in index_unchanged_by_update. Can we (partially)
unify this, and pass which indexes were updated through the IndexInfo,
rather than the current bitmap?

-----

I don't see a good reason to add IndexInfo to Relation, by way of
rd_indexInfoList. It seems like an ad-hoc way of passing data around,
and I don't think that's the right way.

> I believe I've incorporated the gist of your idea in this v5 patch, let me know if I missed something.

Seems about accurate.

---

From: "Burd, Greg" <[email-masked]>
Date: Mon, 17 Feb 2025 19:53:47 +0000

Matthias,

First off, I can't thank you enough for taking the time to review in detail the patch.  I appreciate and value your time and excellent feedback.

Second, I think that I should admit to the fact that I've also been working on making PHOT functional again.  I have it rebased against master, however it is still at the proof-of-concept phase and there are some larger issues to flesh out.  One of the changes in this patch would have enabled that future with PHOT, specifically the bitmap as the method for conveying what indexes need updating.

That said, I agree that this patch should simply focus on expanding HOT to expression indexes and partial indexes.  With that in mind I will return to the TU_UpdateIndexes approach, even though I'm not a fan of it, and later propose the bitmap approach (or something better) as part of PHOT if and when that's ready.

Changes v5 to v6:
* reverted to TU_UpdateIndexes rather than Bitmapset
* renamed ExecIndexesRequiringUpdates to ExecIndexesExpressionsWereNotUpdated
* ExecIndexesExpressionsWereNotUpdated returns bool, exits early if possible
* simple_update paths can be HOT once again
* removed efforts to determine the subset of updated summarizing indexes
* create filtered IndexInfo list in relcache containing only indexes with expressions
* now using index TupleDesc CompactAttributes for arguments to datum_is_equal() <- did I get this one right, I'm not sure it is what you had in mind

best.

-greg

> On Feb 15, 2025, at 5:49 AM, Matthias van de Meent <[email-masked]> wrote:
> 

Fair point.  I'm not a fan of the TU_UpdateIndexes enum, but I appreciate your argument against the bitmapset.  Under the conditions you describe (1000s of indexes) it could grow unwieldy and impact performance.

> from the (lack of) bits in the bitmap that might be output by the

Yes, but... that "clear indication" is lacking the ability to convey more detailed information.  It doesn't tell you which summarizing indexes really need updating just that as a result of being on the HOT path all summarizing indexes require updates.

> small/nonexistent, but potentially huge).

Okay, yes with this patch we need only concern ourselves with all, none, or some subset of summarizing as before.  I'll work on the opaque parameter next iteration.

> when table_tuple_update returns update_indexes=TU_Summarizing.

It did.  (1) for sure, but the second is more related to the PHOT work (as mentioned above).  With that work almost all updates are on the HOT/PHOT path and so the bitmap of changed indexes is small.  It would take an update of a table with 1000s of indexes where almost all those were modified to create a bitmap that was large, which certainly could (and somewhere likely does) exist, but it's not the common case (I'd imagine).  In that case the work to update all those indexes will likely dwarf the work to build that bitmap, but I could be wrong.

But you're fundamentally right, I'm conflating two ideas and I shouldn't.  I will focus the changes required for this idea without pulling in changes useful to a future ones.

> replace the function of TU_UpdateIndexes.

Okay, I'll combine the earlier v3 patch with the changes in v5.  That should leave TU_UpdateIndexes in place and allow for HOT with expression indexes.  I'll change the ExecIndexesRequiringUpdates() a bit (and rename it) so that it is just a boolean test for any index that spoils the HOT path and can exit early in that case potentially avoiding extra work.

> the same series) so that these are separately reviewable?

I agree, but I think that a single simple more focused patch will suffice.

> cases where there are comparatively few of the types we're not going

If I plan on just having ExecIndexesRequiringUpdates() return a bool rather than a bitmap then sorting, or even just filtering the list of IndexInfo to only include indexes with expressions, makes sense.  That way the only indexes in question in that function's loop will be those that may spoil the HOT path.  When that list is length 0, we can skip the tests entirely.

> indexes has been updated when we're still not sure if we can apply HOT

That makes sense, and your sorting idea would inform that kind of work.  I'll keep that in mind if I reintroduce code that aims to only update changed summarized indexes.

> it's quite likely to cause bugs.

Yes.  I'll resurrect that.

> opclass' type information (though, they probably should match).

I hadn't thought of that, I think it's a valid idea and I'll update accordingly.  I think I understand what you are suggesting.
 
> rather than the current bitmap?

I think I do that now, feel free to say otherwise.  When the expression is checked in ExecIndexesExpressionsWereNotUpdated() I set:

/* Shortcut index_unchanged_by_update(), we know the answer. */                                                                                                                            indexInfo->ii_CheckedUnchanged = true;                                                                                                                                                     indexInfo->ii_IndexUnchanged = !changed;

That prevents duplicate effort in index_unchanged_by_update().

> and I don't think that's the right way.

At one point I'd created a way to get this set via relcache, I will resurrect that approach but I'm not sure it is what you were hinting at.  The current method avoids pulling a the lock on the index to build the list, but doing that once in relcache isn't horrible.  Maybe you were suggesting using that opaque struct to pass around the list of IndexInfo?  Let me know on this one if you had a specific idea.  The swap I've made in v6 really just moves the IndexInfo list to a filtered list with a new name created in relcache.

---

From: "Burd, Greg" <[email-masked]>
Date: Tue, 18 Feb 2025 18:09:22 +0000

Changes v6 to v7:
* Fixed documentation oversight causing build failure
* Changed how I convey attribute len/by-val in IndexInfo
* Fixed method to shortcut index_unchanged_by_update() when possible

-greg

---

From: "Burd, Greg" <[email-masked]>
Date: Wed, 5 Mar 2025 17:20:34 +0000

Hello,

I've rebased and updated the patch a bit.  The biggest change is that the performance penalty measured with v1 of this patch is essentially gone in v10.  The overhead was due to re-creating IndexInfo information unnecessarily, which I found existed in the estate.  I've added a few fields in IndexInfo that are not populated by default but necessary when checking expression indexes, those fields are populated on demand and only once limiting their overhead.
  
Here's what you'll find if you look into execIndexing.c where the majority of changes happened. 

* assumes estate->es_result_relations[0] is the ResultRelInfo being updated
* uses ri_IndexRelationInfo[] from within estate rather than re-creating it
* augments IndexInfo only when needed for testing expressions and only once
* only creates a local old/new TupleTableSlot when not present in estate
* retains existing summarized index HOT update logic

One remaining concern stems from the assumption that estate->es_result_relations[0] is always going to be the relation being updated.  This is guarded by assert()'s in the patch.  It seems this is safe, all tests are passing (including TAP) and my review of the code seems to line up with that assumption.  That said... opinions?

Another lingering question is under what conditions the old/new TupleTableSlots are not created and available via the ResultRelInfo found in estate.  I've only seen this happen when there is an INSERT ... ON CONFLICT UPDATE ... with expression indexes.  I was hopeful that in all cases I could avoid re-creating those when checking expression indexes to avoid that repeated overhead.  I still avoid it when possible in this patch.

When you have time I'd appreciate any feedback.

-greg
Amazon Web Services: https://aws.amazon.com

---

From: Matthias van de Meent <[email-masked]>
Date: Wed, 5 Mar 2025 23:56:42 +0100

Hi,

Sorry for the delay. This is a reply for the mail thread up to 17 Feb,
so it might be very out-of-date by now, in which case sorry for the
noise.

> Yes, but... that "clear indication" is lacking the ability to convey more detailed information.  It doesn't tell you which summarizing indexes really need updating just that as a result of being on…

Agreed that it's not great if you want to know about which indexes
were meaningfully updated. I think that barring significant advances
in performance of update checks, we can devise a way of transfering
this info to the table_tuple_update caller once we get a need for more
detailed information (e.g. this could be transfered through the
IndexInfo* that's currently also used by index_unchanged_by_update).

> Okay, yes with this patch we need only concern ourselves with all, none, or some subset of summarizing as before.  I'll work on the opaque parameter next iteration.

Thanks!

> If I plan on just having ExecIndexesRequiringUpdates() return a bool rather than a bitmap then sorting, or even just filtering the list of IndexInfo to only include indexes with expressions, makes…

Yes, exactly. Though I'm not sure it should hit that path if the
length is 0, as would mean we had expression indexes that matched the
updated columns, but somehow none are in the list?

> I hadn't thought of that, I think it's a valid idea and I'll update accordingly.  I think I understand what you are suggesting.

Thanks, that change was exactly what I meant.

> That prevents duplicate effort in index_unchanged_by_update().

Exactly, yes.

> At one point I'd created a way to get this set via relcache, I will resurrect that approach but I'm not sure it is what you were hinting at.

AFAIK, we don't have IndexInfo in the relcaches currently. I'm very
hesitant to add an executor node (!) subtype to catalog caches, as
IndexInfos are also used to store temporary information about e.g.
index tuple insertion state, which (if IndexInfo is stored in
relcaches) would imply modifying relcache entries without any further
locks, and I'm not sure that's at all an OK thing to do.

>  The current method avoids pulling a the lock on the index to build the list, but doing that once in relcache isn't horrible.  Maybe you were suggesting using that opaque struct to pass around the list of IndexInfo?  Let me know on this one if you had a specific idea.  The swap I've made in v6 really just moves the IndexInfo list to a filtered list with a new name created in relcache.

My main concern is the storage of executor nodes(!) directly in the
relcache. I don't think we need that: We have relatively direct access
to the right IndexInfo** in ResultRelInfo->ri_IndexRelationInfo, which
I think should be sufficient for this purpose. (The relevant RRI is
available in table_tuple_update caller ExecUpdateAct; and could be
passed down by ExecSimpleRelationUpdate to simple_table_tuple_update,
covering both (current, core) callers of table_tuple_update). That
would then be passed down to the TableAM using an opaque pointer type;
for example (names, file locations, exact layout all bikesheddable):

/* tableam.h */
/* exact definition somewhere else, in e.g. an executor_internal.h */
typedef struct TU_UpdateIndexData TU_UpdateIndexData;

table_tuple_update(..., TU_UpdateIndexData *idxupdate, ...)

/* executor.h */

TU_UpdateIndexes
UpdateDetermineChangedIndexes(TU_UpdateIndexData *idxupdate,
TableTupleSlot *old, TableTupleSlot *new, bitmap *changed_atts, ...);

/* executor_internal.h */
struct TU_UpdateIndexData
{
    EState estate;
    IndexInfo **idxinfos;
    ...
}

-----

Looking at your later comments about RRI in patch v8, I think that
would solve and clean up the way that you currently get access to the
RRI and thus index set.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)