[Ildar Musin <i.musin@postgrespro.ru>]

Hi hackers,

Following up the recent discussion on zipfian distribution I was trying
to reproduce some YCSB-like workloads. As this paper [1] describes, YCSB
uses zipfian distribution to generate keys in order simulate intensive
load on small number of records as it happens in real world applications
(e.g. blogs). One problem is that most popular records keys are
clustered together. To scatter them across the keyspace authors use
hashing, the FNV-1a hash function in particular [2].

I've read Fabien Coelho's thread on additional operators and functions.
Generally it could be possible to implement some basic hashing
algorithms right in a pgbench script using just bitwise and arithmetic
operators. But should we probably provide users with some general
purpose hash function?

The attached patch introduces hash() function which implements FNV-1a as
an example of such hashing algorithm. There are also couple of images in
the attachement that I have got from visualizing original zipfian
distribution and the hashed one. Usage example:

In psql:
create table abc as select generate_series(0, 999) as a, 0 as b;

pgbench script:
\set rnd random_zipfian(0, 1000000, 0.99)
\set key abs(hash(:rnd)) % 1000
begin;
update abc set b = b + 1 where a = :key;
end;

Any thoughts or suggestions?


[1] http://www.brianfrankcooper.net/home/publications/ycsb.pdf
[2] https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function

Thanks!
-- 
Ildar Musin
Postgres Professional: http://www.postgrespro.com
Russian Postgres Company

Attachments:

zipfian.png (image/png, 56.2K) download
  view image

hashed_zipfian.png (image/png, 75.5K) download
  view image

pgbench_hash.patch (text/plain, 1.7K) download
diff --git a/src/bin/pgbench/exprparse.y b/src/bin/pgbench/exprparse.y
index 25d5ad4..edd74ee 100644
--- a/src/bin/pgbench/exprparse.y
+++ b/src/bin/pgbench/exprparse.y
@@ -194,6 +194,9 @@ static const struct
 	{
 		"random_zipfian", 3, PGBENCH_RANDOM_ZIPFIAN
 	},
+	{
+		"hash", 1, PGBENCH_HASH
+	},
 	/* keep as last array element */
 	{
 		NULL, 0, 0
diff --git a/src/bin/pgbench/pgbench.c b/src/bin/pgbench/pgbench.c
index 7ce6f60..75897cc 100644
--- a/src/bin/pgbench/pgbench.c
+++ b/src/bin/pgbench/pgbench.c
@@ -61,6 +61,12 @@
 #define ERRCODE_UNDEFINED_TABLE  "42P01"
 
 /*
+ * FNV hashing constants
+ */
+#define FNV_PRIME 1099511628211
+#define FNV_OFFSET_BASIS 0xcbf29ce484222325
+
+/*
  * Multi-platform pthread implementations
  */
 
@@ -1850,6 +1856,33 @@ evalFunc(TState *thread, CState *st,
 				return true;
 			}
 
+			/* hashing */
+		case PGBENCH_HASH:
+			{
+				int		i;
+				int64	val;
+				int64	result;
+
+				if (!coerceToInt(&vargs[0], &val))
+					return false;
+
+				/*
+				 * Fowler–Noll–Vo hash
+				 */
+				result = FNV_OFFSET_BASIS;
+				for (i = 0; i < 8; ++i)
+				{
+					int32 octet = val & 0xff;
+
+					val = val >> 8;
+					result = result ^ octet;
+					result = result * FNV_PRIME;
+				}
+
+				setIntValue(retval, result);
+				return true;
+			}
+
 		default:
 			/* cannot get here */
 			Assert(0);
diff --git a/src/bin/pgbench/pgbench.h b/src/bin/pgbench/pgbench.h
index 83fee1a..a91e4e2 100644
--- a/src/bin/pgbench/pgbench.h
+++ b/src/bin/pgbench/pgbench.h
@@ -76,7 +76,8 @@ typedef enum PgBenchFunction
 	PGBENCH_RANDOM,
 	PGBENCH_RANDOM_GAUSSIAN,
 	PGBENCH_RANDOM_EXPONENTIAL,
-	PGBENCH_RANDOM_ZIPFIAN
+	PGBENCH_RANDOM_ZIPFIAN,
+	PGBENCH_HASH
 } PgBenchFunction;
 
 typedef struct PgBenchExpr PgBenchExpr;