A practical deep-dive into full-text search indexing, inverted indices, and microsecond query benchmarks using Android Jetpack Room.

When building search into an Android application — whether querying an offline-first inbox, notes catalog, documentation cache, or e-commerce catalog — almost every developer starts with the same query:

SELECT * FROM mails 
WHERE subject LIKE '%' || :query || '%' 
   OR body LIKE '%' || :query || '%'

It is intuitive, requires zero schema alterations, and works out-of-the-box. During early development, when your local database contains 25 dummy rows, search queries return instantly. Tests pass, the UI feels snappy, and the feature gets shipped.

Then reality strikes.

As users accumulate months of multiline emails, notes, or cached payloads (climbing from hundreds to thousands of records), complaints begin rolling in:

• Keystroke lag when typing in search fields.
• Skipped frames and main-thread micro-stutters.
• Noticeable battery drain during heavy search workflows.

Why does an operation that felt blazing fast in development fall apart under real-world volume? To understand this, we have to look under the hood of SQLite’s query planner.

Why SQL LIKE Fails at Scale

In relational databases, developers rely on indices (B-Trees) to keep lookups at O(log N) time. If you query:

WHERE sender LIKE 'alice%'

SQLite can utilize a standard B-Tree index on sender because it knows the prefix.

However, users rarely search by prefix alone. Real-world full-text search requires substring matching: finding a word anywhere within a subject or paragraph. This forces the query into a leading wildcard:

WHERE body LIKE '%architecture%'

WARNING: The moment a query contains a leading wildcard (%query%), standard B-Tree indices are completely bypassed. SQLite is forced to execute a sequential full table scan O(N).

In a full table scan:

1. SQLite reads every single row off the storage layer into memory.
2. The query engine steps through every single byte of text sequentially, comparing character by character looking for the target substring.
3. If an email body contains 1,500 words and you have 2,000 emails, SQLite inspects up to 3,000,000 words byte-by-byte for every single keystroke!

Furthermore, standard SQL LIKE is “dumb”:

• No tokenization: It doesn’t know what a word boundary is. Searching for “cat” will inadvertently match “catalog”, “scatter”, and “vacation”.
• No stemming: Searching for “optimize” will miss “optimizing”, “optimizer”, or “optimized”.
• No relevance ranking: Results are unweighted; a match in the title has the same weight as a match tucked away in paragraph four.

This is where SQLite’s FTS4 (Full Text Search 4) engine changes the game.

The Solution: How FTS4 and Inverted Indices Work

SQLite includes dedicated full-text search extensions (FTS3/FTS4 and FTS5). In Android’s Room persistence library, this is natively supported via the @Fts4 and @Fts3 annotations.

The Inverted Index: From O(N) to O(1)

Instead of scanning rows at query time, FTS4 does the heavy lifting at insert time.

When a text column is indexed by FTS4, a tokenizer breaks the text down into individual words (tokens), normalizes their case, strips punctuation, and builds an Inverted Index.

An inverted index is essentially a word-to-document dictionary:

+--------------+-----------------------+
| Token        | DocIDs (Posting List) |
+--------------+-----------------------+
| architecture | [1, 14, 108, 492]     |
| benchmark    | [1, 7, 22, 108, 305]  |
| database     | [1, 4, 18, 92, 108]   |
| security     | [2, 6, 11, 45, 99]    |
+--------------+-----------------------+

When you issue a search query like MATCH ‘benchmark*’, FTS4:

1. Tokenizes the search string.
2. Performs an instantaneous lookup in the token dictionary.
3. Retrieves the exact list of docid numbers containing the word.
4. Returns the records without scanning a single byte of irrelevant text.

Whether you have 100 rows or 100,000 rows, lookups happen in fractions of a millisecond.

Implementation in Android Room

A common misconception is that using FTS requires duplicating your data and doubling your database size. With Room’s contentEntity pattern, this is completely avoided.

Let’s look at the production implementation from our Mail Showcase application.

First, create your base table containing all raw fields. This remains your single source of truth:

// MailEntity.kt
import androidx.room.Entity
import androidx.room.PrimaryKey

@Entity(tableName = "mails")
data class MailEntity(
    @PrimaryKey(autoGenerate = true)
    val id: Long = 0,
    val sender: String,
    val recipient: String,
    val subject: String,
    val body: String,
    val timestamp: Long = System.currentTimeMillis()
)

Next, define the virtual FTS entity. By declaring contentEntity = MailEntity::class, Room instructs SQLite to use an External Content Table.

The FTS table maintains only the index structures and token postings. The text itself is fetched on-demand from the base mails table, eliminating storage duplication:

import androidx.room.Entity
import androidx.room.Fts4

@Entity(tableName = "mails_fts")
@Fts4(contentEntity = MailEntity::class)
data class MailFtsEntity(
    val sender: String,
    val subject: String,
    val body: String
)

TIP : Under the hood, Room automatically creates SQLite database triggers (AFTER INSERT, AFTER UPDATE, AFTER DELETE) on the mails table. Whenever you insert or update a MailEntity, the mails_fts index updates automatically!

Register both classes in your @Database declaration:

@Database(
    entities = [MailEntity::class, MailFtsEntity::class],
    version = 1,
    exportSchema = false
)
abstract class MailDatabase : RoomDatabase() {
    abstract fun mailDao(): MailDao
}

Now we can compare both queries in our MailDao.

Notice how the FTS query joins mails.id against mails_fts.docid:

@Dao
interface MailDao {

    @Insert(onConflict = OnConflictStrategy.REPLACE)
    suspend fun insertMails(mails: List<MailEntity>): List<Long>

    /**
     * Standard SQL LIKE operator search.
     * Triggers an O(N) sequential scan across every row.
     */
    @Query(
        """
        SELECT * FROM mails
        WHERE subject LIKE '%' || :query || '%'
           OR body LIKE '%' || :query || '%'
           OR sender LIKE '%' || :query || '%'
        ORDER BY timestamp DESC
        LIMIT :limit
        """
    )
    suspend fun searchMailsLike(query: String, limit: Int = 200): List<MailEntity>

    /**
     * SQLite FTS4 (Full Text Search) MATCH query.
     * Uses inverted index token lookups.
     */
    @Query(
        """
        SELECT mails.* FROM mails
        JOIN mails_fts ON mails.id = mails_fts.docid
        WHERE mails_fts MATCH :query
        ORDER BY mails.timestamp DESC
        LIMIT :limit
        """
    )
    suspend fun searchMailsFts(query: String, limit: Int = 200): List<MailEntity>
}

To provide an “as-you-type” search experience, sanitize the input and append a wildcard * to the tokens so that typing “arch” matches “architecture”:

private fun sanitizeFtsQuery(query: String): String {
    val sanitized = query.replace(""", "").replace("'", "").trim()
    val tokens = sanitized.split("\s+".toRegex()).filter { it.isNotEmpty() }
    if (tokens.isEmpty()) return ""

    // Appending '*' enables fast token prefix matching in FTS
    return tokens.joinToString(" ") { "$it*" }
}

To measure real-world performance, we built a benchmarking suite into the showcase app that measures database execution duration down to the microsecond (measureNanoTime) on identical datasets.

We populated the database with multiline emails and measured search latency across dataset scales:

+--------------+-------------------------+-------------------------+----------------+
| Dataset      | SQL LIKE Latency        | Room @Fts4 MATCH        | Speedup Factor |
+--------------+-------------------------+-------------------------+----------------+
| 100 mails    |  2.840 ms (39 matches)  |  1.800 ms (39 matches)  | 1.6x faster    |
| 500 mails    |  8.114 ms (179 matches) |  3.892 ms (179 matches) | 2.1x faster    |
| 2,000 mails  | 30.181 ms (200 matches) | 13.071 ms (200 matches) | 2.3x faster    |
| 5,000 mails  | 63.762 ms (200 matches) |  6.811 ms (200 matches) | 9.4x faster    |
+--------------+-------------------------+-------------------------+----------------+

Query Execution Time vs Dataset Size
Latency (ms)
  70 ┼                                                  ● SQL LIKE (63.8 ms)
  60 ┼                                                 
  50 ┼                                                
  40 ┼                                              
  30 ┼                                  ● (30.2 ms) 
  20 ┼                                              
  10 ┼                    ● (8.1 ms)             ● FTS4 (6.8 ms)
   0 ┼───● (2.8 ms)───────● (3.9 ms)────● (13.1 ms)──────
     └──────┬─────────────────┬──────────────┬──────────────┬────────
          100               500           2,000          5,000
                                 Email Records

Key Observations:

1. The 16ms Frame Budget Barrier: At 2,000 emails, SQL LIKE takes ~30.18 ms, breaching the ~16.6 ms frame target for 60Hz displays (and ~8.3 ms for 120Hz displays). At 5,000 emails (~63.76 ms), executing LIKE on or near the UI thread causes dropped frames and noticeable UI stutter.
2. Diverging Performance at Scale: While FTS4 offers a steady 1.6x–2.3x improvement on smaller to medium datasets, its advantage explodes at 5,000 records, executing 9.4x faster than LIKE (~6.81 ms vs. ~63.76 ms).
3. Prefix Support: FTS4 handles arch* queries instantly because token prefixes are traversed directly in the index structure.

When to Use Which

| Feature                   | SQL LIKE '%query%'                | Room @Fts4 (MATCH)                           |
+---------------------------+-----------------------------------+----------------------------------------------+
| Algorithmic Complexity    | O(N) Sequential full table scan   | O(1) / Sublinear Inverted index lookup       |
| Execution Time at Scale   | Degrades linearly with row count  | Remains consistently in low single-digit ms  |
| Word Boundary Awareness   | No (matches substrings blindly)   | Yes (tokenized at word boundaries)           |
| Stemming Support          | No                                | Yes (Porter stemmer available)               |
| Prefix Matching           | Wildcards break B-Tree index      | Native (MATCH 'token*')                      |
| Storage Impact            | Zero overhead                     | Minimal index metadata (via contentEntity)   |
| Insert Overhead           | Minimal                           | Slight cost during insert to update index    |
+---------------------------+-----------------------------------+----------------------------------------------+

Conclusion

SQL LIKE is a wonderful tool for prototyping or querying discrete code columns (like status codes or short identifiers). But the moment your application handles human text—messages, documents, notes, product catalogs—relying on LIKE ‘%…%’ is a ticking performance bottleneck.

By incorporating Room’s @Fts4 with the contentEntity pattern:

• You retain clean, relational entities as your source of truth.
• You gain high-performance inverted index lookups that scale effortlessly into tens of thousands of items.
• Your UI remains silky smooth, respecting the user’s frame budget and battery life.

If your Android app has a search bar querying text fields, don’t wait for your dataset to grow in production. Migrate to Room FTS and deliver an instant search experience your users will love.

References

Fts4 | API reference | Android Developers

LinkedIn

Youtube

Love you all.

Stay tune for upcoming blogs.

Take care.

---

Scaling Android Search: Room @Fts4 vs SQL LIKE was originally published in ProAndroidDev on Medium, where people are continuing the conversation by highlighting and responding to this story.