How Instagram efficiently serves HashTags ordered by count

2693 views Backend System Design

Instagram has millions of photos, and each has tens of hashtags, so how does Instagram efficiently serves hashtags for a search query?

Instagram uses Postgres as its primary transactions database. For each hashtag, it stores the media_count in a table. This allows us to render the Hashtag and some meta information on the search page.

Note: Instagram could also use a dedicated search engine for this usecase, but this usecase is trivial to use something as sophisticated as ElasticSearch. We take a look at how they do it with Postgres.

A naive query to get hashtags for a given prefix ordered by count would look something like this

SELECT * from hashtags
WHERE name LIKE 'snow%'
ORDER BY media_count

Executing this query would require the database engine to filter out the hashtags starting with snow and then sort. Sorting is an expensive operation and this query required the engine to sort 15000 rows.

Under high load, this sorting becomes a pain. So, what’s the way out?

The key insight here is the fact that hashtags have a long-tail distribution i.e. most hashtags will have far fewer media counts and while serving we are always ordering by media_count.

Hence, instead of indexing everything, we can simply index the hashtags having media_count > 100 because other hashtags are highly unlikely to be surfaced.

Partial Indexes

Postgres database has this exact same capability and it is called Partial Indexing. With partial indexes, we can keep only a subset of data in the index.

We can create a partial index on our hashtags table like

CREATE INDEX CONCURRENTLY ON hashtags WHERE media_count > 100;

With this index, the query we fire would have to scan a very limited number of index entries to spit out the result.

The SQL query to get hashtags with the prefix snow% would look something like this

SELECT * from hashtags
WHERE name LIKE 'snow%'
AND media_count > 100
ORDER BY media_count

The above query required it to sort only 169 rows, completing its evaluation superfast. This is a classic usecase where we all can utilize Partial Indexes.

Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 21000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.

Other essays that you might like

Overview of Discord's data platform that daily processes petabytes of data and trillion points

924 views 54 likes 2022-11-14

When a company scales, they adopt microservices and each service typically gets its own independent database. With data ...

How Airbnb designed and scaled its central authorization system - Himeji

2206 views 98 likes 2022-11-07

Authorization plays a critical role in ensuring that the platform is not abused. For example, Instagram ensures that if ...

How Gojek masks and keeps users' phone numbers secure at scale?

2572 views 152 likes 2022-10-31

Do hyperlocal companies like Uber, Ola, Swiggy, Gojek, Zomato, etc share our phone numbers with the delivery people or t...

The architecture of Yelp's in-house Search Engine - nrtSearch

2193 views 81 likes 2022-10-24

Elasticsearch is a great search engine, but Yelp was not happy with its performance, so they built their own HTTP layer ...

Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.

Paid Courses

System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

1000+ learners

Details →

Redis Internals

Learn internals of Redis by re-implementing some of the core features in Golang.

28+ learners

Details →

Free Courses

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.

  • v13.7.5
  • © Arpit Bhayani, 2022

Powered by this tech stack.