Add support for INSERT ... ON CONFLICT DO NOTHING/UPDATE.

The newly added ON CONFLICT clause allows to specify an alternative to
raising a unique or exclusion constraint violation error when inserting.
ON CONFLICT refers to constraints that can either be specified using a
inference clause (by specifying the columns of a unique constraint) or
by naming a unique or exclusion constraint.  DO NOTHING avoids the
constraint violation, without touching the pre-existing row.  DO UPDATE
SET ... [WHERE ...] updates the pre-existing tuple, and has access to
both the tuple proposed for insertion and the existing tuple; the
optional WHERE clause can be used to prevent an update from being
executed.  The UPDATE SET and WHERE clauses have access to the tuple
proposed for insertion using the "magic" EXCLUDED alias, and to the
pre-existing tuple using the table name or its alias.

This feature is often referred to as upsert.

This is implemented using a new infrastructure called "speculative
insertion". It is an optimistic variant of regular insertion that first
does a pre-check for existing tuples and then attempts an insert.  If a
violating tuple was inserted concurrently, the speculatively inserted
tuple is deleted and a new attempt is made.  If the pre-check finds a
matching tuple the alternative DO NOTHING or DO UPDATE action is taken.
If the insertion succeeds without detecting a conflict, the tuple is
deemed inserted.

To handle the possible ambiguity between the excluded alias and a table
named excluded, and for convenience with long relation names, INSERT
INTO now can alias its target table.

Bumps catversion as stored rules change.

Author: Peter Geoghegan, with significant contributions from Heikki
    Linnakangas and Andres Freund. Testing infrastructure by Jeff Janes.
Reviewed-By: Heikki Linnakangas, Andres Freund, Robert Haas, Simon Riggs,
    Dean Rasheed, Stephen Frost and many others.

22 files changed, 265 insertions, 35 deletions

diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 888cce7a2d..49c8ca4d66 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -28,6 +28,7 @@
 #define HEAP_INSERT_SKIP_WAL	0x0001
 #define HEAP_INSERT_SKIP_FSM	0x0002
 #define HEAP_INSERT_FROZEN		0x0004
+#define HEAP_INSERT_SPECULATIVE 0x0008
 
 typedef struct BulkInsertStateData *BulkInsertState;
 
@@ -142,6 +143,8 @@ extern void heap_multi_insert(Relation relation, HeapTuple *tuples, int ntuples,
 extern HTSU_Result heap_delete(Relation relation, ItemPointer tid,
 			CommandId cid, Snapshot crosscheck, bool wait,
 			HeapUpdateFailureData *hufd);
+extern void heap_finish_speculative(Relation relation, HeapTuple tuple);
+extern void heap_abort_speculative(Relation relation, HeapTuple tuple);
 extern HTSU_Result heap_update(Relation relation, ItemPointer otid,
 			HeapTuple newtup,
 			CommandId cid, Snapshot crosscheck, bool wait,
diff --git a/src/include/access/heapam_xlog.h b/src/include/access/heapam_xlog.h
index f0f89dec0f..caa0f14f4b 100644
--- a/src/include/access/heapam_xlog.h
+++ b/src/include/access/heapam_xlog.h
@@ -34,7 +34,7 @@
 #define XLOG_HEAP_UPDATE		0x20
 /* 0x030 is free, was XLOG_HEAP_MOVE */
 #define XLOG_HEAP_HOT_UPDATE	0x40
-/* 0x050 is free, was XLOG_HEAP_NEWPAGE */
+#define XLOG_HEAP_CONFIRM		0x50
 #define XLOG_HEAP_LOCK			0x60
 #define XLOG_HEAP_INPLACE		0x70
 
@@ -60,23 +60,43 @@
 #define XLOG_HEAP2_NEW_CID		0x70
 
 /*
- * xl_heap_* ->flag values, 8 bits are available.
+ * xl_heap_insert/xl_heap_multi_insert flag values, 8 bits are available.
  */
 /* PD_ALL_VISIBLE was cleared */
-#define XLOG_HEAP_ALL_VISIBLE_CLEARED		(1<<0)
+#define XLH_INSERT_ALL_VISIBLE_CLEARED			(1<<0)
+#define XLH_INSERT_LAST_IN_MULTI				(1<<1)
+#define XLH_INSERT_IS_SPECULATIVE				(1<<2)
+#define XLH_INSERT_CONTAINS_NEW_TUPLE			(1<<3)
+
+/*
+ * xl_heap_update flag values, 8 bits are available.
+ */
+/* PD_ALL_VISIBLE was cleared */
+#define XLH_UPDATE_OLD_ALL_VISIBLE_CLEARED		(1<<0)
 /* PD_ALL_VISIBLE was cleared in the 2nd page */
-#define XLOG_HEAP_NEW_ALL_VISIBLE_CLEARED	(1<<1)
-#define XLOG_HEAP_CONTAINS_OLD_TUPLE		(1<<2)
-#define XLOG_HEAP_CONTAINS_OLD_KEY			(1<<3)
-#define XLOG_HEAP_CONTAINS_NEW_TUPLE		(1<<4)
-#define XLOG_HEAP_PREFIX_FROM_OLD			(1<<5)
-#define XLOG_HEAP_SUFFIX_FROM_OLD			(1<<6)
-/* last xl_heap_multi_insert record for one heap_multi_insert() call */
-#define XLOG_HEAP_LAST_MULTI_INSERT			(1<<7)
+#define XLH_UPDATE_NEW_ALL_VISIBLE_CLEARED		(1<<1)
+#define XLH_UPDATE_CONTAINS_OLD_TUPLE			(1<<2)
+#define XLH_UPDATE_CONTAINS_OLD_KEY				(1<<3)
+#define XLH_UPDATE_CONTAINS_NEW_TUPLE			(1<<4)
+#define XLH_UPDATE_PREFIX_FROM_OLD				(1<<5)
+#define XLH_UPDATE_SUFFIX_FROM_OLD				(1<<6)
 
 /* convenience macro for checking whether any form of old tuple was logged */
-#define XLOG_HEAP_CONTAINS_OLD						\
-	(XLOG_HEAP_CONTAINS_OLD_TUPLE | XLOG_HEAP_CONTAINS_OLD_KEY)
+#define XLH_UPDATE_CONTAINS_OLD						\
+	(XLH_UPDATE_CONTAINS_OLD_TUPLE | XLH_UPDATE_CONTAINS_OLD_KEY)
+
+/*
+ * xl_heap_delete flag values, 8 bits are available.
+ */
+/* PD_ALL_VISIBLE was cleared */
+#define XLH_DELETE_ALL_VISIBLE_CLEARED			(1<<0)
+#define XLH_DELETE_CONTAINS_OLD_TUPLE			(1<<1)
+#define XLH_DELETE_CONTAINS_OLD_KEY				(1<<2)
+#define XLH_DELETE_IS_SUPER						(1<<3)
+
+/* convenience macro for checking whether any form of old tuple was logged */
+#define XLH_DELETE_CONTAINS_OLD						\
+	(XLH_DELETE_CONTAINS_OLD_TUPLE | XLH_DELETE_CONTAINS_OLD_KEY)
 
 /* This is what we need to know about delete */
 typedef struct xl_heap_delete
@@ -243,6 +263,14 @@ typedef struct xl_heap_lock_updated
 
 #define SizeOfHeapLockUpdated	(offsetof(xl_heap_lock_updated, infobits_set) + sizeof(uint8))
 
+/* This is what we need to know about confirmation of speculative insertion */
+typedef struct xl_heap_confirm
+{
+	OffsetNumber offnum;		/* confirmed tuple's offset on page */
+} xl_heap_confirm;
+
+#define SizeOfHeapConfirm	(offsetof(xl_heap_confirm, offnum) + sizeof(OffsetNumber))
+
 /* This is what we need to know about in-place update */
 typedef struct xl_heap_inplace
 {
diff --git a/src/include/access/hio.h b/src/include/access/hio.h
index b0140298b1..b3b91e70d5 100644
--- a/src/include/access/hio.h
+++ b/src/include/access/hio.h
@@ -36,7 +36,7 @@ typedef struct BulkInsertStateData
 
 
 extern void RelationPutHeapTuple(Relation relation, Buffer buffer,
-					 HeapTuple tuple);
+					 HeapTuple tuple, bool token);
 extern Buffer RelationGetBufferForTuple(Relation relation, Size len,
 						  Buffer otherBuffer, int options,
 						  BulkInsertState bistate,
diff --git a/src/include/access/htup_details.h b/src/include/access/htup_details.h
index 0a673cd526..80285acc3b 100644
--- a/src/include/access/htup_details.h
+++ b/src/include/access/htup_details.h
@@ -96,6 +96,15 @@
  * unrelated tuple stored into a slot recently freed by VACUUM.  If either
  * check fails, one may assume that there is no live descendant version.
  *
+ * t_ctid is sometimes used to store a speculative insertion token, instead
+ * of a real TID.  A speculative token is set on a tuple that's being
+ * inserted, until the inserter is sure that it wants to go ahead with the
+ * insertion.  Hence a token should only be seen on a tuple with an XMAX
+ * that's still in-progress, or invalid/aborted.  The token is replaced with
+ * the tuple's real TID when the insertion is confirmed.  One should never
+ * see a speculative insertion token while following a chain of t_ctid links,
+ * because they are not used on updates, only insertions.
+ *
  * Following the fixed header fields, the nulls bitmap is stored (beginning
  * at t_bits).  The bitmap is *not* stored if t_infomask shows that there
  * are no nulls in the tuple.  If an OID field is present (as indicated by
@@ -138,7 +147,8 @@ struct HeapTupleHeaderData
 		DatumTupleFields t_datum;
 	}			t_choice;
 
-	ItemPointerData t_ctid;		/* current TID of this or newer tuple */
+	ItemPointerData t_ctid;		/* current TID of this or newer tuple (or a
+								 * speculative insertion token) */
 
 	/* Fields below here must match MinimalTupleData! */
 
@@ -242,6 +252,14 @@ struct HeapTupleHeaderData
 #define HEAP_TUPLE_HAS_MATCH	HEAP_ONLY_TUPLE /* tuple has a join match */
 
 /*
+ * Special value used in t_ctid.ip_posid, to indicate that it holds a
+ * speculative insertion token rather than a real TID.  This must be higher
+ * than MaxOffsetNumber, so that it can be distinguished from a valid
+ * offset number in a regular item pointer.
+ */
+#define SpecTokenOffsetNumber		0xfffe
+
+/*
  * HeapTupleHeader accessor macros
  *
  * Note: beware of multiple evaluations of "tup" argument.  But the Set
@@ -377,6 +395,22 @@ do { \
 	(tup)->t_choice.t_heap.t_field3.t_xvac = (xid); \
 } while (0)
 
+#define HeapTupleHeaderIsSpeculative(tup) \
+( \
+	(tup)->t_ctid.ip_posid == SpecTokenOffsetNumber \
+)
+
+#define HeapTupleHeaderGetSpeculativeToken(tup) \
+( \
+	AssertMacro(HeapTupleHeaderIsSpeculative(tup)),	\
+	ItemPointerGetBlockNumber(&(tup)->t_ctid) \
+)
+
+#define HeapTupleHeaderSetSpeculativeToken(tup, token)	\
+( \
+	ItemPointerSet(&(tup)->t_ctid, token, SpecTokenOffsetNumber) \
+)
+
 #define HeapTupleHeaderGetDatumLength(tup) \
 	VARSIZE(tup)
 
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 3d2c5b2a29..969a8e3c35 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201505081
+#define CATALOG_VERSION_NO	201505082
 
 #endif
diff --git a/src/include/catalog/index.h b/src/include/catalog/index.h
index a04def96e4..06f38202a5 100644
--- a/src/include/catalog/index.h
+++ b/src/include/catalog/index.h
@@ -81,6 +81,8 @@ extern void index_drop(Oid indexId, bool concurrent);
 
 extern IndexInfo *BuildIndexInfo(Relation index);
 
+extern void BuildSpeculativeIndexInfo(Relation index, IndexInfo *ii);
+
 extern void FormIndexDatum(IndexInfo *indexInfo,
 			   TupleTableSlot *slot,
 			   EState *estate,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 33c8fad844..1b68b54c7d 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -195,6 +195,7 @@ extern void ExecConstraints(ResultRelInfo *resultRelInfo,
 				TupleTableSlot *slot, EState *estate);
 extern void ExecWithCheckOptions(WCOKind kind, ResultRelInfo *resultRelInfo,
 					 TupleTableSlot *slot, EState *estate);
+extern LockTupleMode ExecUpdateLockMode(EState *estate, ResultRelInfo *relinfo);
 extern ExecRowMark *ExecFindRowMark(EState *estate, Index rti);
 extern ExecAuxRowMark *ExecBuildAuxRowMark(ExecRowMark *erm, List *targetlist);
 extern TupleTableSlot *EvalPlanQual(EState *estate, EPQState *epqstate,
@@ -361,16 +362,18 @@ extern void UnregisterExprContextCallback(ExprContext *econtext,
 /*
  * prototypes from functions in execIndexing.c
  */
-extern void ExecOpenIndices(ResultRelInfo *resultRelInfo);
+extern void ExecOpenIndices(ResultRelInfo *resultRelInfo, bool speculative);
 extern void ExecCloseIndices(ResultRelInfo *resultRelInfo);
 extern List *ExecInsertIndexTuples(TupleTableSlot *slot, ItemPointer tupleid,
-					  EState *estate);
-extern bool check_exclusion_constraint(Relation heap, Relation index,
+					  EState *estate, bool noDupErr, bool *specConflict,
+					  List *arbiterIndexes);
+extern bool ExecCheckIndexConstraints(TupleTableSlot *slot, EState *estate,
+					  ItemPointer conflictTid, List *arbiterIndexes);
+extern void check_exclusion_constraint(Relation heap, Relation index,
 						   IndexInfo *indexInfo,
 						   ItemPointer tupleid,
 						   Datum *values, bool *isnull,
-						   EState *estate,
-						   bool newIndex, bool errorOK);
+						   EState *estate, bool newIndex);
 
 
 #endif   /* EXECUTOR_H  */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index dac542fbc1..210dbe4a53 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -41,6 +41,9 @@
  *		ExclusionOps		Per-column exclusion operators, or NULL if none
  *		ExclusionProcs		Underlying function OIDs for ExclusionOps
  *		ExclusionStrats		Opclass strategy numbers for ExclusionOps
+ *		UniqueOps			Theses are like Exclusion*, but for unique indexes
+ *		UniqueProcs
+ *		UniqueStrats
  *		Unique				is it a unique index?
  *		ReadyForInserts		is it valid for inserts?
  *		Concurrent			are we doing a concurrent index build?
@@ -62,6 +65,9 @@ typedef struct IndexInfo
 	Oid		   *ii_ExclusionOps;	/* array with one entry per column */
 	Oid		   *ii_ExclusionProcs;		/* array with one entry per column */
 	uint16	   *ii_ExclusionStrats;		/* array with one entry per column */
+	Oid		   *ii_UniqueOps;	/* array with one entry per column */
+	Oid		   *ii_UniqueProcs;		/* array with one entry per column */
+	uint16	   *ii_UniqueStrats;		/* array with one entry per column */
 	bool		ii_Unique;
 	bool		ii_ReadyForInserts;
 	bool		ii_Concurrent;
@@ -308,6 +314,8 @@ typedef struct JunkFilter
  *		ConstraintExprs			array of constraint-checking expr states
  *		junkFilter				for removing junk attributes from tuples
  *		projectReturning		for computing a RETURNING list
+ *		onConflictSetProj		for computing ON CONFLICT DO UPDATE SET
+ *		onConflictSetWhere		list of ON CONFLICT DO UPDATE exprs (qual)
  * ----------------
  */
 typedef struct ResultRelInfo
@@ -329,6 +337,8 @@ typedef struct ResultRelInfo
 	List	  **ri_ConstraintExprs;
 	JunkFilter *ri_junkFilter;
 	ProjectionInfo *ri_projectReturning;
+	ProjectionInfo *ri_onConflictSetProj;
+	List	   *ri_onConflictSetWhere;
 } ResultRelInfo;
 
 /* ----------------
@@ -1094,6 +1104,11 @@ typedef struct ModifyTableState
 	List	  **mt_arowmarks;	/* per-subplan ExecAuxRowMark lists */
 	EPQState	mt_epqstate;	/* for evaluating EvalPlanQual rechecks */
 	bool		fireBSTriggers; /* do we need to fire stmt triggers? */
+	OnConflictAction mt_onconflict; /* ON CONFLICT type */
+	List	   *mt_arbiterindexes;	/* unique index OIDs to arbitrate taking alt path */
+	TupleTableSlot *mt_existing; /* slot to store existing target tuple in */
+	List	   *mt_excludedtlist; /* the excluded pseudo relation's tlist  */
+	TupleTableSlot *mt_conflproj; /*  FIXME*/
 } ModifyTableState;
 
 /* ----------------
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 8991f3f80c..768f413a45 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -168,10 +168,12 @@ typedef enum NodeTag
 	T_CoerceToDomainValue,
 	T_SetToDefault,
 	T_CurrentOfExpr,
+	T_InferenceElem,
 	T_TargetEntry,
 	T_RangeTblRef,
 	T_JoinExpr,
 	T_FromExpr,
+	T_OnConflictExpr,
 	T_IntoClause,
 
 	/*
@@ -413,6 +415,8 @@ typedef enum NodeTag
 	T_RowMarkClause,
 	T_XmlSerialize,
 	T_WithClause,
+	T_InferClause,
+	T_OnConflictClause,
 	T_CommonTableExpr,
 	T_RoleSpec,
 
@@ -626,4 +630,17 @@ typedef enum JoinType
 	   (1 << JOIN_RIGHT) | \
 	   (1 << JOIN_ANTI))) != 0)
 
+/*
+ * OnConflictAction -
+ *	  "ON CONFLICT" clause type of query
+ *
+ * This is needed in both parsenodes.h and plannodes.h, so put it here...
+ */
+typedef enum OnConflictAction
+{
+	ONCONFLICT_NONE,		/* No "ON CONFLICT" clause */
+	ONCONFLICT_NOTHING,		/* ON CONFLICT ... DO NOTHING */
+	ONCONFLICT_UPDATE		/* ON CONFLICT ... DO UPDATE */
+} OnConflictAction;
+
 #endif   /* NODES_H */
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 7d15ef2847..91ca9c6fd0 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -132,6 +132,8 @@ typedef struct Query
 
 	List	   *withCheckOptions;		/* a list of WithCheckOption's */
 
+	OnConflictExpr *onConflict;	/* ON CONFLICT DO [NOTHING | UPDATE] */
+
 	List	   *returningList;	/* return-values list (of TargetEntry) */
 
 	List	   *groupClause;	/* a list of SortGroupClause's */
@@ -591,7 +593,7 @@ typedef enum TableLikeOption
 } TableLikeOption;
 
 /*
- * IndexElem - index parameters (used in CREATE INDEX)
+ * IndexElem - index parameters (used in CREATE INDEX, and in ON CONFLICT)
  *
  * For a plain index attribute, 'name' is the name of the table column to
  * index, and 'expr' is NULL.  For an index expression, 'name' is NULL and
@@ -735,9 +737,9 @@ typedef struct XmlSerialize
  *	  For SELECT/INSERT/UPDATE permissions, if the user doesn't have
  *	  table-wide permissions then it is sufficient to have the permissions
  *	  on all columns identified in selectedCols (for SELECT) and/or
- *	  insertedCols and/or updatedCols (INSERT with ON CONFLICT UPDATE may
- *	  have all 3).  selectedCols, insertedCols and updatedCols are
- *	  bitmapsets, which cannot have negative integer members, so we subtract
+ *	  insertedCols and/or updatedCols (INSERT with ON CONFLICT DO UPDATE may
+ *	  have all 3).  selectedCols, insertedCols and updatedCols are bitmapsets,
+ *	  which cannot have negative integer members, so we subtract
  *	  FirstLowInvalidHeapAttributeNumber from column numbers before storing
  *	  them in these fields.  A whole-row Var reference is represented by
  *	  setting the bit for InvalidAttrNumber.
@@ -881,7 +883,8 @@ typedef enum WCOKind
 {
 	WCO_VIEW_CHECK,				/* WCO on an auto-updatable view */
 	WCO_RLS_INSERT_CHECK,		/* RLS INSERT WITH CHECK policy */
-	WCO_RLS_UPDATE_CHECK		/* RLS UPDATE WITH CHECK policy */
+	WCO_RLS_UPDATE_CHECK,		/* RLS UPDATE WITH CHECK policy */
+	WCO_RLS_CONFLICT_CHECK		/* RLS ON CONFLICT DO UPDATE USING policy */
 } WCOKind;
 
 typedef struct WithCheckOption
@@ -1026,6 +1029,37 @@ typedef struct WithClause
 } WithClause;
 
 /*
+ * InferClause -
+ *		ON CONFLICT unique index inference clause
+ *
+ * Note: InferClause does not propagate into the Query representation.
+ */
+typedef struct InferClause
+{
+	NodeTag		type;
+	List	   *indexElems;		/* IndexElems to infer unique index */
+	Node	   *whereClause;	/* qualification (partial-index predicate) */
+	char	   *conname;		/* Constraint name, or NULL if unnamed */
+	int			location;		/* token location, or -1 if unknown */
+} InferClause;
+
+/*
+ * OnConflictClause -
+ *		representation of ON CONFLICT clause
+ *
+ * Note: OnConflictClause does not propagate into the Query representation.
+ */
+typedef struct OnConflictClause
+{
+	NodeTag			type;
+	OnConflictAction action;		/* DO NOTHING or UPDATE? */
+	InferClause	   *infer;			/* Optional index inference clause */
+	List		   *targetList;		/* the target list (of ResTarget) */
+	Node		   *whereClause;	/* qualifications */
+	int				location;		/* token location, or -1 if unknown */
+} OnConflictClause;
+
+/*
  * CommonTableExpr -
  *	   representation of WITH list element
  *
@@ -1075,6 +1109,7 @@ typedef struct InsertStmt
 	RangeVar   *relation;		/* relation to insert into */
 	List	   *cols;			/* optional: names of the target columns */
 	Node	   *selectStmt;		/* the source SELECT/VALUES, or NULL */
+	OnConflictClause *onConflictClause;	/* ON CONFLICT clause */
 	List	   *returningList;	/* list of expressions to return */
 	WithClause *withClause;		/* WITH clause */
 } InsertStmt;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index baeba2d330..c63492fa0b 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -45,6 +45,8 @@ typedef struct PlannedStmt
 
 	bool		hasModifyingCTE;	/* has insert|update|delete in WITH? */
 
+	bool		isUpsert;		/* is it insert ... ON CONFLICT UPDATE? */
+
 	bool		canSetTag;		/* do I set the command result tag? */
 
 	bool		transientPlan;	/* redo plan when TransactionXmin changes? */
@@ -183,6 +185,12 @@ typedef struct ModifyTable
 	List	   *fdwPrivLists;	/* per-target-table FDW private data lists */
 	List	   *rowMarks;		/* PlanRowMarks (non-locking only) */
 	int			epqParam;		/* ID of Param for EvalPlanQual re-eval */
+	OnConflictAction onConflictAction; /* ON CONFLICT action */
+	List	   *arbiterIndexes;	/* List of ON CONFLICT arbiter index OIDs  */
+	List	   *onConflictSet;	/* SET for INSERT ON CONFLICT DO UPDATE */
+	Node	   *onConflictWhere;/* WHERE for ON CONFLICT UPDATE */
+	Index		exclRelRTI;		/* RTI of the EXCLUDED pseudo relation */
+	List	   *exclRelTlist;	/* tlist of the EXCLUDED pseudo relation */
 } ModifyTable;
 
 /* ----------------
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 4f1d234d30..8f2c64847e 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -1143,6 +1143,22 @@ typedef struct CurrentOfExpr
 	int			cursor_param;	/* refcursor parameter number, or 0 */
 } CurrentOfExpr;
 
+/*
+ * InferenceElem - an element of a unique index inference specification
+ *
+ * This mostly matches the structure of IndexElems, but having a dedicated
+ * primnode allows for a clean separation between the use of index parameters
+ * by utility commands, and this node.
+ */
+typedef struct InferenceElem
+{
+	Expr		xpr;
+	Node	   *expr;				/* expression to infer from, or NULL */
+	Oid			infercollid;		/* OID of collation, or InvalidOid */
+	Oid			inferopfamily;		/* OID of att opfamily, or InvalidOid */
+	Oid			inferopcinputtype;	/* OID of att input type, or InvalidOid */
+} InferenceElem;
+
 /*--------------------
  * TargetEntry -
  *	   a target entry (used in query target lists)
@@ -1307,4 +1323,30 @@ typedef struct FromExpr
 	Node	   *quals;			/* qualifiers on join, if any */
 } FromExpr;
 
+/*----------
+ * OnConflictExpr - represents an ON CONFLICT DO ... expression
+ *
+ * The optimizer requires a list of inference elements, and optionally a WHERE
+ * clause to infer a unique index.  The unique index (or, occasionally,
+ * indexes) inferred are used to arbitrate whether or not the alternative ON
+ * CONFLICT path is taken.
+ *----------
+ */
+typedef struct OnConflictExpr
+{
+	NodeTag		type;
+	OnConflictAction action;	/* DO NOTHING or UPDATE? */
+
+	/* Arbiter */
+	List	   *arbiterElems;	/* unique index arbiter list (of InferenceElem's) */
+	Node	   *arbiterWhere;	/* unique index arbiter WHERE clause */
+	Oid			constraint;		/* pg_constraint OID for arbiter */
+
+	/* ON CONFLICT UPDATE */
+	List	   *onConflictSet;	/* List of ON CONFLICT SET TargetEntrys */
+	Node	   *onConflictWhere;/* qualifiers to restrict UPDATE to */
+	int			exclRelIndex;	/* RT index of 'excluded' relation */
+	List	   *exclRelTlist;	/* tlist of the EXCLUDED pseudo relation */
+} OnConflictExpr;
+
 #endif   /* PRIMNODES_H */
diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h
index 8eb2e57d7b..11e7d4d26b 100644
--- a/src/include/optimizer/plancat.h
+++ b/src/include/optimizer/plancat.h
@@ -28,6 +28,8 @@ extern PGDLLIMPORT get_relation_info_hook_type get_relation_info_hook;
 extern void get_relation_info(PlannerInfo *root, Oid relationObjectId,
 				  bool inhparent, RelOptInfo *rel);
 
+extern List *infer_arbiter_indexes(PlannerInfo *root);
+
 extern void estimate_rel_size(Relation rel, int32 *attr_widths,
 				  BlockNumber *pages, double *tuples, double *allvisfrac);
 
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 0c8cbcded9..1d4ab0488e 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -86,7 +86,7 @@ extern ModifyTable *make_modifytable(PlannerInfo *root,
 				 Index nominalRelation,
 				 List *resultRelations, List *subplans,
 				 List *withCheckOptionLists, List *returningLists,
-				 List *rowMarks, int epqParam);
+				 List *rowMarks, OnConflictExpr *onconflict, int epqParam);
 extern bool is_projection_capable_plan(Plan *plan);
 
 /*
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 05e46c5b78..dcd078ee43 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -45,6 +45,9 @@ extern void expand_security_quals(PlannerInfo *root, List *tlist);
  */
 extern List *preprocess_targetlist(PlannerInfo *root, List *tlist);
 
+extern List *preprocess_onconflict_targetlist(List *tlist,
+						  int result_relation, List *range_table);
+
 extern PlanRowMark *get_plan_rowmark(List *rowmarks, Index rtindex);
 
 /*
diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h
index 5b1ee15424..faea99108c 100644
--- a/src/include/parser/kwlist.h
+++ b/src/include/parser/kwlist.h
@@ -87,6 +87,7 @@ PG_KEYWORD("commit", COMMIT, UNRESERVED_KEYWORD)
 PG_KEYWORD("committed", COMMITTED, UNRESERVED_KEYWORD)
 PG_KEYWORD("concurrently", CONCURRENTLY, TYPE_FUNC_NAME_KEYWORD)
 PG_KEYWORD("configuration", CONFIGURATION, UNRESERVED_KEYWORD)
+PG_KEYWORD("conflict", CONFLICT, UNRESERVED_KEYWORD)
 PG_KEYWORD("connection", CONNECTION, UNRESERVED_KEYWORD)
 PG_KEYWORD("constraint", CONSTRAINT, RESERVED_KEYWORD)
 PG_KEYWORD("constraints", CONSTRAINTS, UNRESERVED_KEYWORD)
diff --git a/src/include/parser/parse_clause.h b/src/include/parser/parse_clause.h
index 6a4438f556..f1b7d3d896 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.h
@@ -41,6 +41,10 @@ extern List *transformDistinctClause(ParseState *pstate,
 						List **targetlist, List *sortClause, bool is_agg);
 extern List *transformDistinctOnClause(ParseState *pstate, List *distinctlist,
 						  List **targetlist, List *sortClause);
+extern void transformOnConflictArbiter(ParseState *pstate,
+						   OnConflictClause *onConflictClause,
+						   List **arbiterExpr, Node **arbiterWhere,
+						   Oid *constraint);
 
 extern List *addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 					List *sortlist, List *targetlist, SortBy *sortby,
diff --git a/src/include/replication/reorderbuffer.h b/src/include/replication/reorderbuffer.h
index 6a5528a734..928b1ca170 100644
--- a/src/include/replication/reorderbuffer.h
+++ b/src/include/replication/reorderbuffer.h
@@ -43,6 +43,11 @@ typedef struct ReorderBufferTupleBuf
  * and ComboCids in the same list with the user visible INSERT/UPDATE/DELETE
  * changes. Users of the decoding facilities will never see changes with
  * *_INTERNAL_* actions.
+ *
+ * The INTERNAL_SPEC_INSERT and INTERNAL_SPEC_CONFIRM changes concern
+ * "speculative insertions", and their confirmation respectively.  They're
+ * used by INSERT .. ON CONFLICT .. UPDATE.  Users of logical decoding don't
+ * have to care about these.
  */
 enum ReorderBufferChangeType
 {
@@ -51,7 +56,9 @@ enum ReorderBufferChangeType
 	REORDER_BUFFER_CHANGE_DELETE,
 	REORDER_BUFFER_CHANGE_INTERNAL_SNAPSHOT,
 	REORDER_BUFFER_CHANGE_INTERNAL_COMMAND_ID,
-	REORDER_BUFFER_CHANGE_INTERNAL_TUPLECID
+	REORDER_BUFFER_CHANGE_INTERNAL_TUPLECID,
+	REORDER_BUFFER_CHANGE_INTERNAL_SPEC_INSERT,
+	REORDER_BUFFER_CHANGE_INTERNAL_SPEC_CONFIRM
 };
 
 /*
diff --git a/src/include/rewrite/rowsecurity.h b/src/include/rewrite/rowsecurity.h
index 115c9a8e43..eb4b20559f 100644
--- a/src/include/rewrite/rowsecurity.h
+++ b/src/include/rewrite/rowsecurity.h
@@ -41,7 +41,8 @@ extern PGDLLIMPORT row_security_policy_hook_type row_security_policy_hook_permis
 
 extern PGDLLIMPORT row_security_policy_hook_type row_security_policy_hook_restrictive;
 
-extern void get_row_security_policies(Query* root, RangeTblEntry* rte, int rt_index,
+extern void get_row_security_policies(Query *root, CmdType commandType,
+						  RangeTblEntry *rte, int rt_index,
 						  List **securityQuals, List **withCheckOptions,
 						  bool *hasRowSecurity, bool *hasSubLinks);
 
diff --git a/src/include/storage/lmgr.h b/src/include/storage/lmgr.h
index f5d70e5141..7cc75fc106 100644
--- a/src/include/storage/lmgr.h
+++ b/src/include/storage/lmgr.h
@@ -76,6 +76,11 @@ extern bool ConditionalXactLockTableWait(TransactionId xid);
 extern void WaitForLockers(LOCKTAG heaplocktag, LOCKMODE lockmode);
 extern void WaitForLockersMultiple(List *locktags, LOCKMODE lockmode);
 
+/* Lock an XID for tuple insertion (used to wait for an insertion to finish) */
+extern uint32	SpeculativeInsertionLockAcquire(TransactionId xid);
+extern void		SpeculativeInsertionLockRelease(TransactionId xid);
+extern void		SpeculativeInsertionWait(TransactionId xid, uint32 token);
+
 /* Lock a general object (other than a relation) of the current database */
 extern void LockDatabaseObject(Oid classid, Oid objid, uint16 objsubid,
 				   LOCKMODE lockmode);
diff --git a/src/include/storage/lock.h b/src/include/storage/lock.h
index dae517f3fe..b4eb1b4a9e 100644
--- a/src/include/storage/lock.h
+++ b/src/include/storage/lock.h
@@ -176,6 +176,8 @@ typedef enum LockTagType
 	/* ID info for a transaction is its TransactionId */
 	LOCKTAG_VIRTUALTRANSACTION, /* virtual transaction (ditto) */
 	/* ID info for a virtual transaction is its VirtualTransactionId */
+	LOCKTAG_SPECULATIVE_TOKEN,		/* speculative insertion Xid and token */
+	/* ID info for a transaction is its TransactionId */
 	LOCKTAG_OBJECT,				/* non-relation database object */
 	/* ID info for an object is DB OID + CLASS OID + OBJECT OID + SUBID */
 
@@ -261,6 +263,14 @@ typedef struct LOCKTAG
 	 (locktag).locktag_type = LOCKTAG_VIRTUALTRANSACTION, \
 	 (locktag).locktag_lockmethodid = DEFAULT_LOCKMETHOD)
 
+#define SET_LOCKTAG_SPECULATIVE_INSERTION(locktag,xid,token) \
+	((locktag).locktag_field1 = (xid), \
+	 (locktag).locktag_field2 = (token),		\
+	 (locktag).locktag_field3 = 0, \
+	 (locktag).locktag_field4 = 0, \
+	 (locktag).locktag_type = LOCKTAG_SPECULATIVE_TOKEN, \
+	 (locktag).locktag_lockmethodid = DEFAULT_LOCKMETHOD)
+
 #define SET_LOCKTAG_OBJECT(locktag,dboid,classoid,objoid,objsubid) \
 	((locktag).locktag_field1 = (dboid), \
 	 (locktag).locktag_field2 = (classoid), \
diff --git a/src/include/utils/snapshot.h b/src/include/utils/snapshot.h
index 26fb2573c7..a734bf0075 100644
--- a/src/include/utils/snapshot.h
+++ b/src/include/utils/snapshot.h
@@ -69,31 +69,41 @@ typedef struct SnapshotData
 	 * progress, unless the snapshot was taken during recovery in which case
 	 * it's empty. For historic MVCC snapshots, the meaning is inverted, i.e.
 	 * it contains *committed* transactions between xmin and xmax.
+	 *
+	 * note: all ids in xip[] satisfy xmin <= xip[i] < xmax
 	 */
 	TransactionId *xip;
 	uint32		xcnt;			/* # of xact ids in xip[] */
-	/* note: all ids in xip[] satisfy xmin <= xip[i] < xmax */
-	int32		subxcnt;		/* # of xact ids in subxip[] */
 
 	/*
 	 * For non-historic MVCC snapshots, this contains subxact IDs that are in
 	 * progress (and other transactions that are in progress if taken during
 	 * recovery). For historic snapshot it contains *all* xids assigned to the
 	 * replayed transaction, including the toplevel xid.
+	 *
+	 * note: all ids in subxip[] are >= xmin, but we don't bother filtering
+	 * out any that are >= xmax
 	 */
 	TransactionId *subxip;
+	int32		subxcnt;		/* # of xact ids in subxip[] */
 	bool		suboverflowed;	/* has the subxip array overflowed? */
+
 	bool		takenDuringRecovery;	/* recovery-shaped snapshot? */
 	bool		copied;			/* false if it's a static snapshot */
 
+	CommandId	curcid;			/* in my xact, CID < curcid are visible */
+
 	/*
-	 * note: all ids in subxip[] are >= xmin, but we don't bother filtering
-	 * out any that are >= xmax
+	 * An extra return value for HeapTupleSatisfiesDirty, not used in MVCC
+	 * snapshots.
+	 */
+	uint32		speculativeToken;
+
+	/*
+	 * Book-keeping information, used by the snapshot manager
 	 */
-	CommandId	curcid;			/* in my xact, CID < curcid are visible */
 	uint32		active_count;	/* refcount on ActiveSnapshot stack */
 	uint32		regd_count;		/* refcount on RegisteredSnapshots */
-
 	pairingheap_node ph_node;	/* link in the RegisteredSnapshots heap */
 } SnapshotData;