Full-Text Search Index

To index keywords within large document contents stored in database records, full-text search indexes are used.

For example, to search data types like TEXT, B-Tree indexes provided by InnoDB or MyISAM cannot be used. Searching such data is called a Full Text Search index, but "full-text search index" is a generalized functional name, not the name of a specific full-text search algorithm..

In full-text search indexes, indexing techniques for document keywords can be broadly categorized into delimiters (Stopwords) and n-grams. Other algorithms are not well-known, and especially in MySQL, none are available.

Index Algorithms #

There can be various methods for keyword analysis and index construction. These include the Stopword indexing method, which is provided by the full-text search engine built into all versions of MySQL, and n-gram, which is offered by third-party full-text search functionalities outside of MySQL.

Stopword #

It is also called a delimiter or a stopword.

First, the content of the text is registered to be delimited by sentence symbols such as spaces, tabs, or periods, and by user-defined strings.

The delimiter technique refers to a method that analyzes and extracts keywords using registered delimiters, creates an index from the resulting words, and uses it for searching.

Typically, spaces, commas, or Korean particles are often used as delimiters. MySQL's built-in Full Text Search engine can only index using the delimiter method.

The delimiter technique only requires an additional step of extracting keywords from the document's body; internally, it still uses B-Tree indexes.

While many aspects of full-text search indexes follow the characteristics of B-Trees, records retrieved through a full-text search engine are not sorted by search term or body content.

In full-text search, results are typically ordered by relevance (highest match rate).

If you want to add more stopwords, you can configure them in the conf file or set them as system variables in InnoDB. If registered as an InnoDB system variable, it applies without needing to rebuild MySQL.

n-gram Technique #

It is common for languages in different countries to have no spacing at all or completely different punctuation marks.

Applying a single rule to extract keywords for such diverse languages is not easy, and the delimiter method also has the disadvantage that it's impossible to search only a part of an extracted keyword (the latter part of the keyword).

To compensate for these issues, the n-gram method enables the analysis and search of text without predefined rules.

n-gram is a method that unconditionally cuts the body text into fixed-length character chunks for indexing. Algorithms like Triton or Sphinx also exist, but n-gram is generally used.

In n-gram, 'n' refers to the minimum number of characters or bytes for the keyword to be indexed. It is commonly used in the 2-Gram or Bi-Gram method, which splits keywords into 2-character units for indexing.

1. Create a backend index by dividing the document's body into blocks larger than 2 characters.
2. Create a frontend index by splitting the keywords from the backend index into 2-character chunks.

The index search process, conversely to creation, involves splitting the search query into 2-byte units identically and then searching the frontend index. Afterward, the results are designated as candidate sets, and a final verification is performed through the backend index to retrieve matching results.

Stopword vs n-gram #

When searching using stopwords, the search compares based on left-match criteria using delimiters. However, it cannot find words with prefixes on the right side, whereas n-gram can search all data because it randomly generates N-byte indexes for all data.

For example, if you search for "iPhone" in the WHERE clause using the stopword technique, phrases like "Selling iPhone~" or "Buying iPhone~" will be found, but "Buying Apple iPhone!" will not. However, n-gram can find it.

Let's compare the performance and index size of the n-gram-based Triton full-text search engine with MySQL's built-in delimiter-based full-text search engine. First, n-gram full-text search indexes are larger than delimiter-based ones.

While n-gram indexes have a complex creation process, making keyword additions or deletions to the full-text index time-consuming, the search execution time for Triton's 2-gram algorithm is 2 to 3 times faster. This difference widens as the number of concurrent client queries increases.

Availability #

To use a full-text search index, you cannot use basic comparison operators; you must use the appropriate syntax (functions).

SELECT * FROM tb_test WHERE body LIKE '%애플%';

In this SQL query, the full-text search index is not applied.

To use a full-text search index, search queries must be written using the MATCH() AGAINST() syntax, and all columns defined in the full-text search index must be explicitly specified within the MATCH clause's parentheses.