In Example 3-1 in the preceding section, region_id is given as an ID, not as the plain-text string Washington, DC, United States. Why?
If the UI has a free-text field for entering the region, storing it as a plain-text string makes sense. But there are advantages to having standardized lists of geographic regions and letting users choose from a drop-down list or autocompleter. These include the following:
-
Consistent style and spelling across profiles
-
Avoiding ambiguity if several places have the same name (if the string were just Washington, DC, would it refer to DC or to the state?)
-
Ease of updating—the name is stored in only one place, so it is easy to update across the board if it ever needs to be changed (e.g., change of a city name due to political events)
-
Localization support—when the site is translated into other languages, the standardized lists can be localized, so the region can be displayed in the viewer’s language
-
Better search functionality (e.g., a search for people on the US East Coast can match this profile, because the list of regions can encode the fact that Washington is located on the East Coast—which is not apparent from the string Washington, DC alone)
Whether you store an ID or a text string is a question of normalization. When you use an ID, your data is more normalized: the information that is meaningful to humans (such as the text Washington, DC) is stored in only one place, and everything that refers to it uses an ID (which has meaning only within the database). When you store the text directly, you are duplicating the human-meaningful information in every record that uses it; this representation is denormalized.
The advantage of using an ID is that because it has no meaning to humans, it never needs to change: the ID can remain the same even if the information it identifies changes. Anything that is meaningful to humans may need to change sometime in the future—and if that information is duplicated, all the redundant copies will need to be updated. That requires more code, more write operations, and more disk space, and it risks inconsistencies (as some copies of the information are updated but others aren’t).
The downside of a normalized representation is that every time you want to display a record containing an ID, you have to do an additional lookup to resolve the ID into something human-readable. In a relational data model, this is done using a join. For example:
SELECT users.*, regions.region_name
FROM users
JOIN regions ON users.region_id = regions.id
WHERE users.id = 251;
Document databases can store both normalized and denormalized data, but they are often associated with denormalization—partly because the JSON data model makes it easy to store additional denormalized fields, and partly because the weak support for joins in many document databases makes normalization inconvenient. Some document databases don’t support joins at all, so you have to perform them in application code—that is, you first fetch a document containing an ID, then perform a second query to resolve that ID into another document. In MongoDB, it is also possible to perform a join using the $lookup operator in an aggregation pipeline:
db.users.aggregate([
{ $match: { _id: 251 } },
{ $lookup: {
from: "regions",
localField: "region_id",
foreignField: "_id",
as: "region"
} }
])
Trade-offs of normalization
In the résumé example, while the region_id field is a reference to a standardized set of regions, the organization (the company or government where the person worked) and school_name (where they studied) are just strings. This representation is denormalized: many people may have worked at the same company, but there is no ID linking them.
It’s worth considering whether the organization and school names should be entities instead, and the profile should reference their IDs. The same arguments for referencing the ID of a region also apply here. For example, say we wanted to include the logo of the school or company in addition to its name:
-
In a denormalized representation, we would include the image URL of the logo on every individual person’s profile. This makes the JSON document self-contained, but it creates a headache if we ever need to change the logo, because we now need to find all the occurrences of the old URL and update them.
-
In a normalized representation, we would create an entity representing an organization or school and store its name, logo URL, and perhaps other attributes (description, news feed, etc.) once as part of that entity. Every résumé that mentions the organization would then simply reference its ID, and updating the logo would be easy.
As a general principle, normalized data is usually faster to write (since there is only one copy) but slower to query (since it requires joins); denormalized data is usually faster to read (fewer joins) but more expensive to write (more copies to update, more disk space used). You might find it helpful to view denormalization as a form of derived data (see “Systems of Record and Derived Data”), since you need to set up a process for updating the redundant copies of the data.
Besides the cost of performing all these updates, you need to consider the consistency of the database if a process crashes halfway through making its updates. Databases that offer atomic transactions (see “Atomicity”) make it easier to remain consistent, but not all databases offer atomicity across multiple documents. It is also possible to ensure consistency through stream processing, which we discuss in the related discussion.
Normalization tends to be better for OLTP systems, where both reads and updates need to be fast; analytical systems often fare better with denormalized data, since they perform updates in bulk and the performance of read-only queries is the dominant concern. In systems of small to moderate scale, a normalized data model is often best because you don’t have to worry about keeping multiple copies of the data consistent with one another, and the cost of performing joins is acceptable. However, in very large-scale systems, the cost of joins can become problematic.
Denormalization in the social networking case study
In “Case Study: Social Network Home Timelines” we compared a normalized representation (Figure 2-1) and a denormalized one (precomputed, materialized timelines). Here, the join between posts and follows was too expensive, and the materialized timeline is a cache of the result of that join. The fan-out process that inserts a new post into followers’ timelines was our way of keeping the denormalized representation consistent.
However, the implementation of materialized timelines at X (formerly Twitter) does not store the actual text of each post. Each entry stores only the post ID, the ID of the user who posted it, and a little bit of extra information to identify reposts and replies. In other words, it is a precomputed result of (approximately) the following query:
SELECT posts.id, posts.sender_id FROM posts
JOIN follows ON posts.sender_id = follows.followee_id
WHERE follows.follower_id = current_user
ORDER BY posts.timestamp DESC
LIMIT 1000
This means that whenever the timeline is read, the service still needs to perform two joins: it looks up the post ID to fetch the actual post content (as well as statistics such as the number of likes and replies), and it looks up the sender’s profile by ID (to get their username, profile picture, and other details). This process of looking up the human-readable information by ID is called hydrating the IDs, and it is essentially a join performed in application code.
The reason for storing only IDs in the precomputed timeline is that the data they refer to is fast-changing. The number of likes and replies may change multiple times per second on a popular post, and some users regularly change their username or profile photo. Since the timeline should show the latest like count and profile picture when it is viewed, denormalizing this information into the materialized timeline would not make sense. Moreover, the storage cost would be increased significantly by such denormalization.
This example shows that having to perform joins when reading data is not, as sometimes claimed, an impediment to creating high-performance, scalable services. Hydrating post and user IDs is actually a fairly easy operation to scale, since it parallelizes well, and the cost doesn’t depend on the number of accounts you are following or the number of followers you have.
If you need to decide whether to denormalize something in your application, the social network case study shows that the choice is not immediately obvious; the most scalable approach may involve denormalizing some things and leaving others normalized. You will have to carefully consider how often the information changes and the cost of reads and writes (which might be dominated by outliers, such as users with many follows/followers in the case of a typical social network). Normalization and denormalization are not inherently good or bad—they simply represent trade-offs in terms of performance of reads and writes and implementation effort.