12

Eu nunca encontrei uma boa maneira de indexar várias colunas de uma linha como entradas de um índice ou simular esse recurso no MySQL.

O problema surge quando você tem campos funcionando como tags ou um conceito similar. Ex:. colunas com nomes tag1, tag2, tag3. Para procurar linhas com uma tag específica rapidamente requer que você tenha 3 índices e fazer 3 consultas separadas do jeito mais básico e óbvio.

Existe alguma maneira de indexar esses três campos como entradas de um único índice que permite realizar apenas uma busca.

Tentando exemplificar como ficaria

ID tag1 tag2 tag3
-- ---- ---- ----
01 abc  xyz  bla
02 foo  bar  ble
03 xyz  bla  bar

Como o índice se comportaria:

abc -> 01
bar -> 02 03
bla -> 01 03
ble -> 02
foo -> 02
xyz -> 01 03

Então se eu fizer uma busca por "bla", terei acesso aos IDs "01" e "03".

Há alguma outra maneira de fazer isso de forma eficientemente? Mesmo que mude a estrutura apresentada.

2
  • O objetivo é fazer uma consulta pela tag X e retornar os IDs com ela, ou uma consulta que retorne o "índice" inteiro? E você quer uma solução para essa estrutura específica de tabela, ou está aberto a rever a estrutura?
    – bfavaretto
    Commented 30/01/2014 às 4:56
  • @bfavaretto editado para atender suas dúvidas
    – Maniero
    Commented 30/01/2014 às 5:01

3 Respostas 3

12
+50

Há algum tempo (2013? 2012?) desenvolvi um sistema muito semelhante ao da pergunta. Eu tinha alguns milhões de objetos e uma dúzia de "tags", e cada objeto poderia ter 0 ou mais tags associadas. Eu tinha que filtrar esses objetos baseados em buscas por conjuntos de tags. Semelhante, não?

Como o número de tags por objeto, no meu caso, era teoricamente ilimitado (visto que novas tags poderiam ser adicionadas ao sistema depois de lançado), a solução proposta na pergunta não me servia, i.e., eu não poderia utilizar uma tabela com colunas "tag1", "tag2", etc. Além disso, esse esquema não permite utilização de índices (veja meu primeiro comentário na resposta do @mgibsonbr).

Como eu necessitava de bastante performance (i.e., queries respondidas em "segundos"), na época fiz uma comparação entre diversas soluções, incluindo as duas propostas pelo @mgibsonbr em sua resposta.

A seguir, meus resultados -- se minha memória não falha!

Trade offs...

A solução "1." do @mgibsonbr tem a desvantagem de possivelmente ocupar muito espaço em disco (já que você terá os "caracteres" das tags repetidos inúmeras vezes na tabela toda). Isso é uma desvantagem pois obriga o seu banco de dados a ter que ler muitas "pages" do seu disco rígido, então tem que girar muito o disco e mexer muito a cabeça de leitura, o que pode ter grande latência. A vantagem é que você faz apenas 1 select para obter o seu resultado.

Já a solução "2." do @mgibsonbr utiliza menos espaço em disco (pois na tabela gigante só serão salvos os ids das tags -- e se você utilizar o tipo numérico de tamanho adequado à quantidade máxima de tags, pode reduzir a 4, 2 ou até mesmo 1 byte por linha). Assim, você consegue ler mais linhas por "page" lido do disco reduzindo latência. Em contrapartida, o seu select provavelmente teria um join:

select from tags_objects, tags
 where tags.id = tags_objects.tagId
   and (tags.name = 'tag-buscado-1'
     or tags.name = 'tag-buscado-2') -- etc...

Esse join é o culpado por problemas de performance nessa solução.

Solução mais eficiente (no meu caso de uso específico)

No final das contas, a solução mais eficiente que consegui foi utilizar a solução "2." com 2 selects distintos. O primeiro select busca os ids das tags, e o segundo select utiliza os ids das tags na tabela gigante. É como se eu fizesse o join "manualmente".

Isso era vantajoso para mim pois, no meu caso, era possível eu manter em cache, na minha aplicação, os ids dos tags. Esse cache era atualizado por um thread em background (fazendo um "full scan" na tabela minúscula que contém tags e seus ids a cada "X" segundos). No final das contas, em termos práticos, o cálculo "síncrono" era apenas um select na tabela gigante com a coluna "tagId" sendo algum tipo numérico, portanto menor do que ter que fazer joins.

Obviamente, por questões de performance, é necessário colocar um índice na coluna "tagId" da tabela gigante.

Antes de implementar toda essa solução, minhas queries duravam ~1min ou ~2min com, se não me engano, uns 5 tags. Após tudo isso, consegui reduzir o tempo das queries para algo em torno de ~10s!

Considerações

É bastante complicado analisar de antemão qual será a solução com melhor performance nesse caso, pois realmente depende das características do seu projeto. Espero que esta resposta possa dar alguma orientação para a sua busca pela solução mais eficiente para o seu caso específico.

1
  • Excelente, ainda espero outras respostas mas tanto a sua quanto do mgibsonbr me ajudaram muito.
    – Maniero
    Commented 30/01/2014 às 11:28
9

Não posso falar da eficiência, mas uma maneira de se consultar por um valor usando uma única query seria utilizar o IN de uma maneira pouco convencional - com as colunas no lado direito. Exemplo:

select * from minha_tabela
where 'foo' in (tag1, tag2, tag3)
  and 'bar' in (tag1, tag2, tag3);

Fonte: o livro "SQL Antipatterns", em inglês.

P.S. Segundo esse mesmo livro, modelar os dados dessa maneira (Atributos Multi-Coluna) é uma má prática, e causa diversos problemas além desse da indexação (também complica a inserção, remoção, fazer com que cada tag só apareça no máximo uma vez por linha, etc). O ideal seria criar uma tabela dependente (ou uma tabela de interseção/junção, se cada tag for mais do que uma simples string) para associar as tags à tabela numa relação N para N. A menos que tenha suas razões para manter esse design, sugiro mudá-lo.


Atualização: como a pergunta foi editada de modo a admitir mudar a estrutura apresentada, vou complementar com exemplos de tabela dependente e tabela de interseção:

  1. Tabela dependente

    PK                Índice  FK, Índice
    ID Etc            Tag     ID_Tabela
    -- ---            ---     ---------
    01                abc     01
    02                xyz     01
    03                bla     01
                      foo     02
                      bar     02
                      ...
    

    Nesse caso as tags foram movidas para uma tabela separada, onde cada tag está associada a apenas uma linha na tabela original. A coluna "tag" é indexada, de modo que a consulta Tag -> IDs seja rápida. E a coluna "id_tabela" - chave estrangeira para a tabela original - também é indexada, de modo que a consulta ID -> Tags tambem seja rápida.

    (Nota: a coluna "tag" não é UNIQUE, pois cada tag pode aparecer mais de uma vez na tabela.)

  2. Tabela de interseção/junção

    PK                FK        FK              PK
    ID Etc            ID_Tabela ID_Tag          ID Tag
    -- ---            --------- ------          -- ---
    01                01        01              01 abc
    02                01        02              02 xyz
    03                03        02              03 bla
                      01        03              04 foo
                      03        03              05 bar
                      ...                       ...
    

    Nesse caso (útil caso você queira armazenar mais informações sobre uma tag, ou talvez em uma única query mudar o nome da tag sem mexer nas associações) as tags foram movidas para uma tabela separada, e uma tabela de interseção relaciona as duas (numa relação de N para N). Resta apenas adicionar índices onde for necessário, dependendo das consultas específicas que você pretende fazer.

Essas duas técnicas foram adaptadas também do livro, e em geral são boas práticas que também mantém seu modelo normalizado. Para questões de performance - as quais não posso opinar, pois nunca operei um sistema desse tipo em escala - onde se admite desnormalização ou outras técnicas de otimização (caching, offload na camada de aplicação, etc) ver por exemplo a resposta do @Bruno Reis.

16
  • 1
    Resumiu bem o que eu ia dizer. Só acrescento que um índice composto nas 3 colunas seria utilizado numa query assim. Brinde: sqlfiddle que eu tinha pronto: sqlfiddle.com/#!2/13f8a
    – bfavaretto
    Commented 30/01/2014 às 5:13
  • 1
    @bfavaretto, por acaso o seu comentário se refere à resposta original, antes da primeira edição (i.e., ao select ... where ... in)? Se sim, um único índice composto nas 3 colunas na verdade não poderia ser utilizado. O motivo é simples. Suponha que o seu índice contém as colunas na ordem (tag1, tag2, tag3). Agora suponha uma linha com tag1 = xxx, tag2 = foo, tag3 = bar. Nessa condição, a tabela inteira deve ser percorrida (i.e., full scan) para localizar essa linha, já que nada do select fixa tag1 = xxx.
    – Bruno Reis
    Commented 30/01/2014 às 6:35
  • 2
    @BrunoReis Cara, posta isso como uma resposta! A experiência prática de quem já passou por uma situação vale muito mais do que a opinião de quem só conhece a teoria...
    – mgibsonbr
    Commented 30/01/2014 às 6:48
  • 1
    @mgibsonbr, postado :-). Se quiser uma dica de leitura sobre índices, a documentação do MySQL é excelente. No MySQL 5.6, veja as seguintes páginas do manual: 8.3.1, 8.3.4, 8.3.5 e 8.8.3. Também pode ser útil estudar B-Trees em algum texto de estruturas de dados para entender mais a fundo os índices do MySQL (por exemplo em Algorithms, do Sedgewick).
    – Bruno Reis
    Commented 30/01/2014 às 7:14
  • 1
    @bfavaretto, como prometido, testei mais a fundo. Consegui criar uma situação em que o EXPLAIN realmente diz "using index", porém, na verdade, isso não significa que a query está sendo acelerada. Insira dezenas de milhares de linhas de forma que apenas uma pequena fração delas de match com a query. Depois rode o explain. Veja a coluna "rows", ela mostrará o número total de linhas da tabela -- a tabela toda deverá ser percorrida! Nesse caso, é praticamente indiferente para o MySQL usar o índice ou não, pois fará full scan da tabela ou do índice. [continua]
    – Bruno Reis
    Commented 31/01/2014 às 2:52
7

Query explicada

No PostgreSQL se você criar um indice com multiplas colunas como o exemplo da figura e executar a query também como ilustrado ele será capaz de utilizar o indice para a consulta e tratará sozinho de resolver a consulta de modo eficiente ao executar um mapa de bits nos resultados parciais calculados.
Basta saber o motor de planejamento do MySQL irá tratar a execução da consulta da mesma maneira.

1
  • É exatamente como faço no PostgreSQL :)
    – Maniero
    Commented 30/01/2014 às 12:33

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .