← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/executor/execGrouping.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/executor/execGrouping.c
 
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-2011, 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 "executor/executor.h"
 
22
#include "parser/parse_oper.h"
 
23
#include "utils/lsyscache.h"
 
24
#include "utils/memutils.h"
 
25
#include "utils/syscache.h"
 
26
 
 
27
 
 
28
static TupleHashTable CurTupleHashTable = NULL;
 
29
 
 
30
static uint32 TupleHashTableHash(const void *key, Size keysize);
 
31
static int TupleHashTableMatch(const void *key1, const void *key2,
 
32
                                        Size keysize);
 
33
 
 
34
 
 
35
/*****************************************************************************
 
36
 *              Utility routines for grouping tuples together
 
37
 *****************************************************************************/
 
38
 
 
39
/*
 
40
 * execTuplesMatch
 
41
 *              Return true if two tuples match in all the indicated fields.
 
42
 *
 
43
 * This actually implements SQL's notion of "not distinct".  Two nulls
 
44
 * match, a null and a not-null don't match.
 
45
 *
 
46
 * slot1, slot2: the tuples to compare (must have same columns!)
 
47
 * numCols: the number of attributes to be examined
 
48
 * matchColIdx: array of attribute column numbers
 
49
 * eqFunctions: array of fmgr lookup info for the equality functions to use
 
50
 * evalContext: short-term memory context for executing the functions
 
51
 *
 
52
 * NB: evalContext is reset each time!
 
53
 */
 
54
bool
 
55
execTuplesMatch(TupleTableSlot *slot1,
 
56
                                TupleTableSlot *slot2,
 
57
                                int numCols,
 
58
                                AttrNumber *matchColIdx,
 
59
                                FmgrInfo *eqfunctions,
 
60
                                MemoryContext evalContext)
 
61
{
 
62
        MemoryContext oldContext;
 
63
        bool            result;
 
64
        int                     i;
 
65
 
 
66
        /* Reset and switch into the temp context. */
 
67
        MemoryContextReset(evalContext);
 
68
        oldContext = MemoryContextSwitchTo(evalContext);
 
69
 
 
70
        /*
 
71
         * We cannot report a match without checking all the fields, but we can
 
72
         * report a non-match as soon as we find unequal fields.  So, start
 
73
         * comparing at the last field (least significant sort key). That's the
 
74
         * most likely to be different if we are dealing with sorted input.
 
75
         */
 
76
        result = true;
 
77
 
 
78
        for (i = numCols; --i >= 0;)
 
79
        {
 
80
                AttrNumber      att = matchColIdx[i];
 
81
                Datum           attr1,
 
82
                                        attr2;
 
83
                bool            isNull1,
 
84
                                        isNull2;
 
85
 
 
86
                attr1 = slot_getattr(slot1, att, &isNull1);
 
87
 
 
88
                attr2 = slot_getattr(slot2, att, &isNull2);
 
89
 
 
90
                if (isNull1 != isNull2)
 
91
                {
 
92
                        result = false;         /* one null and one not; they aren't equal */
 
93
                        break;
 
94
                }
 
95
 
 
96
                if (isNull1)
 
97
                        continue;                       /* both are null, treat as equal */
 
98
 
 
99
                /* Apply the type-specific equality function */
 
100
 
 
101
                if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
 
102
                                                                                attr1, attr2)))
 
103
                {
 
104
                        result = false;         /* they aren't equal */
 
105
                        break;
 
106
                }
 
107
        }
 
108
 
 
109
        MemoryContextSwitchTo(oldContext);
 
110
 
 
111
        return result;
 
112
}
 
113
 
 
114
/*
 
115
 * execTuplesUnequal
 
116
 *              Return true if two tuples are definitely unequal in the indicated
 
117
 *              fields.
 
118
 *
 
119
 * Nulls are neither equal nor unequal to anything else.  A true result
 
120
 * is obtained only if there are non-null fields that compare not-equal.
 
121
 *
 
122
 * Parameters are identical to execTuplesMatch.
 
123
 */
 
124
bool
 
125
execTuplesUnequal(TupleTableSlot *slot1,
 
126
                                  TupleTableSlot *slot2,
 
127
                                  int numCols,
 
128
                                  AttrNumber *matchColIdx,
 
129
                                  FmgrInfo *eqfunctions,
 
130
                                  MemoryContext evalContext)
 
131
{
 
132
        MemoryContext oldContext;
 
133
        bool            result;
 
134
        int                     i;
 
135
 
 
136
        /* Reset and switch into the temp context. */
 
137
        MemoryContextReset(evalContext);
 
138
        oldContext = MemoryContextSwitchTo(evalContext);
 
139
 
 
140
        /*
 
141
         * We cannot report a match without checking all the fields, but we can
 
142
         * report a non-match as soon as we find unequal fields.  So, start
 
143
         * comparing at the last field (least significant sort key). That's the
 
144
         * most likely to be different if we are dealing with sorted input.
 
145
         */
 
146
        result = false;
 
147
 
 
148
        for (i = numCols; --i >= 0;)
 
149
        {
 
150
                AttrNumber      att = matchColIdx[i];
 
151
                Datum           attr1,
 
152
                                        attr2;
 
153
                bool            isNull1,
 
154
                                        isNull2;
 
155
 
 
156
                attr1 = slot_getattr(slot1, att, &isNull1);
 
157
 
 
158
                if (isNull1)
 
159
                        continue;                       /* can't prove anything here */
 
160
 
 
161
                attr2 = slot_getattr(slot2, att, &isNull2);
 
162
 
 
163
                if (isNull2)
 
164
                        continue;                       /* can't prove anything here */
 
165
 
 
166
                /* Apply the type-specific equality function */
 
167
 
 
168
                if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
 
169
                                                                                attr1, attr2)))
 
170
                {
 
171
                        result = true;          /* they are unequal */
 
172
                        break;
 
173
                }
 
174
        }
 
175
 
 
176
        MemoryContextSwitchTo(oldContext);
 
177
 
 
178
        return result;
 
179
}
 
180
 
 
181
 
 
182
/*
 
183
 * execTuplesMatchPrepare
 
184
 *              Look up the equality functions needed for execTuplesMatch or
 
185
 *              execTuplesUnequal, given an array of equality operator OIDs.
 
186
 *
 
187
 * The result is a palloc'd array.
 
188
 */
 
189
FmgrInfo *
 
190
execTuplesMatchPrepare(int numCols,
 
191
                                           Oid *eqOperators)
 
192
{
 
193
        FmgrInfo   *eqFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
 
194
        int                     i;
 
195
 
 
196
        for (i = 0; i < numCols; i++)
 
197
        {
 
198
                Oid                     eq_opr = eqOperators[i];
 
199
                Oid                     eq_function;
 
200
 
 
201
                eq_function = get_opcode(eq_opr);
 
202
                fmgr_info(eq_function, &eqFunctions[i]);
 
203
        }
 
204
 
 
205
        return eqFunctions;
 
206
}
 
207
 
 
208
/*
 
209
 * execTuplesHashPrepare
 
210
 *              Look up the equality and hashing functions needed for a TupleHashTable.
 
211
 *
 
212
 * This is similar to execTuplesMatchPrepare, but we also need to find the
 
213
 * hash functions associated with the equality operators.  *eqFunctions and
 
214
 * *hashFunctions receive the palloc'd result arrays.
 
215
 *
 
216
 * Note: we expect that the given operators are not cross-type comparisons.
 
217
 */
 
218
void
 
219
execTuplesHashPrepare(int numCols,
 
220
                                          Oid *eqOperators,
 
221
                                          FmgrInfo **eqFunctions,
 
222
                                          FmgrInfo **hashFunctions)
 
223
{
 
224
        int                     i;
 
225
 
 
226
        *eqFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
 
227
        *hashFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
 
228
 
 
229
        for (i = 0; i < numCols; i++)
 
230
        {
 
231
                Oid                     eq_opr = eqOperators[i];
 
232
                Oid                     eq_function;
 
233
                Oid                     left_hash_function;
 
234
                Oid                     right_hash_function;
 
235
 
 
236
                eq_function = get_opcode(eq_opr);
 
237
                if (!get_op_hash_functions(eq_opr,
 
238
                                                                   &left_hash_function, &right_hash_function))
 
239
                        elog(ERROR, "could not find hash function for hash operator %u",
 
240
                                 eq_opr);
 
241
                /* We're not supporting cross-type cases here */
 
242
                Assert(left_hash_function == right_hash_function);
 
243
                fmgr_info(eq_function, &(*eqFunctions)[i]);
 
244
                fmgr_info(right_hash_function, &(*hashFunctions)[i]);
 
245
        }
 
246
}
 
247
 
 
248
 
 
249
/*****************************************************************************
 
250
 *              Utility routines for all-in-memory hash tables
 
251
 *
 
252
 * These routines build hash tables for grouping tuples together (eg, for
 
253
 * hash aggregation).  There is one entry for each not-distinct set of tuples
 
254
 * presented.
 
255
 *****************************************************************************/
 
256
 
 
257
/*
 
258
 * Construct an empty TupleHashTable
 
259
 *
 
260
 *      numCols, keyColIdx: identify the tuple fields to use as lookup key
 
261
 *      eqfunctions: equality comparison functions to use
 
262
 *      hashfunctions: datatype-specific hashing functions to use
 
263
 *      nbuckets: initial estimate of hashtable size
 
264
 *      entrysize: size of each entry (at least sizeof(TupleHashEntryData))
 
265
 *      tablecxt: memory context in which to store table and table entries
 
266
 *      tempcxt: short-lived context for evaluation hash and comparison functions
 
267
 *
 
268
 * The function arrays may be made with execTuplesHashPrepare().  Note they
 
269
 * are not cross-type functions, but expect to see the table datatype(s)
 
270
 * on both sides.
 
271
 *
 
272
 * Note that keyColIdx, eqfunctions, and hashfunctions must be allocated in
 
273
 * storage that will live as long as the hashtable does.
 
274
 */
 
275
TupleHashTable
 
276
BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
 
277
                                        FmgrInfo *eqfunctions,
 
278
                                        FmgrInfo *hashfunctions,
 
279
                                        int nbuckets, Size entrysize,
 
280
                                        MemoryContext tablecxt, MemoryContext tempcxt)
 
281
{
 
282
        TupleHashTable hashtable;
 
283
        HASHCTL         hash_ctl;
 
284
 
 
285
        Assert(nbuckets > 0);
 
286
        Assert(entrysize >= sizeof(TupleHashEntryData));
 
287
 
 
288
        hashtable = (TupleHashTable) MemoryContextAlloc(tablecxt,
 
289
                                                                                                 sizeof(TupleHashTableData));
 
290
 
 
291
        hashtable->numCols = numCols;
 
292
        hashtable->keyColIdx = keyColIdx;
 
293
        hashtable->tab_hash_funcs = hashfunctions;
 
294
        hashtable->tab_eq_funcs = eqfunctions;
 
295
        hashtable->tablecxt = tablecxt;
 
296
        hashtable->tempcxt = tempcxt;
 
297
        hashtable->entrysize = entrysize;
 
298
        hashtable->tableslot = NULL;    /* will be made on first lookup */
 
299
        hashtable->inputslot = NULL;
 
300
        hashtable->in_hash_funcs = NULL;
 
301
        hashtable->cur_eq_funcs = NULL;
 
302
 
 
303
        MemSet(&hash_ctl, 0, sizeof(hash_ctl));
 
304
        hash_ctl.keysize = sizeof(TupleHashEntryData);
 
305
        hash_ctl.entrysize = entrysize;
 
306
        hash_ctl.hash = TupleHashTableHash;
 
307
        hash_ctl.match = TupleHashTableMatch;
 
308
        hash_ctl.hcxt = tablecxt;
 
309
        hashtable->hashtab = hash_create("TupleHashTable", (long) nbuckets,
 
310
                                                                         &hash_ctl,
 
311
                                        HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
 
312
 
 
313
        return hashtable;
 
314
}
 
315
 
 
316
/*
 
317
 * Find or create a hashtable entry for the tuple group containing the
 
318
 * given tuple.  The tuple must be the same type as the hashtable entries.
 
319
 *
 
320
 * If isnew is NULL, we do not create new entries; we return NULL if no
 
321
 * match is found.
 
322
 *
 
323
 * If isnew isn't NULL, then a new entry is created if no existing entry
 
324
 * matches.  On return, *isnew is true if the entry is newly created,
 
325
 * false if it existed already.  Any extra space in a new entry has been
 
326
 * zeroed.
 
327
 */
 
328
TupleHashEntry
 
329
LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 
330
                                         bool *isnew)
 
331
{
 
332
        TupleHashEntry entry;
 
333
        MemoryContext oldContext;
 
334
        TupleHashTable saveCurHT;
 
335
        TupleHashEntryData dummy;
 
336
        bool            found;
 
337
 
 
338
        /* If first time through, clone the input slot to make table slot */
 
339
        if (hashtable->tableslot == NULL)
 
340
        {
 
341
                TupleDesc       tupdesc;
 
342
 
 
343
                oldContext = MemoryContextSwitchTo(hashtable->tablecxt);
 
344
 
 
345
                /*
 
346
                 * We copy the input tuple descriptor just for safety --- we assume
 
347
                 * all input tuples will have equivalent descriptors.
 
348
                 */
 
349
                tupdesc = CreateTupleDescCopy(slot->tts_tupleDescriptor);
 
350
                hashtable->tableslot = MakeSingleTupleTableSlot(tupdesc);
 
351
                MemoryContextSwitchTo(oldContext);
 
352
        }
 
353
 
 
354
        /* Need to run the hash functions in short-lived context */
 
355
        oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
356
 
 
357
        /*
 
358
         * Set up data needed by hash and match functions
 
359
         *
 
360
         * We save and restore CurTupleHashTable just in case someone manages to
 
361
         * invoke this code re-entrantly.
 
362
         */
 
363
        hashtable->inputslot = slot;
 
364
        hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
 
365
        hashtable->cur_eq_funcs = hashtable->tab_eq_funcs;
 
366
 
 
367
        saveCurHT = CurTupleHashTable;
 
368
        CurTupleHashTable = hashtable;
 
369
 
 
370
        /* Search the hash table */
 
371
        dummy.firstTuple = NULL;        /* flag to reference inputslot */
 
372
        entry = (TupleHashEntry) hash_search(hashtable->hashtab,
 
373
                                                                                 &dummy,
 
374
                                                                                 isnew ? HASH_ENTER : HASH_FIND,
 
375
                                                                                 &found);
 
376
 
 
377
        if (isnew)
 
378
        {
 
379
                if (found)
 
380
                {
 
381
                        /* found pre-existing entry */
 
382
                        *isnew = false;
 
383
                }
 
384
                else
 
385
                {
 
386
                        /*
 
387
                         * created new entry
 
388
                         *
 
389
                         * Zero any caller-requested space in the entry.  (This zaps the
 
390
                         * "key data" dynahash.c copied into the new entry, but we don't
 
391
                         * care since we're about to overwrite it anyway.)
 
392
                         */
 
393
                        MemSet(entry, 0, hashtable->entrysize);
 
394
 
 
395
                        /* Copy the first tuple into the table context */
 
396
                        MemoryContextSwitchTo(hashtable->tablecxt);
 
397
                        entry->firstTuple = ExecCopySlotMinimalTuple(slot);
 
398
 
 
399
                        *isnew = true;
 
400
                }
 
401
        }
 
402
 
 
403
        CurTupleHashTable = saveCurHT;
 
404
 
 
405
        MemoryContextSwitchTo(oldContext);
 
406
 
 
407
        return entry;
 
408
}
 
409
 
 
410
/*
 
411
 * Search for a hashtable entry matching the given tuple.  No entry is
 
412
 * created if there's not a match.  This is similar to the non-creating
 
413
 * case of LookupTupleHashEntry, except that it supports cross-type
 
414
 * comparisons, in which the given tuple is not of the same type as the
 
415
 * table entries.  The caller must provide the hash functions to use for
 
416
 * the input tuple, as well as the equality functions, since these may be
 
417
 * different from the table's internal functions.
 
418
 */
 
419
TupleHashEntry
 
420
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 
421
                                   FmgrInfo *eqfunctions,
 
422
                                   FmgrInfo *hashfunctions)
 
423
{
 
424
        TupleHashEntry entry;
 
425
        MemoryContext oldContext;
 
426
        TupleHashTable saveCurHT;
 
427
        TupleHashEntryData dummy;
 
428
 
 
429
        /* Need to run the hash functions in short-lived context */
 
430
        oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
431
 
 
432
        /*
 
433
         * Set up data needed by hash and match functions
 
434
         *
 
435
         * We save and restore CurTupleHashTable just in case someone manages to
 
436
         * invoke this code re-entrantly.
 
437
         */
 
438
        hashtable->inputslot = slot;
 
439
        hashtable->in_hash_funcs = hashfunctions;
 
440
        hashtable->cur_eq_funcs = eqfunctions;
 
441
 
 
442
        saveCurHT = CurTupleHashTable;
 
443
        CurTupleHashTable = hashtable;
 
444
 
 
445
        /* Search the hash table */
 
446
        dummy.firstTuple = NULL;        /* flag to reference inputslot */
 
447
        entry = (TupleHashEntry) hash_search(hashtable->hashtab,
 
448
                                                                                 &dummy,
 
449
                                                                                 HASH_FIND,
 
450
                                                                                 NULL);
 
451
 
 
452
        CurTupleHashTable = saveCurHT;
 
453
 
 
454
        MemoryContextSwitchTo(oldContext);
 
455
 
 
456
        return entry;
 
457
}
 
458
 
 
459
/*
 
460
 * Compute the hash value for a tuple
 
461
 *
 
462
 * The passed-in key is a pointer to TupleHashEntryData.  In an actual hash
 
463
 * table entry, the firstTuple field points to a tuple (in MinimalTuple
 
464
 * format).  LookupTupleHashEntry sets up a dummy TupleHashEntryData with a
 
465
 * NULL firstTuple field --- that cues us to look at the inputslot instead.
 
466
 * This convention avoids the need to materialize virtual input tuples unless
 
467
 * they actually need to get copied into the table.
 
468
 *
 
469
 * CurTupleHashTable must be set before calling this, since dynahash.c
 
470
 * doesn't provide any API that would let us get at the hashtable otherwise.
 
471
 *
 
472
 * Also, the caller must select an appropriate memory context for running
 
473
 * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
 
474
 */
 
475
static uint32
 
476
TupleHashTableHash(const void *key, Size keysize)
 
477
{
 
478
        MinimalTuple tuple = ((const TupleHashEntryData *) key)->firstTuple;
 
479
        TupleTableSlot *slot;
 
480
        TupleHashTable hashtable = CurTupleHashTable;
 
481
        int                     numCols = hashtable->numCols;
 
482
        AttrNumber *keyColIdx = hashtable->keyColIdx;
 
483
        FmgrInfo   *hashfunctions;
 
484
        uint32          hashkey = 0;
 
485
        int                     i;
 
486
 
 
487
        if (tuple == NULL)
 
488
        {
 
489
                /* Process the current input tuple for the table */
 
490
                slot = hashtable->inputslot;
 
491
                hashfunctions = hashtable->in_hash_funcs;
 
492
        }
 
493
        else
 
494
        {
 
495
                /* Process a tuple already stored in the table */
 
496
                /* (this case never actually occurs in current dynahash.c code) */
 
497
                slot = hashtable->tableslot;
 
498
                ExecStoreMinimalTuple(tuple, slot, false);
 
499
                hashfunctions = hashtable->tab_hash_funcs;
 
500
        }
 
501
 
 
502
        for (i = 0; i < numCols; i++)
 
503
        {
 
504
                AttrNumber      att = keyColIdx[i];
 
505
                Datum           attr;
 
506
                bool            isNull;
 
507
 
 
508
                /* rotate hashkey left 1 bit at each step */
 
509
                hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
 
510
 
 
511
                attr = slot_getattr(slot, att, &isNull);
 
512
 
 
513
                if (!isNull)                    /* treat nulls as having hash key 0 */
 
514
                {
 
515
                        uint32          hkey;
 
516
 
 
517
                        hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
 
518
                                                                                                attr));
 
519
                        hashkey ^= hkey;
 
520
                }
 
521
        }
 
522
 
 
523
        return hashkey;
 
524
}
 
525
 
 
526
/*
 
527
 * See whether two tuples (presumably of the same hash value) match
 
528
 *
 
529
 * As above, the passed pointers are pointers to TupleHashEntryData.
 
530
 *
 
531
 * CurTupleHashTable must be set before calling this, since dynahash.c
 
532
 * doesn't provide any API that would let us get at the hashtable otherwise.
 
533
 *
 
534
 * Also, the caller must select an appropriate memory context for running
 
535
 * the compare functions.  (dynahash.c doesn't change CurrentMemoryContext.)
 
536
 */
 
537
static int
 
538
TupleHashTableMatch(const void *key1, const void *key2, Size keysize)
 
539
{
 
540
        MinimalTuple tuple1 = ((const TupleHashEntryData *) key1)->firstTuple;
 
541
 
 
542
#ifdef USE_ASSERT_CHECKING
 
543
        MinimalTuple tuple2 = ((const TupleHashEntryData *) key2)->firstTuple;
 
544
#endif
 
545
        TupleTableSlot *slot1;
 
546
        TupleTableSlot *slot2;
 
547
        TupleHashTable hashtable = CurTupleHashTable;
 
548
 
 
549
        /*
 
550
         * We assume that dynahash.c will only ever call us with the first
 
551
         * argument being an actual table entry, and the second argument being
 
552
         * LookupTupleHashEntry's dummy TupleHashEntryData.  The other direction
 
553
         * could be supported too, but is not currently used by dynahash.c.
 
554
         */
 
555
        Assert(tuple1 != NULL);
 
556
        slot1 = hashtable->tableslot;
 
557
        ExecStoreMinimalTuple(tuple1, slot1, false);
 
558
        Assert(tuple2 == NULL);
 
559
        slot2 = hashtable->inputslot;
 
560
 
 
561
        /* For crosstype comparisons, the inputslot must be first */
 
562
        if (execTuplesMatch(slot2,
 
563
                                                slot1,
 
564
                                                hashtable->numCols,
 
565
                                                hashtable->keyColIdx,
 
566
                                                hashtable->cur_eq_funcs,
 
567
                                                hashtable->tempcxt))
 
568
                return 0;
 
569
        else
 
570
                return 1;
 
571
}