B-Tree Index: Suffix Lookup

I’m watching PGCon 2016 talks and I really recommend you to see Peter van Hardenberg’s talk: Data Types in PostgreSQL. He gives a great overview over the data types shipped in Postgres and how to create your own. One little trick caught my eye, he showed how to support suffix matching in indexed text columns.

In Postgres, search terms with a prefix can use an index, like:

explain (costs false)
select
  *
from
  users
where
  name like 'Franc%'
QUERY PLAN
--------------------------------------------------------------------
Index Scan using index_users_on_name on users
   Index Cond: ((email ~>=~ 'Franc'::text)
                AND (email ~<~ 'Frand'::text))

In fact, the more selective the prefix before the wildcard is, the faster the index lookup will be.

However, if the search term starts with a wildcard the database has to do a full table scan.

explain (costs false)
select
  *
from
  users
where
  email like '%gmail.com'
QUERY PLAN
--------------------------------------------------------------------
Seq Scan on users
   Filter: (email ~~ '%gmail.com'::text)

As mentioned in the talk, you can use a function based index:

create index index_users_on_email_suffix on users (reverse(email));

Then, suffix matches will be supported by this trick:

explain (costs false)
select
  *
from
  users
where
  reverse(email) like reverse('%gmail.com')
QUERY PLAN
--------------------------------------------------------------------
Bitmap Heap Scan on users
   Filter: (reverse(email) ~~ 'moc.liamg%'::text)
   ->  Bitmap Index Scan on index_users_on_email_suffix
         Index Cond: ((reverse(email) ~>=~ 'moc.liamg'::text)
           AND (reverse(email) ~<~ 'moc.liamh'::text))