How Instagram Efficiently Serves Hashtags Ordered by Count

Instagram processes millions of photo and video uploads daily, almost all accompanied by user-generated hashtags. To make content discoverable, the platform provides search autocomplete: when a user types a prefix into the search bar (e.g., #snow), Instagram must instantly return the most relevant matching hashtags ordered by their total media count.

While complex search queries across media captions often rely on dedicated search engines like Elasticsearch, Instagram handles this high-throughput hashtag search directly within PostgreSQL. By leveraging a first-principles optimization technique—partial indexes—they eliminated heavy database sort operations, reducing scanned rows from over 15,000 to just 169 for popular prefixes.

---

1. The Core Problem: Autocomplete and Prefix Sorting

At a fundamental level, hashtag search requires querying a database table that tracks every unique hashtag and its associated media count.

Simplified Schema

CREATE TABLE hashtags (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    media_count BIGINT DEFAULT 0
);

When a user enters snow into the search box, the backend issues a query to fetch the top 10 most popular tags starting with snow:

SELECT *
FROM hashtags
WHERE name LIKE 'snow%'
ORDER BY media_count DESC
LIMIT 10;

Why Elasticsearch Was Not the Default Choice

Engineers often reach for external search engines (such as Elasticsearch or OpenSearch) as a default reaction to any prefix or text-matching requirement. However, adding an external search cluster introduces significant overhead:

1. Data Synchronization Lag: Maintaining synchronization between PostgreSQL transactions and search indexes via Change Data Capture (CDC) or asynchronous pipelines introduces eventual consistency delays.
2. Operational Complexity: Operating, sharding, monitoring, and scaling an independent distributed cluster.
3. Over-Engineering: For simple prefix matching and counter-based ordering, relational databases like PostgreSQL provide sufficient primitives if tuned correctly.

Instagram’s philosophy emphasizes exhausting the capabilities of their primary data store—PostgreSQL—before introducing external dependencies.

---

2. The Bottleneck: Explain Analyze Breakdown

Under a standard B-Tree index on hashtags(name), PostgreSQL can quickly identify all rows matching the prefix snow%. However, when inspecting the execution plan using EXPLAIN ANALYZE, a critical performance issue emerges:

Limit  (cost=... rows=10)
  ->  Sort  (cost=...)
        Sort Key: media_count DESC
        ->  Index Scan using idx_hashtags_name on hashtags  (cost=... rows=15445)
              Index Cond: (name >= 'snow' AND name < 'snow0')
              Filter: (name ~~ 'snow%')

flowchart TD
    A[User Query: prefix 'snow%'] --> B[Index Scan on 'name']
    B --> C[Match 15,445 rows]
    C --> D[In-Memory / On-Disk Sort by media_count DESC]
    D --> E[Apply LIMIT 10]
    E --> F[Return Top 10 Results]

The Cost of In-Memory Sorting

• The B-Tree index on name locates all matching entries, but these rows are ordered alphabetically, not by popularity.
• PostgreSQL must fetch all 15,445 matching rows and perform an explicit sort operation on media_count DESC before discarding 15,435 of them to satisfy LIMIT 10.
• Multiplying this sorting overhead by thousands of queries per second across millions of active users creates substantial CPU and memory pressure on the database primary and read replicas.

---

3. The Insight: Exploiting Long-Tail Distributions

Hashtag usage strictly follows a long-tail (Power Law / Pareto) distribution:

• A tiny fraction of hashtags (e.g., #snow, #snowboarding, #snowday) are used millions of times.
• The vast majority of hashtags are created once or twice (e.g., #snowdaywithfriendsinmarch2021) and have a media_count close to 1.

Media Count
    ^
    |  *
    |  *
    |  *
    |  * *
    |      * * * * * * * * * * * * * * * * * * * * *  (Long Tail: Count <= 100)
    +--------------------------------------------------> Unique Hashtags

Because the autocomplete endpoint only ever returns the top 10 results ordered by media_count DESC, rows with negligible media counts will practically never appear in the top 10 for broad prefixes.

This insight reveals an opportunity: Why index and sort through millions of rarely used hashtags when the application only cares about popular ones?

---

4. The Solution: PostgreSQL Partial Indexes

A partial index (or filtered index) is an index built over a subset of a table defined by a conditional WHERE clause. Rows that do not satisfy the predicate are excluded from the index entirely.

Creating the Partial Index

Instagram applied this by indexing only hashtags with a media_count greater than a specific threshold (e.g., 100):

CREATE INDEX CONCURRENTLY idx_hashtags_popular
ON hashtags (name, media_count DESC)
WHERE media_count > 100;

(Note: Running with CONCURRENTLY ensures production tables remain unblocked during index construction.)

Query Modification to Utilize the Partial Index

To ensure the PostgreSQL query planner selects the partial index, the query must include a predicate that matches or is a subset of the index’s WHERE clause:

SELECT *
FROM hashtags
WHERE name LIKE 'snow%'
  AND media_count > 100
ORDER BY media_count DESC
LIMIT 10;

flowchart TD
    A[Query: prefix 'snow%' AND media_count > 100] --> B[Partial Index Scan: idx_hashtags_popular]
    B --> C[Match Only 169 Rows]
    C --> D[Sort 169 Rows]
    D --> E[Apply LIMIT 10]
    E --> F[Return Top 10 Results]

The Impact

When running EXPLAIN ANALYZE on the revised query:

1. Rows Scanned & Sorted: The candidate set plummeted from 15,445 rows to just 169 rows—a reduction of over 98.9%.
2. Index Size: Excluding the long tail keeps the B-Tree compact. A smaller index fits entirely into the PostgreSQL buffer pool (shared_buffers) and system RAM, maximizing cache hits and minimizing disk I/O.
3. Write Amplification Reduction: New hashtags created with an initial media_count of 1 bypass this index completely during INSERT operations, avoiding index write amplification until they surpass the threshold.

---

5. Query Planner Subsumption and Adaptability

A common concern with partial indexes is rigidity: what happens if product requirements change and the threshold needs to be adjusted in the application layer?

Because PostgreSQL’s query optimizer understands boolean logic and mathematical subsumption, it can use an existing partial index even if the query’s filter is stricter than the index definition.

For example, if the application query changes to:

SELECT *
FROM hashtags
WHERE name LIKE 'snow%'
  AND media_count >= 500
ORDER BY media_count DESC
LIMIT 10;

The planner recognizes that the set of rows where media_count >= 500 is a strict subset of the indexed rows where media_count > 100 ((media_count >= 500) ⟹ (media_count > 100)). The optimizer will continue using idx_hashtags_popular without requiring a schema migration or an additional index.

---

6. Summary of Trade-Offs

Attribute	Full Table Index	Partial Index (WHERE media_count > 100)
Rows Evaluated on Prefix	High (~15,400+)	Minimal (~169)
Index Size	Large (indexes billions of 1-off tags)	Small (contains only active/popular tags)
Memory Footprint (RAM)	Prone to cache eviction	Easily pinned in database cache
Write Performance	Index updated on every new hashtag creation	Unpopular tags bypass the index on insert
Query Constraint	Queries can search any tag count	Query must include the predicate (or subset)

---

Key Takeaways

1. Know Your Data Distribution: Understanding that hashtags follow a long-tail power law allowed Instagram to discard unneeded candidate rows before they ever hit the execution plan.
2. Avoid Premature Architecture Expansion: Before introducing secondary search systems like Elasticsearch for prefix and ranking problems, verify whether your relational database features (like PostgreSQL partial indexes) can solve the problem natively.
3. Partial Indexes Protect Compute and Memory: By indexing only the minority of rows that are frequently queried, you save disk space, reduce write overhead on row creation, and transform expensive sorting bottlenecks into negligible operations.