Querying 1 Billion Phone Numbers by Last 4 Digits in Milliseconds Without Elasticsearch
Suffix and substring queries on massive datasets are a recurring pain point in user-facing systems, and the instinct to reach for Elasticsearch or full-text search clusters carries real infrastructure and operational costs. This pattern shows how a purpose-built index table with deterministic routing can deliver millisecond lookups using only the database already in place.
A common interview trap at ByteDance asks candidates to query 1 billion phone numbers by the last 4 digits in milliseconds. The naive LIKE '%1234' triggers a full table scan; reversing the string and indexing it works for smaller datasets but collapses under 1 billion rows as B+ tree height and IO become the bottleneck. Throwing Elasticsearch at the problem ignores hardware cost, maintenance overhead, and sync latency.
The correct answer is a heterogeneous index table: a separate mapping table storing only phone_suffix and user_id, sharded into 1,000 tables by suffix % 1000. A query for suffix 1234 hits exactly table 234, avoiding scatter-gather across all shards. Each suffix maps to roughly 100,000 users on average, so mandatory pagination with LIMIT prevents OOM kills on the application server. Redis caches only the first page of hot suffixes; a Bloom filter is useless here since all 10,000 possible suffixes exist.
The core trade-off is refusing expensive infrastructure when a simple modulo routing scheme on a lightweight index table handles the workload. The design keeps the main user table sharded by user_id untouched while the suffix index provides a fast, targeted lookup path.
The question tests whether a candidate understands that the right index structure depends on the query pattern, not just the data volume. Many engineers jump to Elasticsearch as a reflex without calculating whether the existing database can handle it with a different schema.
The modulo routing trick works only because phone suffixes are uniformly distributed across 0000–9999. A different suffix space with skew would require a different sharding strategy, which is the kind of follow-up an interviewer would probe.
Mandatory pagination is not just a performance safeguard; it is a product decision that limits deep scrolling. The answer frames it as a business constraint rather than a technical limitation, which is a mature architectural stance.