Improve dynahash.c's API so that caller can specify the comparison function

as well as the hash function (formerly the comparison function was hardwired
as memcmp()).  This makes it possible to eliminate the special-purpose
hashtable management code in execGrouping.c in favor of using dynahash to
manage tuple hashtables; which is a win because dynahash knows how to expand
a hashtable when the original size estimate was too small, whereas the
special-purpose code was too stupid to do that.  (See recent gripe from
Stephan Szabo about poor performance when hash table size estimate is way
off.)  Free side benefit: when using string_hash, the default comparison
function is now strncmp() instead of memcmp().  This should eliminate some
part of the overhead associated with larger NAMEDATALEN values.

3 files changed, 54 insertions, 38 deletions

diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index af2f123d2d6..88449034fee 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: executor.h,v 1.99 2003/08/08 21:42:44 momjian Exp $
+ * $Id: executor.h,v 1.100 2003/08/19 01:13:41 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -71,8 +71,6 @@ extern TupleHashTable BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
 extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable,
 					 TupleTableSlot *slot,
 					 bool *isnew);
-extern TupleHashEntry ScanTupleHashTable(TupleHashTable hashtable,
-				   TupleHashIterator *state);
 
 /*
  * prototypes from functions in execJunk.c
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 3f163b8fdaa..8d180009bfd 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execnodes.h,v 1.103 2003/08/08 21:42:47 momjian Exp $
+ * $Id: execnodes.h,v 1.104 2003/08/19 01:13:41 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,6 +21,7 @@
 #include "nodes/bitmapset.h"
 #include "nodes/params.h"
 #include "nodes/plannodes.h"
+#include "utils/hsearch.h"
 #include "utils/tuplestore.h"
 
 
@@ -344,14 +345,14 @@ typedef struct TupleHashTableData *TupleHashTable;
 
 typedef struct TupleHashEntryData
 {
-	TupleHashEntry next;		/* next entry in same hash bucket */
-	uint32		hashkey;		/* exact hash key of this entry */
+	/* firstTuple must be the first field in this struct! */
 	HeapTuple	firstTuple;		/* copy of first tuple in this group */
 	/* there may be additional data beyond the end of this struct */
 } TupleHashEntryData;			/* VARIABLE LENGTH STRUCT */
 
 typedef struct TupleHashTableData
 {
+	HTAB	   *hashtab;		/* underlying dynahash table */
 	int			numCols;		/* number of columns in lookup key */
 	AttrNumber *keyColIdx;		/* attr numbers of key columns */
 	FmgrInfo   *eqfunctions;	/* lookup data for comparison functions */
@@ -359,19 +360,15 @@ typedef struct TupleHashTableData
 	MemoryContext tablecxt;		/* memory context containing table */
 	MemoryContext tempcxt;		/* context for function evaluations */
 	Size		entrysize;		/* actual size to make each hash entry */
-	int			nbuckets;		/* number of buckets in hash table */
-	TupleHashEntry buckets[1];	/* VARIABLE LENGTH ARRAY */
-} TupleHashTableData;			/* VARIABLE LENGTH STRUCT */
+	TupleDesc	tupdesc;		/* tuple descriptor */
+} TupleHashTableData;
 
-typedef struct
-{
-	TupleHashEntry next_entry;	/* next entry in current chain */
-	int			next_bucket;	/* next chain */
-} TupleHashIterator;
+typedef HASH_SEQ_STATUS TupleHashIterator;
 
-#define ResetTupleHashIterator(iter) \
-	((iter)->next_entry = NULL, \
-	 (iter)->next_bucket = 0)
+#define ResetTupleHashIterator(htable, iter) \
+	hash_seq_init(iter, (htable)->hashtab)
+#define ScanTupleHashTable(iter) \
+	((TupleHashEntry) hash_seq_search(iter))
 
 
 /* ----------------------------------------------------------------
diff --git a/src/include/utils/hsearch.h b/src/include/utils/hsearch.h
index 905268badc6..05d26e9a150 100644
--- a/src/include/utils/hsearch.h
+++ b/src/include/utils/hsearch.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: hsearch.h,v 1.28 2003/08/04 02:40:15 momjian Exp $
+ * $Id: hsearch.h,v 1.29 2003/08/19 01:13:41 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,6 +16,23 @@
 
 
 /*
+ * Hash and comparison functions must have these signatures.  Comparison
+ * functions return zero for match, nonzero for no match.  (The comparison
+ * function definition is designed to allow memcmp() and strncmp() to be
+ * used directly as key comparison functions.)
+ */
+typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
+typedef int (*HashCompareFunc) (const void *key1, const void *key2,
+								Size keysize);
+
+/*
+ * Space allocation function for a hashtable --- designed to match malloc().
+ * Note: there is no free function API; can't destroy a hashtable unless you
+ * use the default allocator.
+ */
+typedef void *(*HashAllocFunc) (Size request);
+
+/*
  * Constants
  *
  * A hash table has a top-level "directory", each of whose entries points
@@ -44,6 +61,7 @@
 typedef struct HASHELEMENT
 {
 	struct HASHELEMENT *link;	/* link to next entry in same bucket */
+	uint32	hashvalue;			/* hash function result for this entry */
 } HASHELEMENT;
 
 /* A hash bucket is a linked list of HASHELEMENTs */
@@ -64,8 +82,8 @@ typedef struct HASHHDR
 	long		ffactor;		/* Fill factor */
 	long		nentries;		/* Number of entries in hash table */
 	long		nsegs;			/* Number of allocated segments */
-	long		keysize;		/* hash key length in bytes */
-	long		entrysize;		/* total user element size in bytes */
+	Size		keysize;		/* hash key length in bytes */
+	Size		entrysize;		/* total user element size in bytes */
 	long		max_dsize;		/* 'dsize' limit if directory is fixed
 								 * size */
 	HASHELEMENT *freeList;		/* linked list of free elements */
@@ -83,8 +101,9 @@ typedef struct HTAB
 {
 	HASHHDR    *hctl;			/* shared control information */
 	HASHSEGMENT *dir;			/* directory of segment starts */
-	uint32		(*hash) (void *key, int keysize);		/* Hash Function */
-	void	   *(*alloc) (Size);	/* memory allocator */
+	HashValueFunc hash;			/* hash function */
+	HashCompareFunc match;		/* key comparison function */
+	HashAllocFunc alloc;		/* memory allocator */
 	MemoryContext hcxt;			/* memory context if default allocator
 								 * used */
 	char	   *tabname;		/* table name (for error messages) */
@@ -97,28 +116,30 @@ typedef struct HASHCTL
 {
 	long		ssize;			/* Segment Size */
 	long		dsize;			/* (initial) Directory Size */
-	long		ffactor;		/* Fill factor */
-	uint32		(*hash) (void *key, int keysize);		/* Hash Function */
-	long		keysize;		/* hash key length in bytes */
-	long		entrysize;		/* total user element size in bytes */
 	long		max_dsize;		/* limit to dsize if directory size is
 								 * limited */
-	void	   *(*alloc) (Size);	/* memory allocation function */
+	long		ffactor;		/* Fill factor */
+	Size		keysize;		/* hash key length in bytes */
+	Size		entrysize;		/* total user element size in bytes */
+	HashValueFunc hash;			/* hash function */
+	HashCompareFunc match;		/* key comparison function */
+	HashAllocFunc alloc;		/* memory allocator */
 	HASHSEGMENT *dir;			/* directory of segment starts */
 	HASHHDR    *hctl;			/* location of header in shared mem */
 	MemoryContext hcxt;			/* memory context to use for allocations */
 } HASHCTL;
 
 /* Flags to indicate which parameters are supplied */
-#define HASH_SEGMENT	0x002	/* Setting segment size */
-#define HASH_DIRSIZE	0x004	/* Setting directory size */
-#define HASH_FFACTOR	0x008	/* Setting fill factor */
+#define HASH_SEGMENT	0x002	/* Set segment size */
+#define HASH_DIRSIZE	0x004	/* Set directory size */
+#define HASH_FFACTOR	0x008	/* Set fill factor */
 #define HASH_FUNCTION	0x010	/* Set user defined hash function */
-#define HASH_ELEM		0x020	/* Setting key/entry size */
-#define HASH_SHARED_MEM 0x040	/* Setting shared mem const */
+#define HASH_ELEM		0x020	/* Set key/entry size */
+#define HASH_SHARED_MEM 0x040	/* Set shared mem const */
 #define HASH_ATTACH		0x080	/* Do not initialize hctl */
-#define HASH_ALLOC		0x100	/* Setting memory allocator */
-#define HASH_CONTEXT	0x200	/* Setting explicit memory context */
+#define HASH_ALLOC		0x100	/* Set memory allocator */
+#define HASH_CONTEXT	0x200	/* Set explicit memory context */
+#define HASH_COMPARE	0x400	/* Set user defined comparison function */
 
 
 /* max_dsize value to indicate expansible directory */
@@ -151,17 +172,17 @@ extern HTAB *hash_create(const char *tabname, long nelem,
 			HASHCTL *info, int flags);
 extern void hash_destroy(HTAB *hashp);
 extern void hash_stats(const char *where, HTAB *hashp);
-extern void *hash_search(HTAB *hashp, void *keyPtr, HASHACTION action,
+extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
 			bool *foundPtr);
 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
-extern long hash_estimate_size(long num_entries, long entrysize);
+extern long hash_estimate_size(long num_entries, Size entrysize);
 extern long hash_select_dirsize(long num_entries);
 
 /*
  * prototypes for functions in hashfn.c
  */
-extern uint32 string_hash(void *key, int keysize);
-extern uint32 tag_hash(void *key, int keysize);
+extern uint32 string_hash(const void *key, Size keysize);
+extern uint32 tag_hash(const void *key, Size keysize);
 
 #endif   /* HSEARCH_H */