PostgreSQL Source Code  git master
nodeMemoize.c File Reference
#include "postgres.h"
#include "common/hashfn.h"
#include "executor/executor.h"
#include "executor/nodeMemoize.h"
#include "lib/ilist.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
#include "lib/simplehash.h"
Include dependency graph for nodeMemoize.c:

Go to the source code of this file.

Data Structures

struct  MemoizeTuple
 
struct  MemoizeKey
 
struct  MemoizeEntry
 

Macros

#define MEMO_CACHE_LOOKUP   1 /* Attempt to perform a cache lookup */
 
#define MEMO_CACHE_FETCH_NEXT_TUPLE   2 /* Get another tuple from the cache */
 
#define MEMO_FILLING_CACHE   3 /* Read outer node to fill cache */
 
#define MEMO_CACHE_BYPASS_MODE
 
#define MEMO_END_OF_SCAN   5 /* Ready for rescan */
 
#define EMPTY_ENTRY_MEMORY_BYTES(e)
 
#define CACHE_TUPLE_BYTES(t)
 
#define SH_PREFIX   memoize
 
#define SH_ELEMENT_TYPE   MemoizeEntry
 
#define SH_KEY_TYPE   MemoizeKey *
 
#define SH_SCOPE   static inline
 
#define SH_DECLARE
 
#define SH_PREFIX   memoize
 
#define SH_ELEMENT_TYPE   MemoizeEntry
 
#define SH_KEY_TYPE   MemoizeKey *
 
#define SH_KEY   key
 
#define SH_HASH_KEY(tb, key)   MemoizeHash_hash(tb, key)
 
#define SH_EQUAL(tb, a, b)   (MemoizeHash_equal(tb, a, b) == 0)
 
#define SH_SCOPE   static inline
 
#define SH_STORE_HASH
 
#define SH_GET_HASH(tb, a)   a->hash
 
#define SH_DEFINE
 

Typedefs

typedef struct MemoizeTuple MemoizeTuple
 
typedef struct MemoizeKey MemoizeKey
 
typedef struct MemoizeEntry MemoizeEntry
 

Functions

static uint32 MemoizeHash_hash (struct memoize_hash *tb, const MemoizeKey *key)
 
static int MemoizeHash_equal (struct memoize_hash *tb, const MemoizeKey *params1, const MemoizeKey *params2)
 
static void build_hash_table (MemoizeState *mstate, uint32 size)
 
static void prepare_probe_slot (MemoizeState *mstate, MemoizeKey *key)
 
static void entry_purge_tuples (MemoizeState *mstate, MemoizeEntry *entry)
 
static void remove_cache_entry (MemoizeState *mstate, MemoizeEntry *entry)
 
static bool cache_reduce_memory (MemoizeState *mstate, MemoizeKey *specialkey)
 
static MemoizeEntrycache_lookup (MemoizeState *mstate, bool *found)
 
static bool cache_store_tuple (MemoizeState *mstate, TupleTableSlot *slot)
 
static TupleTableSlotExecMemoize (PlanState *pstate)
 
MemoizeStateExecInitMemoize (Memoize *node, EState *estate, int eflags)
 
void ExecEndMemoize (MemoizeState *node)
 
void ExecReScanMemoize (MemoizeState *node)
 
double ExecEstimateCacheEntryOverheadBytes (double ntuples)
 
void ExecMemoizeEstimate (MemoizeState *node, ParallelContext *pcxt)
 
void ExecMemoizeInitializeDSM (MemoizeState *node, ParallelContext *pcxt)
 
void ExecMemoizeInitializeWorker (MemoizeState *node, ParallelWorkerContext *pwcxt)
 
void ExecMemoizeRetrieveInstrumentation (MemoizeState *node)
 

Macro Definition Documentation

◆ CACHE_TUPLE_BYTES

#define CACHE_TUPLE_BYTES (   t)
Value:
(sizeof(MemoizeTuple) + \
(t)->mintuple->t_len)
struct MemoizeTuple MemoizeTuple

Definition at line 89 of file nodeMemoize.c.

Referenced by cache_store_tuple(), entry_purge_tuples(), and ExecEndMemoize().

◆ EMPTY_ENTRY_MEMORY_BYTES

#define EMPTY_ENTRY_MEMORY_BYTES (   e)
Value:
(sizeof(MemoizeEntry) + \
sizeof(MemoizeKey) + \
(e)->key->params->t_len);
struct MemoizeEntry MemoizeEntry
e
Definition: preproc-init.c:82

Definition at line 86 of file nodeMemoize.c.

Referenced by cache_lookup(), ExecEndMemoize(), and remove_cache_entry().

◆ MEMO_CACHE_BYPASS_MODE

#define MEMO_CACHE_BYPASS_MODE
Value:
4 /* Bypass mode. Just read from our
* subplan without caching anything */

Definition at line 80 of file nodeMemoize.c.

Referenced by ExecMemoize().

◆ MEMO_CACHE_FETCH_NEXT_TUPLE

#define MEMO_CACHE_FETCH_NEXT_TUPLE   2 /* Get another tuple from the cache */

Definition at line 78 of file nodeMemoize.c.

Referenced by ExecMemoize().

◆ MEMO_CACHE_LOOKUP

#define MEMO_CACHE_LOOKUP   1 /* Attempt to perform a cache lookup */

Definition at line 77 of file nodeMemoize.c.

Referenced by ExecInitMemoize(), ExecMemoize(), and ExecReScanMemoize().

◆ MEMO_END_OF_SCAN

#define MEMO_END_OF_SCAN   5 /* Ready for rescan */

Definition at line 82 of file nodeMemoize.c.

Referenced by ExecMemoize().

◆ MEMO_FILLING_CACHE

#define MEMO_FILLING_CACHE   3 /* Read outer node to fill cache */

Definition at line 79 of file nodeMemoize.c.

Referenced by ExecMemoize().

◆ SH_DECLARE

#define SH_DECLARE

Definition at line 129 of file nodeMemoize.c.

◆ SH_DEFINE

#define SH_DEFINE

Definition at line 147 of file nodeMemoize.c.

◆ SH_ELEMENT_TYPE [1/2]

#define SH_ELEMENT_TYPE   MemoizeEntry

Definition at line 139 of file nodeMemoize.c.

◆ SH_ELEMENT_TYPE [2/2]

#define SH_ELEMENT_TYPE   MemoizeEntry

Definition at line 139 of file nodeMemoize.c.

◆ SH_EQUAL

#define SH_EQUAL (   tb,
  a,
 
)    (MemoizeHash_equal(tb, a, b) == 0)

Definition at line 143 of file nodeMemoize.c.

◆ SH_GET_HASH

#define SH_GET_HASH (   tb,
 
)    a->hash

Definition at line 146 of file nodeMemoize.c.

◆ SH_HASH_KEY

#define SH_HASH_KEY (   tb,
  key 
)    MemoizeHash_hash(tb, key)

Definition at line 142 of file nodeMemoize.c.

◆ SH_KEY

#define SH_KEY   key

Definition at line 141 of file nodeMemoize.c.

◆ SH_KEY_TYPE [1/2]

#define SH_KEY_TYPE   MemoizeKey *

Definition at line 140 of file nodeMemoize.c.

◆ SH_KEY_TYPE [2/2]

#define SH_KEY_TYPE   MemoizeKey *

Definition at line 140 of file nodeMemoize.c.

◆ SH_PREFIX [1/2]

#define SH_PREFIX   memoize

Definition at line 138 of file nodeMemoize.c.

◆ SH_PREFIX [2/2]

#define SH_PREFIX   memoize

Definition at line 138 of file nodeMemoize.c.

◆ SH_SCOPE [1/2]

#define SH_SCOPE   static inline

Definition at line 144 of file nodeMemoize.c.

◆ SH_SCOPE [2/2]

#define SH_SCOPE   static inline

Definition at line 144 of file nodeMemoize.c.

◆ SH_STORE_HASH

#define SH_STORE_HASH

Definition at line 145 of file nodeMemoize.c.

Typedef Documentation

◆ MemoizeEntry

typedef struct MemoizeEntry MemoizeEntry

◆ MemoizeKey

typedef struct MemoizeKey MemoizeKey

◆ MemoizeTuple

typedef struct MemoizeTuple MemoizeTuple

Function Documentation

◆ build_hash_table()

static void build_hash_table ( MemoizeState mstate,
uint32  size 
)
static

Definition at line 211 of file nodeMemoize.c.

References MemoizeState::hashtable, and MemoizeState::tableContext.

Referenced by ExecInitMemoize().

212 {
213  /* Make a guess at a good size when we're not given a valid size. */
214  if (size == 0)
215  size = 1024;
216 
217  /* memoize_create will convert the size to a power of 2 */
218  mstate->hashtable = memoize_create(mstate->tableContext, size, mstate);
219 }
MemoryContext tableContext
Definition: execnodes.h:2101
struct memoize_hash * hashtable
Definition: execnodes.h:2090

◆ cache_lookup()

static MemoizeEntry* cache_lookup ( MemoizeState mstate,
bool found 
)
static

Definition at line 410 of file nodeMemoize.c.

References Assert, cache_reduce_memory(), MemoizeEntry::complete, dlist_move_tail(), dlist_push_tail(), EMPTY_ENTRY_MEMORY_BYTES, ExecCopySlotMinimalTuple(), MemoizeState::hashtable, sort-test::key, MemoizeEntry::key, MemoizeState::last_tuple, MemoizeState::lru_list, MemoizeKey::lru_node, MemoizeState::mem_limit, MemoizeState::mem_used, MemoryContextSwitchTo(), palloc(), MemoizeKey::params, prepare_probe_slot(), MemoizeState::probeslot, MemoizeEntry::status, MemoizeState::tableContext, MemoizeEntry::tuplehead, and unlikely.

Referenced by ExecMemoize().

411 {
412  MemoizeKey *key;
413  MemoizeEntry *entry;
414  MemoryContext oldcontext;
415 
416  /* prepare the probe slot with the current scan parameters */
417  prepare_probe_slot(mstate, NULL);
418 
419  /*
420  * Add the new entry to the cache. No need to pass a valid key since the
421  * hash function uses mstate's probeslot, which we populated above.
422  */
423  entry = memoize_insert(mstate->hashtable, NULL, found);
424 
425  if (*found)
426  {
427  /*
428  * Move existing entry to the tail of the LRU list to mark it as the
429  * most recently used item.
430  */
431  dlist_move_tail(&mstate->lru_list, &entry->key->lru_node);
432 
433  return entry;
434  }
435 
436  oldcontext = MemoryContextSwitchTo(mstate->tableContext);
437 
438  /* Allocate a new key */
439  entry->key = key = (MemoizeKey *) palloc(sizeof(MemoizeKey));
440  key->params = ExecCopySlotMinimalTuple(mstate->probeslot);
441 
442  /* Update the total cache memory utilization */
443  mstate->mem_used += EMPTY_ENTRY_MEMORY_BYTES(entry);
444 
445  /* Initialize this entry */
446  entry->complete = false;
447  entry->tuplehead = NULL;
448 
449  /*
450  * Since this is the most recently used entry, push this entry onto the
451  * end of the LRU list.
452  */
453  dlist_push_tail(&mstate->lru_list, &entry->key->lru_node);
454 
455  mstate->last_tuple = NULL;
456 
457  MemoryContextSwitchTo(oldcontext);
458 
459  /*
460  * If we've gone over our memory budget, then we'll free up some space in
461  * the cache.
462  */
463  if (mstate->mem_used > mstate->mem_limit)
464  {
465  /*
466  * Try to free up some memory. It's highly unlikely that we'll fail
467  * to do so here since the entry we've just added is yet to contain
468  * any tuples and we're able to remove any other entry to reduce the
469  * memory consumption.
470  */
471  if (unlikely(!cache_reduce_memory(mstate, key)))
472  return NULL;
473 
474  /*
475  * The process of removing entries from the cache may have caused the
476  * code in simplehash.h to shuffle elements to earlier buckets in the
477  * hash table. If it has, we'll need to find the entry again by
478  * performing a lookup. Fortunately, we can detect if this has
479  * happened by seeing if the entry is still in use and that the key
480  * pointer matches our expected key.
481  */
482  if (entry->status != memoize_SH_IN_USE || entry->key != key)
483  {
484  /*
485  * We need to repopulate the probeslot as lookups performed during
486  * the cache evictions above will have stored some other key.
487  */
488  prepare_probe_slot(mstate, key);
489 
490  /* Re-find the newly added entry */
491  entry = memoize_lookup(mstate->hashtable, NULL);
492  Assert(entry != NULL);
493  }
494  }
495 
496  return entry;
497 }
MemoryContext tableContext
Definition: execnodes.h:2101
static void dlist_push_tail(dlist_head *head, dlist_node *node)
Definition: ilist.h:317
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define EMPTY_ENTRY_MEMORY_BYTES(e)
Definition: nodeMemoize.c:86
TupleTableSlot * probeslot
Definition: execnodes.h:2093
MemoizeTuple * tuplehead
Definition: nodeMemoize.c:117
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:463
uint64 mem_limit
Definition: execnodes.h:2100
struct MemoizeTuple * last_tuple
Definition: execnodes.h:2103
static bool cache_reduce_memory(MemoizeState *mstate, MemoizeKey *specialkey)
Definition: nodeMemoize.c:326
static void dlist_move_tail(dlist_head *head, dlist_node *node)
Definition: ilist.h:404
#define Assert(condition)
Definition: c.h:804
struct memoize_hash * hashtable
Definition: execnodes.h:2090
static void prepare_probe_slot(MemoizeState *mstate, MemoizeKey *key)
Definition: nodeMemoize.c:228
dlist_node lru_node
Definition: nodeMemoize.c:107
void * palloc(Size size)
Definition: mcxt.c:1062
MinimalTuple params
Definition: nodeMemoize.c:106
#define unlikely(x)
Definition: c.h:273
dlist_head lru_list
Definition: execnodes.h:2102
MemoizeKey * key
Definition: nodeMemoize.c:116
uint64 mem_used
Definition: execnodes.h:2099

◆ cache_reduce_memory()

static bool cache_reduce_memory ( MemoizeState mstate,
MemoizeKey specialkey 
)
static

Definition at line 326 of file nodeMemoize.c.

References Assert, MemoizeInstrumentation::cache_evictions, dlist_mutable_iter::cur, dlist_container, dlist_foreach_modify, MemoizeState::hashtable, sort-test::key, MemoizeEntry::key, MemoizeState::lru_list, MemoizeState::mem_limit, MemoizeInstrumentation::mem_peak, MemoizeState::mem_used, prepare_probe_slot(), remove_cache_entry(), and MemoizeState::stats.

Referenced by cache_lookup(), and cache_store_tuple().

327 {
328  bool specialkey_intact = true; /* for now */
329  dlist_mutable_iter iter;
330  uint64 evictions = 0;
331 
332  /* Update peak memory usage */
333  if (mstate->mem_used > mstate->stats.mem_peak)
334  mstate->stats.mem_peak = mstate->mem_used;
335 
336  /* We expect only to be called when we've gone over budget on memory */
337  Assert(mstate->mem_used > mstate->mem_limit);
338 
339  /* Start the eviction process starting at the head of the LRU list. */
340  dlist_foreach_modify(iter, &mstate->lru_list)
341  {
342  MemoizeKey *key = dlist_container(MemoizeKey, lru_node, iter.cur);
343  MemoizeEntry *entry;
344 
345  /*
346  * Populate the hash probe slot in preparation for looking up this LRU
347  * entry.
348  */
349  prepare_probe_slot(mstate, key);
350 
351  /*
352  * Ideally the LRU list pointers would be stored in the entry itself
353  * rather than in the key. Unfortunately, we can't do that as the
354  * simplehash.h code may resize the table and allocate new memory for
355  * entries which would result in those pointers pointing to the old
356  * buckets. However, it's fine to use the key to store this as that's
357  * only referenced by a pointer in the entry, which of course follows
358  * the entry whenever the hash table is resized. Since we only have a
359  * pointer to the key here, we must perform a hash table lookup to
360  * find the entry that the key belongs to.
361  */
362  entry = memoize_lookup(mstate->hashtable, NULL);
363 
364  /* A good spot to check for corruption of the table and LRU list. */
365  Assert(entry != NULL);
366  Assert(entry->key == key);
367 
368  /*
369  * If we're being called to free memory while the cache is being
370  * populated with new tuples, then we'd better take some care as we
371  * could end up freeing the entry which 'specialkey' belongs to.
372  * Generally callers will pass 'specialkey' as the key for the cache
373  * entry which is currently being populated, so we must set
374  * 'specialkey_intact' to false to inform the caller the specialkey
375  * entry has been removed.
376  */
377  if (key == specialkey)
378  specialkey_intact = false;
379 
380  /*
381  * Finally remove the entry. This will remove from the LRU list too.
382  */
383  remove_cache_entry(mstate, entry);
384 
385  evictions++;
386 
387  /* Exit if we've freed enough memory */
388  if (mstate->mem_used <= mstate->mem_limit)
389  break;
390  }
391 
392  mstate->stats.cache_evictions += evictions; /* Update Stats */
393 
394  return specialkey_intact;
395 }
dlist_node * cur
Definition: ilist.h:180
#define dlist_foreach_modify(iter, lhead)
Definition: ilist.h:543
static void remove_cache_entry(MemoizeState *mstate, MemoizeEntry *entry)
Definition: nodeMemoize.c:293
#define dlist_container(type, membername, ptr)
Definition: ilist.h:496
uint64 mem_limit
Definition: execnodes.h:2100
#define Assert(condition)
Definition: c.h:804
struct memoize_hash * hashtable
Definition: execnodes.h:2090
static void prepare_probe_slot(MemoizeState *mstate, MemoizeKey *key)
Definition: nodeMemoize.c:228
MemoizeInstrumentation stats
Definition: execnodes.h:2111
dlist_head lru_list
Definition: execnodes.h:2102
MemoizeKey * key
Definition: nodeMemoize.c:116
uint64 mem_used
Definition: execnodes.h:2099

◆ cache_store_tuple()

static bool cache_store_tuple ( MemoizeState mstate,
TupleTableSlot slot 
)
static

Definition at line 507 of file nodeMemoize.c.

References Assert, cache_reduce_memory(), CACHE_TUPLE_BYTES, MemoizeState::entry, ExecCopySlotMinimalTuple(), MemoizeState::hashtable, sort-test::key, MemoizeEntry::key, MemoizeState::last_tuple, MemoizeState::mem_limit, MemoizeState::mem_used, MemoryContextSwitchTo(), MemoizeTuple::mintuple, MemoizeTuple::next, palloc(), prepare_probe_slot(), MemoizeEntry::status, MemoizeState::tableContext, and MemoizeEntry::tuplehead.

Referenced by ExecMemoize().

508 {
509  MemoizeTuple *tuple;
510  MemoizeEntry *entry = mstate->entry;
511  MemoryContext oldcontext;
512 
513  Assert(slot != NULL);
514  Assert(entry != NULL);
515 
516  oldcontext = MemoryContextSwitchTo(mstate->tableContext);
517 
518  tuple = (MemoizeTuple *) palloc(sizeof(MemoizeTuple));
519  tuple->mintuple = ExecCopySlotMinimalTuple(slot);
520  tuple->next = NULL;
521 
522  /* Account for the memory we just consumed */
523  mstate->mem_used += CACHE_TUPLE_BYTES(tuple);
524 
525  if (entry->tuplehead == NULL)
526  {
527  /*
528  * This is the first tuple for this entry, so just point the list head
529  * to it.
530  */
531  entry->tuplehead = tuple;
532  }
533  else
534  {
535  /* push this tuple onto the tail of the list */
536  mstate->last_tuple->next = tuple;
537  }
538 
539  mstate->last_tuple = tuple;
540  MemoryContextSwitchTo(oldcontext);
541 
542  /*
543  * If we've gone over our memory budget then free up some space in the
544  * cache.
545  */
546  if (mstate->mem_used > mstate->mem_limit)
547  {
548  MemoizeKey *key = entry->key;
549 
550  if (!cache_reduce_memory(mstate, key))
551  return false;
552 
553  /*
554  * The process of removing entries from the cache may have caused the
555  * code in simplehash.h to shuffle elements to earlier buckets in the
556  * hash table. If it has, we'll need to find the entry again by
557  * performing a lookup. Fortunately, we can detect if this has
558  * happened by seeing if the entry is still in use and that the key
559  * pointer matches our expected key.
560  */
561  if (entry->status != memoize_SH_IN_USE || entry->key != key)
562  {
563  /*
564  * We need to repopulate the probeslot as lookups performed during
565  * the cache evictions above will have stored some other key.
566  */
567  prepare_probe_slot(mstate, key);
568 
569  /* Re-find the entry */
570  mstate->entry = entry = memoize_lookup(mstate->hashtable, NULL);
571  Assert(entry != NULL);
572  }
573  }
574 
575  return true;
576 }
struct MemoizeTuple * next
Definition: nodeMemoize.c:96
MemoryContext tableContext
Definition: execnodes.h:2101
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
MinimalTuple mintuple
Definition: nodeMemoize.c:95
MemoizeTuple * tuplehead
Definition: nodeMemoize.c:117
static MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: tuptable.h:463
uint64 mem_limit
Definition: execnodes.h:2100
struct MemoizeTuple * last_tuple
Definition: execnodes.h:2103
static bool cache_reduce_memory(MemoizeState *mstate, MemoizeKey *specialkey)
Definition: nodeMemoize.c:326
#define Assert(condition)
Definition: c.h:804
struct MemoizeEntry * entry
Definition: execnodes.h:2107
struct memoize_hash * hashtable
Definition: execnodes.h:2090
#define CACHE_TUPLE_BYTES(t)
Definition: nodeMemoize.c:89
static void prepare_probe_slot(MemoizeState *mstate, MemoizeKey *key)
Definition: nodeMemoize.c:228
void * palloc(Size size)
Definition: mcxt.c:1062
MemoizeKey * key
Definition: nodeMemoize.c:116
uint64 mem_used
Definition: execnodes.h:2099

◆ entry_purge_tuples()

static void entry_purge_tuples ( MemoizeState mstate,
MemoizeEntry entry 
)
inlinestatic

Definition at line 263 of file nodeMemoize.c.

References CACHE_TUPLE_BYTES, MemoizeEntry::complete, MemoizeState::mem_used, MemoizeTuple::mintuple, MemoizeTuple::next, pfree(), and MemoizeEntry::tuplehead.

Referenced by ExecMemoize(), and remove_cache_entry().

264 {
265  MemoizeTuple *tuple = entry->tuplehead;
266  uint64 freed_mem = 0;
267 
268  while (tuple != NULL)
269  {
270  MemoizeTuple *next = tuple->next;
271 
272  freed_mem += CACHE_TUPLE_BYTES(tuple);
273 
274  /* Free memory used for this tuple */
275  pfree(tuple->mintuple);
276  pfree(tuple);
277 
278  tuple = next;
279  }
280 
281  entry->complete = false;
282  entry->tuplehead = NULL;
283 
284  /* Update the memory accounting */
285  mstate->mem_used -= freed_mem;
286 }
static int32 next
Definition: blutils.c:219
struct MemoizeTuple * next
Definition: nodeMemoize.c:96
MinimalTuple mintuple
Definition: nodeMemoize.c:95
void pfree(void *pointer)
Definition: mcxt.c:1169
MemoizeTuple * tuplehead
Definition: nodeMemoize.c:117
#define CACHE_TUPLE_BYTES(t)
Definition: nodeMemoize.c:89
uint64 mem_used
Definition: execnodes.h:2099

◆ ExecEndMemoize()

void ExecEndMemoize ( MemoizeState node)

Definition at line 939 of file nodeMemoize.c.

References Assert, CACHE_TUPLE_BYTES, EMPTY_ENTRY_MEMORY_BYTES, ExecClearTuple(), ExecEndNode(), ExecFreeExprContext(), MemoizeState::hashtable, i, IsParallelWorker, MemoizeInstrumentation::mem_peak, MemoizeState::mem_used, MemoryContextDelete(), MemoizeTuple::next, outerPlanState, ParallelWorkerNumber, ScanState::ps, PlanState::ps_ResultTupleSlot, MemoizeState::shared_info, SharedMemoizeInfo::sinstrument, MemoizeState::ss, ScanState::ss_ScanTupleSlot, MemoizeState::stats, MemoizeState::tableContext, and MemoizeEntry::tuplehead.

Referenced by ExecEndNode().

940 {
941 #ifdef USE_ASSERT_CHECKING
942  /* Validate the memory accounting code is correct in assert builds. */
943  {
944  int count;
945  uint64 mem = 0;
946  memoize_iterator i;
947  MemoizeEntry *entry;
948 
949  memoize_start_iterate(node->hashtable, &i);
950 
951  count = 0;
952  while ((entry = memoize_iterate(node->hashtable, &i)) != NULL)
953  {
954  MemoizeTuple *tuple = entry->tuplehead;
955 
956  mem += EMPTY_ENTRY_MEMORY_BYTES(entry);
957  while (tuple != NULL)
958  {
959  mem += CACHE_TUPLE_BYTES(tuple);
960  tuple = tuple->next;
961  }
962  count++;
963  }
964 
965  Assert(count == node->hashtable->members);
966  Assert(mem == node->mem_used);
967  }
968 #endif
969 
970  /*
971  * When ending a parallel worker, copy the statistics gathered by the
972  * worker back into shared memory so that it can be picked up by the main
973  * process to report in EXPLAIN ANALYZE.
974  */
975  if (node->shared_info != NULL && IsParallelWorker())
976  {
978 
979  /* Make mem_peak available for EXPLAIN */
980  if (node->stats.mem_peak == 0)
981  node->stats.mem_peak = node->mem_used;
982 
983  Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
985  memcpy(si, &node->stats, sizeof(MemoizeInstrumentation));
986  }
987 
988  /* Remove the cache context */
990 
992  /* must drop pointer to cache result tuple */
994 
995  /*
996  * free exprcontext
997  */
998  ExecFreeExprContext(&node->ss.ps);
999 
1000  /*
1001  * shut down the subplan
1002  */
1003  ExecEndNode(outerPlanState(node));
1004 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
struct MemoizeTuple * next
Definition: nodeMemoize.c:96
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:556
MemoryContext tableContext
Definition: execnodes.h:2101
#define EMPTY_ENTRY_MEMORY_BYTES(e)
Definition: nodeMemoize.c:86
TupleTableSlot * ss_ScanTupleSlot
Definition: execnodes.h:1380
void ExecFreeExprContext(PlanState *planstate)
Definition: execUtils.c:650
PlanState ps
Definition: execnodes.h:1377
TupleTableSlot * ps_ResultTupleSlot
Definition: execnodes.h:1004
MemoizeTuple * tuplehead
Definition: nodeMemoize.c:117
#define outerPlanState(node)
Definition: execnodes.h:1062
int ParallelWorkerNumber
Definition: parallel.c:112
#define IsParallelWorker()
Definition: parallel.h:61
ScanState ss
Definition: execnodes.h:2087
#define Assert(condition)
Definition: c.h:804
struct memoize_hash * hashtable
Definition: execnodes.h:2090
#define CACHE_TUPLE_BYTES(t)
Definition: nodeMemoize.c:89
SharedMemoizeInfo * shared_info
Definition: execnodes.h:2112
MemoizeInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER]
Definition: execnodes.h:2075
int i
MemoizeInstrumentation stats
Definition: execnodes.h:2111
uint64 mem_used
Definition: execnodes.h:2099

◆ ExecEstimateCacheEntryOverheadBytes()

double ExecEstimateCacheEntryOverheadBytes ( double  ntuples)

Definition at line 1033 of file nodeMemoize.c.

Referenced by cost_memoize_rescan().

1034 {
1035  return sizeof(MemoizeEntry) + sizeof(MemoizeKey) + sizeof(MemoizeTuple) *
1036  ntuples;
1037 }
struct MemoizeTuple MemoizeTuple
struct MemoizeEntry MemoizeEntry

◆ ExecInitMemoize()

MemoizeState* ExecInitMemoize ( Memoize node,
EState estate,
int  eflags 
)

Definition at line 821 of file nodeMemoize.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert, build_hash_table(), MemoizeState::cache_eq_expr, Memoize::collations, MemoizeState::collations, CurrentMemoryContext, dlist_init(), elog, ERROR, Memoize::est_entries, EXEC_FLAG_BACKWARD, EXEC_FLAG_MARK, ExecAssignExprContext(), ExecBuildParamSetEqual(), ExecCreateScanSlotFromOuterPlan(), ExecInitExpr(), ExecInitNode(), ExecInitResultTupleSlotTL(), ExecMemoize(), PlanState::ExecProcNode, ExecTypeFromExprList(), fmgr_info(), get_hash_memory_limit(), get_op_hash_functions(), get_opcode(), MemoizeState::hashfunctions, MemoizeState::hashkeydesc, Memoize::hashOperators, i, list_nth(), makeNode, MakeSingleTupleTableSlot(), MEMO_CACHE_LOOKUP, MemoizeState::mstatus, MemoizeState::nkeys, Memoize::numKeys, outerPlan, outerPlanState, palloc(), Memoize::param_exprs, MemoizeState::param_exprs, pfree(), PlanState::plan, MemoizeState::probeslot, ScanState::ps, PlanState::ps_ProjInfo, Memoize::singlerow, MemoizeState::ss, PlanState::state, MemoizeState::tableslot, TTSOpsMinimalTuple, and TTSOpsVirtual.

Referenced by ExecInitNode().

822 {
824  Plan *outerNode;
825  int i;
826  int nkeys;
827  Oid *eqfuncoids;
828 
829  /* check for unsupported flags */
830  Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
831 
832  mstate->ss.ps.plan = (Plan *) node;
833  mstate->ss.ps.state = estate;
834  mstate->ss.ps.ExecProcNode = ExecMemoize;
835 
836  /*
837  * Miscellaneous initialization
838  *
839  * create expression context for node
840  */
841  ExecAssignExprContext(estate, &mstate->ss.ps);
842 
843  outerNode = outerPlan(node);
844  outerPlanState(mstate) = ExecInitNode(outerNode, estate, eflags);
845 
846  /*
847  * Initialize return slot and type. No need to initialize projection info
848  * because this node doesn't do projections.
849  */
851  mstate->ss.ps.ps_ProjInfo = NULL;
852 
853  /*
854  * Initialize scan slot and type.
855  */
857 
858  /*
859  * Set the state machine to lookup the cache. We won't find anything
860  * until we cache something, but this saves a special case to create the
861  * first entry.
862  */
863  mstate->mstatus = MEMO_CACHE_LOOKUP;
864 
865  mstate->nkeys = nkeys = node->numKeys;
870  &TTSOpsVirtual);
871 
872  mstate->param_exprs = (ExprState **) palloc(nkeys * sizeof(ExprState *));
873  mstate->collations = node->collations; /* Just point directly to the plan
874  * data */
875  mstate->hashfunctions = (FmgrInfo *) palloc(nkeys * sizeof(FmgrInfo));
876 
877  eqfuncoids = palloc(nkeys * sizeof(Oid));
878 
879  for (i = 0; i < nkeys; i++)
880  {
881  Oid hashop = node->hashOperators[i];
882  Oid left_hashfn;
883  Oid right_hashfn;
884  Expr *param_expr = (Expr *) list_nth(node->param_exprs, i);
885 
886  if (!get_op_hash_functions(hashop, &left_hashfn, &right_hashfn))
887  elog(ERROR, "could not find hash function for hash operator %u",
888  hashop);
889 
890  fmgr_info(left_hashfn, &mstate->hashfunctions[i]);
891 
892  mstate->param_exprs[i] = ExecInitExpr(param_expr, (PlanState *) mstate);
893  eqfuncoids[i] = get_opcode(hashop);
894  }
895 
898  &TTSOpsVirtual,
899  eqfuncoids,
900  node->collations,
901  node->param_exprs,
902  (PlanState *) mstate);
903 
904  pfree(eqfuncoids);
905  mstate->mem_used = 0;
906 
907  /* Limit the total memory consumed by the cache to this */
908  mstate->mem_limit = get_hash_memory_limit();
909 
910  /* A memory context dedicated for the cache */
912  "MemoizeHashTable",
914 
915  dlist_init(&mstate->lru_list);
916  mstate->last_tuple = NULL;
917  mstate->entry = NULL;
918 
919  /*
920  * Mark if we can assume the cache entry is completed after we get the
921  * first record for it. Some callers might not call us again after
922  * getting the first match. e.g. A join operator performing a unique join
923  * is able to skip to the next outer tuple after getting the first
924  * matching inner tuple. In this case, the cache entry is complete after
925  * getting the first tuple. This allows us to mark it as so.
926  */
927  mstate->singlerow = node->singlerow;
928 
929  /* Zero the statistics counters */
930  memset(&mstate->stats, 0, sizeof(MemoizeInstrumentation));
931 
932  /* Allocate and set up the actual cache */
933  build_hash_table(mstate, node->est_entries);
934 
935  return mstate;
936 }
Definition: fmgr.h:56
#define AllocSetContextCreate
Definition: memutils.h:173
bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno)
Definition: lsyscache.c:508
bool singlerow
Definition: execnodes.h:2109
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:1006
Oid * collations
Definition: plannodes.h:797
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1238
MemoryContext tableContext
Definition: execnodes.h:2101
ExprState * ExecBuildParamSetEqual(TupleDesc desc, const TupleTableSlotOps *lops, const TupleTableSlotOps *rops, const Oid *eqfunctions, const Oid *collations, const List *param_exprs, PlanState *parent)
Definition: execExpr.c:3856
ExprState * cache_eq_expr
Definition: execnodes.h:2094
const TupleTableSlotOps TTSOpsVirtual
Definition: execTuples.c:83
static void build_hash_table(MemoizeState *mstate, uint32 size)
Definition: nodeMemoize.c:211
static TupleTableSlot * ExecMemoize(PlanState *pstate)
Definition: nodeMemoize.c:579
TupleTableSlot * probeslot
Definition: execnodes.h:2093
EState * state
Definition: execnodes.h:968
int numKeys
Definition: plannodes.h:794
unsigned int Oid
Definition: postgres_ext.h:31
PlanState ps
Definition: execnodes.h:1377
List * param_exprs
Definition: plannodes.h:798
void pfree(void *pointer)
Definition: mcxt.c:1169
#define ERROR
Definition: elog.h:46
ExprState ** param_exprs
Definition: execnodes.h:2095
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:126
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:195
#define EXEC_FLAG_BACKWARD
Definition: executor.h:58
#define outerPlanState(node)
Definition: execnodes.h:1062
uint64 mem_limit
Definition: execnodes.h:2100
struct MemoizeTuple * last_tuple
Definition: execnodes.h:2103
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define outerPlan(node)
Definition: plannodes.h:171
Oid * collations
Definition: execnodes.h:2098
ScanState ss
Definition: execnodes.h:2087
TupleTableSlot * tableslot
Definition: execnodes.h:2092
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:972
FmgrInfo * hashfunctions
Definition: execnodes.h:2097
bool singlerow
Definition: plannodes.h:799
Plan * plan
Definition: execnodes.h:966
static void dlist_init(dlist_head *head)
Definition: ilist.h:278
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1256
#define makeNode(_type_)
Definition: nodes.h:584
#define Assert(condition)
Definition: c.h:804
struct MemoizeEntry * entry
Definition: execnodes.h:2107
#define EXEC_FLAG_MARK
Definition: executor.h:59
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:480
size_t get_hash_memory_limit(void)
Definition: nodeHash.c:3401
void ExecInitResultTupleSlotTL(PlanState *planstate, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1799
TupleDesc hashkeydesc
Definition: execnodes.h:2091
uint32 est_entries
Definition: plannodes.h:802
TupleDesc ExecTypeFromExprList(List *exprList)
Definition: execTuples.c:1997
void * palloc(Size size)
Definition: mcxt.c:1062
#define elog(elevel,...)
Definition: elog.h:232
int i
#define MEMO_CACHE_LOOKUP
Definition: nodeMemoize.c:77
MemoizeInstrumentation stats
Definition: execnodes.h:2111
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execExpr.c:123
void ExecCreateScanSlotFromOuterPlan(EState *estate, ScanState *scanstate, const TupleTableSlotOps *tts_ops)
Definition: execUtils.c:682
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:141
dlist_head lru_list
Definition: execnodes.h:2102
const TupleTableSlotOps TTSOpsMinimalTuple
Definition: execTuples.c:85
Oid * hashOperators
Definition: plannodes.h:796
uint64 mem_used
Definition: execnodes.h:2099

◆ ExecMemoize()

static TupleTableSlot* ExecMemoize ( PlanState pstate)
static

Definition at line 579 of file nodeMemoize.c.

References Assert, MemoizeInstrumentation::cache_hits, cache_lookup(), MemoizeInstrumentation::cache_misses, MemoizeInstrumentation::cache_overflows, cache_store_tuple(), castNode, MemoizeEntry::complete, elog, MemoizeState::entry, entry_purge_tuples(), ERROR, ExecCopySlot(), ExecProcNode(), ExecStoreMinimalTuple(), MemoizeState::last_tuple, likely, MEMO_CACHE_BYPASS_MODE, MEMO_CACHE_FETCH_NEXT_TUPLE, MEMO_CACHE_LOOKUP, MEMO_END_OF_SCAN, MEMO_FILLING_CACHE, MemoizeTuple::mintuple, MemoizeState::mstatus, MemoizeTuple::next, outerPlanState, ScanState::ps, PlanState::ps_ResultTupleSlot, MemoizeState::singlerow, MemoizeState::ss, MemoizeState::stats, TupIsNull, MemoizeEntry::tuplehead, and unlikely.

Referenced by ExecInitMemoize().

580 {
581  MemoizeState *node = castNode(MemoizeState, pstate);
582  PlanState *outerNode;
583  TupleTableSlot *slot;
584 
585  switch (node->mstatus)
586  {
587  case MEMO_CACHE_LOOKUP:
588  {
589  MemoizeEntry *entry;
590  TupleTableSlot *outerslot;
591  bool found;
592 
593  Assert(node->entry == NULL);
594 
595  /*
596  * We're only ever in this state for the first call of the
597  * scan. Here we have a look to see if we've already seen the
598  * current parameters before and if we have already cached a
599  * complete set of records that the outer plan will return for
600  * these parameters.
601  *
602  * When we find a valid cache entry, we'll return the first
603  * tuple from it. If not found, we'll create a cache entry and
604  * then try to fetch a tuple from the outer scan. If we find
605  * one there, we'll try to cache it.
606  */
607 
608  /* see if we've got anything cached for the current parameters */
609  entry = cache_lookup(node, &found);
610 
611  if (found && entry->complete)
612  {
613  node->stats.cache_hits += 1; /* stats update */
614 
615  /*
616  * Set last_tuple and entry so that the state
617  * MEMO_CACHE_FETCH_NEXT_TUPLE can easily find the next
618  * tuple for these parameters.
619  */
620  node->last_tuple = entry->tuplehead;
621  node->entry = entry;
622 
623  /* Fetch the first cached tuple, if there is one */
624  if (entry->tuplehead)
625  {
627 
628  slot = node->ss.ps.ps_ResultTupleSlot;
630  slot, false);
631 
632  return slot;
633  }
634 
635  /* The cache entry is void of any tuples. */
636  node->mstatus = MEMO_END_OF_SCAN;
637  return NULL;
638  }
639 
640  /* Handle cache miss */
641  node->stats.cache_misses += 1; /* stats update */
642 
643  if (found)
644  {
645  /*
646  * A cache entry was found, but the scan for that entry
647  * did not run to completion. We'll just remove all
648  * tuples and start again. It might be tempting to
649  * continue where we left off, but there's no guarantee
650  * the outer node will produce the tuples in the same
651  * order as it did last time.
652  */
653  entry_purge_tuples(node, entry);
654  }
655 
656  /* Scan the outer node for a tuple to cache */
657  outerNode = outerPlanState(node);
658  outerslot = ExecProcNode(outerNode);
659  if (TupIsNull(outerslot))
660  {
661  /*
662  * cache_lookup may have returned NULL due to failure to
663  * free enough cache space, so ensure we don't do anything
664  * here that assumes it worked. There's no need to go into
665  * bypass mode here as we're setting mstatus to end of
666  * scan.
667  */
668  if (likely(entry))
669  entry->complete = true;
670 
671  node->mstatus = MEMO_END_OF_SCAN;
672  return NULL;
673  }
674 
675  node->entry = entry;
676 
677  /*
678  * If we failed to create the entry or failed to store the
679  * tuple in the entry, then go into bypass mode.
680  */
681  if (unlikely(entry == NULL ||
682  !cache_store_tuple(node, outerslot)))
683  {
684  node->stats.cache_overflows += 1; /* stats update */
685 
687 
688  /*
689  * No need to clear out last_tuple as we'll stay in bypass
690  * mode until the end of the scan.
691  */
692  }
693  else
694  {
695  /*
696  * If we only expect a single row from this scan then we
697  * can mark that we're not expecting more. This allows
698  * cache lookups to work even when the scan has not been
699  * executed to completion.
700  */
701  entry->complete = node->singlerow;
702  node->mstatus = MEMO_FILLING_CACHE;
703  }
704 
705  slot = node->ss.ps.ps_ResultTupleSlot;
706  ExecCopySlot(slot, outerslot);
707  return slot;
708  }
709 
711  {
712  /* We shouldn't be in this state if these are not set */
713  Assert(node->entry != NULL);
714  Assert(node->last_tuple != NULL);
715 
716  /* Skip to the next tuple to output */
717  node->last_tuple = node->last_tuple->next;
718 
719  /* No more tuples in the cache */
720  if (node->last_tuple == NULL)
721  {
722  node->mstatus = MEMO_END_OF_SCAN;
723  return NULL;
724  }
725 
726  slot = node->ss.ps.ps_ResultTupleSlot;
728  false);
729 
730  return slot;
731  }
732 
733  case MEMO_FILLING_CACHE:
734  {
735  TupleTableSlot *outerslot;
736  MemoizeEntry *entry = node->entry;
737 
738  /* entry should already have been set by MEMO_CACHE_LOOKUP */
739  Assert(entry != NULL);
740 
741  /*
742  * When in the MEMO_FILLING_CACHE state, we've just had a
743  * cache miss and are populating the cache with the current
744  * scan tuples.
745  */
746  outerNode = outerPlanState(node);
747  outerslot = ExecProcNode(outerNode);
748  if (TupIsNull(outerslot))
749  {
750  /* No more tuples. Mark it as complete */
751  entry->complete = true;
752  node->mstatus = MEMO_END_OF_SCAN;
753  return NULL;
754  }
755 
756  /*
757  * Validate if the planner properly set the singlerow flag. It
758  * should only set that if each cache entry can, at most,
759  * return 1 row.
760  */
761  if (unlikely(entry->complete))
762  elog(ERROR, "cache entry already complete");
763 
764  /* Record the tuple in the current cache entry */
765  if (unlikely(!cache_store_tuple(node, outerslot)))
766  {
767  /* Couldn't store it? Handle overflow */
768  node->stats.cache_overflows += 1; /* stats update */
769 
771 
772  /*
773  * No need to clear out entry or last_tuple as we'll stay
774  * in bypass mode until the end of the scan.
775  */
776  }
777 
778  slot = node->ss.ps.ps_ResultTupleSlot;
779  ExecCopySlot(slot, outerslot);
780  return slot;
781  }
782 
784  {
785  TupleTableSlot *outerslot;
786 
787  /*
788  * When in bypass mode we just continue to read tuples without
789  * caching. We need to wait until the next rescan before we
790  * can come out of this mode.
791  */
792  outerNode = outerPlanState(node);
793  outerslot = ExecProcNode(outerNode);
794  if (TupIsNull(outerslot))
795  {
796  node->mstatus = MEMO_END_OF_SCAN;
797  return NULL;
798  }
799 
800  slot = node->ss.ps.ps_ResultTupleSlot;
801  ExecCopySlot(slot, outerslot);
802  return slot;
803  }
804 
805  case MEMO_END_OF_SCAN:
806 
807  /*
808  * We've already returned NULL for this scan, but just in case
809  * something calls us again by mistake.
810  */
811  return NULL;
812 
813  default:
814  elog(ERROR, "unrecognized memoize state: %d",
815  (int) node->mstatus);
816  return NULL;
817  } /* switch */
818 }
static TupleTableSlot * ExecCopySlot(TupleTableSlot *dstslot, TupleTableSlot *srcslot)
Definition: tuptable.h:475
#define MEMO_CACHE_FETCH_NEXT_TUPLE
Definition: nodeMemoize.c:78
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
#define likely(x)
Definition: c.h:272
bool singlerow
Definition: execnodes.h:2109
struct MemoizeTuple * next
Definition: nodeMemoize.c:96
#define castNode(_type_, nodeptr)
Definition: nodes.h:605
static bool cache_store_tuple(MemoizeState *mstate, TupleTableSlot *slot)
Definition: nodeMemoize.c:507
PlanState ps
Definition: execnodes.h:1377
MinimalTuple mintuple
Definition: nodeMemoize.c:95
TupleTableSlot * ps_ResultTupleSlot
Definition: execnodes.h:1004
#define ERROR
Definition: elog.h:46
MemoizeTuple * tuplehead
Definition: nodeMemoize.c:117
#define outerPlanState(node)
Definition: execnodes.h:1062
struct MemoizeTuple * last_tuple
Definition: execnodes.h:2103
#define TupIsNull(slot)
Definition: tuptable.h:292
static void entry_purge_tuples(MemoizeState *mstate, MemoizeEntry *entry)
Definition: nodeMemoize.c:263
ScanState ss
Definition: execnodes.h:2087
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:252
#define MEMO_END_OF_SCAN
Definition: nodeMemoize.c:82
#define MEMO_FILLING_CACHE
Definition: nodeMemoize.c:79
#define Assert(condition)
Definition: c.h:804
struct MemoizeEntry * entry
Definition: execnodes.h:2107
#define MEMO_CACHE_BYPASS_MODE
Definition: nodeMemoize.c:80
#define elog(elevel,...)
Definition: elog.h:232
#define MEMO_CACHE_LOOKUP
Definition: nodeMemoize.c:77
MemoizeInstrumentation stats
Definition: execnodes.h:2111
#define unlikely(x)
Definition: c.h:273
static MemoizeEntry * cache_lookup(MemoizeState *mstate, bool *found)
Definition: nodeMemoize.c:410

◆ ExecMemoizeEstimate()

void ExecMemoizeEstimate ( MemoizeState node,
ParallelContext pcxt 
)

Definition at line 1051 of file nodeMemoize.c.

References add_size(), ParallelContext::estimator, PlanState::instrument, mul_size(), ParallelContext::nworkers, offsetof, ScanState::ps, shm_toc_estimate_chunk, shm_toc_estimate_keys, and MemoizeState::ss.

Referenced by ExecParallelEstimate().

1052 {
1053  Size size;
1054 
1055  /* don't need this if not instrumenting or no workers */
1056  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
1057  return;
1058 
1059  size = mul_size(pcxt->nworkers, sizeof(MemoizeInstrumentation));
1060  size = add_size(size, offsetof(SharedMemoizeInfo, sinstrument));
1061  shm_toc_estimate_chunk(&pcxt->estimator, size);
1062  shm_toc_estimate_keys(&pcxt->estimator, 1);
1063 }
Instrumentation * instrument
Definition: execnodes.h:976
shm_toc_estimator estimator
Definition: parallel.h:42
#define shm_toc_estimate_chunk(e, sz)
Definition: shm_toc.h:51
PlanState ps
Definition: execnodes.h:1377
ScanState ss
Definition: execnodes.h:2087
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
size_t Size
Definition: c.h:540
#define shm_toc_estimate_keys(e, cnt)
Definition: shm_toc.h:53
#define offsetof(type, field)
Definition: c.h:727

◆ ExecMemoizeInitializeDSM()

void ExecMemoizeInitializeDSM ( MemoizeState node,
ParallelContext pcxt 
)

Definition at line 1072 of file nodeMemoize.c.

References PlanState::instrument, SharedMemoizeInfo::num_workers, ParallelContext::nworkers, offsetof, PlanState::plan, Plan::plan_node_id, ScanState::ps, MemoizeState::shared_info, shm_toc_allocate(), shm_toc_insert(), MemoizeState::ss, and ParallelContext::toc.

Referenced by ExecParallelInitializeDSM().

1073 {
1074  Size size;
1075 
1076  /* don't need this if not instrumenting or no workers */
1077  if (!node->ss.ps.instrument || pcxt->nworkers == 0)
1078  return;
1079 
1080  size = offsetof(SharedMemoizeInfo, sinstrument)
1081  + pcxt->nworkers * sizeof(MemoizeInstrumentation);
1082  node->shared_info = shm_toc_allocate(pcxt->toc, size);
1083  /* ensure any unfilled slots will contain zeroes */
1084  memset(node->shared_info, 0, size);
1085  node->shared_info->num_workers = pcxt->nworkers;
1086  shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
1087  node->shared_info);
1088 }
Instrumentation * instrument
Definition: execnodes.h:976
struct MemoizeInstrumentation MemoizeInstrumentation
int plan_node_id
Definition: plannodes.h:140
PlanState ps
Definition: execnodes.h:1377
ScanState ss
Definition: execnodes.h:2087
Plan * plan
Definition: execnodes.h:966
size_t Size
Definition: c.h:540
void * shm_toc_allocate(shm_toc *toc, Size nbytes)
Definition: shm_toc.c:88
SharedMemoizeInfo * shared_info
Definition: execnodes.h:2112
void shm_toc_insert(shm_toc *toc, uint64 key, void *address)
Definition: shm_toc.c:171
#define offsetof(type, field)
Definition: c.h:727
shm_toc * toc
Definition: parallel.h:45

◆ ExecMemoizeInitializeWorker()

void ExecMemoizeInitializeWorker ( MemoizeState node,
ParallelWorkerContext pwcxt 
)

Definition at line 1097 of file nodeMemoize.c.

References PlanState::plan, Plan::plan_node_id, ScanState::ps, MemoizeState::shared_info, shm_toc_lookup(), MemoizeState::ss, and ParallelWorkerContext::toc.

Referenced by ExecParallelInitializeWorker().

1098 {
1099  node->shared_info =
1100  shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);
1101 }
int plan_node_id
Definition: plannodes.h:140
PlanState ps
Definition: execnodes.h:1377
ScanState ss
Definition: execnodes.h:2087
Plan * plan
Definition: execnodes.h:966
SharedMemoizeInfo * shared_info
Definition: execnodes.h:2112
void * shm_toc_lookup(shm_toc *toc, uint64 key, bool noError)
Definition: shm_toc.c:232

◆ ExecMemoizeRetrieveInstrumentation()

void ExecMemoizeRetrieveInstrumentation ( MemoizeState node)

Definition at line 1110 of file nodeMemoize.c.

References SharedMemoizeInfo::num_workers, offsetof, palloc(), and MemoizeState::shared_info.

Referenced by ExecParallelRetrieveInstrumentation().

1111 {
1112  Size size;
1113  SharedMemoizeInfo *si;
1114 
1115  if (node->shared_info == NULL)
1116  return;
1117 
1118  size = offsetof(SharedMemoizeInfo, sinstrument)
1119  + node->shared_info->num_workers * sizeof(MemoizeInstrumentation);
1120  si = palloc(size);
1121  memcpy(si, node->shared_info, size);
1122  node->shared_info = si;
1123 }
struct MemoizeInstrumentation MemoizeInstrumentation
size_t Size
Definition: c.h:540
SharedMemoizeInfo * shared_info
Definition: execnodes.h:2112
void * palloc(Size size)
Definition: mcxt.c:1062
#define offsetof(type, field)
Definition: c.h:727

◆ ExecReScanMemoize()

void ExecReScanMemoize ( MemoizeState node)

Definition at line 1007 of file nodeMemoize.c.

References PlanState::chgParam, MemoizeState::entry, ExecReScan(), MemoizeState::last_tuple, MEMO_CACHE_LOOKUP, MemoizeState::mstatus, outerPlan, and outerPlanState.

Referenced by ExecReScan().

1008 {
1010 
1011  /* Mark that we must lookup the cache for a new set of parameters */
1012  node->mstatus = MEMO_CACHE_LOOKUP;
1013 
1014  /* nullify pointers used for the last scan */
1015  node->entry = NULL;
1016  node->last_tuple = NULL;
1017 
1018  /*
1019  * if chgParam of subnode is not null then plan will be re-scanned by
1020  * first ExecProcNode.
1021  */
1022  if (outerPlan->chgParam == NULL)
1023  ExecReScan(outerPlan);
1024 
1025 }
void ExecReScan(PlanState *node)
Definition: execAmi.c:78
#define outerPlanState(node)
Definition: execnodes.h:1062
struct MemoizeTuple * last_tuple
Definition: execnodes.h:2103
Bitmapset * chgParam
Definition: execnodes.h:998
#define outerPlan(node)
Definition: plannodes.h:171
struct MemoizeEntry * entry
Definition: execnodes.h:2107
#define MEMO_CACHE_LOOKUP
Definition: nodeMemoize.c:77

◆ MemoizeHash_equal()

static int MemoizeHash_equal ( struct memoize_hash *  tb,
const MemoizeKey params1,
const MemoizeKey params2 
)
static

Definition at line 191 of file nodeMemoize.c.

References MemoizeState::cache_eq_expr, ExecQualAndReset(), ExecStoreMinimalTuple(), MemoizeKey::params, MemoizeState::probeslot, ScanState::ps, PlanState::ps_ExprContext, MemoizeState::ss, and MemoizeState::tableslot.

193 {
194  MemoizeState *mstate = (MemoizeState *) tb->private_data;
195  ExprContext *econtext = mstate->ss.ps.ps_ExprContext;
196  TupleTableSlot *tslot = mstate->tableslot;
197  TupleTableSlot *pslot = mstate->probeslot;
198 
199  /* probeslot should have already been prepared by prepare_probe_slot() */
200  ExecStoreMinimalTuple(key1->params, tslot, false);
201 
202  econtext->ecxt_innertuple = tslot;
203  econtext->ecxt_outertuple = pslot;
204  return !ExecQualAndReset(mstate->cache_eq_expr, econtext);
205 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
ExprContext * ps_ExprContext
Definition: execnodes.h:1005
ExprState * cache_eq_expr
Definition: execnodes.h:2094
TupleTableSlot * probeslot
Definition: execnodes.h:2093
PlanState ps
Definition: execnodes.h:1377
ScanState ss
Definition: execnodes.h:2087
static bool ExecQualAndReset(ExprState *state, ExprContext *econtext)
Definition: executor.h:423
TupleTableSlot * tableslot
Definition: execnodes.h:2092

◆ MemoizeHash_hash()

static uint32 MemoizeHash_hash ( struct memoize_hash *  tb,
const MemoizeKey key 
)
static

Definition at line 157 of file nodeMemoize.c.

References MemoizeState::collations, DatumGetUInt32, FunctionCall1Coll(), MemoizeState::hashfunctions, i, murmurhash32(), MemoizeState::nkeys, and MemoizeState::probeslot.

158 {
159  MemoizeState *mstate = (MemoizeState *) tb->private_data;
160  TupleTableSlot *pslot = mstate->probeslot;
161  uint32 hashkey = 0;
162  int numkeys = mstate->nkeys;
163  FmgrInfo *hashfunctions = mstate->hashfunctions;
164  Oid *collations = mstate->collations;
165 
166  for (int i = 0; i < numkeys; i++)
167  {
168  /* rotate hashkey left 1 bit at each step */
169  hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
170 
171  if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
172  {
173  uint32 hkey;
174 
175  hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
176  collations[i], pslot->tts_values[i]));
177  hashkey ^= hkey;
178  }
179  }
180 
181  return murmurhash32(hashkey);
182 }
#define DatumGetUInt32(X)
Definition: postgres.h:530
Definition: fmgr.h:56
static uint32 murmurhash32(uint32 data)
Definition: hashfn.h:92
TupleTableSlot * probeslot
Definition: execnodes.h:2093
unsigned int Oid
Definition: postgres_ext.h:31
unsigned int uint32
Definition: c.h:441
Oid * collations
Definition: execnodes.h:2098
FmgrInfo * hashfunctions
Definition: execnodes.h:2097
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1128
int i

◆ prepare_probe_slot()

static void prepare_probe_slot ( MemoizeState mstate,
MemoizeKey key 
)
inlinestatic

Definition at line 228 of file nodeMemoize.c.

References ExecClearTuple(), ExecEvalExpr(), ExecStoreMinimalTuple(), ExecStoreVirtualTuple(), i, MemoizeState::nkeys, MemoizeState::param_exprs, MemoizeKey::params, MemoizeState::probeslot, ScanState::ps, PlanState::ps_ExprContext, slot_getallattrs(), MemoizeState::ss, MemoizeState::tableslot, TupleTableSlot::tts_isnull, and TupleTableSlot::tts_values.

Referenced by cache_lookup(), cache_reduce_memory(), and cache_store_tuple().

229 {
230  TupleTableSlot *pslot = mstate->probeslot;
231  TupleTableSlot *tslot = mstate->tableslot;
232  int numKeys = mstate->nkeys;
233 
234  ExecClearTuple(pslot);
235 
236  if (key == NULL)
237  {
238  /* Set the probeslot's values based on the current parameter values */
239  for (int i = 0; i < numKeys; i++)
240  pslot->tts_values[i] = ExecEvalExpr(mstate->param_exprs[i],
241  mstate->ss.ps.ps_ExprContext,
242  &pslot->tts_isnull[i]);
243  }
244  else
245  {
246  /* Process the key's MinimalTuple and store the values in probeslot */
247  ExecStoreMinimalTuple(key->params, tslot, false);
248  slot_getallattrs(tslot);
249  memcpy(pslot->tts_values, tslot->tts_values, sizeof(Datum) * numKeys);
250  memcpy(pslot->tts_isnull, tslot->tts_isnull, sizeof(bool) * numKeys);
251  }
252 
253  ExecStoreVirtualTuple(pslot);
254 }
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:1446
static TupleTableSlot * ExecClearTuple(TupleTableSlot *slot)
Definition: tuptable.h:425
ExprContext * ps_ExprContext
Definition: execnodes.h:1005
Datum * tts_values
Definition: tuptable.h:126
TupleTableSlot * probeslot
Definition: execnodes.h:2093
PlanState ps
Definition: execnodes.h:1377
ExprState ** param_exprs
Definition: execnodes.h:2095
static void slot_getallattrs(TupleTableSlot *slot)
Definition: tuptable.h:354
bool * tts_isnull
Definition: tuptable.h:128
static Datum ExecEvalExpr(ExprState *state, ExprContext *econtext, bool *isNull)
Definition: executor.h:316
ScanState ss
Definition: execnodes.h:2087
TupleTableSlot * tableslot
Definition: execnodes.h:2092
uintptr_t Datum
Definition: postgres.h:411
int i
MinimalTuple params
Definition: nodeMemoize.c:106
TupleTableSlot * ExecStoreVirtualTuple(TupleTableSlot *slot)
Definition: execTuples.c:1552

◆ remove_cache_entry()

static void remove_cache_entry ( MemoizeState mstate,
MemoizeEntry entry 
)
static

Definition at line 293 of file nodeMemoize.c.

References dlist_delete(), EMPTY_ENTRY_MEMORY_BYTES, entry_purge_tuples(), MemoizeState::hashtable, sort-test::key, MemoizeEntry::key, MemoizeKey::lru_node, MemoizeState::mem_used, MemoizeKey::params, and pfree().

Referenced by cache_reduce_memory().

294 {
295  MemoizeKey *key = entry->key;
296 
297  dlist_delete(&entry->key->lru_node);
298 
299  /* Remove all of the tuples from this entry */
300  entry_purge_tuples(mstate, entry);
301 
302  /*
303  * Update memory accounting. entry_purge_tuples should have already
304  * subtracted the memory used for each cached tuple. Here we just update
305  * the amount used by the entry itself.
306  */
307  mstate->mem_used -= EMPTY_ENTRY_MEMORY_BYTES(entry);
308 
309  /* Remove the entry from the cache */
310  memoize_delete_item(mstate->hashtable, entry);
311 
312  pfree(key->params);
313  pfree(key);
314 }
#define EMPTY_ENTRY_MEMORY_BYTES(e)
Definition: nodeMemoize.c:86
void pfree(void *pointer)
Definition: mcxt.c:1169
static void dlist_delete(dlist_node *node)
Definition: ilist.h:358
static void entry_purge_tuples(MemoizeState *mstate, MemoizeEntry *entry)
Definition: nodeMemoize.c:263
struct memoize_hash * hashtable
Definition: execnodes.h:2090
dlist_node lru_node
Definition: nodeMemoize.c:107
MinimalTuple params
Definition: nodeMemoize.c:106
MemoizeKey * key
Definition: nodeMemoize.c:116
uint64 mem_used
Definition: execnodes.h:2099