PostgreSQL Source Code: src/backend/executor/nodeMemoize.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
68
76
77
78#define MEMO_CACHE_LOOKUP 1
79#define MEMO_CACHE_FETCH_NEXT_TUPLE 2
80#define MEMO_FILLING_CACHE 3
81#define MEMO_CACHE_BYPASS_MODE 4
83#define MEMO_END_OF_SCAN 5
84
85
87#define EMPTY_ENTRY_MEMORY_BYTES(e) (sizeof(MemoizeEntry) + \
88 sizeof(MemoizeKey) + \
89 (e)->key->params->t_len);
90#define CACHE_TUPLE_BYTES(t) (sizeof(MemoizeTuple) + \
91 (t)->mintuple->t_len)
92
97 struct MemoizeTuple *next;
100
101
102
103
110
111
112
113
124
125
126#define SH_PREFIX memoize
127#define SH_ELEMENT_TYPE MemoizeEntry
128#define SH_KEY_TYPE MemoizeKey *
129#define SH_SCOPE static inline
130#define SH_DECLARE
132
139#define SH_PREFIX memoize
140#define SH_ELEMENT_TYPE MemoizeEntry
141#define SH_KEY_TYPE MemoizeKey *
142#define SH_KEY key
143#define SH_HASH_KEY(tb, key) MemoizeHash_hash(tb, key)
144#define SH_EQUAL(tb, a, b) MemoizeHash_equal(tb, a, b)
145#define SH_SCOPE static inline
146#define SH_STORE_HASH
147#define SH_GET_HASH(tb, a) a->hash
148#define SH_DEFINE
150
151
152
153
154
155
156
159{
165 int numkeys = mstate->nkeys;
166
168
170 {
171 for (int i = 0; i < numkeys; i++)
172 {
173
175
176 if (!pslot->tts_isnull[i])
177 {
180
182
184
185 hashkey ^= hkey;
186 }
187 }
188 }
189 else
190 {
193
194 for (int i = 0; i < numkeys; i++)
195 {
196
198
199 if (!pslot->tts_isnull[i])
200 {
202
204 collations[i], pslot->tts_values[i]));
205 hashkey ^= hkey;
206 }
207 }
208 }
209
212}
213
214
215
216
217
218
219
220static bool
223{
228
229
231
233 {
235 int numkeys = mstate->nkeys;
236 bool match = true;
237
239
242
243 for (int i = 0; i < numkeys; i++)
244 {
246
247 if (tslot->tts_isnull[i] != pslot->tts_isnull[i])
248 {
249 match = false;
250 break;
251 }
252
253
254 if (tslot->tts_isnull[i])
255 continue;
256
257
259 if ((tslot->tts_values[i], pslot->tts_values[i],
261 {
262 match = false;
263 break;
264 }
265 }
266
268 return match;
269 }
270 else
271 {
272 econtext->ecxt_innertuple = tslot;
273 econtext->ecxt_outertuple = pslot;
275 }
276}
277
278
279
280
281
282static void
284{
286
287
288 if (size == 0)
289 size = 1024;
290
291
293}
294
295
296
297
298
299
300
301static inline void
303{
306 int numKeys = mstate->nkeys;
307
309
310 if (key == NULL)
311 {
314
316
317
318 for (int i = 0; i < numKeys; i++)
320 econtext,
322
324 }
325 else
326 {
327
332 }
333
335}
336
337
338
339
340
341
342
343static inline void
345{
347 uint64 freed_mem = 0;
348
349 while (tuple != NULL)
350 {
352
354
355
358
359 tuple = next;
360 }
361
364
365
366 mstate->mem_used -= freed_mem;
367}
368
369
370
371
372
373static void
375{
377
379
380
382
383
384
385
386
387
389
390
391 memoize_delete_item(mstate->hashtable, entry);
392
395}
396
397
398
399
400
401static void
403{
404 uint64 evictions = 0;
405
407 evictions = mstate->hashtable->members;
408
409
410
411
412
413
415
416
418
419
422 mstate->entry = NULL;
423
425
426
428}
429
430
431
432
433
434
435
436
437
438
439static bool
441{
442 bool specialkey_intact = true;
444 uint64 evictions = 0;
445
446
449
450
452
453
455 {
458
459
460
461
462
464
465
466
467
468
469
470
471
472
473
474
475
476 entry = memoize_lookup(mstate->hashtable, NULL);
477
478
479
480
481
482
484 elog(ERROR, "could not find memoization table entry");
485
486
487
488
489
490
491
492
493
494
495 if (key == specialkey)
496 specialkey_intact = false;
497
498
499
500
502
503 evictions++;
504
505
507 break;
508 }
509
511
512 return specialkey_intact;
513}
514
515
516
517
518
519
520
521
522
523
524
525
526
529{
533
534
536
537
538
539
540
541 entry = memoize_insert(mstate->hashtable, NULL, found);
542
543 if (*found)
544 {
545
546
547
548
550
551 return entry;
552 }
553
555
556
559
560
562
563
566
567
568
569
570
572
574
576
577
578
579
580
582 {
583
584
585
586
587
588
590 return NULL;
591
592
593
594
595
596
597
598
599
600 if (entry->status != memoize_SH_IN_USE || entry->key != key)
601 {
602
603
604
605
607
608
609 entry = memoize_lookup(mstate->hashtable, NULL);
610 Assert(entry != NULL);
611 }
612 }
613
614 return entry;
615}
616
617
618
619
620
621
622
623
624static bool
626{
630
631 Assert(slot != NULL);
632 Assert(entry != NULL);
633
635
638 tuple->next = NULL;
639
640
642
644 {
645
646
647
648
650 }
651 else
652 {
653
655 }
656
659
660
661
662
663
665 {
667
669 return false;
670
671
672
673
674
675
676
677
678
679 if (entry->status != memoize_SH_IN_USE || entry->key != key)
680 {
681
682
683
684
686
687
688 mstate->entry = entry = memoize_lookup(mstate->hashtable, NULL);
689 Assert(entry != NULL);
690 }
691 }
692
693 return true;
694}
695
698{
703
705
706
707
708
709
711
713 {
715 {
718 bool found;
719
721
722
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
741
742 if (found && entry->complete)
743 {
745
746
747
748
749
750
752 node->entry = entry;
753
754
756 {
758
761 slot, false);
762
763 return slot;
764 }
765
766
768 return NULL;
769 }
770
771
773
774 if (found)
775 {
776
777
778
779
780
781
782
783
785 }
786
787
791 {
792
793
794
795
796
797
798
801
803 return NULL;
804 }
805
806 node->entry = entry;
807
808
809
810
811
812 if (unlikely(entry == NULL ||
814 {
816
818
819
820
821
822
823 }
824 else
825 {
826
827
828
829
830
831
834 }
835
838 return slot;
839 }
840
842 {
843
846
847
849
850
852 {
854 return NULL;
855 }
856
859 false);
860
861 return slot;
862 }
863
865 {
868
869
870 Assert(entry != NULL);
871
872
873
874
875
876
880 {
881
884 return NULL;
885 }
886
887
888
889
890
891
893 elog(ERROR, "cache entry already complete");
894
895
897 {
898
900
902
903
904
905
906
907 }
908
911 return slot;
912 }
913
915 {
917
918
919
920
921
922
926 {
928 return NULL;
929 }
930
933 return slot;
934 }
935
937
938
939
940
941
942 return NULL;
943
944 default:
945 elog(ERROR, "unrecognized memoize state: %d",
947 return NULL;
948 }
949}
950
953{
955 Plan *outerNode;
956 int i;
957 int nkeys;
958 Oid *eqfuncoids;
959
960
962
966
967
968
969
970
971
973
976
977
978
979
980
983
984
985
986
988
989
990
991
992
993
995
1002
1004 mstate->collations = node->collations;
1005
1007
1008 eqfuncoids = palloc(nkeys * sizeof(Oid));
1009
1010 for (i = 0; i < nkeys; i++)
1011 {
1012 Oid hashop = node->hashOperators[i];
1013 Oid left_hashfn;
1014 Oid right_hashfn;
1016
1018 elog(ERROR, "could not find hash function for hash operator %u",
1019 hashop);
1020
1022
1025 }
1026
1030 eqfuncoids,
1031 node->collations,
1034
1035 pfree(eqfuncoids);
1037
1038
1040
1041
1043 "MemoizeHashTable",
1045
1048 mstate->entry = NULL;
1049
1050
1051
1052
1053
1054
1055
1056
1057
1060
1061
1062
1063
1064
1066
1067
1069
1070
1071
1072
1073
1075
1076 return mstate;
1077}
1078
1081{
1082#ifdef USE_ASSERT_CHECKING
1083
1085 {
1086 int count;
1088 memoize_iterator i;
1090
1091 memoize_start_iterate(node->hashtable, &i);
1092
1093 count = 0;
1094 while ((entry = memoize_iterate(node->hashtable, &i)) != NULL)
1095 {
1097
1099 while (tuple != NULL)
1100 {
1102 tuple = tuple->next;
1103 }
1104 count++;
1105 }
1106
1109 }
1110#endif
1111
1112
1113
1114
1115
1116
1118 {
1120
1121
1124
1125 Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
1128 }
1129
1130
1132
1133
1134
1135
1137}
1138
1141{
1143
1144
1146
1147
1148 node->entry = NULL;
1150
1151
1152
1153
1154
1155 if (outerPlan->chgParam == NULL)
1157
1158
1159
1160
1161
1164}
1165
1166
1167
1168
1169
1170
1173{
1175 ntuples;
1176}
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1191{
1193
1194
1196 return;
1197
1202}
1203
1204
1205
1206
1207
1208
1209
1212{
1214
1215
1217 return;
1218
1222
1227}
1228
1229
1230
1231
1232
1233
1234
1237{
1240}
1241
1242
1243
1244
1245
1246
1247
1250{
1253
1255 return;
1256
1262}
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
uint32 datum_image_hash(Datum value, bool typByVal, int typLen)
bool datum_image_eq(Datum value1, Datum value2, bool typByVal, int typLen)
void ExecReScan(PlanState *node)
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
ExprState * ExecBuildParamSetEqual(TupleDesc desc, const TupleTableSlotOps *lops, const TupleTableSlotOps *rops, const Oid *eqfunctions, const Oid *collations, const List *param_exprs, PlanState *parent)
void ExecEndNode(PlanState *node)
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
const TupleTableSlotOps TTSOpsVirtual
TupleTableSlot * ExecStoreVirtualTuple(TupleTableSlot *slot)
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
void ExecInitResultTupleSlotTL(PlanState *planstate, const TupleTableSlotOps *tts_ops)
const TupleTableSlotOps TTSOpsMinimalTuple
TupleDesc ExecTypeFromExprList(List *exprList)
void ExecCreateScanSlotFromOuterPlan(EState *estate, ScanState *scanstate, const TupleTableSlotOps *tts_ops)
void ExecAssignExprContext(EState *estate, PlanState *planstate)
#define outerPlanState(node)
struct MemoizeInstrumentation MemoizeInstrumentation
#define EXEC_FLAG_BACKWARD
#define ResetExprContext(econtext)
static bool ExecQual(ExprState *state, ExprContext *econtext)
static TupleTableSlot * ExecProcNode(PlanState *node)
static Datum ExecEvalExpr(ExprState *state, ExprContext *econtext, bool *isNull)
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
static uint32 murmurhash32(uint32 data)
Assert(PointerIsAligned(start, uint64))
static void dlist_init(dlist_head *head)
static void dlist_delete(dlist_node *node)
#define dlist_foreach_modify(iter, lhead)
static void dlist_push_tail(dlist_head *head, dlist_node *node)
static void dlist_move_tail(dlist_head *head, dlist_node *node)
#define dlist_container(type, membername, ptr)
#define IsParallelWorker()
RegProcedure get_opcode(Oid opno)
bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno)
void MemoryContextReset(MemoryContext context)
void pfree(void *pointer)
MemoryContext CurrentMemoryContext
void MemoryContextDelete(MemoryContext context)
#define AllocSetContextCreate
#define ALLOCSET_DEFAULT_SIZES
#define CHECK_FOR_INTERRUPTS()
size_t get_hash_memory_limit(void)
#define MEMO_CACHE_LOOKUP
#define MEMO_CACHE_FETCH_NEXT_TUPLE
static bool cache_store_tuple(MemoizeState *mstate, TupleTableSlot *slot)
#define MEMO_CACHE_BYPASS_MODE
static uint32 MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
void ExecMemoizeInitializeDSM(MemoizeState *node, ParallelContext *pcxt)
MemoizeState * ExecInitMemoize(Memoize *node, EState *estate, int eflags)
static void cache_purge_all(MemoizeState *mstate)
void ExecReScanMemoize(MemoizeState *node)
double ExecEstimateCacheEntryOverheadBytes(double ntuples)
static bool cache_reduce_memory(MemoizeState *mstate, MemoizeKey *specialkey)
static MemoizeEntry * cache_lookup(MemoizeState *mstate, bool *found)
#define MEMO_FILLING_CACHE
static void prepare_probe_slot(MemoizeState *mstate, MemoizeKey *key)
static TupleTableSlot * ExecMemoize(PlanState *pstate)
#define CACHE_TUPLE_BYTES(t)
void ExecMemoizeEstimate(MemoizeState *node, ParallelContext *pcxt)
void ExecMemoizeRetrieveInstrumentation(MemoizeState *node)
struct MemoizeTuple MemoizeTuple
static void entry_purge_tuples(MemoizeState *mstate, MemoizeEntry *entry)
static void remove_cache_entry(MemoizeState *mstate, MemoizeEntry *entry)
void ExecMemoizeInitializeWorker(MemoizeState *node, ParallelWorkerContext *pwcxt)
struct MemoizeEntry MemoizeEntry
static void build_hash_table(MemoizeState *mstate, uint32 size)
static bool MemoizeHash_equal(struct memoize_hash *tb, const MemoizeKey *key1, const MemoizeKey *key2)
#define EMPTY_ENTRY_MEMORY_BYTES(e)
void ExecEndMemoize(MemoizeState *node)
struct MemoizeKey MemoizeKey
#define castNode(_type_, nodeptr)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
static uint32 pg_rotate_left32(uint32 word, int n)
static void * list_nth(const List *list, int n)
static uint32 DatumGetUInt32(Datum X)
void * shm_toc_allocate(shm_toc *toc, Size nbytes)
void shm_toc_insert(shm_toc *toc, uint64 key, void *address)
void * shm_toc_lookup(shm_toc *toc, uint64 key, bool noError)
#define shm_toc_estimate_chunk(e, sz)
#define shm_toc_estimate_keys(e, cnt)
Size add_size(Size s1, Size s2)
Size mul_size(Size s1, Size s2)
MemoryContext ecxt_per_tuple_memory
TupleTableSlot * probeslot
SharedMemoizeInfo * shared_info
struct MemoizeEntry * entry
ExprState * cache_eq_expr
MemoizeInstrumentation stats
MemoryContext tableContext
struct memoize_hash * hashtable
TupleTableSlot * tableslot
struct MemoizeTuple * last_tuple
struct MemoizeTuple * next
shm_toc_estimator estimator
Instrumentation * instrument
ExprContext * ps_ExprContext
TupleTableSlot * ps_ResultTupleSlot
ProjectionInfo * ps_ProjInfo
ExecProcNodeMtd ExecProcNode
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
static void slot_getallattrs(TupleTableSlot *slot)
static TupleTableSlot * ExecCopySlot(TupleTableSlot *dstslot, TupleTableSlot *srcslot)