Jaký je nejlepší způsob implementace vyhledávání podřetězců v SQL?

Podívejte se na mou prezentaci Praktické fulltextové vyhledávání v MySQL .

Porovnal jsem:

• LIKE predikáty
• Regulární výraz predikáty (ne lepší než LIKE )
• MyISAM FULLTEXT indexování
• Sphinx Search
• Apache Lucene
• Invertované indexování
• Google Vlastní vyhledávač

Dnes bych použil Apache Solr , která zařazuje Lucene do služby s řadou dalších funkcí a nástrojů.

K vašemu komentáři:Aha, dobře, ne. Žádná z možností fulltextového vyhledávání, které jsem zmínil, nepomůže, protože všechny předpokládají určité hranice slov

Dalším způsobem, jak efektivně najít libovolné podřetězce, je N-gram přístup. V podstatě vytvořte index všech možných sekvencí N písmen a ukažte na řetězce, kde se každá příslušná sekvence vyskytuje. Obvykle se to provádí pomocí N=3 nebo trigram , protože je to bod kompromisu mezi porovnáváním delších podřetězců a udržováním indexu na zvládnutelné velikosti.

Nevím o žádné SQL databázi, která by transparentně podporovala N-gram indexování, ale můžete si ji nastavit sami pomocí invertovaného indexu :

create table trigrams (
  trigram char(3) primary key
);

create table trigram_matches (
  trigram char(3),
  document_id int,
  primary key (trigram, document_id),
  foreign key (trigram) references trigrams(trigram),
  foreign key (document_id) references mytable(document_id)
);

Nyní jej naplňte tvrdším způsobem:

insert into trigram_matches
  select t.trigram, d.document_id
  from trigrams t join mytable d
    on d.textcolumn like concat('%', t.trigram, '%');

Samozřejmě to bude chvíli trvat! Ale jakmile je hotovo, můžete vyhledávat mnohem rychleji:

select d.*
from mytable d join trigram_matches t
  on t.document_id = d.document_id
where t.trigram = 'abc'

Samozřejmě můžete hledat vzory delší než tři znaky, ale obrácený index vám stále pomáhá hodně zúžit vyhledávání:

select d.*
from mytable d join trigram_matches t
  on t.document_id = d.document_id
where t.trigram = 'abc'
  and d.textcolumn like '%abcdef%';