8000 Flush Memoize cache when non-key parameters change, take 2 · postgres/postgres@411137a · GitHub
[go: up one dir, main page]
Skip to content

Commit 411137a

Browse files
david-rowleydavid-rowley
committed
Flush Memoize cache when non-key parameters change, take 2
It's possible that a subplan below a Memoize node contains a parameter from above the Memoize node. If this parameter changes then cache entries may become out-dated due to the new parameter value. Previously Memoize was mistakenly not aware of this. We fix this here by flushing the cache whenever a parameter that's not part of the cache key changes. Bug: #17213 Reported by: Elvis Pranskevichus Author: David Rowley Discussion: https://postgr.es/m/17213-988ed34b225a2862@postgresql.org Backpatch-through: 14, where Memoize was added
1 parent fb5961f commit 411137a

File tree

12 files changed

+145
-3
lines changed
  • plannodes.h
  • optimizer
  • test/regress

    • 12 files changed

    +145
    -3
    lines changed

    ‎src/backend/executor/nodeMemoize.c

    Lines changed: 38 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -367,6 +367,37 @@ remove_cache_entry(MemoizeState *mstate, MemoizeEntry *entry)
    367367
    pfree(key);
    368368
    }
    369369

    370+
    /*
    371+
    * cache_purge_all
    372+
    * Remove all items from the cache
    373+
    */
    374+
    static void
    375+
    cache_purge_all(MemoizeState *mstate)
    376+
    {
    377+
    uint64 evictions = mstate->hashtable->members;
    378+
    PlanState *pstate = (PlanState *) mstate;
    379+
    380+
    /*
    381+
    * Likely the most efficient way to remove all items is to just reset the
    382+
    * memory context for the cache and then rebuild a fresh hash table. This
    383+
    * saves having to remove each item one by one and pfree each cached tuple
    384+
    */
    385+
    MemoryContextReset(mstate->tableContext);
    386+
    387+
    /* Make the hash table the same size as the original size */
    388+
    build_hash_table(mstate, ((Memoize *) pstate->plan)->est_entries);
    389+
    390+
    /* reset the LRU list */
    391+
    dlist_init(&mstate->lru_list);
    392+
    mstate->last_tuple = NULL;
    393+
    mstate->entry = NULL;
    394+
    395+
    mstate->mem_used = 0;
    396+
    397+
    /* XXX should we add something new to track these purges? */
    398+
    mstate->stats.cache_evictions += evictions; /* Update Stats */
    399+
    }
    400+
    370401
    /*
    371402
    * cache_reduce_memory
    372403
    * Evict older and less recently used items from the cache in order to
    @@ -979,6 +1010,7 @@ ExecInitMemoize(Memoize *node, EState *estate, int eflags)
    9791010
    * getting the first tuple. This allows us to mark it as so.
    9801011
    */
    9811012
    mstate->singlerow = node->singlerow;
    1013+
    mstate->keyparamids = node->keyparamids;
    9821014

    9831015
    /*
    9841016
    * Record if the cache keys should be compared bit by bit, or logically
    @@ -1082,6 +1114,12 @@ ExecReScanMemoize(MemoizeState *node)
    10821114
    if (outerPlan->chgParam == NULL)
    10831115
    ExecReScan(outerPlan);
    10841116

    1117+
    /*
    1118+
    * Purge the entire cache if a parameter changed that is not part of the
    1119+
    * cache key.
    1120+
    */
    1121+
    if (bms_nonempty_difference(outerPlan->chgParam, node->keyparamids))
    1122+
    cache_purge_all(node);
    10851123
    }
    10861124

    10871125
    /*

    ‎src/backend/nodes/bitmapset.c

    Lines changed: 2 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -540,6 +540,8 @@ bms_overlap_list(const Bitmapset *a, const List *b)
    540540

    541541
    /*
    542542
    * bms_nonempty_difference - do sets have a nonempty difference?
    543+
    *
    544+
    * i.e F438 ., are any members set in 'a' that are not also set in 'b'.
    543545
    */
    544546
    bool
    545547
    bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)

    ‎src/backend/nodes/copyfuncs.c

    Lines changed: 1 addition & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -973,6 +973,7 @@ _copyMemoize(const Memoize *from)
    973973
    COPY_SCALAR_FIELD(singlerow);
    974974
    COPY_SCALAR_FIELD(binary_mode);
    975975
    COPY_SCALAR_FIELD(est_entries);
    976+
    COPY_BITMAPSET_FIELD(keyparamids);
    976977

    977978
    return newnode;
    978979
    }

    ‎src/backend/nodes/outfuncs.c

    Lines changed: 1 addition & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -868,6 +868,7 @@ _outMemoize(StringInfo str, const Memoize *node)
    868868
    WRITE_BOOL_FIELD(singlerow);
    869869
    WRITE_BOOL_FIELD(binary_mode);
    870870
    WRITE_UINT_FIELD(est_entries);
    871+
    WRITE_BITMAPSET_FIELD(keyparamids);
    871872
    }
    872873

    873874
    static void

    ‎src/backend/nodes/readfuncs.c

    Lines changed: 1 addition & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -2232,6 +2232,7 @@ _readMemoize(void)
    22322232
    READ_BOOL_FIELD(singlerow);
    22332233
    READ_BOOL_FIELD(binary_mode);
    22342234
    READ_UINT_FIELD(est_entries);
    2235+
    READ_BITMAPSET_FIELD(keyparamids);
    22352236

    22362237
    READ_DONE();
    22372238
    }

    ‎src/backend/optimizer/plan/createplan.c

    Lines changed: 7 additions & 3 deletions
    Original file line numberDiff line numberDiff line change
    @@ -280,7 +280,7 @@ static Material *make_material(Plan *lefttree);
    280280
    static Memoize *make_memoize(Plan *lefttree, Oid *hashoperators,
    281281
    Oid *collations, List *param_exprs,
    282282
    bool singlerow, bool binary_mode,
    283-
    uint32 est_entries);
    283+
    uint32 est_entries, Bitmapset *keyparamids);
    284284
    static WindowAgg *make_windowagg(List *tlist, Index winref,
    285285
    int partNumCols, AttrNumber *partColIdx, Oid *partOperators, Oid *partCollations,
    286286
    int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations,
    @@ -1586,6 +1586,7 @@ static Memoize *
    15861586
    create_memoize_plan(PlannerInfo *root, MemoizePath *best_path, int flags)
    15871587
    {
    15881588
    Memoize *plan;
    1589+
    Bitmapset *keyparamids;
    15891590
    Plan *subplan;
    15901591
    Oid *operators;
    15911592
    Oid *collations;
    @@ -1617,9 +1618,11 @@ create_memoize_plan(PlannerInfo *root, MemoizePath *best_path, int flags)
    16171618
    i++;
    16181619
    }
    16191620

    1621+
    keyparamids = pull_paramids((Expr *) param_exprs);
    1622+
    16201623
    plan = make_memoize(subplan, operators, collations, param_exprs,
    16211624
    best_path->singlerow, best_path->binary_mode,
    1622-
    best_path->est_entries);
    1625+
    best_path->est_entries, keyparamids);
    16231626

    16241627
    copy_generic_path_info(&plan->plan, (Path *) best_path);
    16251628

    @@ -6420,7 +6423,7 @@ materialize_finished_plan(Plan *subplan)
    64206423
    static Memoize *
    64216424
    make_memoize(Plan *lefttree, Oid *hashoperators, Oid *collations,
    64226425
    List *param_exprs, bool singlerow, bool binary_mode,
    6423-
    uint32 est_entries)
    6426+
    uint32 est_entries, Bitmapset *keyparamids)
    64246427
    {
    64256428
    Memoize *node = makeNode(Memoize);
    64266429
    Plan *plan = &node->plan;
    @@ -6437,6 +6440,7 @@ make_memoize(Plan *lefttree, Oid *hashoperators, Oid *collations,
    64376440
    node->singlerow = singlerow;
    64386441
    node->binary_mode = binary_mode;
    64396442
    node->est_entries = est_entries;
    6443+
    node->keyparamids = keyparamids;
    64406444

    64416445
    return node;
    64426446
    }

    ‎src/backend/optimizer/util/clauses.c

    Lines changed: 31 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -152,6 +152,7 @@ static Query *substitute_actual_srf_parameters(Query *expr,
    152152
    int nargs, List *args);
    153153
    static Node *substitute_actual_srf_parameters_mutator(Node *node,
    154154
    substitute_actual_srf_parameters_context *context);
    155+
    static bool pull_paramids_walker(Node *node, Bitmapset **context);
    155156

    156157

    157158
    /*****************************************************************************
    @@ -5214,3 +5215,33 @@ substitute_actual_srf_parameters_mutator(Node *node,
    52145215
    substitute_actual_srf_parameters_mutator,
    52155216
    (void *) context);
    52165217
    }
    5218+
    5219+
    /*
    5220+
    * pull_paramids
    5221+
    * Returns a Bitmapset containing the paramids of all Params in 'expr'.
    5222+
    */
    5223+
    Bitmapset *
    5224+
    pull_paramids(Expr *expr)
    5225+
    {
    5226+
    Bitmapset *result = NULL;
    5227+
    5228+
    (void) pull_paramids_walker((Node *) expr, &result);
    5229+
    5230+
    return result;
    5231+
    }
    5232+
    5233+
    static bool
    5234+
    pull_paramids_walker(Node *node, Bitmapset **context)
    5235+
    {
    5236+
    if (node == NULL)
    5237+
    return false;
    5238+
    if (IsA(node, Param))
    5239+
    {
    5240+
    Param *param = (Param *)node;
    5241+
    5242+
    *context = bms_add_member(*context, param->paramid);
    5243+
    return false;
    5244+
    }
    5245+
    return expression_tree_walker(node, pull_paramids_walker,
    5246+
    (void *) context);
    5247+
    }

    ‎src/include/nodes/execnodes.h

    Lines changed: 2 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -2113,6 +2113,8 @@ typedef struct MemoizeState
    21132113
    * by bit, false when using hash equality ops */
    21142114
    MemoizeInstrumentation stats; /* execution statistics */
    21152115
    SharedMemoizeInfo *shared_info; /* statistics for parallel workers */
    2116+
    Bitmapset *keyparamids; /* Param->paramids of expressions belonging to
    2117+
    * param_exprs */
    21162118
    } MemoizeState;
    21172119

    21182120
    /* ----------------

    ‎src/include/nodes/plannodes.h

    Lines changed: 1 addition & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -804,6 +804,7 @@ typedef struct Memoize
    804804
    uint32 est_entries; /* The maximum number of entries that the
    805805
    * planner expects will fit in the cache, or 0
    806806
    * if unknown */
    807+
    Bitmapset *keyparamids; /* paramids from param_exprs */
    807808
    } Memoize;
    808809

    809810
    /* ----------------

    ‎src/include/optimizer/clauses.h

    Lines changed: 2 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -53,4 +53,6 @@ extern void CommuteOpExpr(OpExpr *clause);
    5353
    extern Query *inline_set_returning_function(PlannerInfo *root,
    5454
    RangeTblEntry *rte);
    5555

    56+
    extern Bitmapset *pull_paramids(Expr *expr);
    57+
    5658
    #endif /* CLAUSES_H */

    ‎src/test/regress/expected/memoize.out

    Lines changed: 39 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -196,6 +196,45 @@ SELECT * FROM strtest s1 INNER JOIN strtest s2 ON s1.t >= s2.t;', false);
    196196
    (8 rows)
    197197

    198198
    DROP TABLE strtest;
    199+
    -- Exercise Memoize code that flushes the cache when a parameter changes which
    200+
    -- is not part of the cache key.
    201+
    -- Ensure we get a Memoize plan
    202+
    EXPLAIN (COSTS OFF)
    203+
    SELECT unique1 FROM tenk1 t0
    204+
    WHERE unique1 < 3
    205+
    AND EXISTS (
    206+
    SELECT 1 FROM tenk1 t1
    207+
    INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred
    208+
    WHERE t0.ten = t1.twenty AND t0.two <> t2.four OFFSET 0);
    209+
    QUERY PLAN
    210+
    ----------------------------------------------------------------
    211+
    Index Scan using tenk1_unique1 on tenk1 t0
    212+
    Index Cond: (unique1 < 3)
    213+
    Filter: (SubPlan 1)
    214+
    SubPlan 1
    215+
    -> Nested Loop
    216+
    -> Index Scan using tenk1_hundred on tenk1 t2
    217+
    Filter: (t0.two <> four)
    218+
    -> Memoize
    219+
    Cache Key: t2.hundred
    220+
    Cache Mode: logical
    221+
    -> Index Scan using tenk1_unique1 on tenk1 t1
    222+
    Index Cond: (unique1 = t2.hundred)
    223+
    Filter: (t0.ten = twenty)
    224+
    (13 rows)
    225+
    226+
    -- Ensure the above query returns the correct result
    227+
    SELECT unique1 FROM tenk1 t0
    228+
    WHERE unique1 < 3
    229+
    AND EXISTS (
    230+
    SELECT 1 FROM tenk1 t1
    231+
    INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred
    232+
    WHERE t0.ten = t1.twenty AND t0.two <> t2.four OFFSET 0);
    233+
    unique1
    234+
    ---------
    235+
    2
    236+
    (1 row)
    237+
    199238
    RESET enable_seqscan;
    200239
    RESET enable_mergejoin;
    201240
    RESET work_mem;

    ‎src/test/regress/sql/memoize.sql

    Lines changed: 20 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -103,6 +103,26 @@ SELECT * FROM strtest s1 INNER JOIN strtest s2 ON s1.t >= s2.t;', false);
    103103

    104104
    DROP TABLE strtest;
    105105

    106+
    -- Exercise Memoize code that flushes the cache when a parameter changes which
    107+
    -- is not part of the cache key.
    108+
    109+
    -- Ensure we get a Memoize plan
    110+
    EXPLAIN (COSTS OFF)
    111+
    SELECT unique1 FROM tenk1 t0
    112+
    WHERE unique1 < 3
    113+
    AND EXISTS (
    114+
    SELECT 1 FROM tenk1 t1
    115+
    INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred
    116+
    WHERE t0.ten = t1.twenty AND t0.two <> t2.four OFFSET 0);
    117+
    118+
    -- Ensure the above query returns the correct result
    119+
    SELECT unique1 FROM tenk1 t0
    120+
    WHERE unique1 < 3
    121+
    AND EXISTS (
    122+
    SELECT 1 FROM tenk1 t1
    123+
    INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred
    124+
    WHERE t0.ten = t1.twenty AND t0.two <> t2.four OFFSET 0);
    125+
    106126
    RESET enable_seqscan;
    107127
    RESET enable_mergejoin;
    108128
    RESET work_mem;

    0 commit comments

    Comments
     (0)
    0