From ade493e02d25f4807c02dcd763a25d4232b3b68d Mon Sep 17 00:00:00 2001 From: Neil Conway Date: Tue, 8 May 2007 18:56:48 +0000 Subject: [PATCH] Add a hash function for "numeric". Mark the equality operator for numerics as "oprcanhash", and make the corresponding system catalog updates. As a result, hash indexes, hashed aggregation, and hash joins can now be used with the numeric type. Bump the catversion. The only tricky aspect to doing this is writing a correct hash function: it's possible for two Numerics to be equal according to their equality operator, but have different in-memory bit patterns. To cope with this, the hash function doesn't consider the Numeric's "scale" or "sign", and explictly skips any leading or trailing zeros in the Numeric's digit buffer (the current implementation should suppress any such zeros, but it seems unwise to rely upon this). See discussion on pgsql-patches for more details. --- src/backend/utils/adt/numeric.c | 78 ++++++++++++++++++++++++++++++- src/include/catalog/catversion.h | 4 +- src/include/catalog/pg_amop.h | 4 +- src/include/catalog/pg_amproc.h | 3 +- src/include/catalog/pg_opclass.h | 3 +- src/include/catalog/pg_operator.h | 4 +- src/include/catalog/pg_opfamily.h | 3 +- src/include/catalog/pg_proc.h | 4 +- src/include/utils/builtins.h | 3 +- 9 files changed, 95 insertions(+), 11 deletions(-) diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index f173f30211..6a6f3d44af 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -14,7 +14,7 @@ * Copyright (c) 1998-2007, PostgreSQL Global Development Group * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/numeric.c,v 1.101 2007/02/27 23:48:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/numeric.c,v 1.102 2007/05/08 18:56:47 neilc Exp $ * *------------------------------------------------------------------------- */ @@ -26,6 +26,7 @@ #include #include +#include "access/hash.h" #include "catalog/pg_type.h" #include "libpq/pqformat.h" #include "utils/array.h" @@ -1149,6 +1150,81 @@ cmp_numerics(Numeric num1, Numeric num2) return result; } +Datum +hash_numeric(PG_FUNCTION_ARGS) +{ + Numeric key = PG_GETARG_NUMERIC(0); + Datum digit_hash; + Datum result; + int weight; + int start_offset; + int end_offset; + int i; + int hash_len; + + /* If it's NaN, don't try to hash the rest of the fields */ + if (NUMERIC_IS_NAN(key)) + PG_RETURN_UINT32(0); + + weight = key->n_weight; + start_offset = 0; + end_offset = 0; + + /* + * Omit any leading or trailing zeros from the input to the + * hash. The numeric implementation *should* guarantee that + * leading and trailing zeros are suppressed, but we're + * paranoid. Note that we measure the starting and ending offsets + * in units of NumericDigits, not bytes. + */ + for (i = 0; i < NUMERIC_NDIGITS(key); i++) + { + if (NUMERIC_DIGITS(key)[i] != (NumericDigit) 0) + break; + + start_offset++; + /* + * The weight is effectively the # of digits before the + * decimal point, so decrement it for each leading zero we + * skip. + */ + weight--; + } + + /* + * If there are no non-zero digits, then the value of the number + * is zero, regardless of any other fields. + */ + if (NUMERIC_NDIGITS(key) == start_offset) + PG_RETURN_UINT32(-1); + + for (i = NUMERIC_NDIGITS(key) - 1; i >= 0; i--) + { + if (NUMERIC_DIGITS(key)[i] != (NumericDigit) 0) + break; + + end_offset++; + } + + /* If we get here, there should be at least one non-zero digit */ + Assert(start_offset + end_offset < NUMERIC_NDIGITS(key)); + + /* + * Note that we don't hash on the Numeric's scale, since two + * numerics can compare equal but have different scales. We also + * don't hash on the sign, although we could: since a sign + * difference implies inequality, this shouldn't affect correctness. + */ + hash_len = NUMERIC_NDIGITS(key) - start_offset - end_offset; + digit_hash = hash_any((unsigned char *) (NUMERIC_DIGITS(key) + start_offset), + hash_len * sizeof(NumericDigit)); + + /* Mix in the weight, via XOR */ + result = digit_hash ^ weight; + + PG_RETURN_DATUM(result); +} + /* ---------------------------------------------------------------------- * diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h index f614001d37..69ef260ad3 100644 --- a/src/include/catalog/catversion.h +++ b/src/include/catalog/catversion.h @@ -37,7 +37,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.404 2007/04/15 10:56:27 ishii Exp $ + * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.405 2007/05/08 18:56:47 neilc Exp $ * *------------------------------------------------------------------------- */ @@ -53,6 +53,6 @@ */ /* yyyymmddN */ -#define CATALOG_VERSION_NO 200704151 +#define CATALOG_VERSION_NO 200705081 #endif diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h index 2b85264599..26b2ffe4ed 100644 --- a/src/include/catalog/pg_amop.h +++ b/src/include/catalog/pg_amop.h @@ -29,7 +29,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_amop.h,v 1.80 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_amop.h,v 1.81 2007/05/08 18:56:47 neilc Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -568,6 +568,8 @@ DATA(insert ( 2232 19 19 1 f 2334 405 )); DATA(insert ( 2235 1033 1033 1 f 974 405 )); /* uuid_ops */ DATA(insert ( 2969 2950 2950 1 f 2972 405 )); +/* numeric_ops */ +DATA(insert ( 1998 1700 1700 1 f 1752 405 )); /* diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h index d535e615c8..2645e89d66 100644 --- a/src/include/catalog/pg_amproc.h +++ b/src/include/catalog/pg_amproc.h @@ -22,7 +22,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_amproc.h,v 1.64 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_amproc.h,v 1.65 2007/05/08 18:56:47 neilc Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -148,6 +148,7 @@ DATA(insert ( 1990 26 26 1 453 )); DATA(insert ( 1992 30 30 1 457 )); DATA(insert ( 1995 25 25 1 400 )); DATA(insert ( 1997 1083 1083 1 452 )); +DATA(insert ( 1998 1700 1700 1 432 )); DATA(insert ( 1999 1184 1184 1 452 )); DATA(insert ( 2001 1266 1266 1 1696 )); DATA(insert ( 2040 1114 1114 1 452 )); diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h index 2df9b8241a..28fed11301 100644 --- a/src/include/catalog/pg_opclass.h +++ b/src/include/catalog/pg_opclass.h @@ -28,7 +28,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_opclass.h,v 1.75 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_opclass.h,v 1.76 2007/05/08 18:56:47 neilc Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -129,6 +129,7 @@ DATA(insert ( 405 macaddr_ops PGNSP PGUID 1985 829 t 0 )); DATA(insert ( 403 name_ops PGNSP PGUID 1986 19 t 0 )); DATA(insert ( 405 name_ops PGNSP PGUID 1987 19 t 0 )); DATA(insert ( 403 numeric_ops PGNSP PGUID 1988 1700 t 0 )); +DATA(insert ( 405 numeric_ops PGNSP PGUID 1998 1700 t 0 )); DATA(insert OID = 1981 ( 403 oid_ops PGNSP PGUID 1989 26 t 0 )); #define OID_BTREE_OPS_OID 1981 DATA(insert ( 405 oid_ops PGNSP PGUID 1990 26 t 0 )); diff --git a/src/include/catalog/pg_operator.h b/src/include/catalog/pg_operator.h index 2591b1ff7b..6848b274e4 100644 --- a/src/include/catalog/pg_operator.h +++ b/src/include/catalog/pg_operator.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_operator.h,v 1.151 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_operator.h,v 1.152 2007/05/08 18:56:47 neilc Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -675,7 +675,7 @@ DATA(insert OID = 1630 ( "!~~*" PGNSP PGUID b f f 1042 25 16 0 1629 bpcharicn /* NUMERIC type - OID's 1700-1799 */ DATA(insert OID = 1751 ( "-" PGNSP PGUID l f f 0 1700 1700 0 0 numeric_uminus - - )); -DATA(insert OID = 1752 ( "=" PGNSP PGUID b t f 1700 1700 16 1752 1753 numeric_eq eqsel eqjoinsel )); +DATA(insert OID = 1752 ( "=" PGNSP PGUID b t t 1700 1700 16 1752 1753 numeric_eq eqsel eqjoinsel )); DATA(insert OID = 1753 ( "<>" PGNSP PGUID b f f 1700 1700 16 1753 1752 numeric_ne neqsel neqjoinsel )); DATA(insert OID = 1754 ( "<" PGNSP PGUID b f f 1700 1700 16 1756 1757 numeric_lt scalarltsel scalarltjoinsel )); DATA(insert OID = 1755 ( "<=" PGNSP PGUID b f f 1700 1700 16 1757 1756 numeric_le scalarltsel scalarltjoinsel )); diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h index 3d4c0a41d0..a39e28c632 100644 --- a/src/include/catalog/pg_opfamily.h +++ b/src/include/catalog/pg_opfamily.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_opfamily.h,v 1.4 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_opfamily.h,v 1.5 2007/05/08 18:56:47 neilc Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -93,6 +93,7 @@ DATA(insert OID = 1986 ( 403 name_ops PGNSP PGUID )); #define NAME_BTREE_FAM_OID 1986 DATA(insert OID = 1987 ( 405 name_ops PGNSP PGUID )); DATA(insert OID = 1988 ( 403 numeric_ops PGNSP PGUID )); +DATA(insert OID = 1998 ( 405 numeric_ops PGNSP PGUID )); DATA(insert OID = 1989 ( 403 oid_ops PGNSP PGUID )); #define OID_BTREE_FAM_OID 1989 DATA(insert OID = 1990 ( 405 oid_ops PGNSP PGUID )); diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h index d7b048b07f..b300f9b92c 100644 --- a/src/include/catalog/pg_proc.h +++ b/src/include/catalog/pg_proc.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.454 2007/04/02 03:49:40 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.455 2007/05/08 18:56:48 neilc Exp $ * * NOTES * The script catalog/genbki.sh reads this file and generates .bki @@ -838,6 +838,8 @@ DATA(insert OID = 399 ( hashmacaddr PGNSP PGUID 12 1 0 f f t f i 1 23 "829" DESCR("hash"); DATA(insert OID = 422 ( hashinet PGNSP PGUID 12 1 0 f f t f i 1 23 "869" _null_ _null_ _null_ hashinet - _null_ )); DESCR("hash"); +DATA(insert OID = 432 ( hash_numeric PGNSP PGUID 12 1 0 f f t f i 1 23 "1700" _null_ _null_ _null_ hash_numeric - _null_ )); +DESCR("hash"); DATA(insert OID = 458 ( text_larger PGNSP PGUID 12 1 0 f f t f i 2 25 "25 25" _null_ _null_ _null_ text_larger - _null_ )); DESCR("larger of two"); DATA(insert OID = 459 ( text_smaller PGNSP PGUID 12 1 0 f f t f i 2 25 "25 25" _null_ _null_ _null_ text_smaller - _null_ )); diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h index d93599a9ae..22b10841c6 100644 --- a/src/include/utils/builtins.h +++ b/src/include/utils/builtins.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/utils/builtins.h,v 1.291 2007/04/02 03:49:41 tgl Exp $ + * $PostgreSQL: pgsql/src/include/utils/builtins.h,v 1.292 2007/05/08 18:56:48 neilc Exp $ * *------------------------------------------------------------------------- */ @@ -883,6 +883,7 @@ extern Datum int2_avg_accum(PG_FUNCTION_ARGS); extern Datum int4_avg_accum(PG_FUNCTION_ARGS); extern Datum int8_avg(PG_FUNCTION_ARGS); extern Datum width_bucket_numeric(PG_FUNCTION_ARGS); +extern Datum hash_numeric(PG_FUNCTION_ARGS); /* ri_triggers.c */ extern Datum RI_FKey_check_ins(PG_FUNCTION_ARGS); -- 2.40.0