0

With SQL, I need to select rows which have a pattern like %hello% (i.e. <anything>hello<anything>) in a column, with potentially 100 millions of rows or more.

In the answer Infix search in MySQL with an index, it is said that:

  • an index won't help
  • even an FTS index won't help either

Question: are there RDBMS (e.g. PostgreSQL) that have features that can speed up queries like

select * from t where key like "%hello%"

and avoid a full table scan?

With specific data structures (tries, etc.), or bigrams, trigrams, etc.

TL;DR: I have a MySQL InnoDB like this:

create table t (id int primary key auto_increment, 
                key varchar(200), value varchar(200));
create index key_index on t(key) using BTREE;
create index value_index on t(value) using BTREE;

and I would like to do this without a full table scan:

select * from t where key like "%hello%"

Notes:

5
  • There are database systems meant for tokenizing words for efficient contains type of searching, like Elasticsearch. But it's unclear if your question is looking for the proper database suggestion for this use case, or a solution to how to do it with your existing database system, MySQL?
    – J.D.
    Apr 28, 2023 at 23:39
  • Possibly a trigram index is what you are looking for. There are various ways to implement one. Apr 30, 2023 at 1:50
  • @Charlieface Do some RDBMS like MySQL or PostgreSQL or another include this as an out-of-the-box feature? e.g. CREATE INDEX ON t(key) option=trigram;. Feel free to post an answer with the trigram solution, it would be interesting!
    – Basj
    Apr 30, 2023 at 9:05
  • @J.D. If possible I'll continue with MySQL, but since it's the start of my project, I can easily switch to PostgreSQL or another.
    – Basj
    Apr 30, 2023 at 9:07
  • Postgres does support this. PaulWhite has an article on how to implement this yourself in SQL Server using triggers, see sqlperformance.com/2017/09/sql-performance/… Apr 30, 2023 at 10:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.