Full-text indexes in MySQL - Time & Space Complexity

Time Complexity: Full-text indexes

O(k)

Understanding Time Complexity

When searching text in a database, speed matters a lot. Full-text indexes help find words quickly in large text columns.

We want to understand how the search time changes as the text data grows.

Scenario Under Consideration

Analyze the time complexity of the following full-text search query.

SELECT * FROM articles
WHERE MATCH(content) AGAINST('database');
    

This query searches the word 'database' in the content column using a full-text index.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the full-text index for matching words.
• How many times: The search scans index entries related to the search word, not the whole table rows.

How Execution Grows With Input

As the number of rows and text size grows, the full-text index helps keep search fast.

Input Size (n)	Approx. Operations
10	Few index lookups
100	More index lookups but still quick
1000	More index entries checked but not all rows scanned

Pattern observation: The search time grows slowly because it uses the index, not scanning all text.

Final Time Complexity

Time Complexity: O(k)

This means the search time grows slowly as the data grows, thanks to the index structure.

Common Mistake

[X] Wrong: "Full-text search scans every row every time, so it's slow for big data."

[OK] Correct: Full-text indexes let the database jump directly to matching words, avoiding scanning all rows.

Interview Connect

Understanding how full-text indexes speed up searches shows you know how databases handle big text data efficiently. This skill helps you explain and design fast search features.

Self-Check

"What if we searched multiple words instead of one? How would the time complexity change?"

Practice

1. What is the main purpose of a FULLTEXT index in MySQL?

easy

A. To speed up searching for words inside text columns

B. To enforce uniqueness on text columns

C. To sort text columns alphabetically

D. To compress text data for storage

Solution

1. Step 1: Understand what FULLTEXT indexes do

   FULLTEXT indexes are designed to make searching for words inside large text columns faster and more efficient.

2. Step 2: Compare with other index types

   Unlike unique or sorting indexes, FULLTEXT indexes focus on text search, not uniqueness or ordering.

3. Final Answer:

   To speed up searching for words inside text columns -> Option A

4. Quick Check:

   FULLTEXT index = speeds up text search [OK]

Hint: FULLTEXT indexes are for fast word searches in text columns [OK]

Common Mistakes:

• Confusing FULLTEXT with UNIQUE index
• Thinking FULLTEXT sorts data
• Assuming FULLTEXT compresses data

2. Which of the following is the correct syntax to create a FULLTEXT index on the column description in a table products?

easy

A. CREATE INDEX idx_desc FULLTEXT ON products(description);

B. CREATE INDEX idx_desc ON products(description) FULLTEXT;

C. CREATE FULLTEXT INDEX idx_desc ON products(description);

D. CREATE FULLTEXT ON products(description) INDEX idx_desc;

Solution

1. Step 1: Recall correct FULLTEXT index syntax

   The correct syntax is: CREATE FULLTEXT INDEX index_name ON table_name(column_name);

2. Step 2: Match syntax with options

   CREATE FULLTEXT INDEX idx_desc ON products(description); matches the correct syntax exactly.

3. Final Answer:

   CREATE FULLTEXT INDEX idx_desc ON products(description); -> Option C

4. Quick Check:

   CREATE FULLTEXT INDEX ... ON ... [OK]

Hint: FULLTEXT index syntax: CREATE FULLTEXT INDEX name ON table(column) [OK]

Common Mistakes:

• Placing FULLTEXT keyword after INDEX
• Using wrong order of keywords
• Omitting INDEX keyword

3. Given a table articles with a FULLTEXT index on the content column, what will the following query return?

SELECT id FROM articles WHERE MATCH(content) AGAINST('database');

medium

A. Syntax error because MATCH() requires multiple columns

B. All article IDs sorted alphabetically by content

C. All article IDs where content exactly equals 'database'

D. All article IDs where the word 'database' appears in content

Solution

1. Step 1: Understand MATCH() AGAINST() usage

   This function searches the FULLTEXT indexed column for the given word or phrase.

2. Step 2: Interpret the query result

   The query returns IDs of rows where 'database' appears anywhere in the content column.

3. Final Answer:

   All article IDs where the word 'database' appears in content -> Option D

4. Quick Check:

   MATCH() AGAINST() = full-text search result [OK]

Hint: MATCH() AGAINST() finds rows containing the search word [OK]

Common Mistakes:

• Thinking it matches exact whole content
• Assuming it sorts results
• Believing MATCH() needs multiple columns

4. You wrote this query but it returns no results even though matching rows exist:

SELECT * FROM posts WHERE MATCH(body) AGAINST('the');

The body column has a FULLTEXT index. What is the likely problem?

medium

A. AGAINST() requires the IN BOOLEAN MODE modifier

B. The word 'the' is too common and ignored by default stopword list

C. FULLTEXT index must be created on multiple columns

D. MATCH() cannot be used on a single column

Solution

1. Step 1: Recall FULLTEXT stopword behavior

   MySQL ignores very common words (stopwords) by default in FULLTEXT searches.

2. Step 2: Understand why no results appear

   If 'the' is in the stopword list, the search ignores it, returning no matches.

3. Final Answer:

   The word 'the' is too common and ignored by default stopword list -> Option B

4. Quick Check:

   Stopwords cause no results for common words [OK]

Hint: Common words may be ignored by FULLTEXT stopword list [OK]

Common Mistakes:

• Thinking MATCH() needs multiple columns
• Assuming IN BOOLEAN MODE is always required
• Believing FULLTEXT index must cover multiple columns

5. You want to find rows in the reviews table where the comment column contains either 'fast' or 'reliable'. The comment column has a FULLTEXT index. Which query correctly finds these rows using boolean mode?

hard

A. SELECT * FROM reviews WHERE MATCH(comment) AGAINST('fast | reliable' IN BOOLEAN MODE);

B. SELECT * FROM reviews WHERE MATCH(comment) AGAINST('+fast +reliable' IN BOOLEAN MODE);

C. SELECT * FROM reviews WHERE MATCH(comment) AGAINST('fast reliable' IN BOOLEAN MODE);

D. SELECT * FROM reviews WHERE MATCH(comment) AGAINST('"fast reliable"' IN BOOLEAN MODE);

Solution

1. Step 1: Understand boolean mode operators

   In boolean mode, | means OR, + means AND, and quotes mean phrase search.

2. Step 2: Identify correct OR query

   To find rows containing either 'fast' OR 'reliable', use 'fast | reliable'.

3. Step 3: Check other options

   SELECT * FROM reviews WHERE MATCH(comment) AGAINST('fast reliable' IN BOOLEAN MODE); searches for both words but not as OR; SELECT * FROM reviews WHERE MATCH(comment) AGAINST('+fast +reliable' IN BOOLEAN MODE); requires both words; SELECT * FROM reviews WHERE MATCH(comment) AGAINST('"fast reliable"' IN BOOLEAN MODE); searches exact phrase.

4. Final Answer:

   SELECT * FROM reviews WHERE MATCH(comment) AGAINST('fast | reliable' IN BOOLEAN MODE); -> Option A

5. Quick Check:

   Boolean OR uses | operator [OK]

Hint: Use | for OR in boolean full-text searches [OK]

Common Mistakes:

• Using space for OR instead of |
• Using + which means AND
• Using quotes for phrase instead of OR