Skip to content

Commit 19b8863

Browse files
tglsfdctglsfdc
committed
First cut at implementing IN (and NOT IN) via hashtables. There is
more to be done yet, but this is a good start.
1 parent 3e54e26 commit 19b8863

File tree

7 files changed

+709
-129
lines changed

7 files changed

+709
-129
lines changed

‎src/backend/executor/execGrouping.c

Lines changed: 104 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.1 2003/01/10 23:54:24 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.2 2003/01/12 04:03:34 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -23,17 +23,14 @@
2323

2424
/*****************************************************************************
2525
* Utility routines for grouping tuples together
26-
*
27-
* These routines actually implement SQL's notion of "distinct/not distinct".
28-
* Two tuples match if they are not distinct in all the compared columns,
29-
* i.e., the column values are either both null, or both non-null and equal.
3026
*****************************************************************************/
3127

3228
/*
3329
* execTuplesMatch
3430
* Return true if two tuples match in all the indicated fields.
35-
* This is used to detect group boundaries in nodeGroup and nodeAgg,
36-
* and to decide whether two tuples are distinct or not in nodeUnique.
31+
*
32+
* This actually implements SQL's notion of "not distinct". Two nulls
33+
* match, a null and a not-null don't match.
3734
*
3835
* tuple1, tuple2: the tuples to compare
3936
* tupdesc: tuple descriptor applying to both tuples
@@ -112,11 +109,88 @@ execTuplesMatch(HeapTuple tuple1,
112109
return result;
113110
}
114111

112+
/*
113+
* execTuplesUnequal
114+
* Return true if two tuples are definitely unequal in the indicated
115+
* fields.
116+
*
117+
* Nulls are neither equal nor unequal to anything else. A true result
118+
* is obtained only if there are non-null fields that compare not-equal.
119+
*
120+
* Parameters are identical to execTuplesMatch.
121+
*/
122+
bool
123+
execTuplesUnequal(HeapTuple tuple1,
124+
HeapTuple tuple2,
125+
TupleDesc tupdesc,
126+
int numCols,
127+
AttrNumber *matchColIdx,
128+
FmgrInfo *eqfunctions,
129+
MemoryContext evalContext)
130+
{
131+
MemoryContext oldContext;
132+
bool result;
133+
int i;
134+
135+
/* Reset and switch into the temp context. */
136+
MemoryContextReset(evalContext);
137+
oldContext = MemoryContextSwitchTo(evalContext);
138+
139+
/*
140+
* We cannot report a match without checking all the fields, but we
141+
* can report a non-match as soon as we find unequal fields. So,
142+
* start comparing at the last field (least significant sort key).
143+
* That's the most likely to be different if we are dealing with
144+
* 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 = heap_getattr(tuple1,
157+
att,
158+
tupdesc,
159+
&isNull1);
160+
161+
if (isNull1)
162+
continue; /* can't prove anything here */
163+
164+
attr2 = heap_getattr(tuple2,
165+
att,
166+
tupdesc,
167+
&isNull2);
168+
169+
if (isNull2)
170+
continue; /* can't prove anything here */
171+
172+
/* Apply the type-specific equality function */
173+
174+
if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
175+
attr1, attr2)))
176+
{
177+
result = true; /* they are unequal */
178+
break;
179+
}
180+
}
181+
182+
MemoryContextSwitchTo(oldContext);
183+
184+
return result;
185+
}
186+
115187

116188
/*
117189
* execTuplesMatchPrepare
118-
* Look up the equality functions needed for execTuplesMatch.
119-
* The result is a palloc'd array.
190+
* Look up the equality functions needed for execTuplesMatch or
191+
* execTuplesUnequal.
192+
*
193+
* The result is a palloc'd array.
120194
*/
121195
FmgrInfo *
122196
execTuplesMatchPrepare(TupleDesc tupdesc,
@@ -266,8 +340,13 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
266340
* Find or create a hashtable entry for the tuple group containing the
267341
* given tuple.
268342
*
269-
* On return, *isnew is true if the entry is newly created, false if it
270-
* existed already. Any extra space in a new entry has been zeroed.
343+
* If isnew is NULL, we do not create new entries; we return NULL if no
344+
* match is found.
345+
*
346+
* If isnew isn't NULL, then a new entry is created if no existing entry
347+
* matches. On return, *isnew is true if the entry is newly created,
348+
* false if it existed already. Any extra space in a new entry has been
349+
* zeroed.
271350
*/
272351
TupleHashEntry
273352
LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
@@ -318,26 +397,30 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
318397
hashtable->eqfunctions,
319398
hashtable->tempcxt))
320399
{
400+
if (isnew)
401+
*isnew = false;
321402
MemoryContextSwitchTo(oldContext);
322-
*isnew = false;
323403
return entry;
324404
}
325405
}
326406

327-
/* Not there, so build a new one */
328-
MemoryContextSwitchTo(hashtable->tablecxt);
407+
/* Not there, so build a new one if requested */
408+
if (isnew)
409+
{
410+
MemoryContextSwitchTo(hashtable->tablecxt);
329411

330-
entry = (TupleHashEntry) palloc0(hashtable->entrysize);
412+
entry = (TupleHashEntry) palloc0(hashtable->entrysize);
331413

332-
entry->hashkey = hashkey;
333-
entry->firstTuple = heap_copytuple(tuple);
414+
entry->hashkey = hashkey;
415+
entry->firstTuple = heap_copytuple(tuple);
334416

335-
entry->next = hashtable->buckets[bucketno];
336-
hashtable->buckets[bucketno] = entry;
417+
entry->next = hashtable->buckets[bucketno];
418+
hashtable->buckets[bucketno] = entry;
337419

338-
MemoryContextSwitchTo(oldContext);
420+
*isnew = true;
421+
}
339422

340-
*isnew = true;
423+
MemoryContextSwitchTo(oldContext);
341424

342425
return entry;
343426
}

‎src/backend/executor/execQual.c

Lines changed: 19 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/execQual.c,v 1.122 2003/01/10 21:08:07 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execQual.c,v 1.123 2003/01/12 04:03:34 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -2324,8 +2324,13 @@ ExecCleanTargetListLength(List *targetlist)
23242324
/* ----------------------------------------------------------------
23252325
* ExecTargetList
23262326
*
2327-
* Evaluates a targetlist with respect to the current
2328-
* expression context and return a tuple.
2327+
* Evaluates a targetlist with respect to the given
2328+
* expression context and returns a tuple.
2329+
*
2330+
* The caller must pass workspace for the values and nulls arrays
2331+
* as well as the itemIsDone array. This convention saves palloc'ing
2332+
* workspace on each call, and some callers may find it useful to examine
2333+
* the values array directly.
23292334
*
23302335
* As with ExecEvalExpr, the caller should pass isDone = NULL if not
23312336
* prepared to deal with sets of result tuples. Otherwise, a return
@@ -2335,21 +2340,15 @@ ExecCleanTargetListLength(List *targetlist)
23352340
*/
23362341
static HeapTuple
23372342
ExecTargetList(List *targetlist,
2338-
int nodomains,
23392343
TupleDesc targettype,
2340-
Datum *values,
23412344
ExprContext *econtext,
2345+
Datum *values,
2346+
char *nulls,
2347+
ExprDoneCond *itemIsDone,
23422348
ExprDoneCond *isDone)
23432349
{
23442350
MemoryContext oldContext;
2345-
2346-
#define NPREALLOCDOMAINS 64
2347-
char nullsArray[NPREALLOCDOMAINS];
2348-
ExprDoneCond itemIsDoneArray[NPREALLOCDOMAINS];
2349-
char *nulls;
2350-
ExprDoneCond *itemIsDone;
23512351
List *tl;
2352-
HeapTuple newTuple;
23532352
bool isNull;
23542353
bool haveDoneSets;
23552354
static struct tupleDesc NullTupleDesc; /* we assume this inits to
@@ -2378,31 +2377,9 @@ ExecTargetList(List *targetlist,
23782377
if (targettype == NULL)
23792378
targettype = &NullTupleDesc;
23802379

2381-
/*
2382-
* allocate an array of char's to hold the "null" information only if
2383-
* we have a really large targetlist. otherwise we use the stack.
2384-
*
2385-
* We also allocate another array that holds the isDone status for each
2386-
* targetlist item. The isDone status is needed so that we can iterate,
2387-
* generating multiple tuples, when one or more tlist items return
2388-
* sets. (We expect the caller to call us again if we return
2389-
* isDone = ExprMultipleResult.)
2390-
*/
2391-
if (nodomains > NPREALLOCDOMAINS)
2392-
{
2393-
nulls = (char *) palloc(nodomains * sizeof(char));
2394-
itemIsDone = (ExprDoneCond *) palloc(nodomains * sizeof(ExprDoneCond));
2395-
}
2396-
else
2397-
{
2398-
nulls = nullsArray;
2399-
itemIsDone = itemIsDoneArray;
2400-
}
2401-
24022380
/*
24032381
* evaluate all the expressions in the target list
24042382
*/
2405-
24062383
if (isDone)
24072384
*isDone = ExprSingleResult; /* until proven otherwise */
24082385

@@ -2451,8 +2428,7 @@ ExecTargetList(List *targetlist,
24512428
*/
24522429
*isDone = ExprEndResult;
24532430
MemoryContextSwitchTo(oldContext);
2454-
newTuple = NULL;
2455-
goto exit;
2431+
return NULL;
24562432
}
24572433
else
24582434
{
@@ -2511,8 +2487,7 @@ ExecTargetList(List *targetlist,
25112487
}
25122488

25132489
MemoryContextSwitchTo(oldContext);
2514-
newTuple = NULL;
2515-
goto exit;
2490+
return NULL;
25162491
}
25172492
}
25182493
}
@@ -2522,20 +2497,7 @@ ExecTargetList(List *targetlist,
25222497
*/
25232498
MemoryContextSwitchTo(oldContext);
25242499

2525-
newTuple = (HeapTuple) heap_formtuple(targettype, values, nulls);
2526-
2527-
exit:
2528-
2529-
/*
2530-
* free the status arrays if we palloc'd them
2531-
*/
2532-
if (nodomains > NPREALLOCDOMAINS)
2533-
{
2534-
pfree(nulls);
2535-
pfree(itemIsDone);
2536-
}
2537-
2538-
return newTuple;
2500+
return heap_formtuple(targettype, values, nulls);
25392501
}
25402502

25412503
/* ----------------------------------------------------------------
@@ -2555,11 +2517,7 @@ TupleTableSlot *
25552517
ExecProject(ProjectionInfo *projInfo, ExprDoneCond *isDone)
25562518
{
25572519
TupleTableSlot *slot;
2558-
List *targetlist;
2559-
int len;
25602520
TupleDesc tupType;
2561-
Datum *tupValue;
2562-
ExprContext *econtext;
25632521
HeapTuple newTuple;
25642522

25652523
/*
@@ -2572,21 +2530,17 @@ ExecProject(ProjectionInfo *projInfo, ExprDoneCond *isDone)
25722530
* get the projection info we want
25732531
*/
25742532
slot = projInfo->pi_slot;
2575-
targetlist = projInfo->pi_targetlist;
2576-
len = projInfo->pi_len;
25772533
tupType = slot->ttc_tupleDescriptor;
25782534

2579-
tupValue = projInfo->pi_tupValue;
2580-
econtext = projInfo->pi_exprContext;
2581-
25822535
/*
25832536
* form a new result tuple (if possible --- result can be NULL)
25842537
*/
2585-
newTuple = ExecTargetList(targetlist,
2586-
len,
2538+
newTuple = ExecTargetList(projInfo->pi_targetlist,
25872539
tupType,
2588-
tupValue,
2589-
econtext,
2540+
projInfo->pi_exprContext,
2541+
projInfo->pi_tupValues,
2542+
projInfo->pi_tupNulls,
2543+
projInfo->pi_itemIsDone,
25902544
isDone);
25912545

25922546
/*

0 commit comments

Comments
 (0)