Cassandra vs PostgreSQL: How Facebook's Inbox Search Led to a Distributed Database

A database choice that starts with a search problem

Imagine you're building a messaging application.

Users send thousands of messages every second. Over time, the application stores billions of messages. And users expect something that sounds simple:

"Show me all the messages containing the word 'football'."

At first, this looks like a straightforward database query.

If you're familiar with PostgreSQL, you might start with a table like this:

CREATE TABLE messages ( id BIGSERIAL PRIMARY KEY, user_id BIGINT NOT NULL, message_text TEXT NOT NULL, created_at TIMESTAMP NOT NULL ); 

To search for messages containing a particular word, PostgreSQL provides full-text search.

For example:

SELECT id, message_text, created_at FROM messages WHERE to_tsvector('english', message_text) @@ plainto_tsquery('english', 'football'); 

You can improve this with a GIN index:

CREATE INDEX messages_search_idx ON messages USING GIN (to_tsvector('english', message_text)); 

This is a perfectly reasonable starting point.

In fact, PostgreSQL has a mature full-text search implementation. It would be misleading to say that PostgreSQL cannot handle message search or that it automatically becomes slow when a table grows.

So, where does the architectural problem begin?

When the workload starts changing

Let's say the messaging application grows.

Now we're dealing with:

• Billions of messages.
• A continuous stream of new messages.
• Search indexes that grow alongside the message data.
• Users searching their message history frequently.
• A requirement to distribute storage and traffic across multiple machines.

The challenge is no longer just writing a good SQL query.

It's about how we distribute the data, maintain the indexes, handle writes, and serve queries as the system grows.

PostgreSQL can be scaled using partitioning, read replicas, and distributed extensions such as Citus. These are valid approaches.

However, they introduce additional architectural decisions.

For example, PostgreSQL table partitioning divides a table into smaller physical pieces, but it does not automatically distribute writes across independent database servers.

Similarly, read replicas can help scale read traffic, but they don't distribute the primary database's write workload.

There's also the cost of maintaining indexes.

A GIN index is useful for full-text search, but inserting or updating a document can require updating multiple index entries. PostgreSQL's documentation explains that GIN updates can be expensive and that its pending-list mechanism can introduce additional work during searches.

References:

• PostgreSQL: GIN Indexes
• PostgreSQL: Table Partitioning

None of this means PostgreSQL is the wrong choice.

It means that for a particular workload, we may want a storage architecture designed around distributing large amounts of data and handling high write throughput.

And that's where Cassandra becomes interesting.

The real-world example: Facebook Inbox Search

One of the most interesting examples comes from Facebook.

In August 2008, Facebook introduced Cassandra as a distributed storage system.

The original problem was not to replace Facebook's entire database infrastructure.

It was specifically about Inbox Search.

Facebook needed to store reverse indexes of messages that users sent and received. The amount of data was growing, and the team needed a storage system that could scale incrementally across many commodity servers without a single point of failure.

The original engineering article describes Cassandra as a distributed structured-data storage system built on a peer-to-peer architecture.

It also describes the initial deployment: terabytes of indexes distributed across more than 600 CPU cores and 120 TB of disk.

That is an important distinction.

Facebook wasn't using Cassandra as a magical search engine. It was using Cassandra to store and distribute the data structures that made message searching possible.

Source: Cassandra – A Structured Storage System on a P2P Network

Let's understand how that works.

First, what is an inverted index?

An inverted index is a data structure that maps a word to the documents or messages containing that word.

Imagine we have these messages:

A normal message table stores messages and their contents.

An inverted index stores the relationship in the opposite direction:

Now, when a user searches for football, we don't need to inspect every message's text.

We look up the keyword in the index and get the matching message IDs.

The application can then retrieve the actual message contents using those IDs.

The important idea is that the search index is a separate data structure built from the original messages.

This is also the basic concept behind many full-text search systems.

Where Cassandra fits into this architecture

Cassandra is not a full-text search engine.

It doesn't automatically read arbitrary message text, extract keywords, and create a searchable index for you.

The application needs to build that index.

Cassandra's role is to store and distribute the index across a cluster of machines.

Let's understand the architecture through a simplified example.

1. The application extracts keywords

When a new message arrives:

Message ID: 201 User ID: 42 Message: "Let's watch football tonight" 

The application extracts the searchable terms:

football tonight watch 

It then creates index entries connecting those terms to the message.

Conceptually:

football -> Message 201 tonight -> Message 201 watch -> Message 201 

A real implementation would also need to consider tokenization, language handling, stop words, duplicate terms, and possibly word positions.

2. Cassandra stores the index using partitions

Cassandra organizes data around a concept called a partition key.

The partition key determines how data is distributed across the cluster.

For example, we could model a per-user keyword index like this:

CREATE TABLE messages_by_term ( user_id BIGINT, term TEXT, time_bucket TEXT, message_time TIMESTAMP, message_id BIGINT, positions LIST<INT>, PRIMARY KEY ( (user_id, term, time_bucket), message_time, message_id ) ) WITH CLUSTERING ORDER BY ( message_time DESC, message_id ASC ); 

This is an illustrative schema, not Facebook's actual Cassandra schema.

Let's understand its structure.

• user_id: The user whose messages are being searched.
• term: The keyword extracted from a message.
• time_bucket: A time-based grouping, such as a month.
• message_time: Helps retrieve matching messages in chronological order.
• message_id: Identifies the original message.
• positions: Can store where the keyword appeared in the message.

The combination of user_id, term, and time_bucket forms the partition key.

That means all matching index entries for a particular user, keyword, and time bucket are grouped into the same logical partition.

Cassandra uses consistent hashing to distribute partitions across nodes.

It also replicates partitions across multiple nodes according to the configured replication strategy.

So, instead of relying on one database server to store the entire search index, we can distribute that index across a cluster.

3. What happens when a user searches?

Suppose user 42 searches for:

football 

The application knows the user ID and the keyword.

It can query Cassandra:

SELECT message_id, message_time FROM messages_by_term WHERE user_id = 42 AND term = 'football' AND time_bucket = '2026-10'; 

Cassandra locates the partition using its partition key and retrieves the matching entries.

The application then uses the returned message IDs to fetch the actual messages.

Conceptually:

User searches for "football" | v Application extracts search parameters | v Cassandra looks up the matching partition | v Returns matching message IDs | v Application fetches message contents | v Search results are returned to the user 

Notice something important here.

Cassandra isn't scanning every message to find the word football.

The application has already created an index that allows Cassandra to retrieve the matching message references directly.

4. Why do we need time buckets?

You might have noticed the time_bucket column in the partition key.

Why not simply use:

(user_id, term) 

Imagine a user has millions of messages containing the same common word.

If all those index entries belong to one partition, that partition can become extremely large.

Large or heavily accessed partitions can create performance and operational problems.

Time bucketing helps divide those entries into smaller partitions.

For example:

User 42 + football + 2026-08 User 42 + football + 2026-09 User 42 + football + 2026-10 

Now the application can search only the relevant time buckets.

There is a trade-off, though.

If a user wants to search their entire message history, the application may need to query multiple buckets and combine the results.

This is an important Cassandra design principle:

You model your tables around the queries you need to support.

Unlike a traditional relational design, you don't normally depend on joins to combine normalized tables at query time.

Instead, you often duplicate data and maintain separate tables for different access patterns.

That duplication is intentional. It helps make reads predictable and efficient.

Source: Cassandra Data Modeling Introduction

What happens internally when Cassandra receives a write?

So far, we've discussed how Cassandra distributes the index.

But how does it store incoming data efficiently?

Cassandra uses an architecture based on an LSM tree (Log-Structured Merge Tree).

Let's simplify the write path.

When the application sends a write:

1. A coordinator node receives the request.
2. Cassandra identifies the replica nodes responsible for the partition.
3. The replicas persist the write to their commit logs.
4. The data is added to an in-memory structure called a memtable.
5. Eventually, the memtable is flushed to disk as an immutable SSTable.
6. Background compaction merges SSTables over time.

The flow looks like this:

Application | v Coordinator Node | +-----------> Replica Node 1 | | | v | Commit Log | | | v | Memtable | | | v | SSTable | +-----------> Replica Node 2 | +-----------> Replica Node 3 

Why is this useful?

Traditional B-tree indexes often require updating existing structures in place.

An LSM-based storage engine is designed around writing changes to memory and flushing them to disk in sequential files.

This makes it well suited to write-heavy workloads.

However, it isn't free.

Because data can exist across multiple SSTables, reads may need to check more than one file. Cassandra uses mechanisms such as Bloom filters to avoid checking SSTables that definitely don't contain the requested partition.

Compaction also consumes background I/O and creates write amplification.

So Cassandra makes a different trade-off: efficient write handling and distributed storage, with additional work required to manage reads and compaction.

Source: Cassandra Storage Engine

What if one Cassandra node goes down?

Another important part of Cassandra's architecture is replication.

For example, imagine a replication factor of three.

A partition is stored on three replica nodes:

Partition A | +---- Node 1 +---- Node 2 +---- Node 3 

If one node becomes unavailable, the other replicas may still serve requests, depending on the consistency level used.

For example, with a replication factor of three:

• ONE requires a response from one replica.
• QUORUM requires a majority of replicas, which is two in this example.

Choosing the consistency level is an architectural decision.

A quorum read and quorum write generally provide overlapping replica acknowledgements for the same replica set, but this does not mean Cassandra behaves exactly like a traditional relational database transaction.

Cassandra provides tunable consistency, allowing the application to choose a trade-off between availability, latency, and consistency for its operations.

This is useful for systems that need to remain available while distributing data across many machines.

Source: Cassandra Dynamo Architecture

Does this mean Cassandra is always better than PostgreSQL?

Definitely not.

A database should be selected based on the workload, not simply because it can distribute data across more servers.

Consider the differences:

For a typical business application with relational data, complex queries, transactions, and moderate traffic, PostgreSQL may be the simpler and better choice.

For a workload involving huge amounts of data, predictable access patterns, high write throughput, and a need to distribute data across many nodes, Cassandra may be worth considering.

And if the requirement is sophisticated full-text search with relevance ranking, fuzzy matching, and language processing, a dedicated search engine may be a better fit than either database alone.

One important historical detail: Facebook later chose HBase for Messages

There's another interesting part of this story.

In 2010, Facebook published an article explaining the technology behind its newer Messages infrastructure.

The team evaluated multiple technologies, including MySQL, Cassandra, and HBase.

The article explains that MySQL struggled with long-tail data as datasets and indexes grew.

It also explains that Cassandra's eventual consistency model was difficult to reconcile with the requirements of the newer Messages infrastructure.

Facebook ultimately selected HBase for that system.

This is worth mentioning because it prevents us from drawing the wrong conclusion from the original Cassandra story.

Cassandra was a successful fit for Facebook's original Inbox Search problem.

That did not make it the best choice for every subsequent messaging workload.

The same company chose different databases for different engineering requirements.

Source: The Underlying Technology of Messages – Facebook Engineering

What should we take away from this?

The interesting lesson isn't that Cassandra is faster than PostgreSQL.

It's that the way we model and distribute data changes depending on the problem we're trying to solve.

With PostgreSQL, we might begin with normalized message records and a GIN index for full-text search.

As the workload grows, we need to evaluate index maintenance, write throughput, partitioning, replication, and the complexity of distributing the workload.

With Cassandra, we can build an application-managed inverted index, partition it around the queries we need, and distribute and replicate those partitions across a cluster.

But that comes with trade-offs:

• We need to design tables around access patterns.
• We may duplicate data.
• We need to maintain the search index when messages are created or deleted.
• Queries across multiple partitions require additional coordination.
• We need to understand consistency levels and operational trade-offs.

The database isn't the architecture by itself.

The workload determines the architecture, and the architecture helps determine the database.

That's the real lesson behind Cassandra's original use at Facebook.

References and further reading

1. Cassandra – A Structured Storage System on a P2P Network (Facebook Engineering, 2008)
2. The Underlying Technology of Messages (Facebook Engineering, 2010)
3. Cassandra Data Modeling
4. Cassandra Storage Engine
5. Cassandra Dynamo Architecture
6. PostgreSQL GIN Indexes
7. PostgreSQL Table Partitioning