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
77
78
79#define MEMO_CACHE_LOOKUP 1
80#define MEMO_CACHE_FETCH_NEXT_TUPLE 2
81#define MEMO_FILLING_CACHE 3
82#define MEMO_CACHE_BYPASS_MODE 4
84#define MEMO_END_OF_SCAN 5
85
86
88#define EMPTY_ENTRY_MEMORY_BYTES(e) (sizeof(MemoizeEntry) + \
89 sizeof(MemoizeKey) + \
90 (e)->key->params->t_len);
91#define CACHE_TUPLE_BYTES(t) (sizeof(MemoizeTuple) + \
92 (t)->mintuple->t_len)
93
98 struct MemoizeTuple *next;
101
102
103
104
111
112
113
114
125
126
127#define SH_PREFIX memoize
128#define SH_ELEMENT_TYPE MemoizeEntry
129#define SH_KEY_TYPE MemoizeKey *
130#define SH_SCOPE static inline
131#define SH_DECLARE
133
140#define SH_PREFIX memoize
141#define SH_ELEMENT_TYPE MemoizeEntry
142#define SH_KEY_TYPE MemoizeKey *
143#define SH_KEY key
144#define SH_HASH_KEY(tb, key) MemoizeHash_hash(tb, key)
145#define SH_EQUAL(tb, a, b) MemoizeHash_equal(tb, a, b)
146#define SH_SCOPE static inline
147#define SH_STORE_HASH
148#define SH_GET_HASH(tb, a) a->hash
149#define SH_DEFINE
151
152
153
154
155
156
157
160{
166 int numkeys = mstate->nkeys;
167
169
171 {
172 for (int i = 0; i < numkeys; i++)
173 {
174
176
177 if (!pslot->tts_isnull[i])
178 {
181
183
185
186 hashkey ^= hkey;
187 }
188 }
189 }
190 else
191 {
194
195 for (int i = 0; i < numkeys; i++)
196 {
197
199
200 if (!pslot->tts_isnull[i])
201 {
203
205 collations[i], pslot->tts_values[i]));
206 hashkey ^= hkey;
207 }
208 }
209 }
210
213}
214
215
216
217
218
219
220
221static bool
224{
229
230
232
234 {
236 int numkeys = mstate->nkeys;
237 bool match = true;
238
240
243
244 for (int i = 0; i < numkeys; i++)
245 {
247
248 if (tslot->tts_isnull[i] != pslot->tts_isnull[i])
249 {
250 match = false;
251 break;
252 }
253
254
255 if (tslot->tts_isnull[i])
256 continue;
257
258
260 if ((tslot->tts_values[i], pslot->tts_values[i],
262 {
263 match = false;
264 break;
265 }
266 }
267
269 return match;
270 }
271 else
272 {
273 econtext->ecxt_innertuple = tslot;
274 econtext->ecxt_outertuple = pslot;
276 }
277}
278
279
280
281
282
283static void
285{
287
288
289 if (size == 0)
290 size = 1024;
291
292
294}
295
296
297
298
299
300
301
302static inline void
304{
307 int numKeys = mstate->nkeys;
308
310
311 if (key == NULL)
312 {
315
317
318
319 for (int i = 0; i < numKeys; i++)
321 econtext,
323
325 }
326 else
327 {
328
333 }
334
336}
337
338
339
340
341
342
343
344static inline void
346{
348 uint64 freed_mem = 0;
349
350 while (tuple != NULL)
351 {
353
355
356
359
360 tuple = next;
361 }
362
365
366
367 mstate->mem_used -= freed_mem;
368}
369
370
371
372
373
374static void
376{
378
380
381
383
384
385
386
387
388
390
391
392 memoize_delete_item(mstate->hashtable, entry);
393
396}
397
398
399
400
401
402static void
404{
405 uint64 evictions = 0;
406
408 evictions = mstate->hashtable->members;
409
410
411
412
413
414
416
417
419
420
423 mstate->entry = NULL;
424
426
427
429}
430
431
432
433
434
435
436
437
438
439
440static bool
442{
443 bool specialkey_intact = true;
445 uint64 evictions = 0;
446
447
450
451
453
454
456 {
459
460
461
462
463
465
466
467
468
469
470
471
472
473
474
475
476
477 entry = memoize_lookup(mstate->hashtable, NULL);
478
479
480
481
482
483
485 elog(ERROR, "could not find memoization table entry");
486
487
488
489
490
491
492
493
494
495
496 if (key == specialkey)
497 specialkey_intact = false;
498
499
500
501
503
504 evictions++;
505
506
508 break;
509 }
510
512
513 return specialkey_intact;
514}
515
516
517
518
519
520
521
522
523
524
525
526
527
530{
534
535
537
538
539
540
541
542 entry = memoize_insert(mstate->hashtable, NULL, found);
543
544 if (*found)
545 {
546
547
548
549
551
552 return entry;
553 }
554
556
557
560
561
563
564
567
568
569
570
571
573
575
577
578
579
580
581
583 {
584
585
586
587
588
589
591 return NULL;
592
593
594
595
596
597
598
599
600
601 if (entry->status != memoize_SH_IN_USE || entry->key != key)
602 {
603
604
605
606
608
609
610 entry = memoize_lookup(mstate->hashtable, NULL);
611 Assert(entry != NULL);
612 }
613 }
614
615 return entry;
616}
617
618
619
620
621
622
623
624
625static bool
627{
631
632 Assert(slot != NULL);
633 Assert(entry != NULL);
634
636
639 tuple->next = NULL;
640
641
643
645 {
646
647
648
649
651 }
652 else
653 {
654
656 }
657
660
661
662
663
664
666 {
668
670 return false;
671
672
673
674
675
676
677
678
679
680 if (entry->status != memoize_SH_IN_USE || entry->key != key)
681 {
682
683
684
685
687
688
689 mstate->entry = entry = memoize_lookup(mstate->hashtable, NULL);
690 Assert(entry != NULL);
691 }
692 }
693
694 return true;
695}
696
699{
704
706
707
708
709
710
712
714 {
716 {
719 bool found;
720
722
723
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
742
743 if (found && entry->complete)
744 {
746
747
748
749
750
751
753 node->entry = entry;
754
755
757 {
759
762 slot, false);
763
764 return slot;
765 }
766
767
769 return NULL;
770 }
771
772
774
775 if (found)
776 {
777
778
779
780
781
782
783
784
786 }
787
788
792 {
793
794
795
796
797
798
799
802
804 return NULL;
805 }
806
807 node->entry = entry;
808
809
810
811
812
813 if (unlikely(entry == NULL ||
815 {
817
819
820
821
822
823
824 }
825 else
826 {
827
828
829
830
831
832
835 }
836
839 return slot;
840 }
841
843 {
844
847
848
850
851
853 {
855 return NULL;
856 }
857
860 false);
861
862 return slot;
863 }
864
866 {
869
870
871 Assert(entry != NULL);
872
873
874
875
876
877
881 {
882
885 return NULL;
886 }
887
888
889
890
891
892
894 elog(ERROR, "cache entry already complete");
895
896
898 {
899
901
903
904
905
906
907
908 }
909
912 return slot;
913 }
914
916 {
918
919
920
921
922
923
927 {
929 return NULL;
930 }
931
934 return slot;
935 }
936
938
939
940
941
942
943 return NULL;
944
945 default:
946 elog(ERROR, "unrecognized memoize state: %d",
948 return NULL;
949 }
950}
951
954{
956 Plan *outerNode;
957 int i;
958 int nkeys;
959 Oid *eqfuncoids;
960
961
963
967
968
969
970
971
972
974
977
978
979
980
981
984
985
986
987
989
990
991
992
993
994
996
1003
1005 mstate->collations = node->collations;
1006
1008
1009 eqfuncoids = palloc(nkeys * sizeof(Oid));
1010
1011 for (i = 0; i < nkeys; i++)
1012 {
1013 Oid hashop = node->hashOperators[i];
1014 Oid left_hashfn;
1015 Oid right_hashfn;
1017
1019 elog(ERROR, "could not find hash function for hash operator %u",
1020 hashop);
1021
1023
1026 }
1027
1031 eqfuncoids,
1032 node->collations,
1035
1036 pfree(eqfuncoids);
1038
1039
1041
1042
1044 "MemoizeHashTable",
1046
1049 mstate->entry = NULL;
1050
1051
1052
1053
1054
1055
1056
1057
1058
1061
1062
1063
1064
1065
1067
1068
1070
1071
1072
1073
1074
1076
1077 return mstate;
1078}
1079
1082{
1083#ifdef USE_ASSERT_CHECKING
1084
1086 {
1087 int count;
1089 memoize_iterator i;
1091
1092 memoize_start_iterate(node->hashtable, &i);
1093
1094 count = 0;
1095 while ((entry = memoize_iterate(node->hashtable, &i)) != NULL)
1096 {
1098
1100 while (tuple != NULL)
1101 {
1103 tuple = tuple->next;
1104 }
1105 count++;
1106 }
1107
1110 }
1111#endif
1112
1113
1114
1115
1116
1117
1119 {
1121
1122
1125
1126 Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
1129 }
1130
1131
1133
1134
1135
1136
1138}
1139
1142{
1144
1145
1147
1148
1149 node->entry = NULL;
1151
1152
1153
1154
1155
1156 if (outerPlan->chgParam == NULL)
1158
1159
1160
1161
1162
1165}
1166
1167
1168
1169
1170
1171
1174{
1176 ntuples;
1177}
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1192{
1194
1195
1197 return;
1198
1203}
1204
1205
1206
1207
1208
1209
1210
1213{
1215
1216
1218 return;
1219
1223
1228}
1229
1230
1231
1232
1233
1234
1235
1238{
1241}
1242
1243
1244
1245
1246
1247
1248
1251{
1254
1256 return;
1257
1263}
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)
#define palloc_object(type)
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)