v33-0001-Add-equalimage-B-Tree-opclass-support-functions.patch

From 5696e551583712168a62f9dd9bed2c7bdcbfccf6 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Wed, 12 Feb 2020 10:17:25 -0800
Subject: [PATCH v33 1/4] Add equalimage B-Tree opclass support functions.

Invent the concept of a B-Tree equalimage ("equality is image equality")
support function, registered as support function 4.  A B-Tree operator
class may use such a support function to indicate that it is safe (or
not safe) to replace its equality operator with a generic "image
equality" function.  This means that two equal datums can only be equal
when bitwise identical after detoasting.  This is infrastructure for an
upcoming patch that adds B-Tree deduplication, though it is anticipated
that it will eventually be used in other areas.

Add an equalimage routine to almost all of the existing B-Tree
opclasses.  Most can just use a generic equalimage  routine that
indicates that deduplication is safe unconditionally.

Author: Peter Geoghegan, Anastasia Lubennikova
Discussion: https://postgr.es/m/CAH2-Wzn3Ee49Gmxb7V1VJ3-AC8fWn-Fr8pfWQebHe8rYRxt5OQ@mail.gmail.com
---
 src/include/access/nbtree.h                 | 23 +++++--
 src/include/catalog/pg_amproc.dat           | 62 +++++++++++++++++
 src/include/catalog/pg_proc.dat             |  8 +++
 src/backend/access/nbtree/nbtutils.c        | 73 +++++++++++++++++++++
 src/backend/access/nbtree/nbtvalidate.c     |  8 ++-
 src/backend/commands/opclasscmds.c          | 30 ++++++++-
 src/backend/utils/adt/datum.c               | 17 +++++
 src/backend/utils/adt/name.c                | 31 +++++++++
 src/backend/utils/adt/varchar.c             | 15 +++++
 src/backend/utils/adt/varlena.c             | 15 +++++
 doc/src/sgml/btree.sgml                     | 59 ++++++++++++++++-
 doc/src/sgml/ref/alter_opfamily.sgml        |  7 +-
 doc/src/sgml/xindex.sgml                    | 19 ++++--
 src/test/regress/expected/alter_generic.out |  4 +-
 src/test/regress/expected/opr_sanity.out    | 35 ++++++++++
 src/test/regress/sql/opr_sanity.sql         | 15 +++++
 16 files changed, 400 insertions(+), 21 deletions(-)

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 20ace69dab..d520066914 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -380,19 +380,29 @@ typedef struct BTMetaPageData
  *	must return < 0, 0, > 0, respectively, in these three cases.
  *
  *	To facilitate accelerated sorting, an operator class may choose to
- *	offer a second procedure (BTSORTSUPPORT_PROC).  For full details, see
- *	src/include/utils/sortsupport.h.
+ *	offer a sortsupport amproc procedure (BTSORTSUPPORT_PROC).  For full
+ *	details, see src/include/utils/sortsupport.h.
  *
  *	To support window frames defined by "RANGE offset PRECEDING/FOLLOWING",
- *	an operator class may choose to offer a third amproc procedure
- *	(BTINRANGE_PROC), independently of whether it offers sortsupport.
- *	For full details, see doc/src/sgml/btree.sgml.
+ *	an operator class may choose to offer an in_range amproc procedure
+ *	(BTINRANGE_PROC).  For full details, see doc/src/sgml/btree.sgml.
+ *
+ *	To support B-Tree deduplication (and possibly other optimizations), an
+ *	operator class may choose to offer an "equality is image equality" proc
+ *	(BTEQUALIMAGE_PROC).  When the procedure returns true, core code can
+ *	assume that any two opclass-equal datums must also be equivalent in
+ *	every way.  When the procedure returns false (or when there is no
+ *	procedure for an opclass), deduplication cannot proceed because equal
+ *	index tuples might be visibly different (e.g. btree/numeric_ops indexes
+ *	can't support deduplication because "5" is equal to but distinct from
+ *	"5.00").  For full details, see doc/src/sgml/btree.sgml.
  */
 
 #define BTORDER_PROC		1
 #define BTSORTSUPPORT_PROC	2
 #define BTINRANGE_PROC		3
-#define BTNProcs			3
+#define BTEQUALIMAGE_PROC	4
+#define BTNProcs			4
 
 /*
  *	We need to be able to tell the difference between read and write
@@ -829,6 +839,7 @@ extern bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page,
 							OffsetNumber offnum);
 extern void _bt_check_third_page(Relation rel, Relation heap,
 								 bool needheaptidspace, Page page, IndexTuple newtup);
+extern bool _bt_allequalimage(Relation rel, bool debugmessage);
 
 /*
  * prototypes for functions in nbtvalidate.c
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index c67768fcab..4728479978 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -17,23 +17,35 @@
   amprocrighttype => 'anyarray', amprocnum => '1', amproc => 'btarraycmp' },
 { amprocfamily => 'btree/bit_ops', amproclefttype => 'bit',
   amprocrighttype => 'bit', amprocnum => '1', amproc => 'bitcmp' },
+{ amprocfamily => 'btree/bit_ops', amproclefttype => 'bit',
+  amprocrighttype => 'bit', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/bool_ops', amproclefttype => 'bool',
   amprocrighttype => 'bool', amprocnum => '1', amproc => 'btboolcmp' },
+{ amprocfamily => 'btree/bool_ops', amproclefttype => 'bool',
+  amprocrighttype => 'bool', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/bpchar_ops', amproclefttype => 'bpchar',
   amprocrighttype => 'bpchar', amprocnum => '1', amproc => 'bpcharcmp' },
 { amprocfamily => 'btree/bpchar_ops', amproclefttype => 'bpchar',
   amprocrighttype => 'bpchar', amprocnum => '2',
   amproc => 'bpchar_sortsupport' },
+{ amprocfamily => 'btree/bpchar_ops', amproclefttype => 'bpchar',
+  amprocrighttype => 'bpchar', amprocnum => '4', amproc => 'bpchar_equalimage' },
 { amprocfamily => 'btree/bytea_ops', amproclefttype => 'bytea',
   amprocrighttype => 'bytea', amprocnum => '1', amproc => 'byteacmp' },
 { amprocfamily => 'btree/bytea_ops', amproclefttype => 'bytea',
   amprocrighttype => 'bytea', amprocnum => '2', amproc => 'bytea_sortsupport' },
+{ amprocfamily => 'btree/bytea_ops', amproclefttype => 'bytea',
+  amprocrighttype => 'bytea', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/char_ops', amproclefttype => 'char',
   amprocrighttype => 'char', amprocnum => '1', amproc => 'btcharcmp' },
+{ amprocfamily => 'btree/char_ops', amproclefttype => 'char',
+  amprocrighttype => 'char', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'date', amprocnum => '1', amproc => 'date_cmp' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'date', amprocnum => '2', amproc => 'date_sortsupport' },
+{ amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
+  amprocrighttype => 'date', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'timestamp', amprocnum => '1',
   amproc => 'date_cmp_timestamp' },
@@ -45,6 +57,9 @@
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamp',
   amprocrighttype => 'timestamp', amprocnum => '2',
   amproc => 'timestamp_sortsupport' },
+{ amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamp',
+  amprocrighttype => 'timestamp', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamp',
   amprocrighttype => 'date', amprocnum => '1', amproc => 'timestamp_cmp_date' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamp',
@@ -56,6 +71,9 @@
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamptz',
   amprocrighttype => 'timestamptz', amprocnum => '2',
   amproc => 'timestamp_sortsupport' },
+{ amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamptz',
+  amprocrighttype => 'timestamptz', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'timestamptz',
   amprocrighttype => 'date', amprocnum => '1',
   amproc => 'timestamptz_cmp_date' },
@@ -96,10 +114,15 @@
 { amprocfamily => 'btree/network_ops', amproclefttype => 'inet',
   amprocrighttype => 'inet', amprocnum => '2',
   amproc => 'network_sortsupport' },
+{ amprocfamily => 'btree/network_ops', amproclefttype => 'inet',
+  amprocrighttype => 'inet', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
   amprocrighttype => 'int2', amprocnum => '1', amproc => 'btint2cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
   amprocrighttype => 'int2', amprocnum => '2', amproc => 'btint2sortsupport' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
+  amprocrighttype => 'int2', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
   amprocrighttype => 'int4', amprocnum => '1', amproc => 'btint24cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
@@ -117,6 +140,8 @@
   amprocrighttype => 'int4', amprocnum => '1', amproc => 'btint4cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
   amprocrighttype => 'int4', amprocnum => '2', amproc => 'btint4sortsupport' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
+  amprocrighttype => 'int4', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
   amprocrighttype => 'int8', amprocnum => '1', amproc => 'btint48cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
@@ -134,6 +159,8 @@
   amprocrighttype => 'int8', amprocnum => '1', amproc => 'btint8cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
   amprocrighttype => 'int8', amprocnum => '2', amproc => 'btint8sortsupport' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
+  amprocrighttype => 'int8', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
   amprocrighttype => 'int4', amprocnum => '1', amproc => 'btint84cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
@@ -146,11 +173,17 @@
 { amprocfamily => 'btree/interval_ops', amproclefttype => 'interval',
   amprocrighttype => 'interval', amprocnum => '3',
   amproc => 'in_range(interval,interval,interval,bool,bool)' },
+{ amprocfamily => 'btree/interval_ops', amproclefttype => 'interval',
+  amprocrighttype => 'interval', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/macaddr_ops', amproclefttype => 'macaddr',
   amprocrighttype => 'macaddr', amprocnum => '1', amproc => 'macaddr_cmp' },
 { amprocfamily => 'btree/macaddr_ops', amproclefttype => 'macaddr',
   amprocrighttype => 'macaddr', amprocnum => '2',
   amproc => 'macaddr_sortsupport' },
+{ amprocfamily => 'btree/macaddr_ops', amproclefttype => 'macaddr',
+  amprocrighttype => 'macaddr', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/numeric_ops', amproclefttype => 'numeric',
   amprocrighttype => 'numeric', amprocnum => '1', amproc => 'numeric_cmp' },
 { amprocfamily => 'btree/numeric_ops', amproclefttype => 'numeric',
@@ -163,60 +196,89 @@
   amprocrighttype => 'oid', amprocnum => '1', amproc => 'btoidcmp' },
 { amprocfamily => 'btree/oid_ops', amproclefttype => 'oid',
   amprocrighttype => 'oid', amprocnum => '2', amproc => 'btoidsortsupport' },
+{ amprocfamily => 'btree/oid_ops', amproclefttype => 'oid',
+  amprocrighttype => 'oid', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/oidvector_ops', amproclefttype => 'oidvector',
   amprocrighttype => 'oidvector', amprocnum => '1',
   amproc => 'btoidvectorcmp' },
+{ amprocfamily => 'btree/oidvector_ops', amproclefttype => 'oidvector',
+  amprocrighttype => 'oidvector', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'text',
   amprocrighttype => 'text', amprocnum => '1', amproc => 'bttextcmp' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'text',
   amprocrighttype => 'text', amprocnum => '2', amproc => 'bttextsortsupport' },
+{ amprocfamily => 'btree/text_ops', amproclefttype => 'text',
+  amprocrighttype => 'text', amprocnum => '4', amproc => 'bttextequalimage' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'name',
   amprocrighttype => 'name', amprocnum => '1', amproc => 'btnamecmp' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'name',
   amprocrighttype => 'name', amprocnum => '2', amproc => 'btnamesortsupport' },
+{ amprocfamily => 'btree/text_ops', amproclefttype => 'name',
+  amprocrighttype => 'name', amprocnum => '4', amproc => 'btnameequalimage' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'name',
   amprocrighttype => 'text', amprocnum => '1', amproc => 'btnametextcmp' },
 { amprocfamily => 'btree/text_ops', amproclefttype => 'text',
   amprocrighttype => 'name', amprocnum => '1', amproc => 'bttextnamecmp' },
 { amprocfamily => 'btree/time_ops', amproclefttype => 'time',
   amprocrighttype => 'time', amprocnum => '1', amproc => 'time_cmp' },
+{ amprocfamily => 'btree/time_ops', amproclefttype => 'time',
+  amprocrighttype => 'time', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/time_ops', amproclefttype => 'time',
   amprocrighttype => 'interval', amprocnum => '3',
   amproc => 'in_range(time,time,interval,bool,bool)' },
 { amprocfamily => 'btree/timetz_ops', amproclefttype => 'timetz',
   amprocrighttype => 'timetz', amprocnum => '1', amproc => 'timetz_cmp' },
+{ amprocfamily => 'btree/timetz_ops', amproclefttype => 'timetz',
+  amprocrighttype => 'timetz', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/timetz_ops', amproclefttype => 'timetz',
   amprocrighttype => 'interval', amprocnum => '3',
   amproc => 'in_range(timetz,timetz,interval,bool,bool)' },
 { amprocfamily => 'btree/varbit_ops', amproclefttype => 'varbit',
   amprocrighttype => 'varbit', amprocnum => '1', amproc => 'varbitcmp' },
+{ amprocfamily => 'btree/varbit_ops', amproclefttype => 'varbit',
+  amprocrighttype => 'varbit', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/text_pattern_ops', amproclefttype => 'text',
   amprocrighttype => 'text', amprocnum => '1', amproc => 'bttext_pattern_cmp' },
 { amprocfamily => 'btree/text_pattern_ops', amproclefttype => 'text',
   amprocrighttype => 'text', amprocnum => '2',
   amproc => 'bttext_pattern_sortsupport' },
+{ amprocfamily => 'btree/text_pattern_ops', amproclefttype => 'text',
+  amprocrighttype => 'text', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/bpchar_pattern_ops', amproclefttype => 'bpchar',
   amprocrighttype => 'bpchar', amprocnum => '1',
   amproc => 'btbpchar_pattern_cmp' },
 { amprocfamily => 'btree/bpchar_pattern_ops', amproclefttype => 'bpchar',
   amprocrighttype => 'bpchar', amprocnum => '2',
   amproc => 'btbpchar_pattern_sortsupport' },
+{ amprocfamily => 'btree/bpchar_pattern_ops', amproclefttype => 'bpchar',
+  amprocrighttype => 'bpchar', amprocnum => '4',
+  amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/money_ops', amproclefttype => 'money',
   amprocrighttype => 'money', amprocnum => '1', amproc => 'cash_cmp' },
 { amprocfamily => 'btree/tid_ops', amproclefttype => 'tid',
   amprocrighttype => 'tid', amprocnum => '1', amproc => 'bttidcmp' },
+{ amprocfamily => 'btree/tid_ops', amproclefttype => 'tid',
+  amprocrighttype => 'tid', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/uuid_ops', amproclefttype => 'uuid',
   amprocrighttype => 'uuid', amprocnum => '1', amproc => 'uuid_cmp' },
 { amprocfamily => 'btree/uuid_ops', amproclefttype => 'uuid',
   amprocrighttype => 'uuid', amprocnum => '2', amproc => 'uuid_sortsupport' },
+{ amprocfamily => 'btree/uuid_ops', amproclefttype => 'uuid',
+  amprocrighttype => 'uuid', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/record_ops', amproclefttype => 'record',
   amprocrighttype => 'record', amprocnum => '1', amproc => 'btrecordcmp' },
 { amprocfamily => 'btree/record_image_ops', amproclefttype => 'record',
   amprocrighttype => 'record', amprocnum => '1', amproc => 'btrecordimagecmp' },
 { amprocfamily => 'btree/pg_lsn_ops', amproclefttype => 'pg_lsn',
   amprocrighttype => 'pg_lsn', amprocnum => '1', amproc => 'pg_lsn_cmp' },
+{ amprocfamily => 'btree/pg_lsn_ops', amproclefttype => 'pg_lsn',
+  amprocrighttype => 'pg_lsn', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/macaddr8_ops', amproclefttype => 'macaddr8',
   amprocrighttype => 'macaddr8', amprocnum => '1', amproc => 'macaddr8_cmp' },
+{ amprocfamily => 'btree/macaddr8_ops', amproclefttype => 'macaddr8',
+  amprocrighttype => 'macaddr8', amprocnum => '4', amproc => 'btequalimagedatum' },
 { amprocfamily => 'btree/enum_ops', amproclefttype => 'anyenum',
   amprocrighttype => 'anyenum', amprocnum => '1', amproc => 'enum_cmp' },
 { amprocfamily => 'btree/tsvector_ops', amproclefttype => 'tsvector',
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 226c904c04..c8fcff0fde 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1007,12 +1007,16 @@
 { oid => '3135', descr => 'sort support',
   proname => 'btnamesortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'btnamesortsupport' },
+{ oid => '8504', descr => 'equal image', proname => 'btnameequalimage',
+  prorettype => 'bool', proargtypes => '', prosrc => 'btnameequalimage' },
 { oid => '360', descr => 'less-equal-greater',
   proname => 'bttextcmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'text text', prosrc => 'bttextcmp' },
 { oid => '3255', descr => 'sort support',
   proname => 'bttextsortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'bttextsortsupport' },
+{ oid => '8505', descr => 'equal image', proname => 'bttextequalimage',
+  prorettype => 'bool', proargtypes => '', prosrc => 'bttextequalimage' },
 { oid => '377', descr => 'less-equal-greater',
   proname => 'cash_cmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'money money', prosrc => 'cash_cmp' },
@@ -2091,6 +2095,8 @@
 { oid => '3328', descr => 'sort support',
   proname => 'bpchar_sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'bpchar_sortsupport' },
+{ oid => '8506', descr => 'equal image', proname => 'bpchar_equalimage',
+  prorettype => 'bool', proargtypes => '', prosrc => 'bpchar_equalimage' },
 { oid => '1080', descr => 'hash',
   proname => 'hashbpchar', prorettype => 'int4', proargtypes => 'bpchar',
   prosrc => 'hashbpchar' },
@@ -9484,6 +9490,8 @@
 { oid => '3187', descr => 'less-equal-greater based on byte images',
   proname => 'btrecordimagecmp', prorettype => 'int4',
   proargtypes => 'record record', prosrc => 'btrecordimagecmp' },
+{ oid => '8507', descr => 'equal image', proname => 'btequalimagedatum',
+  prorettype => 'bool', proargtypes => '', prosrc => 'btequalimagedatum' },
 
 # Extensions
 { oid => '3082', descr => 'list available extensions',
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 5ab4e712f1..c9f0402f8e 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -20,6 +20,7 @@
 #include "access/nbtree.h"
 #include "access/reloptions.h"
 #include "access/relscan.h"
+#include "catalog/catalog.h"
 #include "commands/progress.h"
 #include "lib/qunique.h"
 #include "miscadmin.h"
@@ -2566,3 +2567,75 @@ _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
 					 "or use full text indexing."),
 			 errtableconstraint(heap, RelationGetRelationName(rel))));
 }
+
+/*
+ * Are all attributes in rel "equality is image equality" attributes?
+ *
+ * We use each attribute's BTEQUALIMAGE_PROC opclass procedure.  If any
+ * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
+ * return false; otherwise we return true.
+ *
+ * Returned boolean value is stored in index metapage during index builds.
+ * Deduplication can only be used when we return true.
+ */
+bool
+_bt_allequalimage(Relation rel, bool debugmessage)
+{
+	bool		allequalimage = true;
+
+	/* INCLUDE indexes don't support deduplication */
+	if (IndexRelationGetNumberOfAttributes(rel) !=
+		IndexRelationGetNumberOfKeyAttributes(rel))
+		return false;
+
+	/*
+	 * There is no special reason why deduplication cannot work with system
+	 * relations (i.e. with system catalog indexes and TOAST indexes).  We
+	 * deem deduplication unsafe for these indexes all the same, since the
+	 * alternative is to force users to always use deduplication, without
+	 * being able to opt out.  (ALTER INDEX is not supported with system
+	 * indexes, so users would have no way to set the deduplicate_items
+	 * storage parameter to 'off'.)
+	 */
+	if (IsSystemRelation(rel))
+		return false;
+
+	for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
+	{
+		Oid			opfamily = rel->rd_opfamily[i];
+		Oid			opcintype = rel->rd_opcintype[i];
+		Oid			collation = rel->rd_indcollation[i];
+		Oid			equalimageproc;
+
+		equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
+										   BTEQUALIMAGE_PROC);
+
+		/*
+		 * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
+		 * be unsafe.  Otherwise, actually call proc and see what it says.
+		 */
+		if (!OidIsValid(equalimageproc) ||
+			!DatumGetBool(OidFunctionCall0Coll(equalimageproc, collation)))
+		{
+			allequalimage = false;
+			break;
+		}
+	}
+
+	/*
+	 * Don't ereport() until here to avoid reporting on a system relation
+	 * index or an INCLUDE index
+	 */
+	if (debugmessage)
+	{
+		if (allequalimage)
+			elog(DEBUG1, "index \"%s\" can safely use deduplication",
+				 RelationGetRelationName(rel));
+		else
+			ereport(NOTICE,
+					(errmsg("index \"%s\" cannot use deduplication",
+							RelationGetRelationName(rel))));
+	}
+
+	return allequalimage;
+}
diff --git a/src/backend/access/nbtree/nbtvalidate.c b/src/backend/access/nbtree/nbtvalidate.c
index ff634b1649..effd04d32e 100644
--- a/src/backend/access/nbtree/nbtvalidate.c
+++ b/src/backend/access/nbtree/nbtvalidate.c
@@ -104,6 +104,10 @@ btvalidate(Oid opclassoid)
 											procform->amprocrighttype,
 											BOOLOID, BOOLOID);
 				break;
+			case BTEQUALIMAGE_PROC:
+				ok = check_amproc_signature(procform->amproc, BOOLOID, true,
+											0, 0);
+				break;
 			default:
 				ereport(INFO,
 						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -211,8 +215,8 @@ btvalidate(Oid opclassoid)
 
 		/*
 		 * Complain if there seems to be an incomplete set of either operators
-		 * or support functions for this datatype pair.  The only things
-		 * considered optional are the sortsupport and in_range functions.
+		 * or support functions for this datatype pair.  The sortsupport,
+		 * in_range, and equalimage functions are considered optional.
 		 */
 		if (thisgroup->operatorset !=
 			((1 << BTLessStrategyNumber) |
diff --git a/src/backend/commands/opclasscmds.c b/src/backend/commands/opclasscmds.c
index e2c6de457c..f63c02d5e9 100644
--- a/src/backend/commands/opclasscmds.c
+++ b/src/backend/commands/opclasscmds.c
@@ -1143,9 +1143,10 @@ assignProcTypes(OpFamilyMember *member, Oid amoid, Oid typeoid)
 	/*
 	 * btree comparison procs must be 2-arg procs returning int4.  btree
 	 * sortsupport procs must take internal and return void.  btree in_range
-	 * procs must be 5-arg procs returning bool.  hash support proc 1 must be
-	 * a 1-arg proc returning int4, while proc 2 must be a 2-arg proc
-	 * returning int8.  Otherwise we don't know.
+	 * procs must be 5-arg procs returning bool.  btree equalimage procs must
+	 * take no args and return bool.  hash support proc 1 must be a 1-arg
+	 * proc returning int4, while proc 2 must be a 2-arg proc returning int8.
+	 * Otherwise we don't know.
 	 */
 	if (amoid == BTREE_AM_OID)
 	{
@@ -1205,6 +1206,29 @@ assignProcTypes(OpFamilyMember *member, Oid amoid, Oid typeoid)
 			if (!OidIsValid(member->righttype))
 				member->righttype = procform->proargtypes.values[2];
 		}
+		else if (member->number == BTEQUALIMAGE_PROC)
+		{
+			if (procform->pronargs != 0)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree equal image functions must have no arguments")));
+			if (procform->prorettype != BOOLOID)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree equal image functions must return boolean")));
+			/*
+			 * pg_amproc functions are indexed by (lefttype, righttype), but
+			 * an equalimage function can only be called at CREATE INDEX time.
+			 * The same opclass opcintype OID is always used for leftype and
+			 * righttype.  Providing a cross-type routine isn't sensible.
+			 * Reject cross-type ALTER OPERATOR FAMILY ...  ADD FUNCTION 4
+			 * statements here.
+			 */
+			if (member->lefttype != member->righttype)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree equal image function cannot be a cross-type function")));
+		}
 	}
 	else if (amoid == HASH_AM_OID)
 	{
diff --git a/src/backend/utils/adt/datum.c b/src/backend/utils/adt/datum.c
index 4e81947352..2881736cd6 100644
--- a/src/backend/utils/adt/datum.c
+++ b/src/backend/utils/adt/datum.c
@@ -44,6 +44,7 @@
 
 #include "access/detoast.h"
 #include "fmgr.h"
+#include "utils/builtins.h"
 #include "utils/datum.h"
 #include "utils/expandeddatum.h"
 
@@ -323,6 +324,22 @@ datum_image_eq(Datum value1, Datum value2, bool typByVal, int typLen)
 	return result;
 }
 
+/*-------------------------------------------------------------------------
+ * btequalimagedatum
+ *
+ * Generic "equalimage" support function -- always returns true.
+ *
+ * B-Tree operator classes whose equality function could safely be replaced by
+ * datum_image_eq() in all cases can use this as their "equalimage" support
+ * function.
+ *-------------------------------------------------------------------------
+ */
+Datum
+btequalimagedatum(PG_FUNCTION_ARGS)
+{
+	PG_RETURN_BOOL(true);
+}
+
 /*-------------------------------------------------------------------------
  * datumEstimateSpace
  *
diff --git a/src/backend/utils/adt/name.c b/src/backend/utils/adt/name.c
index 6749e75c89..16a60626be 100644
--- a/src/backend/utils/adt/name.c
+++ b/src/backend/utils/adt/name.c
@@ -29,6 +29,7 @@
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/lsyscache.h"
+#include "utils/pg_locale.h"
 #include "utils/varlena.h"
 
 
@@ -224,6 +225,36 @@ btnamesortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static void
+check_collation_set(Oid collid)
+{
+	if (!OidIsValid(collid))
+	{
+		/*
+		 * This typically means that the parser could not resolve a conflict
+		 * of implicit collations, so report it that way.
+		 */
+		ereport(ERROR,
+				(errcode(ERRCODE_INDETERMINATE_COLLATION),
+				 errmsg("could not determine which collation to use for string comparison"),
+				 errhint("Use the COLLATE clause to set the collation explicitly.")));
+	}
+}
+
+Datum
+btnameequalimage(PG_FUNCTION_ARGS)
+{
+	Oid			collid = PG_GET_COLLATION();
+
+	check_collation_set(collid);
+
+	if (lc_collate_is_c(collid) ||
+		collid == DEFAULT_COLLATION_OID ||
+		get_collation_isdeterministic(collid))
+		PG_RETURN_BOOL(true);
+	else
+		PG_RETURN_BOOL(false);
+}
 
 /*****************************************************************************
  *	 MISCELLANEOUS PUBLIC ROUTINES											 *
diff --git a/src/backend/utils/adt/varchar.c b/src/backend/utils/adt/varchar.c
index 1e1239a1ba..fbe28ffb05 100644
--- a/src/backend/utils/adt/varchar.c
+++ b/src/backend/utils/adt/varchar.c
@@ -936,6 +936,21 @@ bpchar_sortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+Datum
+bpchar_equalimage(PG_FUNCTION_ARGS)
+{
+	Oid			collid = PG_GET_COLLATION();
+
+	check_collation_set(collid);
+
+	if (lc_collate_is_c(collid) ||
+		collid == DEFAULT_COLLATION_OID ||
+		get_collation_isdeterministic(collid))
+		PG_RETURN_BOOL(true);
+	else
+		PG_RETURN_BOOL(false);
+}
+
 Datum
 bpchar_larger(PG_FUNCTION_ARGS)
 {
diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c
index 1b351cbc68..cc39035c0e 100644
--- a/src/backend/utils/adt/varlena.c
+++ b/src/backend/utils/adt/varlena.c
@@ -1953,6 +1953,21 @@ bttextsortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+Datum
+bttextequalimage(PG_FUNCTION_ARGS)
+{
+	Oid			collid = PG_GET_COLLATION();
+
+	check_collation_set(collid);
+
+	if (lc_collate_is_c(collid) ||
+		collid == DEFAULT_COLLATION_OID ||
+		get_collation_isdeterministic(collid))
+		PG_RETURN_BOOL(true);
+	else
+		PG_RETURN_BOOL(false);
+}
+
 /*
  * Generic sortsupport interface for character type's operator classes.
  * Includes locale support, and support for BpChar semantics (i.e. removing
diff --git a/doc/src/sgml/btree.sgml b/doc/src/sgml/btree.sgml
index ac6c4423e6..e3c69f8de6 100644
--- a/doc/src/sgml/btree.sgml
+++ b/doc/src/sgml/btree.sgml
@@ -207,7 +207,7 @@
 
  <para>
   As shown in <xref linkend="xindex-btree-support-table"/>, btree defines
-  one required and two optional support functions.  The three
+  one required and three optional support functions.  The four
   user-defined methods are:
  </para>
  <variablelist>
@@ -456,6 +456,63 @@ returns bool
     </para>
    </listitem>
   </varlistentry>
+  <varlistentry>
+   <term><function>equalimage</function></term>
+   <listitem>
+    <para>
+     Optionally, a btree operator family may provide
+     <function>equalimage</function> (<quote>equality is image
+     equality</quote>) support functions, registered under support
+     function number 4.  These functions allow B-Tree to apply
+     optimizations that assume that any two datums considered equal by
+     a corresponding <function>order</function> method must also be
+     equivalent in every way.  For example, the output function for
+     the underlying type must always return the same
+     <type>cstring</type>.  When there is no
+     <function>equalimage</function> procedure, or when the procedure
+     returns <literal>false</literal>, the B-Tree implementation
+     assumes that equal index tuples might be visibly different.  This
+     prevents an affected B-Tree index from using the deduplication
+     optimization.
+    </para>
+    <para>
+     An <function>equalimage</function> function must have the
+     signature
+<synopsis>
+equalimage() returns bool
+</synopsis>
+     Note that there are no arguments to the function.  Even still, if
+     the indexed values are of a collatable data type, the appropriate
+     collation OID will be passed to the
+     <function>equalimage</function> function, using the standard
+     <function>PG_GET_COLLATION()</function> mechanism.
+    </para>
+    <para>
+     When an operator class's <function>equalimage</function> function
+     returns <literal>true</literal>, the binary representation of two
+     datums that are considered equal by the operator class's
+     <function>order</function> procedure are generally also bitwise
+     equal.  However, when indexing a varlena datatype, the on-disk
+     representation may not be identical due to inconsistent
+     application of <acronym>TOAST</acronym> compression on input.
+     Formally, when an operator class's
+     <function>equalimage</function> function returns
+     <literal>true</literal>, it is safe to assume that the
+     <literal>datum_image_eq()</literal> C function will always give
+     the same answer as the operator class's <literal>=</literal>
+     operator for any possible set of inputs (assuming the
+     <literal>=</literal> operator is invoked using the collation
+     reported to the <function>equalimage</function> function).
+    </para>
+    <para>
+     A generic <function>equalimage</function> function that returns
+     <literal>true</literal> unconditionally can often be used when
+     authoring a new operator class/family;
+     <function>btequalimagedatum()</function> is provided for this
+     purpose.
+    </para>
+   </listitem>
+  </varlistentry>
  </variablelist>
 
 </sect1>
diff --git a/doc/src/sgml/ref/alter_opfamily.sgml b/doc/src/sgml/ref/alter_opfamily.sgml
index 848156c9d7..4ac1cca95a 100644
--- a/doc/src/sgml/ref/alter_opfamily.sgml
+++ b/doc/src/sgml/ref/alter_opfamily.sgml
@@ -153,9 +153,10 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
       and hash functions it is not necessary to specify <replaceable
       class="parameter">op_type</replaceable> since the function's input
       data type(s) are always the correct ones to use.  For B-tree sort
-      support functions and all functions in GiST, SP-GiST and GIN operator
-      classes, it is necessary to specify the operand data type(s) the function
-      is to be used with.
+      support functions, B-Tree equal image functions, and all
+      functions in GiST, SP-GiST and GIN operator classes, it is
+      necessary to specify the operand data type(s) the function is to
+      be used with.
      </para>
 
      <para>
diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml
index ffb5164aaa..59b1e37163 100644
--- a/doc/src/sgml/xindex.sgml
+++ b/doc/src/sgml/xindex.sgml
@@ -402,7 +402,7 @@
 
   <para>
    B-trees require a comparison support function,
-   and allow two additional support functions to be
+   and allow three additional support functions to be
    supplied at the operator class author's option, as shown in <xref
    linkend="xindex-btree-support-table"/>.
    The requirements for these support functions are explained further in
@@ -441,6 +441,14 @@
        </entry>
        <entry>3</entry>
       </row>
+      <row>
+       <entry>
+        Determine if it is generally safe to apply optimizations that
+        assume that any two equal keys must also be "image equal";
+        this makes the two keys totally interchangeable (optional)
+       </entry>
+       <entry>4</entry>
+      </row>
      </tbody>
     </tgroup>
    </table>
@@ -980,7 +988,8 @@ DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
   OPERATOR 5 > ,
   FUNCTION 1 btint8cmp(int8, int8) ,
   FUNCTION 2 btint8sortsupport(internal) ,
-  FUNCTION 3 in_range(int8, int8, int8, boolean, boolean) ;
+  FUNCTION 3 in_range(int8, int8, int8, boolean, boolean) ,
+  FUNCTION 4 btequalimagedatum() ;
 
 CREATE OPERATOR CLASS int4_ops
 DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
@@ -992,7 +1001,8 @@ DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
   OPERATOR 5 > ,
   FUNCTION 1 btint4cmp(int4, int4) ,
   FUNCTION 2 btint4sortsupport(internal) ,
-  FUNCTION 3 in_range(int4, int4, int4, boolean, boolean) ;
+  FUNCTION 3 in_range(int4, int4, int4, boolean, boolean) ,
+  FUNCTION 4 btequalimagedatum() ;
 
 CREATE OPERATOR CLASS int2_ops
 DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
@@ -1004,7 +1014,8 @@ DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
   OPERATOR 5 > ,
   FUNCTION 1 btint2cmp(int2, int2) ,
   FUNCTION 2 btint2sortsupport(internal) ,
-  FUNCTION 3 in_range(int2, int2, int2, boolean, boolean) ;
+  FUNCTION 3 in_range(int2, int2, int2, boolean, boolean) ,
+  FUNCTION 4 btequalimagedatum() ;
 
 ALTER OPERATOR FAMILY integer_ops USING btree ADD
   -- cross-type comparisons int8 vs int2
diff --git a/src/test/regress/expected/alter_generic.out b/src/test/regress/expected/alter_generic.out
index ac5183c90e..022dec82a3 100644
--- a/src/test/regress/expected/alter_generic.out
+++ b/src/test/regress/expected/alter_generic.out
@@ -354,9 +354,9 @@ ERROR:  invalid operator number 0, must be between 1 and 5
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 1 < ; -- operator without argument types
 ERROR:  operator argument types must be specified in ALTER OPERATOR FAMILY
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 0 btint42cmp(int4, int2); -- function number should be between 1 and 5
-ERROR:  invalid function number 0, must be between 1 and 3
+ERROR:  invalid function number 0, must be between 1 and 4
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 6 btint42cmp(int4, int2); -- function number should be between 1 and 5
-ERROR:  invalid function number 6, must be between 1 and 3
+ERROR:  invalid function number 6, must be between 1 and 4
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD STORAGE invalid_storage; -- Ensure STORAGE is not a part of ALTER OPERATOR FAMILY
 ERROR:  STORAGE cannot be specified in ALTER OPERATOR FAMILY
 DROP OPERATOR FAMILY alt_opf4 USING btree;
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index c19740e5db..0974098fd3 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -2111,6 +2111,41 @@ WHERE p1.amproc = p2.oid AND
 --------------+--------+--------
 (0 rows)
 
+-- Almost all Btree opclasses can use the generic btequalimagedatum function
+-- as their equalimage proc (support function 4).  Look for opclasses that
+-- don't do so; newly added Btree opclasses will usually be able to support
+-- deduplication with little trouble.
+SELECT amproc::regproc AS proc, opf.opfname AS opfamily_name,
+       opc.opcname AS opclass_name, opc.opcintype::regtype AS opcintype
+FROM pg_am am
+JOIN pg_opclass opc ON opc.opcmethod = am.oid
+JOIN pg_opfamily opf ON opc.opcfamily = opf.oid
+LEFT JOIN pg_amproc ON amprocfamily = opf.oid AND
+    amproclefttype = opcintype AND
+    amprocnum = 4
+WHERE am.amname = 'btree' AND
+    amproc IS DISTINCT FROM 'btequalimagedatum'::regproc
+ORDER BY amproc::regproc::text, opfamily_name, opclass_name;
+       proc        |  opfamily_name   |   opclass_name   |    opcintype     
+-------------------+------------------+------------------+------------------
+ bpchar_equalimage | bpchar_ops       | bpchar_ops       | character
+ btnameequalimage  | text_ops         | name_ops         | name
+ bttextequalimage  | text_ops         | text_ops         | text
+ bttextequalimage  | text_ops         | varchar_ops      | text
+                   | array_ops        | array_ops        | anyarray
+                   | enum_ops         | enum_ops         | anyenum
+                   | float_ops        | float4_ops       | real
+                   | float_ops        | float8_ops       | double precision
+                   | jsonb_ops        | jsonb_ops        | jsonb
+                   | money_ops        | money_ops        | money
+                   | numeric_ops      | numeric_ops      | numeric
+                   | range_ops        | range_ops        | anyrange
+                   | record_image_ops | record_image_ops | record
+                   | record_ops       | record_ops       | record
+                   | tsquery_ops      | tsquery_ops      | tsquery
+                   | tsvector_ops     | tsvector_ops     | tsvector
+(16 rows)
+
 -- **************** pg_index ****************
 -- Look for illegal values in pg_index fields.
 SELECT p1.indexrelid, p1.indrelid
diff --git a/src/test/regress/sql/opr_sanity.sql b/src/test/regress/sql/opr_sanity.sql
index 624bea46ce..bd8e79737b 100644
--- a/src/test/regress/sql/opr_sanity.sql
+++ b/src/test/regress/sql/opr_sanity.sql
@@ -1323,6 +1323,21 @@ WHERE p1.amproc = p2.oid AND
     p1.amproclefttype != p1.amprocrighttype AND
     p2.provolatile = 'v';
 
+-- Almost all Btree opclasses can use the generic btequalimagedatum function
+-- as their equalimage proc (support function 4).  Look for opclasses that
+-- don't do so; newly added Btree opclasses will usually be able to support
+-- deduplication with little trouble.
+SELECT amproc::regproc AS proc, opf.opfname AS opfamily_name,
+       opc.opcname AS opclass_name, opc.opcintype::regtype AS opcintype
+FROM pg_am am
+JOIN pg_opclass opc ON opc.opcmethod = am.oid
+JOIN pg_opfamily opf ON opc.opcfamily = opf.oid
+LEFT JOIN pg_amproc ON amprocfamily = opf.oid AND
+    amproclefttype = opcintype AND
+    amprocnum = 4
+WHERE am.amname = 'btree' AND
+    amproc IS DISTINCT FROM 'btequalimagedatum'::regproc
+ORDER BY amproc::regproc::text, opfamily_name, opclass_name;
 
 -- **************** pg_index ****************
 
-- 
2.17.1