diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml
index 271c135..480bfd0 100644
--- a/doc/src/sgml/indices.sgml
+++ b/doc/src/sgml/indices.sgml
@@ -248,7 +248,7 @@ CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable>
   </para>
 
   <para>
-   GiST indexes are also capable of optimizing <quote>nearest-neighbor</>
+   B-tree and GiST indexes are also capable of optimizing <quote>nearest-neighbor</>
    searches, such as
 <programlisting><![CDATA[
 SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml
index 333a36c..6708653 100644
--- a/doc/src/sgml/xindex.sgml
+++ b/doc/src/sgml/xindex.sgml
@@ -1171,7 +1171,7 @@ ALTER OPERATOR FAMILY integer_ops USING btree ADD
   <title>Ordering Operators</title>
 
   <para>
-   Some index access methods (currently, only GiST) support the concept of
+   Some index access methods (currently, only B-tree and GiST) support the concept of
    <firstterm>ordering operators</>.  What we have been discussing so far
    are <firstterm>search operators</>.  A search operator is one for which
    the index can be searched to find all rows satisfying
diff --git a/src/backend/access/nbtree/README b/src/backend/access/nbtree/README
index a3f11da..764c0a9 100644
--- a/src/backend/access/nbtree/README
+++ b/src/backend/access/nbtree/README
@@ -624,6 +624,24 @@ item is irrelevant, and need not be stored at all.  This arrangement
 corresponds to the fact that an L&Y non-leaf page has one more pointer
 than key.
 
+Nearest-neighbor search
+-----------------------
+
+There is a special scan strategy for nearest-neighbor (kNN) search,
+that is used in queries with ORDER BY distance clauses like this:
+SELECT * FROM tab WHERE col > const1 ORDER BY col <-> const2 LIMIT k.
+But, unlike GiST, B-tree supports only a one ordering operator on the
+first index column.
+
+At the beginning of kNN scan, we need to determine which strategy we
+will use --- a special bidirectional or a ordinary unidirectional.
+If the point from which we measure the distance falls into the scan range,
+we use bidirectional scan starting from this point, else we use simple
+unidirectional scan in the right direction.  Algorithm of a bidirectional
+scan is very simple: at each step we advancing scan in that direction,
+which has the nearest point.
+
+
 Notes to Operator Class Implementors
 ------------------------------------
 
@@ -660,6 +678,18 @@ procedure, of course.)
 The other three operators are defined in terms of these two in the obvious way,
 and must act consistently with them.
 
+To implement the distance ordered (nearest-neighbor) search, we only need
+to define a distance operator (usually it called <->) with a correpsonding
+operator family for distance comparison in the index's operator class.
+These operators must satisfy the following assumptions for all non-null
+values A,B,C of the datatype:
+
+	A <-> B = B <-> A								symmetric law
+	if A = B, then A <-> C = B <-> C				distance equivalence
+	if (A <= B and B <= C) or (A >= B and B >= C),
+		then A <-> B <= A <-> C						monotonicity
+
+
 For an operator family supporting multiple datatypes, the above laws must hold
 when A,B,C are taken from any datatypes in the family.  The transitive laws
 are the trickiest to ensure, as in cross-type situations they represent
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index c2da15e..2f476df 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -23,12 +23,16 @@
 #include "access/xlog.h"
 #include "catalog/index.h"
 #include "commands/vacuum.h"
+#include "nodes/primnodes.h"
+#include "nodes/relation.h"
+#include "optimizer/paths.h"
 #include "storage/indexfsm.h"
 #include "storage/ipc.h"
 #include "storage/lmgr.h"
 #include "storage/smgr.h"
 #include "tcop/tcopprot.h"		/* pgrminclude ignore */
 #include "utils/builtins.h"
+#include "utils/datum.h"
 #include "utils/index_selfuncs.h"
 #include "utils/memutils.h"
 
@@ -76,6 +80,10 @@ static void btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 static void btvacuumpage(BTVacState *vstate, BlockNumber blkno,
 			 BlockNumber orig_blkno);
 
+static Expr *btcanorderbyop(IndexOptInfo *index,
+							PathKey *pathkey, int pathkeyno,
+							Expr *expr, int *indexcol_p);
+
 
 /*
  * Btree handler function: return IndexAmRoutine with access method parameters
@@ -86,7 +94,7 @@ bthandler(PG_FUNCTION_ARGS)
 {
 	IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
 
-	amroutine->amstrategies = BTMaxStrategyNumber;
+	amroutine->amstrategies = BtreeMaxStrategyNumber;
 	amroutine->amsupport = BTNProcs;
 	amroutine->amcanorder = true;
 	amroutine->amcanbackward = true;
@@ -117,10 +125,10 @@ bthandler(PG_FUNCTION_ARGS)
 	amroutine->amendscan = btendscan;
 	amroutine->ammarkpos = btmarkpos;
 	amroutine->amrestrpos = btrestrpos;
+	amroutine->amcanorderbyop = btcanorderbyop;
 	amroutine->amestimateparallelscan = NULL;
 	amroutine->aminitparallelscan = NULL;
 	amroutine->amparallelrescan = NULL;
-	amroutine->amcanorderbyop = NULL;
 
 	PG_RETURN_POINTER(amroutine);
 }
@@ -304,6 +312,10 @@ btgettuple(IndexScanDesc scan, ScanDirection dir)
 
 	/* btree indexes are never lossy */
 	scan->xs_recheck = false;
+	scan->xs_recheckorderby = false;
+
+	if (so->scanDirection != NoMovementScanDirection)
+		dir = so->scanDirection;
 
 	/*
 	 * If we have any array keys, initialize them during first call for a
@@ -327,7 +339,8 @@ btgettuple(IndexScanDesc scan, ScanDirection dir)
 		 * the appropriate direction.  If we haven't done so yet, we call
 		 * _bt_first() to get the first item in the scan.
 		 */
-		if (!BTScanPosIsValid(state->currPos))
+		if (!BTScanPosIsValid(state->currPos) &&
+			(!so->knnState || !BTScanPosIsValid(so->knnState->currPos)))
 			res = _bt_first(scan, dir);
 		else
 		{
@@ -435,9 +448,6 @@ btbeginscan(Relation rel, int nkeys, int norderbys)
 	IndexScanDesc scan;
 	BTScanOpaque so;
 
-	/* no order by operators allowed */
-	Assert(norderbys == 0);
-
 	/* get the scan */
 	scan = RelationGetIndexScan(rel, nkeys, norderbys);
 
@@ -464,6 +474,9 @@ btbeginscan(Relation rel, int nkeys, int norderbys)
 	 * scan->xs_itupdesc whether we'll need it or not, since that's so cheap.
 	 */
 	so->state.currTuples = so->state.markTuples = NULL;
+	so->knnState = NULL;
+	so->distanceTypeByVal = true;
+	so->scanDirection = NoMovementScanDirection;
 
 	scan->xs_itupdesc = RelationGetDescr(rel);
 
@@ -493,6 +506,8 @@ _bt_release_current_position(BTScanState state, Relation indexRelation,
 static void
 _bt_release_scan_state(IndexScanDesc scan, BTScanState state, bool free)
 {
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+
 	/* No need to invalidate positions, if the RAM is about to be freed. */
 	_bt_release_current_position(state, scan->indexRelation, !free);
 
@@ -509,6 +524,14 @@ _bt_release_scan_state(IndexScanDesc scan, BTScanState state, bool free)
 	}
 	else
 		BTScanPosInvalidate(state->markPos);
+
+	if (!so->distanceTypeByVal)
+	{
+		pfree(DatumGetPointer(state->currDistance));
+		state->currDistance = PointerGetDatum(NULL);
+		pfree(DatumGetPointer(state->markDistance));
+		state->markDistance = PointerGetDatum(NULL);
+	}
 }
 
 /*
@@ -523,6 +546,13 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
 
 	_bt_release_scan_state(scan, state, false);
 
+	if (so->knnState)
+	{
+		_bt_release_scan_state(scan, so->knnState, true);
+		pfree(so->knnState);
+		so->knnState = NULL;
+	}
+
 	/*
 	 * Allocate tuple workspace arrays, if needed for an index-only scan and
 	 * not already done in a previous rescan call.  To save on palloc
@@ -552,6 +582,14 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
 				scan->numberOfKeys * sizeof(ScanKeyData));
 	so->numberOfKeys = 0;		/* until _bt_preprocess_keys sets it */
 
+	if (orderbys && scan->numberOfOrderBys > 0)
+		memmove(scan->orderByData,
+				orderbys,
+				scan->numberOfOrderBys * sizeof(ScanKeyData));
+
+	so->scanDirection = NoMovementScanDirection;
+	so->distanceTypeByVal = true;
+
 	/* If any keys are SK_SEARCHARRAY type, set up array-key info */
 	_bt_preprocess_array_keys(scan);
 }
@@ -566,6 +604,12 @@ btendscan(IndexScanDesc scan)
 
 	_bt_release_scan_state(scan, &so->state, true);
 
+	if (so->knnState)
+	{
+		_bt_release_scan_state(scan, so->knnState, true);
+		pfree(so->knnState);
+	}
+
 	/* Release storage */
 	if (so->keyData != NULL)
 		pfree(so->keyData);
@@ -577,7 +621,7 @@ btendscan(IndexScanDesc scan)
 }
 
 static void
-_bt_mark_current_position(BTScanState state)
+_bt_mark_current_position(BTScanOpaque so, BTScanState state)
 {
 	/* There may be an old mark with a pin (but no lock). */
 	BTScanPosUnpinIfPinned(state->markPos);
@@ -595,6 +639,21 @@ _bt_mark_current_position(BTScanState state)
 		BTScanPosInvalidate(state->markPos);
 		state->markItemIndex = -1;
 	}
+
+	if (so->knnState)
+	{
+		if (!so->distanceTypeByVal)
+			pfree(DatumGetPointer(state->markDistance));
+
+		state->markIsNull = !BTScanPosIsValid(state->currPos) ||
+			state->currIsNull;
+
+		state->markDistance =
+			state->markIsNull ? PointerGetDatum(NULL)
+			: datumCopy(state->currDistance,
+						so->distanceTypeByVal,
+						so->distanceTypeLen);
+	}
 }
 
 /*
@@ -605,7 +664,13 @@ btmarkpos(IndexScanDesc scan)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
-	_bt_mark_current_position(&so->state);
+	_bt_mark_current_position(so, &so->state);
+
+	if (so->knnState)
+	{
+		_bt_mark_current_position(so, so->knnState);
+		so->markRightIsNearest = so->currRightIsNearest;
+	}
 
 	/* Also record the current positions of any array keys */
 	if (so->numArrayKeys)
@@ -615,6 +680,8 @@ btmarkpos(IndexScanDesc scan)
 static void
 _bt_restore_marked_position(IndexScanDesc scan, BTScanState state)
 {
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+
 	if (state->markItemIndex >= 0)
 	{
 		/*
@@ -650,6 +717,19 @@ _bt_restore_marked_position(IndexScanDesc scan, BTScanState state)
 					   state->markPos.nextTupleOffset);
 		}
 	}
+
+	if (so->knnState)
+	{
+		if (!so->distanceTypeByVal)
+			pfree(DatumGetPointer(state->currDistance));
+
+		state->currIsNull = state->markIsNull;
+		state->currDistance =
+			state->markIsNull ? PointerGetDatum(NULL)
+			: datumCopy(state->markDistance,
+						so->distanceTypeByVal,
+						so->distanceTypeLen);
+	}
 }
 
 /*
@@ -665,6 +745,12 @@ btrestrpos(IndexScanDesc scan)
 		_bt_restore_array_keys(scan);
 
 	_bt_restore_marked_position(scan, &so->state);
+
+	if (so->knnState)
+	{
+		_bt_restore_marked_position(scan, so->knnState);
+		so->currRightIsNearest = so->markRightIsNearest;
+	}
 }
 
 /*
@@ -1152,3 +1238,26 @@ btcanreturn(Relation index, int attno)
 {
 	return true;
 }
+
+/*
+ *	btcanorderbyop() -- Check whether KNN-search strategy is applicable to
+ *		the given ORDER BY distance operator.
+ */
+static Expr *
+btcanorderbyop(IndexOptInfo *index, PathKey *pathkey, int pathkeyno,
+			   Expr *expr, int *indexcol_p)
+{
+	if (pathkeyno > 1)
+		return NULL; /* only one ORDER BY clause is supported */
+
+	expr = match_clause_to_ordering_op(index,
+									   0, /* ORDER BY distance to the first
+										   * index column is only supported */
+									   expr,
+									   pathkey->pk_opfamily);
+
+	if (expr)
+		*indexcol_p = 0;
+
+	return expr;
+}
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index c041056..97a1061 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -561,6 +561,127 @@ _bt_load_first_page(IndexScanDesc scan, BTScanState state, ScanDirection dir,
 }
 
 /*
+ *  _bt_calc_current_dist() -- Calculate distance from the current item
+ *		of the scan state to the target order-by ScanKey argument.
+ */
+static void
+_bt_calc_current_dist(IndexScanDesc scan, BTScanState state)
+{
+	BTScanOpaque	so = (BTScanOpaque) scan->opaque;
+	BTScanPosItem  *currItem = &state->currPos.items[state->currPos.itemIndex];
+	IndexTuple		itup = (IndexTuple) (state->currTuples + currItem->tupleOffset);
+	ScanKey			scankey = &scan->orderByData[0];
+	Datum			value;
+
+	value = index_getattr(itup, 1, scan->xs_itupdesc, &state->currIsNull);
+
+	if (state->currIsNull)
+		return; /* NULL distance */
+
+	value = FunctionCall2Coll(&scankey->sk_func,
+							  scankey->sk_collation,
+							  value,
+							  scankey->sk_argument);
+
+	/* free previous distance value for by-ref types */
+	if (!so->distanceTypeByVal)
+		pfree(DatumGetPointer(state->currDistance));
+
+	state->currDistance = value;
+}
+
+/*
+ *  _bt_compare_current_dist() -- Compare current distances of the left and right scan states.
+ *
+ *  NULL distances are considered to be greater than any non-NULL distances.
+ *
+ *  Returns true if right distance is lesser than left, otherwise false.
+ */
+static bool
+_bt_compare_current_dist(BTScanOpaque so, BTScanState rstate, BTScanState lstate)
+{
+	if (lstate->currIsNull)
+		return true; /* non-NULL < NULL */
+
+	if (rstate->currIsNull)
+		return false; /* NULL > non-NULL */
+
+	return DatumGetBool(FunctionCall2Coll(&so->distanceCmpProc,
+										  InvalidOid, /* XXX collation for distance comparison */
+										  rstate->currDistance,
+										  lstate->currDistance));
+}
+
+/*
+ * _bt_init_knn_scan() -- Init additional scan state for KNN search.
+ *
+ * Caller must pin and read-lock scan->state.currPos.buf buffer.
+ *
+ * If empty result was found returned false.
+ * Otherwise prepared current item, and returned true.
+ */
+static bool
+_bt_init_knn_scan(IndexScanDesc scan, OffsetNumber offnum)
+{
+	BTScanOpaque	so = (BTScanOpaque) scan->opaque;
+	BTScanState		rstate = &so->state; /* right (forward) main scan state */
+	BTScanState		lstate; /* additional left (backward) KNN scan state */
+	Buffer			buf = rstate->currPos.buf;
+	bool			left,
+					right;
+
+	lstate = so->knnState = (BTScanState) palloc(sizeof(BTScanStateData));
+	_bt_allocate_tuple_workspaces(lstate);
+
+	if (!scan->xs_want_itup)
+	{
+		/* We need to request index tuples for distance comparison. */
+		scan->xs_want_itup = true;
+		_bt_allocate_tuple_workspaces(rstate);
+	}
+
+	/* Bump pin and lock count before BTScanPosData copying. */
+	IncrBufferRefCount(buf);
+	LockBuffer(buf, BT_READ);
+
+	memcpy(&lstate->currPos, &rstate->currPos, sizeof(BTScanPosData));
+	lstate->currPos.moreLeft = true;
+	lstate->currPos.moreRight = false;
+
+	BTScanPosInvalidate(lstate->markPos);
+	lstate->markItemIndex = -1;
+	lstate->killedItems = NULL;
+	lstate->numKilled = 0;
+	lstate->currDistance = PointerGetDatum(NULL);
+	lstate->markDistance = PointerGetDatum(NULL);
+
+	/* Load first pages from the both scans. */
+	right = _bt_load_first_page(scan, rstate, ForwardScanDirection, offnum);
+	left = _bt_load_first_page(scan, lstate, BackwardScanDirection,
+							   OffsetNumberPrev(offnum));
+
+	if (!left && !right)
+		return false; /* empty result */
+
+	if (left && right)
+	{
+		/*
+		 * We have found items in both scan directions,
+		 * determine nearest item to return.
+		 */
+		_bt_calc_current_dist(scan, rstate);
+		_bt_calc_current_dist(scan, lstate);
+		so->currRightIsNearest = _bt_compare_current_dist(so, rstate, lstate);
+
+		/* Reset right flag if the left item is nearer. */
+		right = so->currRightIsNearest;
+	}
+
+	/* Return current item of the selected scan direction. */
+	return _bt_return_current_item(scan, right ? rstate : lstate);
+}
+
+/*
  *	_bt_first() -- Find the first item in a scan.
  *
  *		We need to be clever about the direction of scan, the search
@@ -663,7 +784,21 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	 *----------
 	 */
 	strat_total = BTEqualStrategyNumber;
-	if (so->numberOfKeys > 0)
+
+	if (scan->numberOfOrderBys > 0)
+	{
+		if (_bt_process_orderings(scan, startKeys, &keysCount, notnullkeys))
+			/* use bidirectional KNN scan */
+			strat_total = BtreeKNNSearchStrategyNumber;
+
+		/* use selected KNN scan direction */
+		if (so->scanDirection != NoMovementScanDirection)
+			dir = so->scanDirection;
+	}
+
+	if (so->numberOfKeys > 0 &&
+	/* startKeys for KNN search already have been initialized */
+		strat_total != BtreeKNNSearchStrategyNumber)
 	{
 		AttrNumber	curattr;
 		ScanKey		chosen;
@@ -1003,6 +1138,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 			break;
 
 		case BTGreaterEqualStrategyNumber:
+		case BtreeKNNSearchStrategyNumber:
 
 			/*
 			 * Find first item >= scankey.  (This is only used for forward
@@ -1093,16 +1229,21 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	Assert(!BTScanPosIsValid(*currPos));
 	currPos->buf = buf;
 
+	if (strat_total == BtreeKNNSearchStrategyNumber)
+		return _bt_init_knn_scan(scan, offnum);
+
 	if (!_bt_load_first_page(scan, &so->state, dir, offnum))
-		return false;
+		return false; /* empty result */
 
 	/* OK, currPos->itemIndex says what to return */
 	return _bt_return_current_item(scan, &so->state);
 }
 
 /*
- *	Advance to next tuple on current page; or if there's no more,
- *	try to step to the next page with data.
+ *	_bt_next_item() -- Advance to next tuple on current page;
+ *		or if there's no more, try to step to the next page with data.
+ *
+ *	If there are no more matching records in the given direction
  */
 static bool
 _bt_next_item(IndexScanDesc scan, BTScanState state, ScanDirection dir)
@@ -1122,6 +1263,52 @@ _bt_next_item(IndexScanDesc scan, BTScanState state, ScanDirection dir)
 }
 
 /*
+ *	_bt_next_nearest() -- Return next nearest item from bidirectional KNN scan.
+ */
+static bool
+_bt_next_nearest(IndexScanDesc scan)
+{
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+	BTScanState rstate = &so->state;
+	BTScanState lstate = so->knnState;
+	bool		right = BTScanPosIsValid(rstate->currPos);
+	bool		left = BTScanPosIsValid(lstate->currPos);
+	bool		advanceRight;
+
+	if (right && left)
+		advanceRight = so->currRightIsNearest;
+	else if (right)
+		advanceRight = true;
+	else if (left)
+		advanceRight = false;
+	else
+		return false; /* end of the scan */
+
+	*(advanceRight ? &right : &left) =
+		_bt_next_item(scan,
+					  advanceRight ? rstate : lstate,
+					  advanceRight ? ForwardScanDirection :
+					  BackwardScanDirection);
+
+	if (!left && !right)
+		return false; /* end of the scan */
+
+	if (left && right)
+	{
+		/*
+		 * If there are items in both scans we must recalculate distance
+		 * in the advanced scan.
+		 */
+		_bt_calc_current_dist(scan, advanceRight ? rstate : lstate);
+		so->currRightIsNearest = _bt_compare_current_dist(so, rstate, lstate);
+		right = so->currRightIsNearest;
+	}
+
+	/* return nearest item */
+	return _bt_return_current_item(scan, right ? rstate : lstate);
+}
+
+/*
  *	_bt_next() -- Get the next item in a scan.
  *
  *		On entry, so->currPos describes the current page, which may be pinned
@@ -1140,6 +1327,10 @@ _bt_next(IndexScanDesc scan, ScanDirection dir)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
+	if (so->knnState)
+		/* return next neareset item from KNN scan */
+		return _bt_next_nearest(scan);
+
 	if (!_bt_next_item(scan, &so->state, dir))
 		return false;
 
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index ebcba7e..e5e855e 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -20,11 +20,13 @@
 #include "access/nbtree.h"
 #include "access/reloptions.h"
 #include "access/relscan.h"
+#include "catalog/pg_amop.h"
 #include "miscadmin.h"
 #include "utils/array.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
 #include "utils/rel.h"
+#include "utils/syscache.h"
 
 
 typedef struct BTSortArrayContext
@@ -2061,6 +2063,34 @@ btproperty(Oid index_oid, int attno,
 			*res = true;
 			return true;
 
+		case AMPROP_DISTANCE_ORDERABLE:
+			{
+				Oid			opclass,
+							opfamily,
+							opcindtype;
+
+				/* answer only for columns, not AM or whole index */
+				if (attno == 0)
+					return false;
+
+				opclass = get_index_column_opclass(index_oid, attno);
+
+				if (!OidIsValid(opclass) ||
+					!get_opclass_opfamily_and_input_type(opclass,
+													 &opfamily, &opcindtype))
+				{
+					*isnull = true;
+					return true;
+				}
+
+				*res = SearchSysCacheExists(AMOPSTRATEGY,
+											ObjectIdGetDatum(opfamily),
+											ObjectIdGetDatum(opcindtype),
+											ObjectIdGetDatum(opcindtype),
+								   Int16GetDatum(BtreeKNNSearchStrategyNumber));
+				return true;
+			}
+
 		default:
 			return false;		/* punt to generic code */
 	}
@@ -2076,3 +2106,242 @@ _bt_allocate_tuple_workspaces(BTScanState state)
 	state->currTuples = (char *) palloc(BLCKSZ * 2);
 	state->markTuples = state->currTuples + BLCKSZ;
 }
+
+static Oid
+_bt_get_sortfamily_for_ordering_key(Relation rel, ScanKey skey)
+{
+	HeapTuple	tp;
+	Form_pg_amop amop_tup;
+	Oid			sortfamily;
+
+	tp = SearchSysCache4(AMOPSTRATEGY,
+						 ObjectIdGetDatum(rel->rd_opfamily[skey->sk_attno - 1]),
+						 ObjectIdGetDatum(rel->rd_opcintype[skey->sk_attno - 1]),
+						 ObjectIdGetDatum(skey->sk_subtype),
+						 Int16GetDatum(skey->sk_strategy));
+	if (!HeapTupleIsValid(tp))
+		return InvalidOid;
+	amop_tup = (Form_pg_amop) GETSTRUCT(tp);
+	sortfamily = amop_tup->amopsortfamily;
+	ReleaseSysCache(tp);
+
+	return sortfamily;
+}
+
+static bool
+_bt_compare_row_key_with_ordering_key(ScanKey row, ScanKey ord, bool *result)
+{
+	ScanKey		subkey = (ScanKey) DatumGetPointer(row->sk_argument);
+	int32		cmpresult;
+
+	Assert(subkey->sk_attno == 1);
+	Assert(subkey->sk_flags & SK_ROW_MEMBER);
+
+	if (subkey->sk_flags & SK_ISNULL)
+		return false;
+
+	/* Perform the test --- three-way comparison not bool operator */
+	cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func,
+												subkey->sk_collation,
+												ord->sk_argument,
+												subkey->sk_argument));
+
+	if (subkey->sk_flags & SK_BT_DESC)
+		cmpresult = -cmpresult;
+
+	/*
+	 * At this point cmpresult indicates the overall result of the row
+	 * comparison, and subkey points to the deciding column (or the last
+	 * column if the result is "=").
+	 */
+	switch (subkey->sk_strategy)
+	{
+			/* EQ and NE cases aren't allowed here */
+		case BTLessStrategyNumber:
+			*result = cmpresult < 0;
+			break;
+		case BTLessEqualStrategyNumber:
+			*result = cmpresult <= 0;
+			break;
+		case BTGreaterEqualStrategyNumber:
+			*result = cmpresult >= 0;
+			break;
+		case BTGreaterStrategyNumber:
+			*result = cmpresult > 0;
+			break;
+		default:
+			elog(ERROR, "unrecognized RowCompareType: %d",
+				 (int) subkey->sk_strategy);
+			*result = false;	/* keep compiler quiet */
+	}
+
+	return true;
+}
+
+/* _bt_select_knn_search_strategy() -- Determine which KNN scan strategy to use:
+ *		bidirectional or unidirectional. We are checking here if the
+ *		ordering scankey argument falls into the scan range: if it falls
+ *		we must use bidirectional scan, otherwise we use unidirectional.
+ *
+ *	Returns BtreeKNNSearchStrategyNumber for bidirectional scan or
+ *			strategy number of non-matched scankey for unidirectional.
+ */
+static StrategyNumber
+_bt_select_knn_search_strategy(IndexScanDesc scan, ScanKey ord)
+{
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+	ScanKey		cond;
+
+	for (cond = so->keyData; cond < so->keyData + so->numberOfKeys; cond++)
+	{
+		bool		result;
+
+		if (cond->sk_attno != 1)
+			break; /* only interesting in the first index attribute */
+
+		if (cond->sk_strategy == BTEqualStrategyNumber)
+			/* always use simple unidirectional scan for equals operators */
+			return BTEqualStrategyNumber;
+
+		if (cond->sk_flags & SK_ROW_HEADER)
+		{
+			if (!_bt_compare_row_key_with_ordering_key(cond, ord, &result))
+				return BTEqualStrategyNumber; /* ROW(fist_index_attr, ...) IS NULL */
+		}
+		else
+		{
+			if (!_bt_compare_scankey_args(scan, cond, ord, cond, &result))
+				elog(ERROR, "could not compare ordering key");
+		}
+
+		if (!result)
+			/*
+			 * Ordering scankey argument is out of scan range,
+			 * use unidirectional scan.
+			 */
+			return cond->sk_strategy;
+	}
+
+	return BtreeKNNSearchStrategyNumber; /* use bidirectional scan */
+}
+
+/*
+ *  _bt_init_distance_comparison() -- Init distance typlen/typbyval and its
+ *  	comparison procedure.
+ */
+static void
+_bt_init_distance_comparison(IndexScanDesc scan, ScanKey ord)
+{
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+	RegProcedure opcode;
+	Oid			sortfamily;
+	Oid			opno;
+	Oid			distanceType;
+
+	distanceType = get_func_rettype(ord->sk_func.fn_oid);
+
+	sortfamily = _bt_get_sortfamily_for_ordering_key(scan->indexRelation, ord);
+
+	if (!OidIsValid(sortfamily))
+		elog(ERROR, "could not find sort family for btree ordering operator");
+
+	opno = get_opfamily_member(sortfamily,
+							   distanceType,
+							   distanceType,
+							   BTLessEqualStrategyNumber);
+
+	if (!OidIsValid(opno))
+		elog(ERROR, "could not find operator for btree distance comparison");
+
+	opcode = get_opcode(opno);
+
+	if (!RegProcedureIsValid(opcode))
+		elog(ERROR,
+		  "could not find procedure for btree distance comparison operator");
+
+	fmgr_info(opcode, &so->distanceCmpProc);
+
+	get_typlenbyval(distanceType, &so->distanceTypeLen, &so->distanceTypeByVal);
+
+	if (!so->distanceTypeByVal)
+	{
+		so->state.currDistance = PointerGetDatum(NULL);
+		so->state.markDistance = PointerGetDatum(NULL);
+	}
+}
+
+/*
+ * _bt_process_orderings() -- Process ORDER BY distance scankeys and
+ *		select corresponding KNN strategy.
+ *
+ * If bidirectional scan is selected then one scankey is initialized
+ * using bufKeys and placed into startKeys/keysCount, true is returned.
+ *
+ * Otherwise, so->scanDirection is set and false is returned.
+ */
+bool
+_bt_process_orderings(IndexScanDesc scan, ScanKey *startKeys, int *keysCount,
+					  ScanKeyData bufKeys[])
+{
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+	ScanKey		ord = scan->orderByData;
+
+	if (scan->numberOfOrderBys > 1 || ord->sk_attno != 1)
+		/* it should not happen, see btcanorderbyop() */
+		elog(ERROR, "only one btree ordering operator "
+					"for the first index column is supported");
+
+	Assert(ord->sk_strategy == BtreeKNNSearchStrategyNumber);
+
+	switch (_bt_select_knn_search_strategy(scan, ord))
+	{
+		case BTLessStrategyNumber:
+		case BTLessEqualStrategyNumber:
+			/*
+			 * Ordering key argument is greater than all values in scan range.
+			 * select backward scan direction.
+			 */
+			so->scanDirection = BackwardScanDirection;
+			return false;
+
+		case BTEqualStrategyNumber:
+			/* Use default unidirectional scan direction. */
+			return false;
+
+		case BTGreaterEqualStrategyNumber:
+		case BTGreaterStrategyNumber:
+			/*
+			 * Ordering key argument is lesser than all values in scan range.
+			 * select forward scan direction.
+			 */
+			so->scanDirection = ForwardScanDirection;
+			return false;
+
+		case BtreeKNNSearchStrategyNumber:
+			/*
+			 * Ordering key argument falls into scan range,
+			 * use bidirectional scan.
+			 */
+			break;
+	}
+
+	_bt_init_distance_comparison(scan, ord);
+
+	/* Init btree search key with ordering key argument. */
+	ScanKeyEntryInitialize(&bufKeys[0],
+					 (scan->indexRelation->rd_indoption[ord->sk_attno - 1] <<
+					  SK_BT_INDOPTION_SHIFT) |
+						   SK_ORDER_BY |
+						   SK_SEARCHNULL /* only for invalid procedure oid, see
+										  * assert in ScanKeyEntryInitialize */,
+						   ord->sk_attno,
+						   BtreeKNNSearchStrategyNumber,
+						   ord->sk_subtype,
+						   ord->sk_collation,
+						   InvalidOid,
+						   ord->sk_argument);
+
+	startKeys[(*keysCount)++] = &bufKeys[0];
+
+	return true;
+}
diff --git a/src/backend/access/nbtree/nbtvalidate.c b/src/backend/access/nbtree/nbtvalidate.c
index 88e33f5..c56f4e8 100644
--- a/src/backend/access/nbtree/nbtvalidate.c
+++ b/src/backend/access/nbtree/nbtvalidate.c
@@ -22,9 +22,17 @@
 #include "catalog/pg_opfamily.h"
 #include "catalog/pg_type.h"
 #include "utils/builtins.h"
+#include "utils/lsyscache.h"
 #include "utils/regproc.h"
 #include "utils/syscache.h"
 
+#define BTRequiredOperatorSet \
+		((1 << BTLessStrategyNumber) | \
+		 (1 << BTLessEqualStrategyNumber) | \
+		 (1 << BTEqualStrategyNumber) | \
+		 (1 << BTGreaterEqualStrategyNumber) | \
+		 (1 << BTGreaterStrategyNumber))
+
 
 /*
  * Validator for a btree opclass.
@@ -123,10 +131,11 @@ btvalidate(Oid opclassoid)
 	{
 		HeapTuple	oprtup = &oprlist->members[i]->tuple;
 		Form_pg_amop oprform = (Form_pg_amop) GETSTRUCT(oprtup);
+		Oid			op_rettype;
 
 		/* Check that only allowed strategy numbers exist */
 		if (oprform->amopstrategy < 1 ||
-			oprform->amopstrategy > BTMaxStrategyNumber)
+			oprform->amopstrategy > BtreeMaxStrategyNumber)
 		{
 			ereport(INFO,
 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
@@ -137,20 +146,29 @@ btvalidate(Oid opclassoid)
 			result = false;
 		}
 
-		/* btree doesn't support ORDER BY operators */
-		if (oprform->amoppurpose != AMOP_SEARCH ||
-			OidIsValid(oprform->amopsortfamily))
+		/* btree supports ORDER BY operators */
+		if (oprform->amoppurpose != AMOP_SEARCH)
 		{
-			ereport(INFO,
-					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
-					 errmsg("btree operator family \"%s\" contains invalid ORDER BY specification for operator %s",
-							opfamilyname,
-							format_operator(oprform->amopopr))));
-			result = false;
+			/* ... and operator result must match the claimed btree opfamily */
+			op_rettype = get_op_rettype(oprform->amopopr);
+			if (!opfamily_can_sort_type(oprform->amopsortfamily, op_rettype))
+			{
+				ereport(INFO,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree operator family %s contains invalid ORDER BY specification for operator %s",
+								opfamilyname,
+								format_operator(oprform->amopopr))));
+				result = false;
+			}
+		}
+		else
+		{
+			/* Search operators must always return bool */
+			op_rettype = BOOLOID;
 		}
 
 		/* Check operator signature --- same for all btree strategies */
-		if (!check_amop_signature(oprform->amopopr, BOOLOID,
+		if (!check_amop_signature(oprform->amopopr, op_rettype,
 								  oprform->amoplefttype,
 								  oprform->amoprighttype))
 		{
@@ -189,12 +207,8 @@ btvalidate(Oid opclassoid)
 		 * or support functions for this datatype pair.  The only thing that
 		 * is considered optional is the sortsupport function.
 		 */
-		if (thisgroup->operatorset !=
-			((1 << BTLessStrategyNumber) |
-			 (1 << BTLessEqualStrategyNumber) |
-			 (1 << BTEqualStrategyNumber) |
-			 (1 << BTGreaterEqualStrategyNumber) |
-			 (1 << BTGreaterStrategyNumber)))
+		if ((thisgroup->operatorset & BTRequiredOperatorSet) !=
+			BTRequiredOperatorSet)
 		{
 			ereport(INFO,
 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 21659a6..9762e8d 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -982,6 +982,10 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 	 * if we are only trying to build bitmap indexscans, nor if we have to
 	 * assume the scan is unordered.
 	 */
+	useful_pathkeys = NIL;
+	orderbyclauses = NIL;
+	orderbyclausecols = NIL;
+
 	pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
 								!found_lower_saop_clause &&
 								has_useful_pathkeys(root, rel));
@@ -992,10 +996,10 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 											  ForwardScanDirection);
 		useful_pathkeys = truncate_useless_pathkeys(root, rel,
 													index_pathkeys);
-		orderbyclauses = NIL;
-		orderbyclausecols = NIL;
 	}
-	else if (index->amcanorderbyop && pathkeys_possibly_useful)
+
+	if (useful_pathkeys == NIL &&
+		index->amcanorderbyop && pathkeys_possibly_useful)
 	{
 		/* see if we can generate ordering operators for query_pathkeys */
 		match_pathkeys_to_index(index, root->query_pathkeys,
@@ -1006,12 +1010,6 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 		else
 			useful_pathkeys = NIL;
 	}
-	else
-	{
-		useful_pathkeys = NIL;
-		orderbyclauses = NIL;
-		orderbyclausecols = NIL;
-	}
 
 	/*
 	 * 3. Check if an index-only scan is possible.  If we're not building
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 4124010..030993b 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -624,6 +624,12 @@ typedef struct BTScanStateData
 	/* keep these last in struct for efficiency */
 	BTScanPosData currPos;		/* current position data */
 	BTScanPosData markPos;		/* marked position, if any */
+
+	/* KNN-search fields: */
+	Datum		currDistance;	/* current distance */
+	Datum		markDistance;	/* marked distance */
+	bool		currIsNull;		/* current item is NULL */
+	bool		markIsNull;		/* marked item is NULL */
 }	BTScanStateData, *BTScanState;
 
 typedef struct BTScanOpaqueData
@@ -640,7 +646,17 @@ typedef struct BTScanOpaqueData
 	BTArrayKeyInfo *arrayKeys;	/* info about each equality-type array key */
 	MemoryContext arrayContext; /* scan-lifespan context for array data */
 
-	BTScanStateData	state;
+	BTScanStateData state;		/* main scan state */
+
+	/* KNN-search fields: */
+	BTScanState knnState;			/* optional scan state for KNN search */
+	ScanDirection scanDirection;	/* selected scan direction for
+									 * unidirectional KNN scan */
+	FmgrInfo	distanceCmpProc;	/* distance comparison procedure */
+	int16		distanceTypeLen;	/* distance typlen */
+	bool		distanceTypeByVal;	/* distance typebyval */
+	bool		currRightIsNearest;	/* current right item is nearest */
+	bool		markRightIsNearest;	/* marked right item is nearest */
 } BTScanOpaqueData;
 
 typedef BTScanOpaqueData *BTScanOpaque;
@@ -756,6 +772,8 @@ extern bool btproperty(Oid index_oid, int attno,
 		   IndexAMProperty prop, const char *propname,
 		   bool *res, bool *isnull);
 extern void _bt_allocate_tuple_workspaces(BTScanState state);
+extern bool _bt_process_orderings(IndexScanDesc scan,
+				  ScanKey *startKeys, int *keysCount, ScanKeyData bufKeys[]);
 
 /*
  * prototypes for functions in nbtvalidate.c
diff --git a/src/include/access/stratnum.h b/src/include/access/stratnum.h
index 489e5c5..0852f8a 100644
--- a/src/include/access/stratnum.h
+++ b/src/include/access/stratnum.h
@@ -32,7 +32,10 @@ typedef uint16 StrategyNumber;
 #define BTGreaterEqualStrategyNumber	4
 #define BTGreaterStrategyNumber			5
 
-#define BTMaxStrategyNumber				5
+#define BTMaxStrategyNumber				5		/* number of canonical B-tree strategies */
+
+#define BtreeKNNSearchStrategyNumber	6		/* for <-> (distance) */
+#define BtreeMaxStrategyNumber			6		/* number of extended B-tree strategies */
 
 
 /*
diff --git a/src/test/regress/expected/alter_generic.out b/src/test/regress/expected/alter_generic.out
index b01be59..778dae3 100644
--- a/src/test/regress/expected/alter_generic.out
+++ b/src/test/regress/expected/alter_generic.out
@@ -347,10 +347,10 @@ ROLLBACK;
 CREATE OPERATOR FAMILY alt_opf4 USING btree;
 ALTER OPERATOR FAMILY alt_opf4 USING invalid_index_method ADD  OPERATOR 1 < (int4, int2); -- invalid indexing_method
 ERROR:  access method "invalid_index_method" does not exist
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 6 < (int4, int2); -- operator number should be between 1 and 5
-ERROR:  invalid operator number 6, must be between 1 and 5
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 0 < (int4, int2); -- operator number should be between 1 and 5
-ERROR:  invalid operator number 0, must be between 1 and 5
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 7 < (int4, int2); -- operator number should be between 1 and 6
+ERROR:  invalid operator number 7, must be between 1 and 6
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 0 < (int4, int2); -- operator number should be between 1 and 6
+ERROR:  invalid operator number 0, must be between 1 and 6
 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
@@ -397,11 +397,12 @@ DROP OPERATOR FAMILY alt_opf8 USING btree;
 CREATE OPERATOR FAMILY alt_opf9 USING gist;
 ALTER OPERATOR FAMILY alt_opf9 USING gist ADD OPERATOR 1 < (int4, int4) FOR ORDER BY float_ops;
 DROP OPERATOR FAMILY alt_opf9 USING gist;
--- Should fail. Ensure correct ordering methods in ALTER OPERATOR FAMILY ... ADD OPERATOR .. FOR ORDER BY
+-- Should work. Ensure correct ordering methods in ALTER OPERATOR FAMILY ... ADD OPERATOR .. FOR ORDER BY
+BEGIN TRANSACTION;
 CREATE OPERATOR FAMILY alt_opf10 USING btree;
 ALTER OPERATOR FAMILY alt_opf10 USING btree ADD OPERATOR 1 < (int4, int4) FOR ORDER BY float_ops;
-ERROR:  access method "btree" does not support ordering operators
 DROP OPERATOR FAMILY alt_opf10 USING btree;
+ROLLBACK;
 -- Should work. Textbook case of ALTER OPERATOR FAMILY ... ADD OPERATOR with FOR ORDER BY
 CREATE OPERATOR FAMILY alt_opf11 USING gist;
 ALTER OPERATOR FAMILY alt_opf11 USING gist ADD OPERATOR 1 < (int4, int4) FOR ORDER BY float_ops;
diff --git a/src/test/regress/sql/alter_generic.sql b/src/test/regress/sql/alter_generic.sql
index c9ea479..bcf9cf6 100644
--- a/src/test/regress/sql/alter_generic.sql
+++ b/src/test/regress/sql/alter_generic.sql
@@ -295,8 +295,8 @@ ROLLBACK;
 -- Should fail. Invalid values for ALTER OPERATOR FAMILY .. ADD / DROP
 CREATE OPERATOR FAMILY alt_opf4 USING btree;
 ALTER OPERATOR FAMILY alt_opf4 USING invalid_index_method ADD  OPERATOR 1 < (int4, int2); -- invalid indexing_method
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 6 < (int4, int2); -- operator number should be between 1 and 5
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 0 < (int4, int2); -- operator number should be between 1 and 5
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 7 < (int4, int2); -- operator number should be between 1 and 6
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 0 < (int4, int2); -- operator number should be between 1 and 6
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 1 < ; -- operator without argument types
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 0 btint42cmp(int4, int2); -- function number should be between 1 and 5
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 6 btint42cmp(int4, int2); -- function number should be between 1 and 5
@@ -340,10 +340,12 @@ CREATE OPERATOR FAMILY alt_opf9 USING gist;
 ALTER OPERATOR FAMILY alt_opf9 USING gist ADD OPERATOR 1 < (int4, int4) FOR ORDER BY float_ops;
 DROP OPERATOR FAMILY alt_opf9 USING gist;
 
--- Should fail. Ensure correct ordering methods in ALTER OPERATOR FAMILY ... ADD OPERATOR .. FOR ORDER BY
+-- Should work. Ensure correct ordering methods in ALTER OPERATOR FAMILY ... ADD OPERATOR .. FOR ORDER BY
+BEGIN TRANSACTION;
 CREATE OPERATOR FAMILY alt_opf10 USING btree;
 ALTER OPERATOR FAMILY alt_opf10 USING btree ADD OPERATOR 1 < (int4, int4) FOR ORDER BY float_ops;
 DROP OPERATOR FAMILY alt_opf10 USING btree;
+ROLLBACK;
 
 -- Should work. Textbook case of ALTER OPERATOR FAMILY ... ADD OPERATOR with FOR ORDER BY
 CREATE OPERATOR FAMILY alt_opf11 USING gist;