MySQL: how to implement a text search without delimiter

full-text-searchMySQL

I have a table table1 that contains several fields, some textual and other non-textual, on which I do search queries. Let's focus on some text fields, which I simply call field1, field2, field3.
The table contains about 1.5 million records and the queries are not so fast, because when I have to search on these fields, I'm doing in fullscan mode.

I give you a concrete example:

SELECT *
FROM table1
WHERE [some conditions]
AND (field1 LIKE "%str1%" OR field2 LIKE "%str1%" or field3 LIKE "%str1%")
AND (field1 LIKE "%str2%" OR field2 LIKE "%str2%" or field3 LIKE "%str2%")
AND (field3 LIKE "%str3%")

Point out that str1, str2, etc … can be a word or a part of a word (for example "Table" or "Tabl").

Considering how the query is build, I don't see any sense to define any index on field1, field2, field3: they would not bring any advantage, just an useless waste of resources in my opionion.

So, I have evaluated the FULLTEXT indexes of MySQL and the query MATCH() AGAINST(): this is not good, because in my case it works only when exactly field1=word1 or field2=word2, while often the fields contain concatenated words without delimiters (for example field1 contains the value "HOUSETABLERAIN" and not "HOUSE TABLE RAIN").

What can I do to improve the execution time? My question includes changes to the query and the edit of data structure as well.

I thought two solutions, but I'm not convinced of either.

Solution A)
Introduce another table table2 (table1_id INT, field VARCHAR, string VARCHAR); for each record in table1, insert all possible substrings (confining itself to combinations with at least 4 characters).
Practical example:

If in table1 there is the record

id | field1
45 | HOUSETABLERAIN

then in table2 there will be

table1_id | field | string
       45 | field1 | HOUS
       45 | field1 | HOUSE
       45 | field1 | HOUSET
       45 | field1 | HOUSETA
       45 | field1 | HOUSETAB
       45 | field1 | HOUSETABL
       45 | field1 | HOUSETABLE
       45 | field1 | HOUSETABLER
       45 | field1 | HOUSETABLERA
       45 | field1 | HOUSETABLERAI
       45 | field1 | HOUSETABLERAIN
       45 | field1 | OUSE
       45 | field1 | OUSET
       45 | field1 | OUSETA
...

Afterwards I could define an index on table2.string and I should have some advantages; furthermore, I could also eliminate a part of the fields in table1, because I would no longer search on them.

But I fear it's madness … even before testing it.

Solution B)
Add a TEXT field for the search and enter all possible combinations separated by the blank space " ", then define a FULLTEXT index. The problem are the stopwords that are not considered by the MATCH AGAINST query.

I'd like to have some opinions and maybe some better ideas.
Thank you.

Best Answer

Digrams (or trigrams).

Take each pair (or triple) of letters in the text, hash it down to 0..63, set a bit in a BIGINT UNSIGNED. The "OR" of a few dozen bits together like that will usually lead to about half the bits being on. (If most of the bits are on, the method is less effective; if too few bits are on, it wastes space.

Do that as you store the data, and store the bigints in extra columns. When testing, do likewise to the data coming in -- get a bigint representing the query.

WHERE (big3 & test3) = test3

Where big3 is the bigint for field3 and test3 is the bigint for "str3", that clause will check that all of the letter pairs of "str3" are probably in field3.

For the combined test of field1/2/3 against "str1", 

AND ((big1 | big2 | big3) & test1) = test1

Better yet is to precompute (big1 | big2 | big3) into a combined big123 initially.

I said "probably". That means you will get some false positives and need to double check the 'hard' way, as you already discussed.

Note: If there is some meaning you would like to apply for "word boundary", that can easily be done in the building of the bigints.

Hash

One such hash:

SELECT HEX(1 << (CONV(MID(MD5(LOWER('th')), 5,2), 16, 10) & 0x3F));
+-------------------------------------------------------------+
| HEX(1 << (CONV(MID(MD5(LOWER('th')), 5,2), 16, 10) & 0x3F)) |
+-------------------------------------------------------------+
| 8000                                                        |
+-------------------------------------------------------------+

Translate this into your programming language; it would probably be easier there, not in SQL.

Dissecting it:

HEX(1 << (CONV(MID(MD5(LOWER('th')), 5,2), 16, 10) & 0x3F))
                              ^^  sample digraph
                       ^^^^^  fold case unless you need to differentiate
                   ^^^  a readily available hashing function
               ^^^                   ^^^  -- pick some hex digits out of it
          ^^^^                             ^^^^^^  -- hex -> decimal
                                                   ^^^^^^  -- only 6 bits
    ^^^^  -- shift "1" to the bit position given by the 6-bit number
^^^  -- (just for displaying the result; not part of the algorithm)
Related Question