Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1afac12

Browse files
committed
Create a new file executor/execGrouping.c to centralize utility routines
shared by nodeGroup, nodeAgg, and soon nodeSubplan.
1 parentc837026 commit1afac12

File tree

12 files changed

+498
-337
lines changed

12 files changed

+498
-337
lines changed

‎src/backend/executor/Makefile

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,15 @@
44
# Makefile for executor
55
#
66
# IDENTIFICATION
7-
# $Header: /cvsroot/pgsql/src/backend/executor/Makefile,v 1.19 2002/05/12 23:43:02 tgl Exp $
7+
# $Header: /cvsroot/pgsql/src/backend/executor/Makefile,v 1.20 2003/01/10 23:54:24 tgl Exp $
88
#
99
#-------------------------------------------------------------------------
1010

1111
subdir = src/backend/executor
1212
top_builddir = ../../..
1313
include$(top_builddir)/src/Makefile.global
1414

15-
OBJS = execAmi.o execJunk.o execMain.o\
15+
OBJS = execAmi.oexecGrouping.oexecJunk.o execMain.o\
1616
execProcnode.o execQual.o execScan.o execTuples.o\
1717
execUtils.o functions.o instrument.o nodeAppend.o nodeAgg.o nodeHash.o\
1818
nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o\

‎src/backend/executor/execGrouping.c

Lines changed: 369 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,369 @@
1+
/*-------------------------------------------------------------------------
2+
*
3+
* execGrouping.c
4+
* executor utility routines for grouping, hashing, and aggregation
5+
*
6+
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
7+
* Portions Copyright (c) 1994, Regents of the University of California
8+
*
9+
*
10+
* IDENTIFICATION
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.1 2003/01/10 23:54:24 tgl Exp $
12+
*
13+
*-------------------------------------------------------------------------
14+
*/
15+
#include"postgres.h"
16+
17+
#include"access/hash.h"
18+
#include"access/heapam.h"
19+
#include"executor/executor.h"
20+
#include"parser/parse_oper.h"
21+
#include"utils/memutils.h"
22+
23+
24+
/*****************************************************************************
25+
*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.
30+
*****************************************************************************/
31+
32+
/*
33+
* execTuplesMatch
34+
*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.
37+
*
38+
* tuple1, tuple2: the tuples to compare
39+
* tupdesc: tuple descriptor applying to both tuples
40+
* numCols: the number of attributes to be examined
41+
* matchColIdx: array of attribute column numbers
42+
* eqFunctions: array of fmgr lookup info for the equality functions to use
43+
* evalContext: short-term memory context for executing the functions
44+
*
45+
* NB: evalContext is reset each time!
46+
*/
47+
bool
48+
execTuplesMatch(HeapTupletuple1,
49+
HeapTupletuple2,
50+
TupleDesctupdesc,
51+
intnumCols,
52+
AttrNumber*matchColIdx,
53+
FmgrInfo*eqfunctions,
54+
MemoryContextevalContext)
55+
{
56+
MemoryContextoldContext;
57+
boolresult;
58+
inti;
59+
60+
/* Reset and switch into the temp context. */
61+
MemoryContextReset(evalContext);
62+
oldContext=MemoryContextSwitchTo(evalContext);
63+
64+
/*
65+
* We cannot report a match without checking all the fields, but we
66+
* can report a non-match as soon as we find unequal fields. So,
67+
* start comparing at the last field (least significant sort key).
68+
* That's the most likely to be different if we are dealing with
69+
* sorted input.
70+
*/
71+
result= true;
72+
73+
for (i=numCols;--i >=0;)
74+
{
75+
AttrNumberatt=matchColIdx[i];
76+
Datumattr1,
77+
attr2;
78+
boolisNull1,
79+
isNull2;
80+
81+
attr1=heap_getattr(tuple1,
82+
att,
83+
tupdesc,
84+
&isNull1);
85+
86+
attr2=heap_getattr(tuple2,
87+
att,
88+
tupdesc,
89+
&isNull2);
90+
91+
if (isNull1!=isNull2)
92+
{
93+
result= false;/* one null and one not; they aren't equal */
94+
break;
95+
}
96+
97+
if (isNull1)
98+
continue;/* both are null, treat as equal */
99+
100+
/* Apply the type-specific equality function */
101+
102+
if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
103+
attr1,attr2)))
104+
{
105+
result= false;/* they aren't equal */
106+
break;
107+
}
108+
}
109+
110+
MemoryContextSwitchTo(oldContext);
111+
112+
returnresult;
113+
}
114+
115+
116+
/*
117+
* execTuplesMatchPrepare
118+
*Look up the equality functions needed for execTuplesMatch.
119+
*The result is a palloc'd array.
120+
*/
121+
FmgrInfo*
122+
execTuplesMatchPrepare(TupleDesctupdesc,
123+
intnumCols,
124+
AttrNumber*matchColIdx)
125+
{
126+
FmgrInfo*eqfunctions= (FmgrInfo*)palloc(numCols*sizeof(FmgrInfo));
127+
inti;
128+
129+
for (i=0;i<numCols;i++)
130+
{
131+
AttrNumberatt=matchColIdx[i];
132+
Oidtypid=tupdesc->attrs[att-1]->atttypid;
133+
Oideq_function;
134+
135+
eq_function=equality_oper_funcid(typid);
136+
fmgr_info(eq_function,&eqfunctions[i]);
137+
}
138+
139+
returneqfunctions;
140+
}
141+
142+
143+
/*****************************************************************************
144+
*Utility routines for hashing
145+
*****************************************************************************/
146+
147+
/*
148+
* ComputeHashFunc
149+
*
150+
*the hash function for hash joins (also used for hash aggregation)
151+
*
152+
*XXX this probably ought to be replaced with datatype-specific
153+
*hash functions, such as those already implemented for hash indexes.
154+
*/
155+
uint32
156+
ComputeHashFunc(Datumkey,inttypLen,boolbyVal)
157+
{
158+
unsignedchar*k;
159+
160+
if (byVal)
161+
{
162+
/*
163+
* If it's a by-value data type, just hash the whole Datum value.
164+
* This assumes that datatypes narrower than Datum are
165+
* consistently padded (either zero-extended or sign-extended, but
166+
* not random bits) to fill Datum; see the XXXGetDatum macros in
167+
* postgres.h. NOTE: it would not work to do hash_any(&key, len)
168+
* since this would get the wrong bytes on a big-endian machine.
169+
*/
170+
k= (unsignedchar*)&key;
171+
typLen=sizeof(Datum);
172+
}
173+
else
174+
{
175+
if (typLen>0)
176+
{
177+
/* fixed-width pass-by-reference type */
178+
k= (unsignedchar*)DatumGetPointer(key);
179+
}
180+
elseif (typLen==-1)
181+
{
182+
/*
183+
* It's a varlena type, so 'key' points to a "struct varlena".
184+
* NOTE: VARSIZE returns the "real" data length plus the
185+
* sizeof the "vl_len" attribute of varlena (the length
186+
* information). 'key' points to the beginning of the varlena
187+
* struct, so we have to use "VARDATA" to find the beginning
188+
* of the "real" data.Also, we have to be careful to detoast
189+
* the datum if it's toasted. (We don't worry about freeing
190+
* the detoasted copy; that happens for free when the
191+
* per-tuple memory context is reset in ExecHashGetBucket.)
192+
*/
193+
structvarlena*vkey=PG_DETOAST_DATUM(key);
194+
195+
typLen=VARSIZE(vkey)-VARHDRSZ;
196+
k= (unsignedchar*)VARDATA(vkey);
197+
}
198+
elseif (typLen==-2)
199+
{
200+
/* It's a null-terminated C string */
201+
typLen=strlen(DatumGetCString(key))+1;
202+
k= (unsignedchar*)DatumGetPointer(key);
203+
}
204+
else
205+
{
206+
elog(ERROR,"ComputeHashFunc: Invalid typLen %d",typLen);
207+
k=NULL;/* keep compiler quiet */
208+
}
209+
}
210+
211+
returnDatumGetUInt32(hash_any(k,typLen));
212+
}
213+
214+
215+
/*****************************************************************************
216+
*Utility routines for all-in-memory hash tables
217+
*
218+
* These routines build hash tables for grouping tuples together (eg, for
219+
* hash aggregation). There is one entry for each not-distinct set of tuples
220+
* presented.
221+
*****************************************************************************/
222+
223+
/*
224+
* Construct an empty TupleHashTable
225+
*
226+
*numCols, keyColIdx: identify the tuple fields to use as lookup key
227+
*eqfunctions: equality comparison functions to use
228+
*nbuckets: number of buckets to make
229+
*entrysize: size of each entry (at least sizeof(TupleHashEntryData))
230+
*tablecxt: memory context in which to store table and table entries
231+
*tempcxt: short-lived context for evaluation hash and comparison functions
232+
*
233+
* The eqfunctions array may be made with execTuplesMatchPrepare().
234+
*
235+
* Note that keyColIdx and eqfunctions must be allocated in storage that
236+
* will live as long as the hashtable does.
237+
*/
238+
TupleHashTable
239+
BuildTupleHashTable(intnumCols,AttrNumber*keyColIdx,
240+
FmgrInfo*eqfunctions,
241+
intnbuckets,Sizeentrysize,
242+
MemoryContexttablecxt,MemoryContexttempcxt)
243+
{
244+
TupleHashTablehashtable;
245+
Sizetabsize;
246+
247+
Assert(nbuckets>0);
248+
Assert(entrysize >=sizeof(TupleHashEntryData));
249+
250+
tabsize=sizeof(TupleHashTableData)+
251+
(nbuckets-1)*sizeof(TupleHashEntry);
252+
hashtable= (TupleHashTable)MemoryContextAllocZero(tablecxt,tabsize);
253+
254+
hashtable->numCols=numCols;
255+
hashtable->keyColIdx=keyColIdx;
256+
hashtable->eqfunctions=eqfunctions;
257+
hashtable->tablecxt=tablecxt;
258+
hashtable->tempcxt=tempcxt;
259+
hashtable->entrysize=entrysize;
260+
hashtable->nbuckets=nbuckets;
261+
262+
returnhashtable;
263+
}
264+
265+
/*
266+
* Find or create a hashtable entry for the tuple group containing the
267+
* given tuple.
268+
*
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.
271+
*/
272+
TupleHashEntry
273+
LookupTupleHashEntry(TupleHashTablehashtable,TupleTableSlot*slot,
274+
bool*isnew)
275+
{
276+
intnumCols=hashtable->numCols;
277+
AttrNumber*keyColIdx=hashtable->keyColIdx;
278+
HeapTupletuple=slot->val;
279+
TupleDesctupdesc=slot->ttc_tupleDescriptor;
280+
uint32hashkey=0;
281+
inti;
282+
intbucketno;
283+
TupleHashEntryentry;
284+
MemoryContextoldContext;
285+
286+
/* Need to run the hash function in short-lived context */
287+
oldContext=MemoryContextSwitchTo(hashtable->tempcxt);
288+
289+
for (i=0;i<numCols;i++)
290+
{
291+
AttrNumberatt=keyColIdx[i];
292+
Datumattr;
293+
boolisNull;
294+
295+
/* rotate hashkey left 1 bit at each step */
296+
hashkey= (hashkey <<1) | ((hashkey&0x80000000) ?1 :0);
297+
298+
attr=heap_getattr(tuple,att,tupdesc,&isNull);
299+
if (isNull)
300+
continue;/* treat nulls as having hash key 0 */
301+
hashkey ^=ComputeHashFunc(attr,
302+
(int)tupdesc->attrs[att-1]->attlen,
303+
tupdesc->attrs[att-1]->attbyval);
304+
}
305+
bucketno=hashkey % (uint32)hashtable->nbuckets;
306+
307+
for (entry=hashtable->buckets[bucketno];
308+
entry!=NULL;
309+
entry=entry->next)
310+
{
311+
/* Quick check using hashkey */
312+
if (entry->hashkey!=hashkey)
313+
continue;
314+
if (execTuplesMatch(entry->firstTuple,
315+
tuple,
316+
tupdesc,
317+
numCols,keyColIdx,
318+
hashtable->eqfunctions,
319+
hashtable->tempcxt))
320+
{
321+
MemoryContextSwitchTo(oldContext);
322+
*isnew= false;
323+
returnentry;
324+
}
325+
}
326+
327+
/* Not there, so build a new one */
328+
MemoryContextSwitchTo(hashtable->tablecxt);
329+
330+
entry= (TupleHashEntry)palloc0(hashtable->entrysize);
331+
332+
entry->hashkey=hashkey;
333+
entry->firstTuple=heap_copytuple(tuple);
334+
335+
entry->next=hashtable->buckets[bucketno];
336+
hashtable->buckets[bucketno]=entry;
337+
338+
MemoryContextSwitchTo(oldContext);
339+
340+
*isnew= true;
341+
342+
returnentry;
343+
}
344+
345+
/*
346+
* Walk through all the entries of a hash table, in no special order.
347+
* Returns NULL when no more entries remain.
348+
*
349+
* Iterator state must be initialized with ResetTupleHashIterator() macro.
350+
*/
351+
TupleHashEntry
352+
ScanTupleHashTable(TupleHashTablehashtable,TupleHashIterator*state)
353+
{
354+
TupleHashEntryentry;
355+
356+
entry=state->next_entry;
357+
while (entry==NULL)
358+
{
359+
if (state->next_bucket >=hashtable->nbuckets)
360+
{
361+
/* No more entries in hashtable, so done */
362+
returnNULL;
363+
}
364+
entry=hashtable->buckets[state->next_bucket++];
365+
}
366+
state->next_entry=entry->next;
367+
368+
returnentry;
369+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp