diff --git a/src/test/regress/expected/btree_index.out b/src/test/regress/expected/btree_index.out
index 755cd17..3ab1ad7 100644
--- a/src/test/regress/expected/btree_index.out
+++ b/src/test/regress/expected/btree_index.out
@@ -150,3 +150,489 @@ vacuum btree_tall_tbl;
 -- need to insert some rows to cause the fast root page to split.
 insert into btree_tall_tbl (id, t)
   select g, repeat('x', 100) from generate_series(1, 500) g;
+---
+--- Test B-tree distance ordering
+---
+SET enable_bitmapscan = OFF;
+-- temporarily disable bt_i4_index index on bt_i4_heap(seqno)
+UPDATE pg_index SET indisvalid = false WHERE indexrelid = 'bt_i4_index'::regclass;
+CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random, seqno);
+-- test unsupported orderings (by non-first index attribute or by more than one order keys)
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY seqno <-> 0;
+          QUERY PLAN          
+------------------------------
+ Sort
+   Sort Key: ((seqno <-> 0))
+   ->  Seq Scan on bt_i4_heap
+(3 rows)
+
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, seqno <-> 0;
+                  QUERY PLAN                   
+-----------------------------------------------
+ Sort
+   Sort Key: ((random <-> 0)), ((seqno <-> 0))
+   ->  Seq Scan on bt_i4_heap
+(3 rows)
+
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, random <-> 1;
+                   QUERY PLAN                   
+------------------------------------------------
+ Sort
+   Sort Key: ((random <-> 0)), ((random <-> 1))
+   ->  Seq Scan on bt_i4_heap
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+                                  QUERY PLAN                                   
+-------------------------------------------------------------------------------
+ Index Only Scan using bt_i4_heap_random_idx on bt_i4_heap
+   Index Cond: ((random > 1000000) AND (ROW(random, seqno) < ROW(6000000, 0)))
+   Order By: (random <-> 4000000)
+(3 rows)
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+ seqno | random  
+-------+---------
+  6448 | 4157193
+  9004 | 3783884
+  4408 | 4488889
+  8391 | 4825069
+  8984 | 3148979
+  1829 | 3053937
+  6262 | 3013326
+  5380 | 3000193
+  9142 | 2847247
+  8411 | 2809541
+  2859 | 5224694
+  6320 | 5257716
+  2126 | 2648497
+  8729 | 5450460
+  6862 | 5556001
+  1836 | 5593978
+  2681 | 2321799
+  2893 | 1919087
+   210 | 1809552
+(19 rows)
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 10000000;
+ seqno | random  
+-------+---------
+  1836 | 5593978
+  6862 | 5556001
+  8729 | 5450460
+  6320 | 5257716
+  2859 | 5224694
+  8391 | 4825069
+  4408 | 4488889
+  6448 | 4157193
+  9004 | 3783884
+  8984 | 3148979
+  1829 | 3053937
+  6262 | 3013326
+  5380 | 3000193
+  9142 | 2847247
+  8411 | 2809541
+  2126 | 2648497
+  2681 | 2321799
+  2893 | 1919087
+   210 | 1809552
+(19 rows)
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 0;
+ seqno | random  
+-------+---------
+   210 | 1809552
+  2893 | 1919087
+  2681 | 2321799
+  2126 | 2648497
+  8411 | 2809541
+  9142 | 2847247
+  5380 | 3000193
+  6262 | 3013326
+  1829 | 3053937
+  8984 | 3148979
+  9004 | 3783884
+  6448 | 4157193
+  4408 | 4488889
+  8391 | 4825069
+  2859 | 5224694
+  6320 | 5257716
+  8729 | 5450460
+  6862 | 5556001
+  1836 | 5593978
+(19 rows)
+
+DROP INDEX bt_i4_heap_random_idx;
+CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random DESC, seqno);
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+ seqno | random  
+-------+---------
+  6448 | 4157193
+  9004 | 3783884
+  4408 | 4488889
+  8391 | 4825069
+  8984 | 3148979
+  1829 | 3053937
+  6262 | 3013326
+  5380 | 3000193
+  9142 | 2847247
+  8411 | 2809541
+  2859 | 5224694
+  6320 | 5257716
+  2126 | 2648497
+  8729 | 5450460
+  6862 | 5556001
+  1836 | 5593978
+  2681 | 2321799
+  2893 | 1919087
+   210 | 1809552
+(19 rows)
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 10000000;
+ seqno | random  
+-------+---------
+  1836 | 5593978
+  6862 | 5556001
+  8729 | 5450460
+  6320 | 5257716
+  2859 | 5224694
+  8391 | 4825069
+  4408 | 4488889
+  6448 | 4157193
+  9004 | 3783884
+  8984 | 3148979
+  1829 | 3053937
+  6262 | 3013326
+  5380 | 3000193
+  9142 | 2847247
+  8411 | 2809541
+  2126 | 2648497
+  2681 | 2321799
+  2893 | 1919087
+   210 | 1809552
+(19 rows)
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 0;
+ seqno | random  
+-------+---------
+   210 | 1809552
+  2893 | 1919087
+  2681 | 2321799
+  2126 | 2648497
+  8411 | 2809541
+  9142 | 2847247
+  5380 | 3000193
+  6262 | 3013326
+  1829 | 3053937
+  8984 | 3148979
+  9004 | 3783884
+  6448 | 4157193
+  4408 | 4488889
+  8391 | 4825069
+  2859 | 5224694
+  6320 | 5257716
+  8729 | 5450460
+  6862 | 5556001
+  1836 | 5593978
+(19 rows)
+
+DROP INDEX bt_i4_heap_random_idx;
+-- enable bt_i4_index index on bt_i4_heap(seqno)
+UPDATE pg_index SET indisvalid = true WHERE indexrelid = 'bt_i4_index'::regclass;
+CREATE TABLE tenk3 AS SELECT thousand, tenthous FROM tenk1;
+INSERT INTO tenk3 VALUES (NULL, 1), (NULL, 2), (NULL, 3);
+-- Test distance ordering by ASC index
+CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand, tenthous);
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 998;
+ thousand | tenthous 
+----------+----------
+      998 |      998
+      998 |     1998
+      998 |     2998
+      998 |     3998
+      998 |     4998
+      998 |     5998
+      998 |     6998
+      998 |     7998
+      998 |     8998
+      998 |     9998
+      999 |      999
+      999 |     1999
+      999 |     2999
+      999 |     3999
+      999 |     4999
+      999 |     5999
+      999 |     6999
+      999 |     7999
+      999 |     8999
+      999 |     9999
+      997 |     9997
+      997 |     8997
+      997 |     7997
+      997 |     6997
+      997 |     5997
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 0;
+ thousand | tenthous 
+----------+----------
+      997 |     5997
+      997 |     6997
+      997 |     7997
+      997 |     8997
+      997 |     9997
+      998 |      998
+      998 |     1998
+      998 |     2998
+      998 |     3998
+      998 |     4998
+      998 |     5998
+      998 |     6998
+      998 |     7998
+      998 |     8998
+      998 |     9998
+      999 |      999
+      999 |     1999
+      999 |     2999
+      999 |     3999
+      999 |     4999
+      999 |     5999
+      999 |     6999
+      999 |     7999
+      999 |     8999
+      999 |     9999
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000
+ORDER BY thousand <-> 10000;
+ thousand | tenthous 
+----------+----------
+      999 |     9999
+      999 |     8999
+      999 |     7999
+      999 |     6999
+      999 |     5999
+      999 |     4999
+      999 |     3999
+      999 |     2999
+      999 |     1999
+      999 |      999
+      998 |     9998
+      998 |     8998
+      998 |     7998
+      998 |     6998
+      998 |     5998
+      998 |     4998
+      998 |     3998
+      998 |     2998
+      998 |     1998
+      998 |      998
+      997 |     9997
+      997 |     8997
+      997 |     7997
+      997 |     6997
+      997 |     5997
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+ORDER BY thousand <-> 500
+OFFSET 9970;
+ thousand | tenthous 
+----------+----------
+      999 |      999
+      999 |     1999
+      999 |     2999
+      999 |     3999
+      999 |     4999
+      999 |     5999
+      999 |     6999
+      999 |     7999
+      999 |     8999
+      999 |     9999
+        1 |     9001
+        1 |     8001
+        1 |     7001
+        1 |     6001
+        1 |     5001
+        1 |     4001
+        1 |     3001
+        1 |     2001
+        1 |     1001
+        1 |        1
+        0 |     9000
+        0 |     8000
+        0 |     7000
+        0 |     6000
+        0 |     5000
+        0 |     4000
+        0 |     3000
+        0 |     2000
+        0 |     1000
+        0 |        0
+          |        1
+          |        2
+          |        3
+(33 rows)
+
+DROP INDEX tenk3_idx;
+-- Test distance ordering by DESC index
+CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand DESC, tenthous);
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 998;
+ thousand | tenthous 
+----------+----------
+      998 |      998
+      998 |     1998
+      998 |     2998
+      998 |     3998
+      998 |     4998
+      998 |     5998
+      998 |     6998
+      998 |     7998
+      998 |     8998
+      998 |     9998
+      997 |     5997
+      997 |     6997
+      997 |     7997
+      997 |     8997
+      997 |     9997
+      999 |     9999
+      999 |     8999
+      999 |     7999
+      999 |     6999
+      999 |     5999
+      999 |     4999
+      999 |     3999
+      999 |     2999
+      999 |     1999
+      999 |      999
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 0;
+ thousand | tenthous 
+----------+----------
+      997 |     9997
+      997 |     8997
+      997 |     7997
+      997 |     6997
+      997 |     5997
+      998 |     9998
+      998 |     8998
+      998 |     7998
+      998 |     6998
+      998 |     5998
+      998 |     4998
+      998 |     3998
+      998 |     2998
+      998 |     1998
+      998 |      998
+      999 |     9999
+      999 |     8999
+      999 |     7999
+      999 |     6999
+      999 |     5999
+      999 |     4999
+      999 |     3999
+      999 |     2999
+      999 |     1999
+      999 |      999
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000
+ORDER BY thousand <-> 10000;
+ thousand | tenthous 
+----------+----------
+      999 |      999
+      999 |     1999
+      999 |     2999
+      999 |     3999
+      999 |     4999
+      999 |     5999
+      999 |     6999
+      999 |     7999
+      999 |     8999
+      999 |     9999
+      998 |      998
+      998 |     1998
+      998 |     2998
+      998 |     3998
+      998 |     4998
+      998 |     5998
+      998 |     6998
+      998 |     7998
+      998 |     8998
+      998 |     9998
+      997 |     5997
+      997 |     6997
+      997 |     7997
+      997 |     8997
+      997 |     9997
+(25 rows)
+
+SELECT thousand, tenthous FROM tenk3
+ORDER BY thousand <-> 500
+OFFSET 9970;
+ thousand | tenthous 
+----------+----------
+        1 |        1
+        1 |     1001
+        1 |     2001
+        1 |     3001
+        1 |     4001
+        1 |     5001
+        1 |     6001
+        1 |     7001
+        1 |     8001
+        1 |     9001
+      999 |     9999
+      999 |     8999
+      999 |     7999
+      999 |     6999
+      999 |     5999
+      999 |     4999
+      999 |     3999
+      999 |     2999
+      999 |     1999
+      999 |      999
+        0 |        0
+        0 |     1000
+        0 |     2000
+        0 |     3000
+        0 |     4000
+        0 |     5000
+        0 |     6000
+        0 |     7000
+        0 |     8000
+        0 |     9000
+          |        3
+          |        2
+          |        1
+(33 rows)
+
+DROP INDEX tenk3_idx;
+DROP TABLE tenk3;
+RESET enable_bitmapscan;
diff --git a/src/test/regress/sql/btree_index.sql b/src/test/regress/sql/btree_index.sql
index 65b08c8..b0559d7 100644
--- a/src/test/regress/sql/btree_index.sql
+++ b/src/test/regress/sql/btree_index.sql
@@ -92,3 +92,108 @@ vacuum btree_tall_tbl;
 -- need to insert some rows to cause the fast root page to split.
 insert into btree_tall_tbl (id, t)
   select g, repeat('x', 100) from generate_series(1, 500) g;
+
+---
+--- Test B-tree distance ordering
+---
+
+SET enable_bitmapscan = OFF;
+
+-- temporarily disable bt_i4_index index on bt_i4_heap(seqno)
+UPDATE pg_index SET indisvalid = false WHERE indexrelid = 'bt_i4_index'::regclass;
+
+CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random, seqno);
+
+-- test unsupported orderings (by non-first index attribute or by more than one order keys)
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY seqno <-> 0;
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, seqno <-> 0;
+EXPLAIN (COSTS OFF) SELECT * FROM bt_i4_heap ORDER BY random <-> 0, random <-> 1;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 10000000;
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 0;
+
+DROP INDEX bt_i4_heap_random_idx;
+
+CREATE INDEX bt_i4_heap_random_idx ON bt_i4_heap USING btree(random DESC, seqno);
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 4000000;
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 10000000;
+
+SELECT * FROM bt_i4_heap
+WHERE random > 1000000 AND (random, seqno) < (6000000, 0)
+ORDER BY random <-> 0;
+
+DROP INDEX bt_i4_heap_random_idx;
+
+-- enable bt_i4_index index on bt_i4_heap(seqno)
+UPDATE pg_index SET indisvalid = true WHERE indexrelid = 'bt_i4_index'::regclass;
+
+
+CREATE TABLE tenk3 AS SELECT thousand, tenthous FROM tenk1;
+
+INSERT INTO tenk3 VALUES (NULL, 1), (NULL, 2), (NULL, 3);
+
+-- Test distance ordering by ASC index
+CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand, tenthous);
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 998;
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 0;
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000
+ORDER BY thousand <-> 10000;
+
+SELECT thousand, tenthous FROM tenk3
+ORDER BY thousand <-> 500
+OFFSET 9970;
+
+DROP INDEX tenk3_idx;
+
+-- Test distance ordering by DESC index
+CREATE INDEX tenk3_idx ON tenk3 USING btree(thousand DESC, tenthous);
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 998;
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000)
+ORDER BY thousand <-> 0;
+
+SELECT thousand, tenthous FROM tenk3
+WHERE (thousand, tenthous) >= (997, 5000) AND thousand < 1000
+ORDER BY thousand <-> 10000;
+
+SELECT thousand, tenthous FROM tenk3
+ORDER BY thousand <-> 500
+OFFSET 9970;
+
+DROP INDEX tenk3_idx;
+
+DROP TABLE tenk3;
+
+RESET enable_bitmapscan;