I would like to replicate something like command-t or Sublime "Go to file" / CMD + P search in postgres. Where the search matches consecutive but not necessarily adjacent characters. Like so

• 
  Here's the library underlying command-t.


• I saw trigrams but that is for portions of three consecutive letters.


• I saw Levenshtein but that calculates distance not quite the non consecutive char behaviour I was hoping for.

What kind of fuzzy search is this called? If this is not possible in postgres, is it possible in elasticsearch or another DB?

😇Desired output

for example given that your query was "doc" I would expect the following ordering:

doc

d***o***c

d***oo**c

dpc

dppc

d***p***c

d

asdf

a

Update

Using ilike

with documents(title) as (

values

    ('d***o***c'),

    ('d***p***c'),

    ('d'),

    ('a'),

    ('dppc'),

    ('d***oo**c'),

    ('asdf'),

    ('dpc'),

    ('doc')

) select *

from documents

where title ilike '%d%o%c%';

😒Actual output

Doesn't order for similarity. With trigram index on title and 700k rows around 30ms.

   title

-----------

 d***o***c

 d***oo**c

 doc

Using Similarity

select title, similarity(title, 'doc') as sml

    from documents

    where similarity(title, 'doc') > 0

    order by sml desc

    limit 50;

😒Actual Output

Doesn't prioritize non consecutive letters. With trigram index on title and 700k rows around 30ms

   title   |   sml

-----------+----------

 doc       |        1

 d         |      0.2

 dpc       | 0.142857

 dppc      |    0.125

 d***o***c | 0.111111

 d***p***c | 0.111111

 d***oo**c |      0.1

Using Levenshtein

Prioritizes consecutive letters. With btree index on title and 700k rows around 89ms

select levenshtein(title, 'doc', 30, 1, 60), title

    from documents

    where levenshtein(title, 'doc', 30, 1, 60) <= 500

    order by levenshtein(title, 'doc', 30, 1, 60)

    limit 50;

🎉 Actual output

 levenshtein |   title

-------------+-----------

           0 | doc

           6 | d***o***c

           6 | d***oo**c

          31 | dpc

          32 | dppc

          37 | d***p***c

          60 | d

          63 | asdf

          91 | a

(9 rows)

My timing results aren't particularly reliable as they fluctuated to up to 3 seconds on my local 16GB 2.5Ghz quad core cpu but they may help for relative estimates.

Overall levenshtein was the only one which produced the desired results but tended to be a lot slower, sometimes 5x slower than the other methods. I couldn't see any indexes which could have helped with the levenshtein method.