O PostgreSQL possui um módulo chamado fuzzystrmatch que está no pacote contrib, este módulo possui diversas funções para trabalhar com consultas aproximadas, muito útil quando queremos fazer buscas em palavras com erro de digitação.

Segundo Euler na pgcon 2008 (), esse tipo de consula possui um custo computacional alto..

1 PASSO: ativar o pacote que contém as funções

nei@terra:~$ sudo apt-get install postgresql-contrib-8.3

2 PASSO: criar as funções

No meu caso, já existia o pacote instalado, porém não estava disponível a função, então eu criei ela das seguinte forma:

# /usr/share/postgresql/8.3/contrib/fuzzystrmatch.sql

-- Adjust this setting to control where the objects get created.
SET search_path = public;

CREATE OR REPLACE FUNCTION levenshtein (text,text) RETURNS int
AS '$libdir/fuzzystrmatch','levenshtein'
LANGUAGE C IMMUTABLE STRICT;

3 passo: have fun!

teste=# create table usuario ( nome varchar(100) not null );
teste=# insert into usuario values ( 'patrick' ), ('patric' ), ('petrick');

teste=# SELECT * from usuario where levenshtein( nome, 'patrick' ) = 1;
  nome   
---------
 patric
 petrick
(2 registros)

teste=# SELECT levenshtein('JOAO', 'JOAO');
 levenshtein 
-------------
           0
(1 registro)

teste=# SELECT levenshtein('JOAO', 'JOÃO');
 levenshtein 
-------------
           2
(1 registro)

caracteres com acentos serão contados como 2 caracteres no UTF-8.

referências: http://www.postgresql.org/docs/8.3/static/fuzzystrmatch.html