A Detailed Guide to High Cardinality

Cardinality is an important concept when it comes to working with databases, and high-cardinality data can pose major challenges with large datasets. But what is cardinality exactly? And why is the concept so important, especially when it comes to high cardinality and big data?

This detailed guide will start with some basic concepts, including what data cardinality is and the differences between cardinality and dimensionality.

Once we’ve covered the basic concepts, we’ll get more technical and cover the why. Why is high-cardinality data more challenging to work with, and what are some strategies for managing it?

You can start from the beginning of this guide if you’re new to these concepts. Or skip ahead if you’re ready to get more technical.

This guide will cover the following topics:

• What cardinality means in the context of databases.
• The difference between high and low cardinality, including real-world examples of both types of data.
• The difference between cardinality and dimensionality.
• The challenges of working with high-cardinality data.
• Strategies for working with high-cardinality data.

What Is Data Cardinality?

In mathematics, the term cardinality refers to the number of elements in a set—and this is pretty similar to what it means in the world of databases. However, in the case of databases, cardinality refers to the number of elements in a column.

A column has high cardinality if it has many unique values.

Meanwhile, a column has low cardinality if it has few unique values. It could either be a smaller dataset or it could be a large dataset with many repeated values.

Understanding the Difference Between High and Low Cardinality Data

Here’s a trick question. Which of the following columns has higher cardinality?

If you’re new to the concept of the cardinality, you may be tempted to answer column #2. After all, column #2 has more rows.

However, cardinality isn’t a measurement of the number of rows in a column. It’s a measurement of the number of unique values.

Each of these columns has two values: A and B. As a result, they have the same cardinality.

The majority of databases (especially column-oriented ones) compress repeated data. Using an algorithm like run-length encoding would offer similar compression benefits for both of these columns. In fact, they could be represented like this if the data is also sorted:

There isn’t an exact number that differentiates between high and low cardinality. When it comes to databases, the issue of high cardinality arises when two things are combined:

• There are many rows in a column (for large datasets, the number could be billions or even trillions).
• There is a high degree of uniqueness—that is, there are fewer repeated values.

For example, a column with a trillion rows isn’t high cardinality if it always contains a boolean value. Each row can only be true or false, so this column is much easier to compress and read than a smaller column with many unique values.

On the other hand, a user ID column where each value is unique would be high cardinality in a large dataset. However, in a smaller dataset, it wouldn’t be an issue. You won’t hear data engineers talking about high cardinality for a column where each value is unique if it only has 1000 rows.

So it’s not really about a percentage or the total number of rows in a column. Rather, it’s the intersection of these two properties. Together, they can create one of the biggest challenges for modern databases: the problem of high cardinality.

Examples of High and Low Cardinality Columns

Let’s take a look at a few examples of columns with the potential for high cardinality as well as a few columns that will always be low cardinality. These are common examples from log data.

High Cardinality Columns in Log Data

Any attribute that uses a unique identifier has the potential to be high cardinality. This includes columns like:

• User ID: Each user typically has its own unique ID, which is often in UUID format.
• Client IP: Users typically have their own unique IP address as well, and may even have more than one.

Other attributes may not be unique identifiers, but they also aren’t bound by a limited set of values. Here are a few examples:

• URL query parameter: When a user makes a query on a website, the query is typically attached to the URL in the form of a query parameter. While there may be some common query parameters in a column, a query parameter is simply a string of characters, leading to the potential for high cardinality. Query strings can also be malformed, misspelled, and so on, leading to more possible permutations.
• Form fill: Any column that contains the result of a string field in a form will be high cardinality in a large dataset.

Low Cardinality Columns in Log Data

Meanwhile, the majority of columns in log data are inherently low cardinality. This is fortunate because many enterprises are dealing with huge volumes of log data, and low-cardinality data is much easier to manage than high-cardinality data. Here are a few examples:

• HTTP request method: The majority of requests are GET or POST, with PUT and DELETE being other common request methods, resulting in a low-cardinality column.
• Log level: There are typically only a few labels for log levels, such as WARN, INFO, and ERROR.
• HTTP status code: There are only 63 regularly used status codes, and only a limited number of custom status codes available. A few of these status codes (such as 200) will be most frequent.
• Boolean fields: Any column that can only contain true or false values has low cardinality.

Data Cardinality Versus Dimensionality

In contrast to data cardinality, which refers to the number of unique values in a column, data dimensionality refers to the number of attributes in a row.

The following diagram illustrates the difference between data cardinality and dimensionality.

These are easy terms to get confused, especially at first. Ultimately, both high dimensionality and high cardinality can lead to major challenges when it comes to big data.

Why Is High Cardinality So Challenging for Big Data?

Many enterprises are dealing with huge increases in the volume of incoming data, often in the form of log data. And high cardinality is a core challenge when it comes to big data, with the potential to dramatically increase costs, query latency, and the mean time to resolution (MTTR), among other things. And none of these are things that you want to increase!

Let’s take a closer look at some of these challenges.

Lower Compression Rates

OLAP (online analytical processing) databases are designed to write and read large volumes of data very quickly. This makes them an ideal fit for use cases like real-time analytics. OLAP-style databases use columnar storage.

Because data is stored in columns instead of rows, columnar databases can achieve very high rates of compression on each column. This is really important for big data, because compression reduces the overall need for storage along with storage costs. It also has other benefits like improving query performance.

Learn about the benefits of compression for big data. These benefits extend far beyond reducing costs and storage.

Compression algorithms typically rely heavily on patterns and repetition to achieve high levels of compression. Because high-cardinality data has fewer repeated values and fewer patterns, compression rates are much lower.

In the case of a 100-terabyte dataset, there’s a massive difference between a 90% compression rate and a 10% compression rate—in the former, the dataset is reduced to ten terabytes in size, while in the latter, it’s still ninety terabytes.

Let’s drill down a little further and consider two examples of algorithms that are highly effective for low-cardinality datasets but not for high cardinality—and then look at one algorithm that can sometimes be effective for high-cardinality data.

Run-Length Encoding

Run-length encoding (RLE) is a simple compression algorithm that works really well for long runs of repeated data. And it works even better when combined with sorting to create longer runs.

For a deep dive into RLE, check out the complete guide to run-length encoding.

However, with high-cardinality data, there are fewer runs of repeated values and RLE is less effective.

Dictionary Encoding

With dictionary encoding, each unique value in a column is mapped to a key in a separate dictionary. This is a very effective technique for low-cardinality columns that don’t have very many values to map. But for a high-cardinality column, the dictionary can get very large because each unique value has its own mapping. As a result, it’s less efficient and takes considerably more memory.

Delta Encoding

Now let’s take a quick look at an encoding method that can sometimes be effective for high-cardinality data.

Delta encoding encodes the delta, or difference, between data points.

Let’s look at a very simple example. The following column has the potential for high cardinality—every value is unique.

What if we instead use delta encoding to capture the first value and then record the difference for each subsequent value? The first value is 1, the difference between the first and second value is 1 (2-1), the difference between the second and third value is also 1 (3-2), and so on. The data now looks like this, with no unique values:

Now it can easily be compressed using a technique like run-length encoding. Of course, data in the real world is never so orderly, but this simple example illustrates how delta encoding can sometimes reduce data cardinality—but only if the deltas between data points are fairly consistent.

Challenges With Indexing Data

Indexing data impacts both analytics and storage. In the case of analytics, indexes can dramatically improve the performance of queries. But on the flip side, indexes also increase the size of storage as well.

The storage overhead of an index should typically be relatively small compared to the size of the dataset. But once again, high-cardinality data can create additional headaches, bloating the size of indexes and making them less effective.

Let’s look at a few examples of indexing strategies that have challenges with high-cardinality data.

B-Tree Indexing

B-trees are a common indexing structure, including for high-cardinality data. However, data with high cardinality presents challenges that can bloat the size of B-trees while slowing down performance.

As cardinality grows, the height of the tree grows, resulting in queries that require greater traversal through the tree—and longer lookup times.

Larger B-trees also take up more space in memory. If they become too large, they’ll no longer fit in memory, resulting in spillover to disk and slower I/O. This degrades performance and creates a new set of engineering challenges. And rebalancing B-trees, which is essential to keeping them performant, becomes more intensive with high-cardinality data.

Bitmap Indexing

With bitmap indexing, each unique value in a column is assigned to a bitmap, which is an array of binary values (bits). Bitmap indexing is extremely efficient for low-cardinality data, but for high-cardinality data, each unique value needs to have its own bitmap. This leads to higher memory usage and a larger storage footprint.

Approaches such as binning can make bitmap indexes much more efficient for high-cardinality data.

Higher Compute and Latency for Queries

Engineers that work with big data often must think carefully about how they structure queries to reduce query latency and compute resources. And this is especially true for high-cardinality data.

Consider the example of a full table scan, which is typically an antipractice for big data analytics. With a full table scan, the entire table is read, leading to high compute and latency if a table has billions or trillions of rows. With some databases, queries can potentially take days to run—or time out while in process and never complete.

JOIN statements, which involve joining data from multiple tables, can be especially complex and expensive for high-cardinality data.

Even just getting an accurate count of the unique values in a high-cardinality column can be challenging because counting requires an amount of memory proportional to column cardinality. Algorithms like HyperLogLog are designed to reduce the amount of memory this process takes, but at the expense of some precision.

Many databases also rely heavily on parallelism, with groups of “workers” performing tasks in parallel to reduce latency. High-cardinality data can have an uneven distribution of query results, causing some workers to do more work while others are idle. In addition to making parallelism less efficient, databases where compute and storage are tightly-coupled can have “hot spots” where workers are doing an uneven amount of work, which can negatively impact performance further.

Aggregating Data Is More Challenging

Data aggregation is critical for many data use cases such as observability and application monitoring. Groups of individual logs are often aggregated into metrics—for example, you might want to see the total number of HTTP requests made across microservices or the average latency of those requests.

However, queries like GROUP BY, which involves aggregating data by unique groups, can be extremely challenging with high-cardinality data. These queries typically involve sorting the data, which could involve sorting billions of rows in a large table.

Aggregations are also typically stored in intermediary states that are kept in memory or in temporary data structures. With high-cardinality data, these intermediary states can have high memory requirements, causing spillover to disk, decreased performance, and other issues.

The same general issues with parallelism mentioned in the previous section also come into play with aggregating data as well.

Lower Accuracy for Machine Learning Models

Machine learning models, large language models (LLMs), and other AI implementations can be extremely useful for predictive use cases, whether that’s anomaly detection, predicting the next word in a sentence, or predicting risk in a financial model.

For machine learning models to be accurate, though, they must be trained on quality data. However, high-cardinality data can cause problems for machine learning. In addition to taking longer to train (and requiring larger amounts of compute resources to do so), high-cardinality data can lead to issues with overfitting.

Overfitting happens when a model matches its training data so closely that it can’t effectively make predictions. With high-cardinality data, models may have more challenges finding patterns, affecting their ability to be used in production.

Higher Costs and Shorter Data Retention Windows

All of these issues have an impact on the bottom line. Less compressibility and bloated indexes lead to higher storage costs. And with high-cardinality data, queries and analytics are more computationally expensive, especially full table scans and operations like JOIN and GROUP BY statements.

These issues can be catastrophic for enterprises that are already dealing with sticker shock when it comes to managing big data. Enterprises are often ingesting terabytes of log data every day, and these high bills often lead to significant compromises like shorter data retention periods. With shorter data retention periods, enterprises have much less visibility into their data, especially for long-term use cases.

Strategies for Handling High-Cardinality Data

While high-cardinality data can be challenging to work with, some modern databases (especially OLAP-style DBs) are optimized to work with large volumes of data—including data that has high dimensionality and cardinality.

Here are some of the strategies that these databases and data engineers use. These techniques include optimizations as well as best practices to reduce cardinality and compute-intensive procedures like full table scans.

Partitioning and Partition Pruning

Databases often use partitioning to make querying data more manageable, regardless of whether the data has high or low cardinality. Let’s look at Hydrolix as an example. Hydrolix is designed for high volumes of log data, and tables can be very large, holding billions or even trillions of rows. To make querying and analyzing these tables more manageable, data is partitioned by time.

When a user makes a time-filtered query, all partitions that don’t include the requested time range are immediately pruned from consideration. As a result, queries typically retrieve a small slice of data, making queries much more efficient—and avoiding anti-practices like full table scans.

Columnar Storage and Column Pruning

With columnar databases, each column can typically have a different number of values, and each column can even be compressed in different ways. Just as importantly, users can select with columns they want to retrieve from storage and maximize the benefits of column pruning.

With column pruning, a query only scans the columns you specify. All other columns are pruned from consideration.

As an example, a table using columnar storage could have one hundred columns, with only a small handful of those high-cardinality columns. By minimizing the number of columns retrieved, users can often avoid querying high-cardinality columns altogether. And even if it’s necessary to query one or more high-cardinality columns, users will still avoid compute-intensive full table scans.

Data Transformation, Cleaning, and Standardizing

Where possible, data engineers should reduce the cardinality of their data. For some databases that have challenges handling very large volumes of data, teams might be forced into anti-practices like downsampling data (reducing its granularity) or discarding data altogether. But there are much better practices that don’t lead to data loss, and they typically involve cleaning and standardizing data.

For example, in the case of log data, it’s typical to have a data transformation process before data goes into storage (this is known as ETL, for extract—transform—load). This transformation process can help reduce cardinality through techniques like standardized naming conventions and data cleaning.

Even something as simple as removing additional whitespaces and making the case of strings (whether they are capitalized or not) consistent can reduce the number of possible permutations of a string. The diagram below shows an example for a potential “occupation” attribute.

In this example, five different strings are formatted slightly differently. By standardizing them all to lowercase and removing extra whitespaces, the cardinality for this particular occupation is reduced from five to one. Standardizing data in this way also makes it easier to query and analyze.

In addition to ETL processes, data lakes in particular use ELT processes (for extract—load—transform) which clean and process data after it is stored. These processes can reduce cardinality further.

Learn about the differences between ETL and ELT.

Cardinality Analysis (Understanding the Data)

Teams should perform cardinality analysis to get a better understanding of their data, including which columns have high cardinality. High-cardinality columns can then be further analyzed for optimizations. These could include reducing cardinality (by cleaning and standardizing it more) or even modifying the data type to improve performance.

For example, this blog post by an engineer on Hydrolix’s core team discusses cardinality analysis on a client IP column that stored more than 185 million unique IP addresses. IP addresses are typically stored as strings, and converting them to integers dramatically reduces the total amount of space the column takes in storage.

This is a small but mighty optimization because IP address columns are high cardinality, and it’s a very common attribute in log data.

High-cardinality columns are worthy of additional analysis because even small optimizations can lead to big improvements in performance and a reduced storage footprint.

Eliminating Storage Redundancy and Using Cost-Effective Storage

High-cardinality data can take up a lot of space in storage, especially for columns where compression isn’t optimal. And when it comes to big data, these columns can take a gargantuan amount of space, quickly leading to high costs.

Some databases are poorly suited to handle these volumes of data, in large part due to the following reasons:

• Expensive storage: For example, local block storage is much more expensive than distributed object storage, and these costs quickly add up for high-cardinality data.
• Replicas: Backing up data is important, but some data solutions (such as Elasticsearch) rely on replicas—copies of database clusters—to ensure durability and resiliency. This is extremely expensive for high-cardinality data.
• Denormalization: Denormalization involves copying different slices of data to new tables. While this can improve performance for specialized queries (and can sometimes even be a good practice for avoiding queries to high-cardinality columns), denormalized tables can be a headache to maintain and bloat storage costs further.

The solution to this problem of storage costs? Some modern databases are finding ways to maximize the performance of cloud-based object storage, which is much more cost-effective than block storage. Even better, cloud providers guarantee the resiliency of their object storage, making replicas unnecessary.

These are just a few of the ways that engineers and databases can effectively work with high-cardinality data. And Hydrolix’s engineering team (and customers) are always finding new ways to improve performance and reduce costs further.

Next Steps

Learn more about Hydrolix, a platform for ingesting, transforming, storing, and analyzing high volumes of log data, including high-cardinality data.