Wat is de beste manier om een ​​substring-zoekopdracht in SQL te implementeren?

Bekijk mijn presentatie Praktisch zoeken in volledige tekst in MySQL .

• LIKE predikaten
• Regelmatige expressie predikaten (niet beter dan LIKE )
• MijnISAM FULLTEXT indexeren
• Sphinx zoeken
• Apache Lucene
• Omgekeerde indexering
• Google Engine voor Google Aangepast zoeken

Wat ik vandaag zou gebruiken is Apache Solr , waarmee Lucene een service wordt met een heleboel extra functies en tools.

Re uw commentaar:Aha, oke, nee. Geen van de fulltext-zoekmogelijkheden die ik noemde, zullen helpen, omdat ze allemaal een soort van woordgrenzen aannemen

De andere manier om willekeurige substrings efficiënt te vinden is de N-gram nadering. Maak in principe een index van alle mogelijke reeksen van N-letters en wijs naar de tekenreeksen waar elke respectieve reeks voorkomt. Meestal wordt dit gedaan met N=3, of een trigram , omdat het een compromis is tussen het matchen van langere substrings en het op een beheersbare grootte houden van de index.

Ik ken geen SQL-database die N-gram-indexering transparant ondersteunt, maar je zou het zelf kunnen instellen met behulp van een inverted index :

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)
);

Vul het nu op de harde manier in:

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

Dit duurt natuurlijk nog even! Maar als het eenmaal klaar is, kun je veel sneller zoeken:

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

Natuurlijk kunt u zoeken naar patronen die langer zijn dan drie tekens, maar de geïnverteerde index helpt nog steeds om uw zoekopdracht te verfijnen:

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%';