postgres
diff --git a/‎contrib/pageinspect/expected/gist.out
Lines changed: 8 additions & 10 deletions b/‎contrib/pageinspect/expected/gist.out
Lines changed: 8 additions & 10 deletions
diff --git a/‎src/backend/access/gist/README
Lines changed: 16 additions & 0 deletions b/‎src/backend/access/gist/README
Lines changed: 16 additions & 0 deletions
@@ -33,14 +33,13 @@ COMMIT;
 SELECT * FROM gist_page_items(get_raw_page('test_gist_idx', 0), 'test_gist_idx');
  itemoffset |   ctid    | itemlen | dead |       keys        
 ------------+-----------+---------+------+-------------------
-          1 | (1,65535) |      40 | f    | (p)=((166,166))
-          2 | (2,65535) |      40 | f    | (p)=((332,332))
-          3 | (3,65535) |      40 | f    | (p)=((498,498))
-          4 | (4,65535) |      40 | f    | (p)=((664,664))
-          5 | (5,65535) |      40 | f    | (p)=((830,830))
-          6 | (6,65535) |      40 | f    | (p)=((996,996))
-          7 | (7,65535) |      40 | f    | (p)=((1000,1000))
-(7 rows)
+          1 | (1,65535) |      40 | f    | (p)=((185,185))
+          2 | (2,65535) |      40 | f    | (p)=((370,370))
+          3 | (3,65535) |      40 | f    | (p)=((555,555))
+          4 | (4,65535) |      40 | f    | (p)=((740,740))
+          5 | (5,65535) |      40 | f    | (p)=((870,870))
+          6 | (6,65535) |      40 | f    | (p)=((1000,1000))
+(6 rows)
 
 SELECT * FROM gist_page_items(get_raw_page('test_gist_idx', 1), 'test_gist_idx') LIMIT 5;
  itemoffset | ctid  | itemlen | dead |    keys     
@@ -63,7 +62,6 @@ SELECT itemoffset, ctid, itemlen FROM gist_page_items_bytea(get_raw_page('test_g
           4 | (4,65535) |      40
           5 | (5,65535) |      40
           6 | (6,65535) |      40
-          7 | (7,65535) |      40
-(7 rows)
+(6 rows)
 
 DROP TABLE test_gist;
@@ -26,6 +26,7 @@ The current implementation of GiST supports:
   * Concurrency
   * Recovery support via WAL logging
   * Buffering build algorithm
+  * Sorted build method
 
 The support for concurrency implemented in PostgreSQL was developed based on
 the paper "Access Methods for Next-Generation Database Systems" by
@@ -414,6 +415,21 @@ emptied yet; tuples never move upwards in the tree. The final emptying loops
 through buffers at a given level until all buffers at that level have been
 emptied, and then moves down to the next level.
 
+Sorted build method
+-------------------
+
+Sort all input tuples, pack them into GiST leaf pages in the sorted order,
+and create downlinks and internal pages as we go. This method builds the index
+from the bottom up, similar to how the B-tree index is built.
+
+The sorted method is used if the operator classes for all columns have a
+"sortsupport" defined. Otherwise, we fall back on inserting tuples one by one
+with optional buffering.
+
+Sorting GiST build requires good linearization of the sort opclass. That is not
+always the case in multidimensional data. To tackle the anomalies, we buffer
+index tuples and apply a picksplit function that can be multidimensional-aware.
+
 Bulk delete algorithm (VACUUM)
 ------------------------------