Querying 1 Billion Phone Numbers by Last 4 Digits in Milliseconds Without Elasticsearch

Written at the beginning

Yesterday I saw a guy in a tech group whose mindset completely collapsed. He went to ByteDance for a second-round interview, and the interviewer threw out a scenario question: "I have 1 billion user phone numbers. Please design a system that supports millisecond-level queries by the last 4 digits of the phone number."

The guy thought it was too simple and blurted out: "Build an index in MySQL, or use LIKE '%1234'."

The interviewer laughed on the spot: "1 billion records, and you use LIKE? Are you trying to blow up the database with a full table scan? Even if you built a regular index, the leftmost prefix principle of the B+ tree doesn't recognize suffixes. Think again."

The guy was sweating profusely and stammered for a while: "Then... use ES?"

The interviewer shook his head: "Just to query a suffix, you want me to set up an entire ES cluster? What about the hardware cost, maintenance cost, and data synchronization latency? Using a sledgehammer to crack a nut?"

This question is actually a classic "mirror" in architecture design. It doesn't test SQL syntax at all. It tests your trade-offs regarding "heterogeneous indexes," "distributed routing," and "storage cost."

Today, let's peel back the layers of these 1 billion records and see how to squeeze out performance from the architectural level.

1. The Death Flow: LIKE % / Brute-force Index

Many beginners' first reaction is: SELECT * FROM users WHERE phone LIKE '%1234'.

The result: The DBA comes running with a knife, and your job might be in danger.

Why? MySQL's B+ tree index is strictly sorted "from left to right." Querying a suffix (tail number) completely violates the "leftmost prefix principle." At this point, the index is just decoration, and the database is forced into a full table scan. 1 billion records, even if all on SSD, would take dozens of minutes to scan. Millisecond-level? Only in your dreams.

2. The Beginner Flow: The Great Reversal

Developers with a bit more experience think: "Since the index doesn't support querying from right to left, I'll just store the data reversed."

The trick: When storing the phone number, also store a reversed string. For example, 13800138000 becomes 00083100831. Querying suffix 1234 becomes querying reversed_phone LIKE '4321%'.

The effect: This perfectly conforms to the "leftmost prefix," the index works, and the query is indeed fast.

But in front of 1 billion records, this trick is still not enough: A single table with 1 billion records means the index file alone is dozens or hundreds of GB. As the B+ tree height increases, IO is still the bottleneck. And how much concurrency can this single database handle?

3. The Advanced Flow: Sharding + Heterogeneous Index (P7 Killer Move)

At this scale, sharding is mandatory. But there's a huge pitfall here.

Usually, we shard by User_ID. If you want to query "suffix 1234," you have no idea which database these people are in. This leads to the most dreaded thing in distributed systems: "Scatter-Gather" — you have to send queries to all shard databases simultaneously and then aggregate the results. This will instantly blow up the database connection pool.

How to solve it? Build a "heterogeneous index table."

Don't touch the main table (the main table is still sharded by ID). We separately build a mapping table, storing only phone_suffix and user_id.

1. How to shard? (Key point) Don't foolishly use Hash. Phone suffixes (0000-9999) are numbers themselves, and their distribution is extremely uniform! It is recommended to directly split into 1000 tables. Routing algorithm: table_index = suffix % 1000.

Explosive effect: You want to query suffix 1234? 1234 % 1000 = 234. The request goes directly to table number 234. Precise targeting, no need to disturb the other 999 tables. Even if the data volume is huge, a single table is only 1 million rows, and MySQL runs it like a joke.

2. Hidden minefield (many people fail here) The interviewer usually smirks at this point: "Querying suffix 1234, how many records will be returned?"

Let's do the math: 1 billion users, only 10,000 suffix combinations. 1 billion / 10,000 = 100,000. On average, each suffix corresponds to 100,000 users!

If you write SELECT * in your code and return 100,000 records at once, your application server memory will directly OOM, and bandwidth will be instantly saturated.

Solution: Must enforce pagination (Limit). Tell the interviewer: "In business terms, we only display the 20 'most recently registered' users. The SQL forces ORDER BY user_id DESC LIMIT 20. Want to see more? Not supported, or pay more to use an analytical database."

4. The Fallback Flow: How to use Redis?

At this point, someone will definitely say: "Add a Redis cache!"

Pitfall avoidance guide: Never mention Bloom Filter! There are only 0000-9999 suffixes, and these 10,000 suffixes definitely all exist. Bloom filters are for preventing empty lookups; here everything is full, using it is pointless.

The correct Redis posture: Only cache the "first page". Throw the first 50 user_ids of hot data like suffix 8888 into Redis (List or ZSet). 99% of users are just browsing; Redis blocking this traffic is enough. For those who truly want deep pagination, let them query the heterogeneous table; the volume isn't large anyway.

Summary (Recommended to memorize)

Next time an interview asks this, directly use this line for a dimensionality strike:

"Interviewer, the essence of this problem is non-shard-key querying of massive data.

I won't use expensive ES, but adopt a 'Heterogeneous Index Table + Covering Index' solution. Build an independent index table, utilize the natural discreteness of phone suffixes, and directly modulo route to 1000 shard tables, avoiding full-database broadcast scans. At the same time, to prevent a single query from returning too much data and blowing up memory, I will strictly limit pagination queries. For hot suffixes, use Redis to cache first-page data as a fallback. This is a lowest-cost, highest-performance, and fully implementable architectural solution."

Written at the end

So-called architecture design is never about piling up components. If MySQL can solve it, never use ES; if modulo can solve it, never use Hash. Leave the complexity to yourself, leave the simplicity to the machine — this is the realm of a master.

Brothers, if the product manager forces you to support "fuzzy search for any middle 4 digits" (e.g., %1234%), besides running away, what other tricks do you have? Let's chat in the comments.

Brothers who find this useful, give a like and bookmark it. You never know, it might come in handy in your next interview!