LCOV - code coverage report
Current view: top level - src/backend/executor - execGrouping.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 97 103 94.2 %
Date: 2019-06-18 07:06:57 Functions: 8 9 88.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * execGrouping.c
       4             :  *    executor utility routines for grouping, hashing, and aggregation
       5             :  *
       6             :  * Note: we currently assume that equality and hashing functions are not
       7             :  * collation-sensitive, so the code in this file has no support for passing
       8             :  * collation settings through from callers.  That may have to change someday.
       9             :  *
      10             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
      11             :  * Portions Copyright (c) 1994, Regents of the University of California
      12             :  *
      13             :  *
      14             :  * IDENTIFICATION
      15             :  *    src/backend/executor/execGrouping.c
      16             :  *
      17             :  *-------------------------------------------------------------------------
      18             :  */
      19             : #include "postgres.h"
      20             : 
      21             : #include "access/parallel.h"
      22             : #include "executor/executor.h"
      23             : #include "miscadmin.h"
      24             : #include "utils/lsyscache.h"
      25             : #include "utils/hashutils.h"
      26             : #include "utils/memutils.h"
      27             : 
      28             : static uint32 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple);
      29             : static int  TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2);
      30             : 
      31             : /*
      32             :  * Define parameters for tuple hash table code generation. The interface is
      33             :  * *also* declared in execnodes.h (to generate the types, which are externally
      34             :  * visible).
      35             :  */
      36             : #define SH_PREFIX tuplehash
      37             : #define SH_ELEMENT_TYPE TupleHashEntryData
      38             : #define SH_KEY_TYPE MinimalTuple
      39             : #define SH_KEY firstTuple
      40             : #define SH_HASH_KEY(tb, key) TupleHashTableHash(tb, key)
      41             : #define SH_EQUAL(tb, a, b) TupleHashTableMatch(tb, a, b) == 0
      42             : #define SH_SCOPE extern
      43             : #define SH_STORE_HASH
      44             : #define SH_GET_HASH(tb, a) a->hash
      45             : #define SH_DEFINE
      46             : #include "lib/simplehash.h"
      47             : 
      48             : 
      49             : /*****************************************************************************
      50             :  *      Utility routines for grouping tuples together
      51             :  *****************************************************************************/
      52             : 
      53             : /*
      54             :  * execTuplesMatchPrepare
      55             :  *      Build expression that can be evaluated using ExecQual(), returning
      56             :  *      whether an ExprContext's inner/outer tuples are NOT DISTINCT
      57             :  */
      58             : ExprState *
      59        3260 : execTuplesMatchPrepare(TupleDesc desc,
      60             :                        int numCols,
      61             :                        const AttrNumber *keyColIdx,
      62             :                        const Oid *eqOperators,
      63             :                        const Oid *collations,
      64             :                        PlanState *parent)
      65             : {
      66        3260 :     Oid        *eqFunctions = (Oid *) palloc(numCols * sizeof(Oid));
      67             :     int         i;
      68             :     ExprState  *expr;
      69             : 
      70        3260 :     if (numCols == 0)
      71          34 :         return NULL;
      72             : 
      73             :     /* lookup equality functions */
      74        7428 :     for (i = 0; i < numCols; i++)
      75        4202 :         eqFunctions[i] = get_opcode(eqOperators[i]);
      76             : 
      77             :     /* build actual expression */
      78        3226 :     expr = ExecBuildGroupingEqual(desc, desc, NULL, NULL,
      79             :                                   numCols, keyColIdx, eqFunctions, collations,
      80             :                                   parent);
      81             : 
      82        3226 :     return expr;
      83             : }
      84             : 
      85             : /*
      86             :  * execTuplesHashPrepare
      87             :  *      Look up the equality and hashing functions needed for a TupleHashTable.
      88             :  *
      89             :  * This is similar to execTuplesMatchPrepare, but we also need to find the
      90             :  * hash functions associated with the equality operators.  *eqFunctions and
      91             :  * *hashFunctions receive the palloc'd result arrays.
      92             :  *
      93             :  * Note: we expect that the given operators are not cross-type comparisons.
      94             :  */
      95             : void
      96        3316 : execTuplesHashPrepare(int numCols,
      97             :                       const Oid *eqOperators,
      98             :                       Oid **eqFuncOids,
      99             :                       FmgrInfo **hashFunctions)
     100             : {
     101             :     int         i;
     102             : 
     103        3316 :     *eqFuncOids = (Oid *) palloc(numCols * sizeof(Oid));
     104        3316 :     *hashFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
     105             : 
     106        7944 :     for (i = 0; i < numCols; i++)
     107             :     {
     108        4628 :         Oid         eq_opr = eqOperators[i];
     109             :         Oid         eq_function;
     110             :         Oid         left_hash_function;
     111             :         Oid         right_hash_function;
     112             : 
     113        4628 :         eq_function = get_opcode(eq_opr);
     114        4628 :         if (!get_op_hash_functions(eq_opr,
     115             :                                    &left_hash_function, &right_hash_function))
     116           0 :             elog(ERROR, "could not find hash function for hash operator %u",
     117             :                  eq_opr);
     118             :         /* We're not supporting cross-type cases here */
     119             :         Assert(left_hash_function == right_hash_function);
     120        4628 :         (*eqFuncOids)[i] = eq_function;
     121        4628 :         fmgr_info(right_hash_function, &(*hashFunctions)[i]);
     122             :     }
     123        3316 : }
     124             : 
     125             : 
     126             : /*****************************************************************************
     127             :  *      Utility routines for all-in-memory hash tables
     128             :  *
     129             :  * These routines build hash tables for grouping tuples together (eg, for
     130             :  * hash aggregation).  There is one entry for each not-distinct set of tuples
     131             :  * presented.
     132             :  *****************************************************************************/
     133             : 
     134             : /*
     135             :  * Construct an empty TupleHashTable
     136             :  *
     137             :  *  numCols, keyColIdx: identify the tuple fields to use as lookup key
     138             :  *  eqfunctions: equality comparison functions to use
     139             :  *  hashfunctions: datatype-specific hashing functions to use
     140             :  *  nbuckets: initial estimate of hashtable size
     141             :  *  additionalsize: size of data stored in ->additional
     142             :  *  metacxt: memory context for long-lived allocation, but not per-entry data
     143             :  *  tablecxt: memory context in which to store table entries
     144             :  *  tempcxt: short-lived context for evaluation hash and comparison functions
     145             :  *
     146             :  * The function arrays may be made with execTuplesHashPrepare().  Note they
     147             :  * are not cross-type functions, but expect to see the table datatype(s)
     148             :  * on both sides.
     149             :  *
     150             :  * Note that keyColIdx, eqfunctions, and hashfunctions must be allocated in
     151             :  * storage that will live as long as the hashtable does.
     152             :  */
     153             : TupleHashTable
     154        3868 : BuildTupleHashTableExt(PlanState *parent,
     155             :                        TupleDesc inputDesc,
     156             :                        int numCols, AttrNumber *keyColIdx,
     157             :                        const Oid *eqfuncoids,
     158             :                        FmgrInfo *hashfunctions,
     159             :                        Oid *collations,
     160             :                        long nbuckets, Size additionalsize,
     161             :                        MemoryContext metacxt,
     162             :                        MemoryContext tablecxt,
     163             :                        MemoryContext tempcxt,
     164             :                        bool use_variable_hash_iv)
     165             : {
     166             :     TupleHashTable hashtable;
     167        3868 :     Size        entrysize = sizeof(TupleHashEntryData) + additionalsize;
     168             :     MemoryContext oldcontext;
     169             : 
     170             :     Assert(nbuckets > 0);
     171             : 
     172             :     /* Limit initial table size request to not more than work_mem */
     173        3868 :     nbuckets = Min(nbuckets, (long) ((work_mem * 1024L) / entrysize));
     174             : 
     175        3868 :     oldcontext = MemoryContextSwitchTo(metacxt);
     176             : 
     177        3868 :     hashtable = (TupleHashTable) palloc(sizeof(TupleHashTableData));
     178             : 
     179        3868 :     hashtable->numCols = numCols;
     180        3868 :     hashtable->keyColIdx = keyColIdx;
     181        3868 :     hashtable->tab_hash_funcs = hashfunctions;
     182        3868 :     hashtable->tab_collations = collations;
     183        3868 :     hashtable->tablecxt = tablecxt;
     184        3868 :     hashtable->tempcxt = tempcxt;
     185        3868 :     hashtable->entrysize = entrysize;
     186        3868 :     hashtable->tableslot = NULL; /* will be made on first lookup */
     187        3868 :     hashtable->inputslot = NULL;
     188        3868 :     hashtable->in_hash_funcs = NULL;
     189        3868 :     hashtable->cur_eq_func = NULL;
     190             : 
     191             :     /*
     192             :      * If parallelism is in use, even if the master backend is performing the
     193             :      * scan itself, we don't want to create the hashtable exactly the same way
     194             :      * in all workers. As hashtables are iterated over in keyspace-order,
     195             :      * doing so in all processes in the same way is likely to lead to
     196             :      * "unbalanced" hashtables when the table size initially is
     197             :      * underestimated.
     198             :      */
     199        3868 :     if (use_variable_hash_iv)
     200         586 :         hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
     201             :     else
     202        3282 :         hashtable->hash_iv = 0;
     203             : 
     204        3868 :     hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
     205             : 
     206             :     /*
     207             :      * We copy the input tuple descriptor just for safety --- we assume all
     208             :      * input tuples will have equivalent descriptors.
     209             :      */
     210        3868 :     hashtable->tableslot = MakeSingleTupleTableSlot(CreateTupleDescCopy(inputDesc),
     211             :                                                     &TTSOpsMinimalTuple);
     212             : 
     213             :     /* build comparator for all columns */
     214             :     /* XXX: should we support non-minimal tuples for the inputslot? */
     215        3868 :     hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
     216             :                                                     &TTSOpsMinimalTuple, &TTSOpsMinimalTuple,
     217             :                                                     numCols,
     218             :                                                     keyColIdx, eqfuncoids, collations,
     219             :                                                     NULL);
     220             : 
     221             :     /*
     222             :      * While not pretty, it's ok to not shut down this context, but instead
     223             :      * rely on the containing memory context being reset, as
     224             :      * ExecBuildGroupingEqual() only builds a very simple expression calling
     225             :      * functions (i.e. nothing that'd employ RegisterExprContextCallback()).
     226             :      */
     227        3868 :     hashtable->exprcontext = CreateStandaloneExprContext();
     228             : 
     229        3868 :     MemoryContextSwitchTo(oldcontext);
     230             : 
     231        3868 :     return hashtable;
     232             : }
     233             : 
     234             : /*
     235             :  * BuildTupleHashTable is a backwards-compatibilty wrapper for
     236             :  * BuildTupleHashTableExt(), that allocates the hashtable's metadata in
     237             :  * tablecxt. Note that hashtables created this way cannot be reset leak-free
     238             :  * with ResetTupleHashTable().
     239             :  */
     240             : TupleHashTable
     241           0 : BuildTupleHashTable(PlanState *parent,
     242             :                     TupleDesc inputDesc,
     243             :                     int numCols, AttrNumber *keyColIdx,
     244             :                     const Oid *eqfuncoids,
     245             :                     FmgrInfo *hashfunctions,
     246             :                     Oid *collations,
     247             :                     long nbuckets, Size additionalsize,
     248             :                     MemoryContext tablecxt,
     249             :                     MemoryContext tempcxt,
     250             :                     bool use_variable_hash_iv)
     251             : {
     252           0 :     return BuildTupleHashTableExt(parent,
     253             :                                   inputDesc,
     254             :                                   numCols, keyColIdx,
     255             :                                   eqfuncoids,
     256             :                                   hashfunctions,
     257             :                                   collations,
     258             :                                   nbuckets, additionalsize,
     259             :                                   tablecxt,
     260             :                                   tablecxt,
     261             :                                   tempcxt,
     262             :                                   use_variable_hash_iv);
     263             : }
     264             : 
     265             : /*
     266             :  * Reset contents of the hashtable to be empty, preserving all the non-content
     267             :  * state. Note that the tablecxt passed to BuildTupleHashTableExt() should
     268             :  * also be reset, otherwise there will be leaks.
     269             :  */
     270             : void
     271       36308 : ResetTupleHashTable(TupleHashTable hashtable)
     272             : {
     273       36308 :     tuplehash_reset(hashtable->hashtab);
     274       36308 : }
     275             : 
     276             : /*
     277             :  * Find or create a hashtable entry for the tuple group containing the
     278             :  * given tuple.  The tuple must be the same type as the hashtable entries.
     279             :  *
     280             :  * If isnew is NULL, we do not create new entries; we return NULL if no
     281             :  * match is found.
     282             :  *
     283             :  * If isnew isn't NULL, then a new entry is created if no existing entry
     284             :  * matches.  On return, *isnew is true if the entry is newly created,
     285             :  * false if it existed already.  ->additional_data in the new entry has
     286             :  * been zeroed.
     287             :  */
     288             : TupleHashEntry
     289     3194482 : LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
     290             :                      bool *isnew)
     291             : {
     292             :     TupleHashEntryData *entry;
     293             :     MemoryContext oldContext;
     294             :     bool        found;
     295             :     MinimalTuple key;
     296             : 
     297             :     /* Need to run the hash functions in short-lived context */
     298     3194482 :     oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
     299             : 
     300             :     /* set up data needed by hash and match functions */
     301     3194482 :     hashtable->inputslot = slot;
     302     3194482 :     hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
     303     3194482 :     hashtable->cur_eq_func = hashtable->tab_eq_func;
     304             : 
     305     3194482 :     key = NULL;                 /* flag to reference inputslot */
     306             : 
     307     3194482 :     if (isnew)
     308             :     {
     309     3099858 :         entry = tuplehash_insert(hashtable->hashtab, key, &found);
     310             : 
     311     3099854 :         if (found)
     312             :         {
     313             :             /* found pre-existing entry */
     314     2756930 :             *isnew = false;
     315             :         }
     316             :         else
     317             :         {
     318             :             /* created new entry */
     319      342924 :             *isnew = true;
     320             :             /* zero caller data */
     321      342924 :             entry->additional = NULL;
     322      342924 :             MemoryContextSwitchTo(hashtable->tablecxt);
     323             :             /* Copy the first tuple into the table context */
     324      342924 :             entry->firstTuple = ExecCopySlotMinimalTuple(slot);
     325             :         }
     326             :     }
     327             :     else
     328             :     {
     329       94624 :         entry = tuplehash_lookup(hashtable->hashtab, key);
     330             :     }
     331             : 
     332     3194478 :     MemoryContextSwitchTo(oldContext);
     333             : 
     334     3194478 :     return entry;
     335             : }
     336             : 
     337             : /*
     338             :  * Search for a hashtable entry matching the given tuple.  No entry is
     339             :  * created if there's not a match.  This is similar to the non-creating
     340             :  * case of LookupTupleHashEntry, except that it supports cross-type
     341             :  * comparisons, in which the given tuple is not of the same type as the
     342             :  * table entries.  The caller must provide the hash functions to use for
     343             :  * the input tuple, as well as the equality functions, since these may be
     344             :  * different from the table's internal functions.
     345             :  */
     346             : TupleHashEntry
     347      468046 : FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
     348             :                    ExprState *eqcomp,
     349             :                    FmgrInfo *hashfunctions)
     350             : {
     351             :     TupleHashEntry entry;
     352             :     MemoryContext oldContext;
     353             :     MinimalTuple key;
     354             : 
     355             :     /* Need to run the hash functions in short-lived context */
     356      468046 :     oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
     357             : 
     358             :     /* Set up data needed by hash and match functions */
     359      468046 :     hashtable->inputslot = slot;
     360      468046 :     hashtable->in_hash_funcs = hashfunctions;
     361      468046 :     hashtable->cur_eq_func = eqcomp;
     362             : 
     363             :     /* Search the hash table */
     364      468046 :     key = NULL;                 /* flag to reference inputslot */
     365      468046 :     entry = tuplehash_lookup(hashtable->hashtab, key);
     366      468046 :     MemoryContextSwitchTo(oldContext);
     367             : 
     368      468046 :     return entry;
     369             : }
     370             : 
     371             : /*
     372             :  * Compute the hash value for a tuple
     373             :  *
     374             :  * The passed-in key is a pointer to TupleHashEntryData.  In an actual hash
     375             :  * table entry, the firstTuple field points to a tuple (in MinimalTuple
     376             :  * format).  LookupTupleHashEntry sets up a dummy TupleHashEntryData with a
     377             :  * NULL firstTuple field --- that cues us to look at the inputslot instead.
     378             :  * This convention avoids the need to materialize virtual input tuples unless
     379             :  * they actually need to get copied into the table.
     380             :  *
     381             :  * Also, the caller must select an appropriate memory context for running
     382             :  * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
     383             :  */
     384             : static uint32
     385     3662528 : TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple)
     386             : {
     387     3662528 :     TupleHashTable hashtable = (TupleHashTable) tb->private_data;
     388     3662528 :     int         numCols = hashtable->numCols;
     389     3662528 :     AttrNumber *keyColIdx = hashtable->keyColIdx;
     390     3662528 :     uint32      hashkey = hashtable->hash_iv;
     391             :     TupleTableSlot *slot;
     392             :     FmgrInfo   *hashfunctions;
     393             :     int         i;
     394             : 
     395     3662528 :     if (tuple == NULL)
     396             :     {
     397             :         /* Process the current input tuple for the table */
     398     3662528 :         slot = hashtable->inputslot;
     399     3662528 :         hashfunctions = hashtable->in_hash_funcs;
     400             :     }
     401             :     else
     402             :     {
     403             :         /*
     404             :          * Process a tuple already stored in the table.
     405             :          *
     406             :          * (this case never actually occurs due to the way simplehash.h is
     407             :          * used, as the hash-value is stored in the entries)
     408             :          */
     409           0 :         slot = hashtable->tableslot;
     410           0 :         ExecStoreMinimalTuple(tuple, slot, false);
     411           0 :         hashfunctions = hashtable->tab_hash_funcs;
     412             :     }
     413             : 
     414     8926710 :     for (i = 0; i < numCols; i++)
     415             :     {
     416     5264186 :         AttrNumber  att = keyColIdx[i];
     417             :         Datum       attr;
     418             :         bool        isNull;
     419             : 
     420             :         /* rotate hashkey left 1 bit at each step */
     421     5264186 :         hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
     422             : 
     423     5264186 :         attr = slot_getattr(slot, att, &isNull);
     424             : 
     425     5264186 :         if (!isNull)            /* treat nulls as having hash key 0 */
     426             :         {
     427             :             uint32      hkey;
     428             : 
     429     5098682 :             hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
     430             :                                                     hashtable->tab_collations[i],
     431             :                                                     attr));
     432     5098678 :             hashkey ^= hkey;
     433             :         }
     434             :     }
     435             : 
     436             :     /*
     437             :      * The way hashes are combined above, among each other and with the IV,
     438             :      * doesn't lead to good bit perturbation. As the IV's goal is to lead to
     439             :      * achieve that, perform a round of hashing of the combined hash -
     440             :      * resulting in near perfect perturbation.
     441             :      */
     442     3662524 :     return murmurhash32(hashkey);
     443             : }
     444             : 
     445             : /*
     446             :  * See whether two tuples (presumably of the same hash value) match
     447             :  *
     448             :  * As above, the passed pointers are pointers to TupleHashEntryData.
     449             :  */
     450             : static int
     451     2836458 : TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
     452             : {
     453             :     TupleTableSlot *slot1;
     454             :     TupleTableSlot *slot2;
     455     2836458 :     TupleHashTable hashtable = (TupleHashTable) tb->private_data;
     456     2836458 :     ExprContext *econtext = hashtable->exprcontext;
     457             : 
     458             :     /*
     459             :      * We assume that simplehash.h will only ever call us with the first
     460             :      * argument being an actual table entry, and the second argument being
     461             :      * LookupTupleHashEntry's dummy TupleHashEntryData.  The other direction
     462             :      * could be supported too, but is not currently required.
     463             :      */
     464             :     Assert(tuple1 != NULL);
     465     2836458 :     slot1 = hashtable->tableslot;
     466     2836458 :     ExecStoreMinimalTuple(tuple1, slot1, false);
     467             :     Assert(tuple2 == NULL);
     468     2836458 :     slot2 = hashtable->inputslot;
     469             : 
     470             :     /* For crosstype comparisons, the inputslot must be first */
     471     2836458 :     econtext->ecxt_innertuple = slot2;
     472     2836458 :     econtext->ecxt_outertuple = slot1;
     473     2836458 :     return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
     474             : }

Generated by: LCOV version 1.13