Skip to content

Commit 9dc718b

Browse files
petergeogheganpetergeoghegan
committed
Pass down "logically unchanged index" hint.
Add an executor aminsert() hint mechanism that informs index AMs that the incoming index tuple (the tuple that accompanies the hint) is not being inserted by execution of an SQL statement that logically modifies any of the index's key columns. The hint is received by indexes when an UPDATE takes place that does not apply an optimization like heapam's HOT (though only for indexes where all key columns are logically unchanged). Any index tuple that receives the hint on insert is expected to be a duplicate of at least one existing older version that is needed for the same logical row. Related versions will typically be stored on the same index page, at least within index AMs that apply the hint. Recognizing the difference between MVCC version churn duplicates and true logical row duplicates at the index AM level can help with cleanup of garbage index tuples. Cleanup can intelligently target tuples that are likely to be garbage, without wasting too many cycles on less promising tuples/pages (index pages with little or no version churn). This is infrastructure for an upcoming commit that will teach nbtree to perform bottom-up index deletion. No index AM actually applies the hint just yet. Author: Peter Geoghegan <pg@bowt.ie> Reviewed-By: Victor Yegorov <vyegorov@gmail.com> Discussion: https://postgr.es/m/CAH2-Wz=CEKFa74EScx_hFVshCOn6AA5T-ajFASTdzipdkLTNQQ@mail.gmail.com
1 parent 39b0369 commit 9dc718b

File tree

31 files changed

+214
-25
lines changed

31 files changed

+214
-25
lines changed

‎contrib/bloom/blinsert.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -198,6 +198,7 @@ bool
198198
blinsert(Relation index, Datum *values, bool *isnull,
199199
ItemPointer ht_ctid, Relation heapRel,
200200
IndexUniqueCheck checkUnique,
201+
bool indexUnchanged,
201202
IndexInfo *indexInfo)
202203
{
203204
BloomState blstate;

‎contrib/bloom/bloom.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -192,6 +192,7 @@ extern bool blvalidate(Oid opclassoid);
192192
extern bool blinsert(Relation index, Datum *values, bool *isnull,
193193
ItemPointer ht_ctid, Relation heapRel,
194194
IndexUniqueCheck checkUnique,
195+
bool indexUnchanged,
195196
struct IndexInfo *indexInfo);
196197
extern IndexScanDesc blbeginscan(Relation r, int nkeys, int norderbys);
197198
extern int64 blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);

‎doc/src/sgml/indexam.sgml

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -293,6 +293,7 @@ aminsert (Relation indexRelation,
293293
ItemPointer heap_tid,
294294
Relation heapRelation,
295295
IndexUniqueCheck checkUnique,
296+
bool indexUnchanged,
296297
IndexInfo *indexInfo);
297298
</programlisting>
298299
Insert a new tuple into an existing index. The <literal>values</literal> and
@@ -308,6 +309,20 @@ aminsert (Relation indexRelation,
308309
look into the heap to verify tuple liveness).
309310
</para>
310311

312+
<para>
313+
The <literal>indexUnchanged</literal> boolean value gives a hint
314+
about the nature of the tuple to be indexed. When it is true,
315+
the tuple is a duplicate of some existing tuple in the index. The
316+
new tuple is a logically unchanged successor MVCC tuple version. This
317+
happens when an <command>UPDATE</command> takes place that does not
318+
modify any columns covered by the index, but nevertheless requires a
319+
new version in the index. The index AM may use this hint to decide
320+
to apply bottom-up index deletion in parts of the index where many
321+
versions of the same logical row accumulate. Note that updating a
322+
non-key column does not affect the value of
323+
<literal>indexUnchanged</literal>.
324+
</para>
325+
311326
<para>
312327
The function's Boolean result value is significant only when
313328
<literal>checkUnique</literal> is <literal>UNIQUE_CHECK_PARTIAL</literal>.

‎src/backend/access/brin/brin.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -151,6 +151,7 @@ bool
151151
brininsert(Relation idxRel, Datum *values, bool *nulls,
152152
ItemPointer heaptid, Relation heapRel,
153153
IndexUniqueCheck checkUnique,
154+
bool indexUnchanged,
154155
IndexInfo *indexInfo)
155156
{
156157
BlockNumber pagesPerRange;

‎src/backend/access/common/toast_internals.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -328,7 +328,7 @@ toast_save_datum(Relation rel, Datum value,
328328
toastrel,
329329
toastidxs[i]->rd_index->indisunique ?
330330
UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
331-
NULL);
331+
false, NULL);
332332
}
333333

334334
/*

‎src/backend/access/gin/gininsert.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -488,6 +488,7 @@ bool
488488
gininsert(Relation index, Datum *values, bool *isnull,
489489
ItemPointer ht_ctid, Relation heapRel,
490490
IndexUniqueCheck checkUnique,
491+
bool indexUnchanged,
491492
IndexInfo *indexInfo)
492493
{
493494
GinState *ginstate = (GinState *) indexInfo->ii_AmCache;

‎src/backend/access/gist/gist.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -156,6 +156,7 @@ bool
156156
gistinsert(Relation r, Datum *values, bool *isnull,
157157
ItemPointer ht_ctid, Relation heapRel,
158158
IndexUniqueCheck checkUnique,
159+
bool indexUnchanged,
159160
IndexInfo *indexInfo)
160161
{
161162
GISTSTATE *giststate = (GISTSTATE *) indexInfo->ii_AmCache;

‎src/backend/access/hash/hash.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -247,6 +247,7 @@ bool
247247
hashinsert(Relation rel, Datum *values, bool *isnull,
248248
ItemPointer ht_ctid, Relation heapRel,
249249
IndexUniqueCheck checkUnique,
250+
bool indexUnchanged,
250251
IndexInfo *indexInfo)
251252
{
252253
Datum index_values[1];

‎src/backend/access/heap/heapam_handler.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1956,6 +1956,7 @@ heapam_index_validate_scan(Relation heapRelation,
19561956
heapRelation,
19571957
indexInfo->ii_Unique ?
19581958
UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
1959+
false,
19591960
indexInfo);
19601961

19611962
state->tups_inserted += 1;

‎src/backend/access/index/indexam.c

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -179,6 +179,7 @@ index_insert(Relation indexRelation,
179179
ItemPointer heap_t_ctid,
180180
Relation heapRelation,
181181
IndexUniqueCheck checkUnique,
182+
bool indexUnchanged,
182183
IndexInfo *indexInfo)
183184
{
184185
RELATION_CHECKS;
@@ -191,7 +192,8 @@ index_insert(Relation indexRelation,
191192

192193
return indexRelation->rd_indam->aminsert(indexRelation, values, isnull,
193194
heap_t_ctid, heapRelation,
194-
checkUnique, indexInfo);
195+
checkUnique, indexUnchanged,
196+
indexInfo);
195197
}
196198

197199
/*

‎src/backend/access/nbtree/nbtree.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,7 @@ bool
199199
btinsert(Relation rel, Datum *values, bool *isnull,
200200
ItemPointer ht_ctid, Relation heapRel,
201201
IndexUniqueCheck checkUnique,
202+
bool indexUnchanged,
202203
IndexInfo *indexInfo)
203204
{
204205
bool result;

‎src/backend/access/spgist/spginsert.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,6 +207,7 @@ bool
207207
spginsert(Relation index, Datum *values, bool *isnull,
208208
ItemPointer ht_ctid, Relation heapRel,
209209
IndexUniqueCheck checkUnique,
210+
bool indexUnchanged,
210211
IndexInfo *indexInfo)
211212
{
212213
SpGistState spgstate;

‎src/backend/catalog/indexing.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -162,6 +162,7 @@ CatalogIndexInsert(CatalogIndexState indstate, HeapTuple heapTuple)
162162
heapRelation,
163163
index->rd_index->indisunique ?
164164
UNIQUE_CHECK_YES : UNIQUE_CHECK_NO,
165+
false,
165166
indexInfo);
166167
}
167168

‎src/backend/commands/constraint.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -175,7 +175,7 @@ unique_key_recheck(PG_FUNCTION_ARGS)
175175
*/
176176
index_insert(indexRel, values, isnull, &checktid,
177177
trigdata->tg_relation, UNIQUE_CHECK_EXISTING,
178-
indexInfo);
178+
false, indexInfo);
179179
}
180180
else
181181
{

‎src/backend/commands/copyfrom.c

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -342,8 +342,8 @@ CopyMultiInsertBufferFlush(CopyMultiInsertInfo *miinfo,
342342
cstate->cur_lineno = buffer->linenos[i];
343343
recheckIndexes =
344344
ExecInsertIndexTuples(resultRelInfo,
345-
buffer->slots[i], estate, false, NULL,
346-
NIL);
345+
buffer->slots[i], estate, false, false,
346+
NULL, NIL);
347347
ExecARInsertTriggers(estate, resultRelInfo,
348348
slots[i], recheckIndexes,
349349
cstate->transition_capture);
@@ -1087,6 +1087,7 @@ CopyFrom(CopyFromState cstate)
10871087
myslot,
10881088
estate,
10891089
false,
1090+
false,
10901091
NULL,
10911092
NIL);
10921093
}

‎src/backend/commands/trigger.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -71,10 +71,8 @@ int SessionReplicationRole = SESSION_REPLICATION_ROLE_ORIGIN;
7171
static int MyTriggerDepth = 0;
7272

7373
/*
74-
* Note that similar macros also exist in executor/execMain.c. There does not
75-
* appear to be any good header to put them into, given the structures that
76-
* they use, so we let them be duplicated. Be sure to update all if one needs
77-
* to be changed, however.
74+
* The authoritative version of this macro is in executor/execMain.c. Be sure
75+
* to keep everything in sync.
7876
*/
7977
#define GetAllUpdatedColumns(relinfo, estate) \
8078
(bms_union(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->updatedCols, \

‎src/backend/executor/execIndexing.c

Lines changed: 156 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,15 @@ typedef enum
124124
CEOUC_LIVELOCK_PREVENTING_WAIT
125125
} CEOUC_WAIT_MODE;
126126

127+
/*
128+
* The authoritative version of these macro are in executor/execMain.c. Be
129+
* sure to keep everything in sync.
130+
*/
131+
#define GetUpdatedColumns(relinfo, estate) \
132+
(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->updatedCols)
133+
#define GetExtraUpdatedColumns(relinfo, estate) \
134+
(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->extraUpdatedCols)
135+
127136
static bool check_exclusion_or_unique_constraint(Relation heap, Relation index,
128137
IndexInfo *indexInfo,
129138
ItemPointer tupleid,
@@ -136,6 +145,11 @@ static bool check_exclusion_or_unique_constraint(Relation heap, Relation index,
136145
static bool index_recheck_constraint(Relation index, Oid *constr_procs,
137146
Datum *existing_values, bool *existing_isnull,
138147
Datum *new_values);
148+
static bool index_unchanged_by_update(ResultRelInfo *resultRelInfo,
149+
EState *estate, IndexInfo *indexInfo,
150+
Relation indexRelation);
151+
static bool index_expression_changed_walker(Node *node,
152+
Bitmapset *allUpdatedCols);
139153

140154
/* ----------------------------------------------------------------
141155
* ExecOpenIndices
@@ -254,6 +268,16 @@ ExecCloseIndices(ResultRelInfo *resultRelInfo)
254268
* into all the relations indexing the result relation
255269
* when a heap tuple is inserted into the result relation.
256270
*
271+
* When 'update' is true, executor is performing an UPDATE
272+
* that could not use an optimization like heapam's HOT (in
273+
* more general terms a call to table_tuple_update() took
274+
* place and set 'update_indexes' to true). Receiving this
275+
* hint makes us consider if we should pass down the
276+
* 'indexUnchanged' hint in turn. That's something that we
277+
* figure out for each index_insert() call iff 'update' is
278+
* true. (When 'update' is false we already know not to pass
279+
* the hint to any index.)
280+
*
257281
* Unique and exclusion constraints are enforced at the same
258282
* time. This returns a list of index OIDs for any unique or
259283
* exclusion constraints that are deferred and that had
@@ -263,16 +287,13 @@ ExecCloseIndices(ResultRelInfo *resultRelInfo)
263287
*
264288
* If 'arbiterIndexes' is nonempty, noDupErr applies only to
265289
* those indexes. NIL means noDupErr applies to all indexes.
266-
*
267-
* CAUTION: this must not be called for a HOT update.
268-
* We can't defend against that here for lack of info.
269-
* Should we change the API to make it safer?
270290
* ----------------------------------------------------------------
271291
*/
272292
List *
273293
ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
274294
TupleTableSlot *slot,
275295
EState *estate,
296+
bool update,
276297
bool noDupErr,
277298
bool *specConflict,
278299
List *arbiterIndexes)
@@ -319,6 +340,7 @@ ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
319340
IndexInfo *indexInfo;
320341
bool applyNoDupErr;
321342
IndexUniqueCheck checkUnique;
343+
bool indexUnchanged;
322344
bool satisfiesConstraint;
323345

324346
if (indexRelation == NULL)
@@ -389,13 +411,24 @@ ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
389411
else
390412
checkUnique = UNIQUE_CHECK_PARTIAL;
391413

414+
/*
415+
* There's definitely going to be an index_insert() call for this
416+
* index. If we're being called as part of an UPDATE statement,
417+
* consider if the 'indexUnchanged' = true hint should be passed.
418+
*/
419+
indexUnchanged = update && index_unchanged_by_update(resultRelInfo,
420+
estate,
421+
indexInfo,
422+
indexRelation);
423+
392424
satisfiesConstraint =
393425
index_insert(indexRelation, /* index relation */
394426
values, /* array of index Datums */
395427
isnull, /* null flags */
396428
tupleid, /* tid of heap tuple */
397429
heapRelation, /* heap relation */
398430
checkUnique, /* type of uniqueness check to do */
431+
indexUnchanged, /* UPDATE without logical change? */
399432
indexInfo); /* index AM may need this */
400433

401434
/*
@@ -899,3 +932,122 @@ index_recheck_constraint(Relation index, Oid *constr_procs,
899932

900933
return true;
901934
}
935+
936+
/*
937+
* Check if ExecInsertIndexTuples() should pass indexUnchanged hint.
938+
*
939+
* When the executor performs an UPDATE that requires a new round of index
940+
* tuples, determine if we should pass 'indexUnchanged' = true hint for one
941+
* single index.
942+
*/
943+
static bool
944+
index_unchanged_by_update(ResultRelInfo *resultRelInfo, EState *estate,
945+
IndexInfo *indexInfo, Relation indexRelation)
946+
{
947+
Bitmapset *updatedCols = GetUpdatedColumns(resultRelInfo, estate);
948+
Bitmapset *extraUpdatedCols = GetExtraUpdatedColumns(resultRelInfo, estate);
949+
Bitmapset *allUpdatedCols;
950+
bool hasexpression = false;
951+
List *idxExprs;
952+
953+
/*
954+
* Check for indexed attribute overlap with updated columns.
955+
*
956+
* Only do this for key columns. A change to a non-key column within an
957+
* INCLUDE index should not be counted here. Non-key column values are
958+
* opaque payload state to the index AM, a little like an extra table TID.
959+
*/
960+
for (int attr = 0; attr < indexInfo->ii_NumIndexKeyAttrs; attr++)
961+
{
962+
int keycol = indexInfo->ii_IndexAttrNumbers[attr];
963+
964+
if (keycol <= 0)
965+
{
966+
/*
967+
* Skip expressions for now, but remember to deal with them later
968+
* on
969+
*/
970+
hasexpression = true;
971+
continue;
972+
}
973+
974+
if (bms_is_member(keycol - FirstLowInvalidHeapAttributeNumber,
975+
updatedCols) ||
976+
bms_is_member(keycol - FirstLowInvalidHeapAttributeNumber,
977+
extraUpdatedCols))
978+
{
979+
/* Changed key column -- don't hint for this index */
980+
return false;
981+
}
982+
}
983+
984+
/*
985+
* When we get this far and index has no expressions, return true so that
986+
* index_insert() call will go on to pass 'indexUnchanged' = true hint.
987+
*
988+
* The _absence_ of an indexed key attribute that overlaps with updated
989+
* attributes (in addition to the total absence of indexed expressions)
990+
* shows that the index as a whole is logically unchanged by UPDATE.
991+
*/
992+
if (!hasexpression)
993+
return true;
994+
995+
/*
996+
* Need to pass only one bms to expression_tree_walker helper function.
997+
* Avoid allocating memory in common case where there are no extra cols.
998+
*/
999+
if (!extraUpdatedCols)
1000+
allUpdatedCols = updatedCols;
1001+
else
1002+
allUpdatedCols = bms_union(updatedCols, extraUpdatedCols);
1003+
1004+
/*
1005+
* We have to work slightly harder in the event of indexed expressions,
1006+
* but the principle is the same as before: try to find columns (Vars,
1007+
* actually) that overlap with known-updated columns.
1008+
*
1009+
* If we find any matching Vars, don't pass hint for index. Otherwise
1010+
* pass hint.
1011+
*/
1012+
idxExprs = RelationGetIndexExpressions(indexRelation);
1013+
hasexpression = index_expression_changed_walker((Node *) idxExprs,
1014+
allUpdatedCols);
1015+
list_free(idxExprs);
1016+
if (extraUpdatedCols)
1017+
bms_free(allUpdatedCols);
1018+
1019+
if (hasexpression)
1020+
return false;
1021+
1022+
return true;
1023+
}
1024+
1025+
/*
1026+
* Indexed expression helper for index_unchanged_by_update().
1027+
*
1028+
* Returns true when Var that appears within allUpdatedCols located.
1029+
*/
1030+
static bool
1031+
index_expression_changed_walker(Node *node, Bitmapset *allUpdatedCols)
1032+
{
1033+
if (node == NULL)
1034+
return false;
1035+
1036+
if (IsA(node, Var))
1037+
{
1038+
Var *var = (Var *) node;
1039+
1040+
if (bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
1041+
allUpdatedCols))
1042+
{
1043+
/* Var was updated -- indicates that we should not hint */
1044+
return true;
1045+
}
1046+
1047+
/* Still haven't found a reason to not pass the hint */
1048+
return false;
1049+
}
1050+
1051+
return expression_tree_walker(node, index_expression_changed_walker,
1052+
(void *) allUpdatedCols);
1053+
}

0 commit comments

Comments
 (0)