There are even more indexing-related features that can be added. In PostgreSQL, there is the concept of operator classes, which we discussed in Chapter 3, Making Use of Indexes.

The contrib module offers two extensions (namely, btree_gist and btree_gin) so that we can add B-tree functionality to GiST and GIN indexes. Why is this so useful? GiST indexes offer various features that are not supported by B-trees. One of those features is the ability to perform a k-nearest neighbor (KNN) search.

Why is this relevant? Imagine that somebody is looking for data that was added yesterday, around noon. So, when was that? In some cases, it may be hard to come up with boundaries, for example, if somebody is looking for a product that costs around 70 euros. KNN can come to the rescue here. Following is an example:

test=# CREATE TABLE t_test (id int);
CREATE TABLE

Now, some simple data needs to be added:

test=# INSERT INTO t_test SELECT * FROM generate_series(1, 100000);
INSERT 0 100000

Now, the extension can be added:

test=# CREATE EXTENSION btree_gist;
CREATE EXTENSION

Adding a gist index to the column is easy; just use the USING gist clause. Note that adding a gist index to an integer column only works if the extension is present. Otherwise, PostgreSQL will report that there is no suitable operator class:

test=# CREATE INDEX idx_id ON t_test USING gist(id);
CREATE INDEX

Once the index has been deployed, it is possible to order by distance:

test=# SELECT * 
 FROM t_test 
 ORDER BY id <-> 100
 LIMIT 6;
 id
-----
 100
 101
 99
 102
 98
 97
(6 rows)

As you can see, the first row is an exact match. The matches that follow are already less precise and are getting worse. The query will always return a fixed number of rows.

The important thing here is the execution plan:

test=# explain SELECT * 
  FROM  t_test 
  ORDER BY id <-> 100
 LIMIT 6;
                                  QUERY PLAN 
---------------------------------------------------------------------
 Limit (cost=0.28..0.64 rows=6 width=8) 
   -> Index Only Scan using idx_id on t_test 
              (cost=0.28..5968.28 rows=100000 width=8) 
         Order By: (id <-> 100) 
(3 rows) 

As you can see, PostgreSQL goes straight for an index scan, which speeds up the query significantly.

In future versions of PostgreSQL, B-trees will most likely also support KNN searches. A patch to add this feature has already been added to the development mailing list. Maybe it will eventually make it to the core. Having KNN as a B-tree feature could eventually lead to fewer GiST indexes on standard datatypes.