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

Commitbff0422

Browse files
committed
Revise hash join and hash aggregation code to use the same datatype-
specific hash functions used by hash indexes, rather than the oldnot-datatype-aware ComputeHashFunc routine. This makes it safe to dohash joining on several datatypes that previously couldn't use hashing.The sets of datatypes that are hash indexable and hash joinable are nowexactly the same, whereas before each had some that weren't in the other.
1 parent0dda75f commitbff0422

File tree

27 files changed

+490
-233
lines changed

27 files changed

+490
-233
lines changed

‎doc/src/sgml/catalogs.sgml

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
<!--
22
Documentation of the system catalogs, directed toward PostgreSQL developers
3-
$Header: /cvsroot/pgsql/doc/src/sgml/catalogs.sgml,v 2.71 2003/05/28 16:03:55 tgl Exp $
3+
$Header: /cvsroot/pgsql/doc/src/sgml/catalogs.sgml,v 2.72 2003/06/22 22:04:54 tgl Exp $
44
-->
55

66
<chapter id="catalogs">
@@ -2525,7 +2525,7 @@
25252525
<entry><structfield>oprcanhash</structfield></entry>
25262526
<entry><type>bool</type></entry>
25272527
<entry></entry>
2528-
<entry>This operator supports hash joins.</entry>
2528+
<entry>This operator supports hash joins</entry>
25292529
</row>
25302530

25312531
<row>

‎doc/src/sgml/xfunc.sgml

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$Header: /cvsroot/pgsql/doc/src/sgml/xfunc.sgml,v 1.68 2003/05/29 20:40:36 tgl Exp $
2+
$Header: /cvsroot/pgsql/doc/src/sgml/xfunc.sgml,v 1.69 2003/06/22 22:04:54 tgl Exp $
33
-->
44

55
<sect1 id="xfunc">
@@ -1442,11 +1442,10 @@ concat_text(PG_FUNCTION_ARGS)
14421442
<listitem>
14431443
<para>
14441444
Always zero the bytes of your structures using
1445-
<function>memset</function> or <function>bzero</function>.
1446-
Several routines (such as the hash access method, hash joins,
1447-
and the sort algorithm) compute functions of the raw bits
1448-
contained in your structure. Even if you initialize all
1449-
fields of your structure, there may be several bytes of
1445+
<function>memset</function>. Without this, it's difficult to
1446+
support hash indexes or hash joins, as you must pick out only
1447+
the significant bits of your data structure to compute a hash.
1448+
Even if you initialize all fields of your structure, there may be
14501449
alignment padding (holes in the structure) that may contain
14511450
garbage values.
14521451
</para>

‎doc/src/sgml/xoper.sgml

Lines changed: 23 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$Header: /cvsroot/pgsql/doc/src/sgml/xoper.sgml,v 1.23 2003/04/10 01:22:45 petere Exp $
2+
$Header: /cvsroot/pgsql/doc/src/sgml/xoper.sgml,v 1.24 2003/06/2222:04:54 tgl Exp $
33
-->
44

55
<sect1 id="xoper">
@@ -315,46 +315,34 @@ table1.column1 OP table2.column2
315315
same hash code. If two values get put in different hash buckets, the
316316
join will never compare them at all, implicitly assuming that the
317317
result of the join operator must be false. So it never makes sense
318-
to specify <literal>HASHES</literal> for operators that do not represent equality.
318+
to specify <literal>HASHES</literal> for operators that do not represent
319+
equality.
319320
</para>
320321

321322
<para>
322-
In fact, logical equality is not good enough either; the operator
323-
had better represent pure bitwise equality, because the hash
324-
function will be computed on the memory representation of the
325-
values regardless of what the bits mean. For example, the
326-
polygon operator <literal>~=</literal>, which checks whether two
327-
polygons are the same, is not bitwise equality, because two
328-
polygons can be considered the same even if their vertices are
329-
specified in a different order. What this means is that a join
330-
using <literal>~=</literal> between polygon fields would yield
331-
different results if implemented as a hash join than if
332-
implemented another way, because a large fraction of the pairs
333-
that should match will hash to different values and will never be
334-
compared by the hash join. But if the optimizer chooses to use a
335-
different kind of join, all the pairs that the operator
336-
<literal>~=</literal> says are the same will be found. We don't
337-
want that kind of inconsistency, so we don't mark the polygon
338-
operator <literal>~=</literal> as hashable.
323+
To be marked <literal>HASHES</literal>, the join operator must appear
324+
in a hash index operator class. This is not enforced when you create
325+
the operator, since of course the referencing operator class couldn't
326+
exist yet. But attempts to use the operator in hash joins will fail
327+
at runtime if no such operator class exists. The system needs the
328+
operator class to find the datatype-specific hash function for the
329+
operator's input datatype. Of course, you must also supply a suitable
330+
hash function before you can create the operator class.
339331
</para>
340332

341333
<para>
342-
There are also machine-dependent ways in which a hash join might fail
343-
to do the right thing. For example, if your data type
344-
is a structure in which there may be uninteresting pad bits, it's unsafe
345-
to mark the equality operator <literal>HASHES</>. (Unless you write
346-
your other operators and functions to ensure that the unused bits are always zero, which is the recommended strategy.)
347-
Another example is that the floating-point data types are unsafe for hash
348-
joins. On machines that meet the <acronym>IEEE</> floating-point standard, negative
349-
zero and positive zero are different values (different bit patterns) but
350-
they are defined to compare equal. So, if the equality operator on floating-point data types were marked
351-
<literal>HASHES</>, a negative zero and a positive zero would probably not be matched up
352-
by a hash join, but they would be matched up by any other join process.
353-
</para>
354-
355-
<para>
356-
The bottom line is that you should probably only use <literal>HASHES</literal> for
357-
equality operators that are (or could be) implemented by <function>memcmp()</function>.
334+
Care should be exercised when preparing a hash function, because there
335+
are machine-dependent ways in which it might fail to do the right thing.
336+
For example, if your data type is a structure in which there may be
337+
uninteresting pad bits, you can't simply pass the whole structure to
338+
<function>hash_any</>. (Unless you write your other operators and
339+
functions to ensure that the unused bits are always zero, which is the
340+
recommended strategy.)
341+
Another example is that on machines that meet the <acronym>IEEE</>
342+
floating-point standard, negative zero and positive zero are different
343+
values (different bit patterns) but they are defined to compare equal.
344+
If a float value might contain negative zero then extra steps are needed
345+
to ensure it generates the same hash value as positive zero.
358346
</para>
359347

360348
<note>

‎src/backend/access/hash/hashfunc.c

Lines changed: 38 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/access/hash/hashfunc.c,v 1.35 2002/09/04 20:31:09 momjian Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/access/hash/hashfunc.c,v 1.36 2003/06/22 22:04:54 tgl Exp $
1212
*
1313
* NOTES
1414
* These functions are stored in pg_amproc.For each operator class
@@ -22,6 +22,7 @@
2222
#include"access/hash.h"
2323

2424

25+
/* Note: this is used for both "char" and boolean datatypes */
2526
Datum
2627
hashchar(PG_FUNCTION_ARGS)
2728
{
@@ -58,6 +59,14 @@ hashfloat4(PG_FUNCTION_ARGS)
5859
{
5960
float4key=PG_GETARG_FLOAT4(0);
6061

62+
/*
63+
* On IEEE-float machines, minus zero and zero have different bit patterns
64+
* but should compare as equal. We must ensure that they have the same
65+
* hash value, which is most easily done this way:
66+
*/
67+
if (key== (float4)0)
68+
PG_RETURN_UINT32(0);
69+
6170
returnhash_any((unsignedchar*)&key,sizeof(key));
6271
}
6372

@@ -66,6 +75,14 @@ hashfloat8(PG_FUNCTION_ARGS)
6675
{
6776
float8key=PG_GETARG_FLOAT8(0);
6877

78+
/*
79+
* On IEEE-float machines, minus zero and zero have different bit patterns
80+
* but should compare as equal. We must ensure that they have the same
81+
* hash value, which is most easily done this way:
82+
*/
83+
if (key== (float8)0)
84+
PG_RETURN_UINT32(0);
85+
6986
returnhash_any((unsignedchar*)&key,sizeof(key));
7087
}
7188

@@ -77,11 +94,6 @@ hashoidvector(PG_FUNCTION_ARGS)
7794
returnhash_any((unsignedchar*)key,INDEX_MAX_KEYS*sizeof(Oid));
7895
}
7996

80-
/*
81-
* Note: hashint2vector currently can't be used as a user hash table
82-
* hash function, because it has no pg_proc entry.We only need it
83-
* for catcache indexing.
84-
*/
8597
Datum
8698
hashint2vector(PG_FUNCTION_ARGS)
8799
{
@@ -102,6 +114,26 @@ hashname(PG_FUNCTION_ARGS)
102114
returnhash_any((unsignedchar*)key,keylen);
103115
}
104116

117+
Datum
118+
hashtext(PG_FUNCTION_ARGS)
119+
{
120+
text*key=PG_GETARG_TEXT_P(0);
121+
Datumresult;
122+
123+
/*
124+
* Note: this is currently identical in behavior to hashvarlena,
125+
* but it seems likely that we may need to do something different
126+
* in non-C locales. (See also hashbpchar, if so.)
127+
*/
128+
result=hash_any((unsignedchar*)VARDATA(key),
129+
VARSIZE(key)-VARHDRSZ);
130+
131+
/* Avoid leaking memory for toasted inputs */
132+
PG_FREE_IF_COPY(key,0);
133+
134+
returnresult;
135+
}
136+
105137
/*
106138
* hashvarlena() can be used for any varlena datatype in which there are
107139
* no non-significant bits, ie, distinct bitpatterns never compare as equal.

‎src/backend/executor/execGrouping.c

Lines changed: 51 additions & 72 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.2 2003/01/1204:03:34 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.3 2003/06/22 22:04:54 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -19,6 +19,8 @@
1919
#include"executor/executor.h"
2020
#include"parser/parse_oper.h"
2121
#include"utils/memutils.h"
22+
#include"utils/lsyscache.h"
23+
#include"utils/syscache.h"
2224

2325

2426
/*****************************************************************************
@@ -213,76 +215,46 @@ execTuplesMatchPrepare(TupleDesc tupdesc,
213215
returneqfunctions;
214216
}
215217

216-
217-
/*****************************************************************************
218-
*Utility routines for hashing
219-
*****************************************************************************/
220-
221218
/*
222-
* ComputeHashFunc
219+
* execTuplesHashPrepare
220+
*Look up the equality and hashing functions needed for a TupleHashTable.
223221
*
224-
*the hash function for hash joins (also used for hash aggregation)
225-
*
226-
*XXX this probably ought to be replaced with datatype-specific
227-
*hash functions, such as those already implemented for hash indexes.
222+
* This is similar to execTuplesMatchPrepare, but we also need to find the
223+
* hash functions associated with the equality operators. *eqfunctions and
224+
* *hashfunctions receive the palloc'd result arrays.
228225
*/
229-
uint32
230-
ComputeHashFunc(Datumkey,inttypLen,boolbyVal)
226+
void
227+
execTuplesHashPrepare(TupleDesctupdesc,
228+
intnumCols,
229+
AttrNumber*matchColIdx,
230+
FmgrInfo**eqfunctions,
231+
FmgrInfo**hashfunctions)
231232
{
232-
unsignedchar*k;
233+
inti;
233234

234-
if (byVal)
235-
{
236-
/*
237-
* If it's a by-value data type, just hash the whole Datum value.
238-
* This assumes that datatypes narrower than Datum are
239-
* consistently padded (either zero-extended or sign-extended, but
240-
* not random bits) to fill Datum; see the XXXGetDatum macros in
241-
* postgres.h. NOTE: it would not work to do hash_any(&key, len)
242-
* since this would get the wrong bytes on a big-endian machine.
243-
*/
244-
k= (unsignedchar*)&key;
245-
typLen=sizeof(Datum);
246-
}
247-
else
235+
*eqfunctions= (FmgrInfo*)palloc(numCols*sizeof(FmgrInfo));
236+
*hashfunctions= (FmgrInfo*)palloc(numCols*sizeof(FmgrInfo));
237+
238+
for (i=0;i<numCols;i++)
248239
{
249-
if (typLen>0)
250-
{
251-
/* fixed-width pass-by-reference type */
252-
k= (unsignedchar*)DatumGetPointer(key);
253-
}
254-
elseif (typLen==-1)
255-
{
256-
/*
257-
* It's a varlena type, so 'key' points to a "struct varlena".
258-
* NOTE: VARSIZE returns the "real" data length plus the
259-
* sizeof the "vl_len" attribute of varlena (the length
260-
* information). 'key' points to the beginning of the varlena
261-
* struct, so we have to use "VARDATA" to find the beginning
262-
* of the "real" data.Also, we have to be careful to detoast
263-
* the datum if it's toasted. (We don't worry about freeing
264-
* the detoasted copy; that happens for free when the
265-
* per-tuple memory context is reset in ExecHashGetBucket.)
266-
*/
267-
structvarlena*vkey=PG_DETOAST_DATUM(key);
268-
269-
typLen=VARSIZE(vkey)-VARHDRSZ;
270-
k= (unsignedchar*)VARDATA(vkey);
271-
}
272-
elseif (typLen==-2)
273-
{
274-
/* It's a null-terminated C string */
275-
typLen=strlen(DatumGetCString(key))+1;
276-
k= (unsignedchar*)DatumGetPointer(key);
277-
}
278-
else
279-
{
280-
elog(ERROR,"ComputeHashFunc: Invalid typLen %d",typLen);
281-
k=NULL;/* keep compiler quiet */
282-
}
240+
AttrNumberatt=matchColIdx[i];
241+
Oidtypid=tupdesc->attrs[att-1]->atttypid;
242+
Operatoroptup;
243+
Oideq_opr;
244+
Oideq_function;
245+
Oidhash_function;
246+
247+
optup=equality_oper(typid, false);
248+
eq_opr=oprid(optup);
249+
eq_function=oprfuncid(optup);
250+
ReleaseSysCache(optup);
251+
hash_function=get_op_hash_function(eq_opr);
252+
if (!OidIsValid(hash_function))
253+
elog(ERROR,"Could not find hash function for hash operator %u",
254+
eq_opr);
255+
fmgr_info(eq_function,&(*eqfunctions)[i]);
256+
fmgr_info(hash_function,&(*hashfunctions)[i]);
283257
}
284-
285-
returnDatumGetUInt32(hash_any(k,typLen));
286258
}
287259

288260

@@ -299,19 +271,21 @@ ComputeHashFunc(Datum key, int typLen, bool byVal)
299271
*
300272
*numCols, keyColIdx: identify the tuple fields to use as lookup key
301273
*eqfunctions: equality comparison functions to use
274+
*hashfunctions: datatype-specific hashing functions to use
302275
*nbuckets: number of buckets to make
303276
*entrysize: size of each entry (at least sizeof(TupleHashEntryData))
304277
*tablecxt: memory context in which to store table and table entries
305278
*tempcxt: short-lived context for evaluation hash and comparison functions
306279
*
307-
* Theeqfunctions array may be made withexecTuplesMatchPrepare().
280+
* Thefunction arrays may be made withexecTuplesHashPrepare().
308281
*
309-
* Note that keyColIdxandeqfunctions must be allocated in storage that
310-
* will live as long as the hashtable does.
282+
* Note that keyColIdx, eqfunctions,andhashfunctions must be allocated in
283+
*storage thatwill live as long as the hashtable does.
311284
*/
312285
TupleHashTable
313286
BuildTupleHashTable(intnumCols,AttrNumber*keyColIdx,
314287
FmgrInfo*eqfunctions,
288+
FmgrInfo*hashfunctions,
315289
intnbuckets,Sizeentrysize,
316290
MemoryContexttablecxt,MemoryContexttempcxt)
317291
{
@@ -328,6 +302,7 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
328302
hashtable->numCols=numCols;
329303
hashtable->keyColIdx=keyColIdx;
330304
hashtable->eqfunctions=eqfunctions;
305+
hashtable->hashfunctions=hashfunctions;
331306
hashtable->tablecxt=tablecxt;
332307
hashtable->tempcxt=tempcxt;
333308
hashtable->entrysize=entrysize;
@@ -375,11 +350,15 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
375350
hashkey= (hashkey <<1) | ((hashkey&0x80000000) ?1 :0);
376351

377352
attr=heap_getattr(tuple,att,tupdesc,&isNull);
378-
if (isNull)
379-
continue;/* treat nulls as having hash key 0 */
380-
hashkey ^=ComputeHashFunc(attr,
381-
(int)tupdesc->attrs[att-1]->attlen,
382-
tupdesc->attrs[att-1]->attbyval);
353+
354+
if (!isNull)/* treat nulls as having hash key 0 */
355+
{
356+
uint32hkey;
357+
358+
hkey=DatumGetUInt32(FunctionCall1(&hashtable->hashfunctions[i],
359+
attr));
360+
hashkey ^=hkey;
361+
}
383362
}
384363
bucketno=hashkey % (uint32)hashtable->nbuckets;
385364

0 commit comments

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