Otimizando um campo de Autocomplete com Postgres e Rails

Sabe quando você e seu time erra a mão na hora de estimar uma task?

Task: Criar campo autocomplete que deve sugerir "tags" para o usuário
Estimado em: 3SP

Assim que comecei a trabalhar task ouvi o Faustão falando no meu ouvido: "E-r-r-r-r-r-oooouu".

Existem inúmeras otimizações que podem ser feitas em um campo desses que fiquei até desnorteado.

Gostaria de compartilhar um pouco do que acabei produzindo nessa task. Estou longe de dizer que esta é a melhor forma possível de fazer um campo como esse, mas acredito que é um bom ponta-pé inicial.

Para facilitar a conversa e deixar esse post mais interessante, ao invés de buscar tags, vamos buscar personagens da Marvel.

Se quiser dar uma olhada no resultado final, acessa aí:

• Exemplo Funcional: https://marvel.apps.jony.dev/
• Código-fonte: https://github.com/jonyhayama/find-marvel-characters

O que eu fiz no Postgres

Se você ainda não conheçe, a Marvel fornece uma API para podermos coletar dados: https://developer.marvel.com/

Como meu objetivo aqui é falar sobre o Postgres, fiz alguns requests para a API, salvei os dados que me interessam em um CSV e criei um seed para importar esses dados no banco.

Se quiser, pode baixar o repositório do projeto e rodar rails db:seed, o CSV está commitado 😜.

Vamos considerar, portanto, que temos uma tabela chamada characters e que precisamos fazer uma busca na coluna name para devolver o resultado dessa pesquisa para o usuário.

Minha primeira ideia foi bem simples:

Character.where('name ILIKE ?', "%#{params[:query]}%").pluck(:name)
# SELECT "characters"."name" FROM "characters" WHERE (name ILIKE '%Iron Man%');
# Execution Time: 2.995 ms

⚠️ OBS:
1 - Vou sempre deixar query gerada pelo ActiveRecord comentada em baixo da instrução para facilitar o papo 😜
2 - Considere que estamos em um Controller e que params[:query] = 'Iron Man'

Logo de cara temos uma otimização a fazer: Em linhas gerais, o Postgres é mais performático fazendo comparações com LIKE do que ILIKE.

Nós conseguimos exatamente o mesmo resultado, porém com um tempo de execução menor, se escrevermos:

Character.where('lower(name) LIKE ?', "%#{params[:query].downcase}%").pluck(:name)
# SELECT "characters"."name" FROM "characters" WHERE (lower(name) LIKE '%iron man%');
# Execution Time: 1.012 ms

A próxima otimização seria criar um índice para a coluna name que está sendo alvo da busca.

Eu já estava pronto para criar uma migration com add_index :characters, :name quando descobri que é possível criar índices baseados em expressões.

Algo simples como:

CREATE INDEX index_characters_lower_name ON characters (lower(name));

O que, naturalmente, traria ainda mais performance já que estamos fazendo a busca baseado exatamente nessa expressão.

Foi então que, antes mesmo de ter tempo de implementar esse índice, o StackOverflow me indagou...

StackOverflow: Já ouviu falar da palavra de pg_trgm?
Eu: Caramba, como será que se fala "trgm"?
Documentação do Postgres: it's "Trigram"
Google Translate: "Trigram" = "Trigrama" em terras tupiniquins.
Eu: Mas o que diabos é um trigrama?
Google: vocábulo de três letras.
Eu:

Lendo a documentação com um pouco mais de carinho e, sem entrar em muitos detalhes (até porque eu acho que nem conseguiria), entendi que:

Usando Trigramas, o Postgres consegue gerar um valor numérico para dizer qual é a similaridade entre dois termos, sendo 0 completamente diferente e 1 exatamente igual.

Isso quer dizer que, com uma simples ordenação, eu poderia retornar sugestões de personagens com mais assertividade:

SELECT
  name,
  similarity(name, 'iron man') AS score
FROM characters
WHERE lower(name) LIKE '%iron man%' 
ORDER BY score DESC;

Corri, abri o rails dbconsole, colei a query e...

ERROR:  function similarity(character varying, unknown) does not exist
LINE 3:   similarity(name, 'iron man') AS score
          ^
HINT:  No function matches the given name and argument types. You might need to add explicit type casts.

De volta à documentação, descobri que é necessário habilitar a extesão primeiro 🙈... então criei uma migration rapidinho:

class EnablePgTrgmExtension < ActiveRecord::Migration[6.0]
  def change
    enable_extension 'pg_trgm'
  end
end
# CREATE EXTENSION pg_trgm;

Agora, com a extensão ativada, query executada, temos o seguinte resultado:

name	score
Iron Man	1
Iron Man (Ultimate)	0.5
Iron Man (Marvel Heroes)	0.42857143
Iron Man/Tony Stark (MAA)	0.4090909
Iron Man (Marvel War of Heroes)	0.32142857
Iron Man (Iron Man 3 - The Official Game)	0.31034482
Iron Man (LEGO Marvel Super Heroes)	0.28125
M.O.D.O.K. (Iron Man 3 - The Official Game)	0.25714287
War Machine (Iron Man 3 - The Official Game)	0.23076923
Crimson Dynamo (Iron Man 3 - The Official Game)	0.20930232

Repare que temos uma ordenação bem diferente em relação à nossa primeira query:

name
Crimson Dynamo (Iron Man 3 - The Official Game)
Iron Man
Iron Man (Iron Man 3 - The Official Game)
Iron Man (LEGO Marvel Super Heroes)
Iron Man (Marvel Heroes)
Iron Man (Marvel War of Heroes)
Iron Man (Ultimate)
Iron Man/Tony Stark (MAA)
M.O.D.O.K. (Iron Man 3 - The Official Game)
War Machine (Iron Man 3 - The Official Game)

Você deve estar se perguntando por que comecei a falar da ordenação antes de criar o índice né?

Simples: podemos criar um índice para o trigrama 😜

Então, finalmente, bora para a migration:

class AddCharacterNameLowerTagIndex < ActiveRecord::Migration[6.0]
  def up
    execute "CREATE INDEX index_characters_lower_name ON characters USING gin (lower(name) gin_trgm_ops);"
  end

  def down
    execute "DROP INDEX index_characters_lower_name;"
  end
end

O que eu fiz no Rails

Agora que temos uma query bacana, é só uma questão de reescrevê-la utilizando o ActiveRecord, certo?

query = params[:query].downcase
Character.select("name, similarity(name, '#{query}') AS score").where('lower(name) LIKE ?', "%#{query}%").order('score DESC').load.pluck(:name)

🤔 Ficou meio grande né?

Sem contar que, naturalmente, a gente não deve simplesmente concatenar um parâmetro enviado pelo usuário na nossa query...

Infelizmente o select() não tem a mesma sanitização que o where() que te permite fazer parameter binding.

Para driblar esse problema, podemos usar um método chamado sanitize_sql_array() para nos auxiliar:

query = params[:query].downcase
Character.select(ActiveRecord::Base::sanitize_sql_array(["name, similarity(name, ?) AS score", query])).where('lower(name) LIKE ?', "%#{query}%").order('score DESC').load.pluck(:name)

🤔 Como estamos acessando ActiveRecord::Base, há grandes chances de isso ficar melhor no Model...vamos transformar isso num scopo?

# app/models/character.rb
class Character < ApplicationRecord
  scope :order_by_name_similarity, ->(name) {
    select('*')
      .select(sanitize_sql_array(["similarity(name, ?) AS score", name]))
      .order("score DESC")
  }
end

Repare que optei por deixar o padrão select(*) ao invés de select(:name), dessa forma temos o objeto completo e podemos utilizar outros dados no retorno (se necessário).

Agora a consulta em si fica bem mais simples:

query = params[:query].downcase
Character.where('lower(name) LIKE ?', "%#{query}%").order_by_name_similarity(query)
# SELECT *, similarity(name, 'iron man') AS score FROM "characters" WHERE (lower(name) LIKE '%iron man%') ORDER BY score DESC

Acho interessante também adicionar um limit(10) para não ter uma lista muito grande de opções aparecendo para o usuário.

No final do dia, o método no Controller ficou assim:

def index
  query = params[:query].downcase
  @characters = Character.where('lower(name) LIKE ?', "%#{query}%").order_by_name_similarity(query).limit(10)
  # SELECT *, similarity(name, 'iron man') AS score FROM "characters" WHERE (lower(name) LIKE '%iron man%') ORDER BY score DESC LIMIT 10

  expires_in 10.minutes
end

Repare que também adicionei um expires_in 10.minutes para o navegador pode cachear essa resposta.

É claro que cada caso é um caso e - talvez - 10 minutos não seja a melhor estratégia, mas meu ponto é: é importante ter alguma estratégia de cache.

---

Não sei você, mas pra mim tudo isso passou longe dos 3SPs estimados inicialmente. Especialmente se considerarmos que ainda falta fazer o front.

Para falar a verdade mesmo, eu dei uma ajustada na história... quando disse que "antes mesmo de criar o índice"... convenhamos... você sabe que eu fiz, desfiz e fiz de novo né? 😜

Só organizei a história de uma forma mais cronológica, mas rolou muita pesquisa, teste e re-teste até chegar nessa nessa solução.

E olha que só falamos de Back...vou deixar o Front para um próximo post.

PS: Não encontrei um lugar no meio do texto, mas queria deixar uma queryzinha de presente que talvez lhe seja útil:

SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'characters';

Ess query lista os índices de uma determinada tabela.

EM TEMPO:

Quando comecei a trabalhar no front, comecei a tentar faze a busca por outras personagens.

Foi nessa que eu descobri que o nome oficial é "Spider-man". Não é "Spider man", nem "spiderman"...

Para a busca por "Spider man", podemos fazer um mini-hack rapidinho:

query = params[:query].downcase.gsub(/ /, '%')

Já para "spiderman" acho que a coisa complica mais e - talvez - pg_trgm não seja o ideal...

É nessa hora que ferramentas como Elastic Search, Algolia e afins podem ser aliadas...mas tudo tem seu custo (seja financeiro ou de implementação) 😜

---

Tem ideias, críticas ou sugestões? comenta aí :D