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/datum.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)
#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 bool	MemoizeHash_equal (struct memoize_hash *tb, const MemoizeKey *key1, const MemoizeKey *key2)
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 void	cache_purge_all (MemoizeState *mstate)
static bool	cache_reduce_memory (MemoizeState *mstate, MemoizeKey *specialkey)
static MemoizeEntry *	cache_lookup (MemoizeState *mstate, bool *found)
static bool	cache_store_tuple (MemoizeState *mstate, TupleTableSlot *slot)
static TupleTableSlot *	ExecMemoize (PlanState *pstate)
MemoizeState *	ExecInitMemoize (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)

Definition at line 89 of file nodeMemoize.c.

EMPTY_ENTRY_MEMORY_BYTES

#define EMPTY_ENTRY_MEMORY_BYTES

(

e

)

Value:

                                         (sizeof(MemoizeEntry) + \
                                         sizeof(MemoizeKey) + \
                                         (e)->key->params->t_len);

Definition at line 86 of file nodeMemoize.c.

MEMO_CACHE_BYPASS_MODE

#define MEMO_CACHE_BYPASS_MODE

Value:

                                         4  /* Bypass mode.  Just read from our
                                         * subplan without caching anything */

Definition at line 81 of file nodeMemoize.c.

MEMO_CACHE_FETCH_NEXT_TUPLE

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

Definition at line 79 of file nodeMemoize.c.

MEMO_CACHE_LOOKUP

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

Definition at line 78 of file nodeMemoize.c.

MEMO_END_OF_SCAN

#define MEMO_END_OF_SCAN   5 /* Ready for rescan */

Definition at line 82 of file nodeMemoize.c.

MEMO_FILLING_CACHE

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

Definition at line 80 of file nodeMemoize.c.

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,
			b
	)		MemoizeHash_equal(tb, a, b)

Definition at line 143 of file nodeMemoize.c.

SH_GET_HASH

#define SH_GET_HASH	(		tb,
			a
	)		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 283 of file nodeMemoize.c.

{
    /* Make a guess at a good size when we're not given a valid size. */
    if (size == 0)
        size = 1024;
 
    /* memoize_create will convert the size to a power of 2 */
    mstate->hashtable = memoize_create(mstate->tableContext, size, mstate);

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

Referenced by cache_purge_all(), and ExecInitMemoize().

cache_lookup()

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

static

Definition at line 524 of file nodeMemoize.c.

{
    MemoizeKey *key;
    MemoizeEntry *entry;
    MemoryContext oldcontext;
 
    /* prepare the probe slot with the current scan parameters */
    prepare_probe_slot(mstate, NULL);
 
    /*
     * Add the new entry to the cache.  No need to pass a valid key since the
     * hash function uses mstate's probeslot, which we populated above.
     */
    entry = memoize_insert(mstate->hashtable, NULL, found);
 
    if (*found)
    {
        /*
         * Move existing entry to the tail of the LRU list to mark it as the
         * most recently used item.
         */
        dlist_move_tail(&mstate->lru_list, &entry->key->lru_node);
 
        return entry;
    }
 
    oldcontext = MemoryContextSwitchTo(mstate->tableContext);
 
    /* Allocate a new key */
    entry->key = key = (MemoizeKey *) palloc(sizeof(MemoizeKey));
    key->params = ExecCopySlotMinimalTuple(mstate->probeslot);
 
    /* Update the total cache memory utilization */
    mstate->mem_used += EMPTY_ENTRY_MEMORY_BYTES(entry);
 
    /* Initialize this entry */
    entry->complete = false;
    entry->tuplehead = NULL;
 
    /*
     * Since this is the most recently used entry, push this entry onto the
     * end of the LRU list.
     */
    dlist_push_tail(&mstate->lru_list, &entry->key->lru_node);
 
    mstate->last_tuple = NULL;
 
    MemoryContextSwitchTo(oldcontext);
 
    /*
     * If we've gone over our memory budget, then we'll free up some space in
     * the cache.
     */
    if (mstate->mem_used > mstate->mem_limit)
    {
        /*
         * Try to free up some memory.  It's highly unlikely that we'll fail
         * to do so here since the entry we've just added is yet to contain
         * any tuples and we're able to remove any other entry to reduce the
         * memory consumption.
         */
        if (unlikely(!cache_reduce_memory(mstate, key)))
            return NULL;
 
        /*
         * The process of removing entries from the cache may have caused the
         * code in simplehash.h to shuffle elements to earlier buckets in the
         * hash table.  If it has, we'll need to find the entry again by
         * performing a lookup.  Fortunately, we can detect if this has
         * happened by seeing if the entry is still in use and that the key
         * pointer matches our expected key.
         */
        if (entry->status != memoize_SH_IN_USE || entry->key != key)
        {
            /*
             * We need to repopulate the probeslot as lookups performed during
             * the cache evictions above will have stored some other key.
             */
            prepare_probe_slot(mstate, key);
 
            /* Re-find the newly added entry */
            entry = memoize_lookup(mstate->hashtable, NULL);
            Assert(entry != NULL);
        }
    }
 
    return entry;

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

Referenced by ExecMemoize().

cache_purge_all()

static void cache_purge_all ( MemoizeState *  mstate )

static

Definition at line 400 of file nodeMemoize.c.

{
    uint64      evictions = mstate->hashtable->members;
    PlanState  *pstate = (PlanState *) mstate;
 
    /*
     * Likely the most efficient way to remove all items is to just reset the
     * memory context for the cache and then rebuild a fresh hash table.  This
     * saves having to remove each item one by one and pfree each cached tuple
     */
    MemoryContextReset(mstate->tableContext);
 
    /* Make the hash table the same size as the original size */
    build_hash_table(mstate, ((Memoize *) pstate->plan)->est_entries);
 
    /* reset the LRU list */
    dlist_init(&mstate->lru_list);
    mstate->last_tuple = NULL;
    mstate->entry = NULL;
 
    mstate->mem_used = 0;
 
    /* XXX should we add something new to track these purges? */
    mstate->stats.cache_evictions += evictions; /* Update Stats */

References build_hash_table(), MemoizeInstrumentation::cache_evictions, dlist_init(), MemoizeState::entry, MemoizeState::hashtable, MemoizeState::last_tuple, MemoizeState::lru_list, MemoizeState::mem_used, MemoryContextReset(), PlanState::plan, MemoizeState::stats, and MemoizeState::tableContext.

Referenced by ExecReScanMemoize().

cache_reduce_memory()

static bool cache_reduce_memory ( MemoizeState *  mstate, MemoizeKey *  specialkey  )

static

Definition at line 436 of file nodeMemoize.c.

{
    bool        specialkey_intact = true;   /* for now */
    dlist_mutable_iter iter;
    uint64      evictions = 0;
 
    /* Update peak memory usage */
    if (mstate->mem_used > mstate->stats.mem_peak)
        mstate->stats.mem_peak = mstate->mem_used;
 
    /* We expect only to be called when we've gone over budget on memory */
    Assert(mstate->mem_used > mstate->mem_limit);
 
    /* Start the eviction process starting at the head of the LRU list. */
    dlist_foreach_modify(iter, &mstate->lru_list)
    {
        MemoizeKey *key = dlist_container(MemoizeKey, lru_node, iter.cur);
        MemoizeEntry *entry;
 
        /*
         * Populate the hash probe slot in preparation for looking up this LRU
         * entry.
         */
        prepare_probe_slot(mstate, key);
 
        /*
         * Ideally the LRU list pointers would be stored in the entry itself
         * rather than in the key.  Unfortunately, we can't do that as the
         * simplehash.h code may resize the table and allocate new memory for
         * entries which would result in those pointers pointing to the old
         * buckets.  However, it's fine to use the key to store this as that's
         * only referenced by a pointer in the entry, which of course follows
         * the entry whenever the hash table is resized.  Since we only have a
         * pointer to the key here, we must perform a hash table lookup to
         * find the entry that the key belongs to.
         */
        entry = memoize_lookup(mstate->hashtable, NULL);
 
        /*
         * Sanity check that we found the entry belonging to the LRU list
         * item.  A misbehaving hash or equality function could cause the
         * entry not to be found or the wrong entry to be found.
         */
        if (unlikely(entry == NULL || entry->key != key))
            elog(ERROR, "could not find memoization table entry");
 
        /*
         * If we're being called to free memory while the cache is being
         * populated with new tuples, then we'd better take some care as we
         * could end up freeing the entry which 'specialkey' belongs to.
         * Generally callers will pass 'specialkey' as the key for the cache
         * entry which is currently being populated, so we must set
         * 'specialkey_intact' to false to inform the caller the specialkey
         * entry has been removed.
         */
        if (key == specialkey)
            specialkey_intact = false;
 
        /*
         * Finally remove the entry.  This will remove from the LRU list too.
         */
        remove_cache_entry(mstate, entry);
 
        evictions++;
 
        /* Exit if we've freed enough memory */
        if (mstate->mem_used <= mstate->mem_limit)
            break;
    }
 
    mstate->stats.cache_evictions += evictions; /* Update Stats */
 
    return specialkey_intact;

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

Referenced by cache_lookup(), and cache_store_tuple().

cache_store_tuple()

static bool cache_store_tuple ( MemoizeState *  mstate, TupleTableSlot *  slot  )

static

Definition at line 621 of file nodeMemoize.c.

{
    MemoizeTuple *tuple;
    MemoizeEntry *entry = mstate->entry;
    MemoryContext oldcontext;
 
    Assert(slot != NULL);
    Assert(entry != NULL);
 
    oldcontext = MemoryContextSwitchTo(mstate->tableContext);
 
    tuple = (MemoizeTuple *) palloc(sizeof(MemoizeTuple));
    tuple->mintuple = ExecCopySlotMinimalTuple(slot);
    tuple->next = NULL;
 
    /* Account for the memory we just consumed */
    mstate->mem_used += CACHE_TUPLE_BYTES(tuple);
 
    if (entry->tuplehead == NULL)
    {
        /*
         * This is the first tuple for this entry, so just point the list head
         * to it.
         */
        entry->tuplehead = tuple;
    }
    else
    {
        /* push this tuple onto the tail of the list */
        mstate->last_tuple->next = tuple;
    }
 
    mstate->last_tuple = tuple;
    MemoryContextSwitchTo(oldcontext);
 
    /*
     * If we've gone over our memory budget then free up some space in the
     * cache.
     */
    if (mstate->mem_used > mstate->mem_limit)
    {
        MemoizeKey *key = entry->key;
 
        if (!cache_reduce_memory(mstate, key))
            return false;
 
        /*
         * The process of removing entries from the cache may have caused the
         * code in simplehash.h to shuffle elements to earlier buckets in the
         * hash table.  If it has, we'll need to find the entry again by
         * performing a lookup.  Fortunately, we can detect if this has
         * happened by seeing if the entry is still in use and that the key
         * pointer matches our expected key.
         */
        if (entry->status != memoize_SH_IN_USE || entry->key != key)
        {
            /*
             * We need to repopulate the probeslot as lookups performed during
             * the cache evictions above will have stored some other key.
             */
            prepare_probe_slot(mstate, key);
 
            /* Re-find the entry */
            mstate->entry = entry = memoize_lookup(mstate->hashtable, NULL);
            Assert(entry != NULL);
        }
    }
 
    return true;

References Assert(), cache_reduce_memory(), CACHE_TUPLE_BYTES, MemoizeState::entry, ExecCopySlotMinimalTuple(), MemoizeState::hashtable, MemoizeEntry::key, sort-test::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().

entry_purge_tuples()

static void entry_purge_tuples ( MemoizeState *  mstate, MemoizeEntry *  entry  )

inlinestatic

Definition at line 342 of file nodeMemoize.c.

{
    MemoizeTuple *tuple = entry->tuplehead;
    uint64      freed_mem = 0;
 
    while (tuple != NULL)
    {
        MemoizeTuple *next = tuple->next;
 
        freed_mem += CACHE_TUPLE_BYTES(tuple);
 
        /* Free memory used for this tuple */
        pfree(tuple->mintuple);
        pfree(tuple);
 
        tuple = next;
    }
 
    entry->complete = false;
    entry->tuplehead = NULL;
 
    /* Update the memory accounting */
    mstate->mem_used -= freed_mem;

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

Referenced by ExecMemoize(), and remove_cache_entry().

ExecEndMemoize()

void ExecEndMemoize

(

MemoizeState *

node

)

Definition at line 1060 of file nodeMemoize.c.

{
#ifdef USE_ASSERT_CHECKING
    /* Validate the memory accounting code is correct in assert builds. */
    {
        int         count;
        uint64      mem = 0;
        memoize_iterator i;
        MemoizeEntry *entry;
 
        memoize_start_iterate(node->hashtable, &i);
 
        count = 0;
        while ((entry = memoize_iterate(node->hashtable, &i)) != NULL)
        {
            MemoizeTuple *tuple = entry->tuplehead;
 
            mem += EMPTY_ENTRY_MEMORY_BYTES(entry);
            while (tuple != NULL)
            {
                mem += CACHE_TUPLE_BYTES(tuple);
                tuple = tuple->next;
            }
            count++;
        }
 
        Assert(count == node->hashtable->members);
        Assert(mem == node->mem_used);
    }
#endif
 
    /*
     * When ending a parallel worker, copy the statistics gathered by the
     * worker back into shared memory so that it can be picked up by the main
     * process to report in EXPLAIN ANALYZE.
     */
    if (node->shared_info != NULL && IsParallelWorker())
    {
        MemoizeInstrumentation *si;
 
        /* Make mem_peak available for EXPLAIN */
        if (node->stats.mem_peak == 0)
            node->stats.mem_peak = node->mem_used;
 
        Assert(ParallelWorkerNumber <= node->shared_info->num_workers);
        si = &node->shared_info->sinstrument[ParallelWorkerNumber];
        memcpy(si, &node->stats, sizeof(MemoizeInstrumentation));
    }
 
    /* Remove the cache context */
    MemoryContextDelete(node->tableContext);
 
    /*
     * shut down the subplan
     */
    ExecEndNode(outerPlanState(node));

References Assert(), CACHE_TUPLE_BYTES, EMPTY_ENTRY_MEMORY_BYTES, ExecEndNode(), MemoizeState::hashtable, i, IsParallelWorker, MemoizeInstrumentation::mem_peak, MemoizeState::mem_used, MemoryContextDelete(), MemoizeTuple::next, outerPlanState, ParallelWorkerNumber, MemoizeState::shared_info, SharedMemoizeInfo::sinstrument, MemoizeState::stats, MemoizeState::tableContext, and MemoizeEntry::tuplehead.

Referenced by ExecEndNode().

ExecEstimateCacheEntryOverheadBytes()

double ExecEstimateCacheEntryOverheadBytes

(

double

ntuples

)

Definition at line 1151 of file nodeMemoize.c.

{
    return sizeof(MemoizeEntry) + sizeof(MemoizeKey) + sizeof(MemoizeTuple) *
        ntuples;

Referenced by cost_memoize_rescan().

ExecInitMemoize()

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

Definition at line 935 of file nodeMemoize.c.

{
    MemoizeState *mstate = makeNode(MemoizeState);
    Plan       *outerNode;
    int         i;
    int         nkeys;
    Oid        *eqfuncoids;
 
    /* check for unsupported flags */
    Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
 
    mstate->ss.ps.plan = (Plan *) node;
    mstate->ss.ps.state = estate;
    mstate->ss.ps.ExecProcNode = ExecMemoize;
 
    /*
     * Miscellaneous initialization
     *
     * create expression context for node
     */
    ExecAssignExprContext(estate, &mstate->ss.ps);
 
    outerNode = outerPlan(node);
    outerPlanState(mstate) = ExecInitNode(outerNode, estate, eflags);
 
    /*
     * Initialize return slot and type. No need to initialize projection info
     * because this node doesn't do projections.
     */
    ExecInitResultTupleSlotTL(&mstate->ss.ps, &TTSOpsMinimalTuple);
    mstate->ss.ps.ps_ProjInfo = NULL;
 
    /*
     * Initialize scan slot and type.
     */
    ExecCreateScanSlotFromOuterPlan(estate, &mstate->ss, &TTSOpsMinimalTuple);
 
    /*
     * Set the state machine to lookup the cache.  We won't find anything
     * until we cache something, but this saves a special case to create the
     * first entry.
     */
    mstate->mstatus = MEMO_CACHE_LOOKUP;
 
    mstate->nkeys = nkeys = node->numKeys;
    mstate->hashkeydesc = ExecTypeFromExprList(node->param_exprs);
    mstate->tableslot = MakeSingleTupleTableSlot(mstate->hashkeydesc,
                                                 &TTSOpsMinimalTuple);
    mstate->probeslot = MakeSingleTupleTableSlot(mstate->hashkeydesc,
                                                 &TTSOpsVirtual);
 
    mstate->param_exprs = (ExprState **) palloc(nkeys * sizeof(ExprState *));
    mstate->collations = node->collations;  /* Just point directly to the plan
                                             * data */
    mstate->hashfunctions = (FmgrInfo *) palloc(nkeys * sizeof(FmgrInfo));
 
    eqfuncoids = palloc(nkeys * sizeof(Oid));
 
    for (i = 0; i < nkeys; i++)
    {
        Oid         hashop = node->hashOperators[i];
        Oid         left_hashfn;
        Oid         right_hashfn;
        Expr       *param_expr = (Expr *) list_nth(node->param_exprs, i);
 
        if (!get_op_hash_functions(hashop, &left_hashfn, &right_hashfn))
            elog(ERROR, "could not find hash function for hash operator %u",
                 hashop);
 
        fmgr_info(left_hashfn, &mstate->hashfunctions[i]);
 
        mstate->param_exprs[i] = ExecInitExpr(param_expr, (PlanState *) mstate);
        eqfuncoids[i] = get_opcode(hashop);
    }
 
    mstate->cache_eq_expr = ExecBuildParamSetEqual(mstate->hashkeydesc,
                                                   &TTSOpsMinimalTuple,
                                                   &TTSOpsVirtual,
                                                   eqfuncoids,
                                                   node->collations,
                                                   node->param_exprs,
                                                   (PlanState *) mstate);
 
    pfree(eqfuncoids);
    mstate->mem_used = 0;
 
    /* Limit the total memory consumed by the cache to this */
    mstate->mem_limit = get_hash_memory_limit();
 
    /* A memory context dedicated for the cache */
    mstate->tableContext = AllocSetContextCreate(CurrentMemoryContext,
                                                 "MemoizeHashTable",
                                                 ALLOCSET_DEFAULT_SIZES);
 
    dlist_init(&mstate->lru_list);
    mstate->last_tuple = NULL;
    mstate->entry = NULL;
 
    /*
     * Mark if we can assume the cache entry is completed after we get the
     * first record for it.  Some callers might not call us again after
     * getting the first match. e.g. A join operator performing a unique join
     * is able to skip to the next outer tuple after getting the first
     * matching inner tuple.  In this case, the cache entry is complete after
     * getting the first tuple.  This allows us to mark it as so.
     */
    mstate->singlerow = node->singlerow;
    mstate->keyparamids = node->keyparamids;
 
    /*
     * Record if the cache keys should be compared bit by bit, or logically
     * using the type's hash equality operator
     */
    mstate->binary_mode = node->binary_mode;
 
    /* Zero the statistics counters */
    memset(&mstate->stats, 0, sizeof(MemoizeInstrumentation));
 
    /* Allocate and set up the actual cache */
    build_hash_table(mstate, node->est_entries);
 
    return mstate;

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), MemoizeState::binary_mode, Memoize::binary_mode, build_hash_table(), MemoizeState::cache_eq_expr, MemoizeState::collations, CurrentMemoryContext, dlist_init(), elog(), MemoizeState::entry, 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, i, MemoizeState::keyparamids, Memoize::keyparamids, MemoizeState::last_tuple, list_nth(), MemoizeState::lru_list, makeNode, MakeSingleTupleTableSlot(), MemoizeState::mem_limit, MemoizeState::mem_used, MEMO_CACHE_LOOKUP, MemoizeState::mstatus, MemoizeState::nkeys, Memoize::numKeys, outerPlan, outerPlanState, palloc(), MemoizeState::param_exprs, Memoize::param_exprs, pfree(), PlanState::plan, MemoizeState::probeslot, ScanState::ps, PlanState::ps_ProjInfo, MemoizeState::singlerow, Memoize::singlerow, MemoizeState::ss, PlanState::state, MemoizeState::stats, MemoizeState::tableContext, MemoizeState::tableslot, TTSOpsMinimalTuple, and TTSOpsVirtual.

Referenced by ExecInitNode().

ExecMemoize()

static TupleTableSlot* ExecMemoize ( PlanState *  pstate )

static

Definition at line 693 of file nodeMemoize.c.

{
    MemoizeState *node = castNode(MemoizeState, pstate);
    PlanState  *outerNode;
    TupleTableSlot *slot;
 
    switch (node->mstatus)
    {
        case MEMO_CACHE_LOOKUP:
            {
                MemoizeEntry *entry;
                TupleTableSlot *outerslot;
                bool        found;
 
                Assert(node->entry == NULL);
 
                /*
                 * We're only ever in this state for the first call of the
                 * scan.  Here we have a look to see if we've already seen the
                 * current parameters before and if we have already cached a
                 * complete set of records that the outer plan will return for
                 * these parameters.
                 *
                 * When we find a valid cache entry, we'll return the first
                 * tuple from it. If not found, we'll create a cache entry and
                 * then try to fetch a tuple from the outer scan.  If we find
                 * one there, we'll try to cache it.
                 */
 
                /* see if we've got anything cached for the current parameters */
                entry = cache_lookup(node, &found);
 
                if (found && entry->complete)
                {
                    node->stats.cache_hits += 1;    /* stats update */
 
                    /*
                     * Set last_tuple and entry so that the state
                     * MEMO_CACHE_FETCH_NEXT_TUPLE can easily find the next
                     * tuple for these parameters.
                     */
                    node->last_tuple = entry->tuplehead;
                    node->entry = entry;
 
                    /* Fetch the first cached tuple, if there is one */
                    if (entry->tuplehead)
                    {
                        node->mstatus = MEMO_CACHE_FETCH_NEXT_TUPLE;
 
                        slot = node->ss.ps.ps_ResultTupleSlot;
                        ExecStoreMinimalTuple(entry->tuplehead->mintuple,
                                              slot, false);
 
                        return slot;
                    }
 
                    /* The cache entry is void of any tuples. */
                    node->mstatus = MEMO_END_OF_SCAN;
                    return NULL;
                }
 
                /* Handle cache miss */
                node->stats.cache_misses += 1;  /* stats update */
 
                if (found)
                {
                    /*
                     * A cache entry was found, but the scan for that entry
                     * did not run to completion.  We'll just remove all
                     * tuples and start again.  It might be tempting to
                     * continue where we left off, but there's no guarantee
                     * the outer node will produce the tuples in the same
                     * order as it did last time.
                     */
                    entry_purge_tuples(node, entry);
                }
 
                /* Scan the outer node for a tuple to cache */
                outerNode = outerPlanState(node);
                outerslot = ExecProcNode(outerNode);
                if (TupIsNull(outerslot))
                {
                    /*
                     * cache_lookup may have returned NULL due to failure to
                     * free enough cache space, so ensure we don't do anything
                     * here that assumes it worked. There's no need to go into
                     * bypass mode here as we're setting mstatus to end of
                     * scan.
                     */
                    if (likely(entry))
                        entry->complete = true;
 
                    node->mstatus = MEMO_END_OF_SCAN;
                    return NULL;
                }
 
                node->entry = entry;
 
                /*
                 * If we failed to create the entry or failed to store the
                 * tuple in the entry, then go into bypass mode.
                 */
                if (unlikely(entry == NULL ||
                             !cache_store_tuple(node, outerslot)))
                {
                    node->stats.cache_overflows += 1;   /* stats update */
 
                    node->mstatus = MEMO_CACHE_BYPASS_MODE;
 
                    /*
                     * No need to clear out last_tuple as we'll stay in bypass
                     * mode until the end of the scan.
                     */
                }
                else
                {
                    /*
                     * If we only expect a single row from this scan then we
                     * can mark that we're not expecting more.  This allows
                     * cache lookups to work even when the scan has not been
                     * executed to completion.
                     */
                    entry->complete = node->singlerow;
                    node->mstatus = MEMO_FILLING_CACHE;
                }
 
                slot = node->ss.ps.ps_ResultTupleSlot;
                ExecCopySlot(slot, outerslot);
                return slot;
            }
 
        case MEMO_CACHE_FETCH_NEXT_TUPLE:
            {
                /* We shouldn't be in this state if these are not set */
                Assert(node->entry != NULL);
                Assert(node->last_tuple != NULL);
 
                /* Skip to the next tuple to output */
                node->last_tuple = node->last_tuple->next;
 
                /* No more tuples in the cache */
                if (node->last_tuple == NULL)
                {
                    node->mstatus = MEMO_END_OF_SCAN;
                    return NULL;
                }
 
                slot = node->ss.ps.ps_ResultTupleSlot;
                ExecStoreMinimalTuple(node->last_tuple->mintuple, slot,
                                      false);
 
                return slot;
            }
 
        case MEMO_FILLING_CACHE:
            {
                TupleTableSlot *outerslot;
                MemoizeEntry *entry = node->entry;
 
                /* entry should already have been set by MEMO_CACHE_LOOKUP */
                Assert(entry != NULL);
 
                /*
                 * When in the MEMO_FILLING_CACHE state, we've just had a
                 * cache miss and are populating the cache with the current
                 * scan tuples.
                 */
                outerNode = outerPlanState(node);
                outerslot = ExecProcNode(outerNode);
                if (TupIsNull(outerslot))
                {
                    /* No more tuples.  Mark it as complete */
                    entry->complete = true;
                    node->mstatus = MEMO_END_OF_SCAN;
                    return NULL;
                }
 
                /*
                 * Validate if the planner properly set the singlerow flag. It
                 * should only set that if each cache entry can, at most,
                 * return 1 row.
                 */
                if (unlikely(entry->complete))
                    elog(ERROR, "cache entry already complete");
 
                /* Record the tuple in the current cache entry */
                if (unlikely(!cache_store_tuple(node, outerslot)))
                {
                    /* Couldn't store it?  Handle overflow */
                    node->stats.cache_overflows += 1;   /* stats update */
 
                    node->mstatus = MEMO_CACHE_BYPASS_MODE;
 
                    /*
                     * No need to clear out entry or last_tuple as we'll stay
                     * in bypass mode until the end of the scan.
                     */
                }
 
                slot = node->ss.ps.ps_ResultTupleSlot;
                ExecCopySlot(slot, outerslot);
                return slot;
            }
 
        case MEMO_CACHE_BYPASS_MODE:
            {
                TupleTableSlot *outerslot;
 
                /*
                 * When in bypass mode we just continue to read tuples without
                 * caching.  We need to wait until the next rescan before we
                 * can come out of this mode.
                 */
                outerNode = outerPlanState(node);
                outerslot = ExecProcNode(outerNode);
                if (TupIsNull(outerslot))
                {
                    node->mstatus = MEMO_END_OF_SCAN;
                    return NULL;
                }
 
                slot = node->ss.ps.ps_ResultTupleSlot;
                ExecCopySlot(slot, outerslot);
                return slot;
            }
 
        case MEMO_END_OF_SCAN:
 
            /*
             * We've already returned NULL for this scan, but just in case
             * something calls us again by mistake.
             */
            return NULL;
 
        default:
            elog(ERROR, "unrecognized memoize state: %d",
                 (int) node->mstatus);
            return NULL;
    }                           /* switch */

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().

ExecMemoizeEstimate()

void ExecMemoizeEstimate	(	MemoizeState *	node,
		ParallelContext *	pcxt
	)

Definition at line 1169 of file nodeMemoize.c.

{
    Size        size;
 
    /* don't need this if not instrumenting or no workers */
    if (!node->ss.ps.instrument || pcxt->nworkers == 0)
        return;
 
    size = mul_size(pcxt->nworkers, sizeof(MemoizeInstrumentation));
    size = add_size(size, offsetof(SharedMemoizeInfo, sinstrument));
    shm_toc_estimate_chunk(&pcxt->estimator, size);
    shm_toc_estimate_keys(&pcxt->estimator, 1);

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

Referenced by ExecParallelEstimate().

ExecMemoizeInitializeDSM()

void ExecMemoizeInitializeDSM	(	MemoizeState *	node,
		ParallelContext *	pcxt
	)

Definition at line 1190 of file nodeMemoize.c.

{
    Size        size;
 
    /* don't need this if not instrumenting or no workers */
    if (!node->ss.ps.instrument || pcxt->nworkers == 0)
        return;
 
    size = offsetof(SharedMemoizeInfo, sinstrument)
        + pcxt->nworkers * sizeof(MemoizeInstrumentation);
    node->shared_info = shm_toc_allocate(pcxt->toc, size);
    /* ensure any unfilled slots will contain zeroes */
    memset(node->shared_info, 0, size);
    node->shared_info->num_workers = pcxt->nworkers;
    shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id,
                   node->shared_info);

References PlanState::instrument, SharedMemoizeInfo::num_workers, ParallelContext::nworkers, 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().

ExecMemoizeInitializeWorker()

void ExecMemoizeInitializeWorker	(	MemoizeState *	node,
		ParallelWorkerContext *	pwcxt
	)

Definition at line 1215 of file nodeMemoize.c.

{
    node->shared_info =
        shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, true);

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

Referenced by ExecParallelInitializeWorker().

ExecMemoizeRetrieveInstrumentation()

void ExecMemoizeRetrieveInstrumentation

(

MemoizeState *

node

)

Definition at line 1228 of file nodeMemoize.c.

{
    Size        size;
    SharedMemoizeInfo *si;
 
    if (node->shared_info == NULL)
        return;
 
    size = offsetof(SharedMemoizeInfo, sinstrument)
        + node->shared_info->num_workers * sizeof(MemoizeInstrumentation);
    si = palloc(size);
    memcpy(si, node->shared_info, size);
    node->shared_info = si;

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

Referenced by ExecParallelRetrieveInstrumentation().

ExecReScanMemoize()

void ExecReScanMemoize

(

MemoizeState *

node

)

Definition at line 1119 of file nodeMemoize.c.

{
    PlanState  *outerPlan = outerPlanState(node);
 
    /* Mark that we must lookup the cache for a new set of parameters */
    node->mstatus = MEMO_CACHE_LOOKUP;
 
    /* nullify pointers used for the last scan */
    node->entry = NULL;
    node->last_tuple = NULL;
 
    /*
     * if chgParam of subnode is not null then plan will be re-scanned by
     * first ExecProcNode.
     */
    if (outerPlan->chgParam == NULL)
        ExecReScan(outerPlan);
 
    /*
     * Purge the entire cache if a parameter changed that is not part of the
     * cache key.
     */
    if (bms_nonempty_difference(outerPlan->chgParam, node->keyparamids))
        cache_purge_all(node);

References bms_nonempty_difference(), cache_purge_all(), MemoizeState::entry, ExecReScan(), MemoizeState::keyparamids, MemoizeState::last_tuple, MEMO_CACHE_LOOKUP, MemoizeState::mstatus, outerPlan, and outerPlanState.

Referenced by ExecReScan().

MemoizeHash_equal()

static bool MemoizeHash_equal ( struct memoize_hash *  tb, const MemoizeKey *  key1, const MemoizeKey *  key2  )

static

Definition at line 221 of file nodeMemoize.c.

{
    MemoizeState *mstate = (MemoizeState *) tb->private_data;
    ExprContext *econtext = mstate->ss.ps.ps_ExprContext;
    TupleTableSlot *tslot = mstate->tableslot;
    TupleTableSlot *pslot = mstate->probeslot;
 
    /* probeslot should have already been prepared by prepare_probe_slot() */
    ExecStoreMinimalTuple(key1->params, tslot, false);
 
    if (mstate->binary_mode)
    {
        MemoryContext oldcontext;
        int         numkeys = mstate->nkeys;
        bool        match = true;
 
        oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 
        slot_getallattrs(tslot);
        slot_getallattrs(pslot);
 
        for (int i = 0; i < numkeys; i++)
        {
            FormData_pg_attribute *attr;
 
            if (tslot->tts_isnull[i] != pslot->tts_isnull[i])
            {
                match = false;
                break;
            }
 
            /* both NULL? they're equal */
            if (tslot->tts_isnull[i])
                continue;
 
            /* perform binary comparison on the two datums */
            attr = &tslot->tts_tupleDescriptor->attrs[i];
            if (!datum_image_eq(tslot->tts_values[i], pslot->tts_values[i],
                                attr->attbyval, attr->attlen))
            {
                match = false;
                break;
            }
        }
 
        ResetExprContext(econtext);
        MemoryContextSwitchTo(oldcontext);
        return match;
    }
    else
    {
        econtext->ecxt_innertuple = tslot;
        econtext->ecxt_outertuple = pslot;
        return ExecQualAndReset(mstate->cache_eq_expr, econtext);
    }

References MemoizeState::binary_mode, MemoizeState::cache_eq_expr, datum_image_eq(), ExecQualAndReset(), ExecStoreMinimalTuple(), FormData_pg_attribute, i, MemoryContextSwitchTo(), MemoizeState::nkeys, MemoizeKey::params, MemoizeState::probeslot, ScanState::ps, PlanState::ps_ExprContext, ResetExprContext, slot_getallattrs(), MemoizeState::ss, and MemoizeState::tableslot.

MemoizeHash_hash()

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

static

Definition at line 157 of file nodeMemoize.c.

{
    MemoizeState *mstate = (MemoizeState *) tb->private_data;
    ExprContext *econtext = mstate->ss.ps.ps_ExprContext;
    MemoryContext oldcontext;
    TupleTableSlot *pslot = mstate->probeslot;
    uint32      hashkey = 0;
    int         numkeys = mstate->nkeys;
 
    oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 
    if (mstate->binary_mode)
    {
        for (int i = 0; i < numkeys; i++)
        {
            /* combine successive hashkeys by rotating */
            hashkey = pg_rotate_left32(hashkey, 1);
 
            if (!pslot->tts_isnull[i])  /* treat nulls as having hash key 0 */
            {
                FormData_pg_attribute *attr;
                uint32      hkey;
 
                attr = &pslot->tts_tupleDescriptor->attrs[i];
 
                hkey = datum_image_hash(pslot->tts_values[i], attr->attbyval, attr->attlen);
 
                hashkey ^= hkey;
            }
        }
    }
    else
    {
        FmgrInfo   *hashfunctions = mstate->hashfunctions;
        Oid        *collations = mstate->collations;
 
        for (int i = 0; i < numkeys; i++)
        {
            /* combine successive hashkeys by rotating */
            hashkey = pg_rotate_left32(hashkey, 1);
 
            if (!pslot->tts_isnull[i])  /* treat nulls as having hash key 0 */
            {
                uint32      hkey;
 
                hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
                                                        collations[i], pslot->tts_values[i]));
                hashkey ^= hkey;
            }
        }
    }
 
    ResetExprContext(econtext);
    MemoryContextSwitchTo(oldcontext);
    return murmurhash32(hashkey);

References MemoizeState::binary_mode, MemoizeState::collations, datum_image_hash(), DatumGetUInt32(), FormData_pg_attribute, FunctionCall1Coll(), MemoizeState::hashfunctions, i, MemoryContextSwitchTo(), murmurhash32(), MemoizeState::nkeys, pg_rotate_left32(), MemoizeState::probeslot, ScanState::ps, PlanState::ps_ExprContext, ResetExprContext, and MemoizeState::ss.

prepare_probe_slot()

static void prepare_probe_slot ( MemoizeState *  mstate, MemoizeKey *  key  )

inlinestatic

Definition at line 300 of file nodeMemoize.c.

{
    TupleTableSlot *pslot = mstate->probeslot;
    TupleTableSlot *tslot = mstate->tableslot;
    int         numKeys = mstate->nkeys;
 
    ExecClearTuple(pslot);
 
    if (key == NULL)
    {
        ExprContext *econtext = mstate->ss.ps.ps_ExprContext;
        MemoryContext oldcontext;
 
        oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
 
        /* Set the probeslot's values based on the current parameter values */
        for (int i = 0; i < numKeys; i++)
            pslot->tts_values[i] = ExecEvalExpr(mstate->param_exprs[i],
                                                econtext,
                                                &pslot->tts_isnull[i]);
 
        MemoryContextSwitchTo(oldcontext);
    }
    else
    {
        /* Process the key's MinimalTuple and store the values in probeslot */
        ExecStoreMinimalTuple(key->params, tslot, false);
        slot_getallattrs(tslot);
        memcpy(pslot->tts_values, tslot->tts_values, sizeof(Datum) * numKeys);
        memcpy(pslot->tts_isnull, tslot->tts_isnull, sizeof(bool) * numKeys);
    }
 
    ExecStoreVirtualTuple(pslot);

References ExprContext::ecxt_per_tuple_memory, ExecClearTuple(), ExecEvalExpr(), ExecStoreMinimalTuple(), ExecStoreVirtualTuple(), i, sort-test::key, MemoryContextSwitchTo(), MemoizeState::nkeys, MemoizeState::param_exprs, 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().

remove_cache_entry()

static void remove_cache_entry ( MemoizeState *  mstate, MemoizeEntry *  entry  )

static

Definition at line 372 of file nodeMemoize.c.

{
    MemoizeKey *key = entry->key;
 
    dlist_delete(&entry->key->lru_node);
 
    /* Remove all of the tuples from this entry */
    entry_purge_tuples(mstate, entry);
 
    /*
     * Update memory accounting. entry_purge_tuples should have already
     * subtracted the memory used for each cached tuple.  Here we just update
     * the amount used by the entry itself.
     */
    mstate->mem_used -= EMPTY_ENTRY_MEMORY_BYTES(entry);
 
    /* Remove the entry from the cache */
    memoize_delete_item(mstate->hashtable, entry);
 
    pfree(key->params);
    pfree(key);

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

Referenced by cache_reduce_memory().