diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index 96b7593..5085008 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -468,8 +468,19 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 					{
 						if (nbuf != InvalidBuffer)
 							_bt_relbuf(rel, nbuf);
-						/* Tell _bt_doinsert to wait... */
+						/*
+						 * Tell _bt_doinsert to wait...
+						 *
+						 * Also, invalidate the search bounds saved in
+						 * insertstate during the previous call to
+						 * _bt_binsrch_insert(). We will do the fresh binary
+						 * search as the transaction on which we waited for
+						 * might have inserted a new tuple.
+						 */
 						*speculativeToken = SnapshotDirty.speculativeToken;
+
+						insertstate->bounds_valid = false;
+						
 						return xwait;
 					}