Run-length encoding (RLE) is a simple but powerful data compression technique that’s useful for a wide range of use cases from image compression to log data. It’s especially effective for columnar databases that have many repeated values.
In this guide, you’ll learn all the basics of RLE including:
- What is run-length encoding?
- How to improve the performance of run-length encoding
- Use cases for run-length encoding
- Benefits of run-length encoding
- Disadvantages of Run-Length Encoding
What Is Run-Length Encoding (RLE)?
RLE is a method for efficiently encoding runs of consecutive identical values. It is a lossless compression algorithm, which means all of the original data is retained. This is in contrast to lossy compression algorithms where some of the original data is permanently removed during the compression process.
It’s especially useful with data that has many repeated values, while it’s less effective for data that has a high degree of cardinality (many unique values).
Let’s take a look at an example of RLE.
In this example, the number 200 is repeated eight times. Why the number 200 in this example? 200 is an HTTP status code that means that a request was successful, and you’ll see this value frequently in log data.
| | | | | | | | |
| — | — | — | — | — | — | — | — |
| 200 | 200 | 200 | 200 | 200 | 200 | 200 | 200 |
This is an inefficient way to represent this repeated data. The number 200 takes 8 bits in binary. Since it’s repeated 8 times, the total amount of space this run will take is 64 bits.
With run-length encoding, we can represent this run with just two values.
| | |
| — | — |
| 8 | 200 |
The first value is the total number of occurrences in the run. The number 8 takes 4 bits to represent.
The second number is the value of the repeated data, in this case 200.
With run-length encoding, it takes a total of 12 bits (4 + 8) to represent the sequence, a compression rate over 5x.
This is a very simplistic example, but it shows just how effective run-length encoding can be for repeated values.
Improving the Performance of Run-Length Encoding
In the real world, data is often messy and complex. It may have many repeated values (low cardinality), but they may not occur in runs. Fortunately, there are many methods for improving the performance of run-length encoding, including sorting, finding longer patterns of runs, and compressing deltas.
Let’s take a closer look at a few of these methods.
Sorting for Longer Runs
Let’s take a look at another example. This one mixes the values 200 (HTTP success code) and 404 (HTTP page not found code).
| | | | | | | | |
| — | — | — | — | — | — | — | — |
| 200 | 200 | 404 | 200 | 404 | 200 | 404 | 404 |
With each instance of 200 taking 8 bits and each instance of 404 taking 9 bits, this takes 68 bits to represent.
Representing this as-is with run-length encoding isn’t very efficient:
| | | | | | | | | | | | |
| — | — | — | — | — | — | — | — | — | — | — | — |
| 2 | 200 | 1 | 404 | 1 | 200 | 1 | 404 | 1 | 200 | 2 | 404 |
This is a total of 58 bits—not much improvement over the original!
Instead, we can first sort the data to produce longer runs. Sorted, the data looks like this:
| | | | | | | | |
| — | — | — | — | — | — | — | — |
| 200 | 200 | 200 | 200 | 404 | 404 | 404 | 404 |
Now we can represent this much more efficiently with run-length encoding:
| | | | |
| — | — | — | — |
| 4 | 200 | 4 | 404 |
The number 4 is 3 bits, so the total space this information takes is now 23 bits (3 + 8 + 3 + 9). With sorting, the compression rate is much improved, with a 3x compression rate over the original.
When sorting data, you need to think about how you’ll maintain the integrity of the data if the original ordering is important.
Run-Length Encoding with Longer Patterns
Run-length encoding can also be used for longer patterns in data as well. Here’s a simple example.
| | | | | | | | | |
| — | — | — | — | — | — | — | — | — |
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
If we first apply sorting and then run-length encoding, we get the following:
| | | | | | |
| — | — | — | — | — | — |
| 3 | 1 | 3 | 2 | 3 | 3 |
Instead, we could use run-length encoding on the pattern “123” to save more space—no sorting required. The following is much more efficient!
| | |
| — | — |
| 3 | 123 |
Combining Run-Length Encoding with Delta Encoding
RLE can also be combined with other encoding techniques. There are too many to go in this guide, but let’s look at one example: delta encoding.
With delta encoding, you look at the difference, or delta, between each consecutive value. The first value is the starting value, but then each subsequent value is represented as the delta of the previous value. This is easier to understand with an example.
Run-length encoding wouldn’t be very effective with the following sequence of sorted numbers since they are mostly different.
| | | | | | | | |
| — | — | — | — | — | — | — | — |
| 2 | 3 | 4 | 5 | 5 | 6 | 7 | 8 |
But we can instead use delta encoding to portray this information instead:
| | | | | | | | |
| — | — | — | — | — | — | — | — |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
The starting value is 2. The second value is 1 greater than the previous value, so the delta is 1. The third value is 1 greater than the second value, so the delta between the second and third value is 1. And so on.
Now we can use RLE to compress the longer runs (in this case, 2 separate runs with 3 instances of the value 1).
Delta encoding is effective when there is a small amount of variation between the different values in a dataset.
Use Cases for Run-Length Encoding
Run-length encoding is extremely useful for datasets that have low cardinality. Low cardinality datasets have many repeated values. This is in contrast to high cardinality datasets, which have many unique values.
Datasets with many unique values won’t have many runs, so run-length encoding isn’t as helpful, and can even make the size of the dataset bigger instead of compressing it.
Let’s take a look at some use cases where run-length encoding is especially effective.
Log Data in Columnar Storage
One of the most powerful real-world use cases for run-length encoding is log data. Log data is typically stored in OLAP-style, columnar datastores that are optimized for compression and query performance.
With columnar data stores, data is stored in columns instead of rows. Imagine expanding the status code example from earlier with millions or even billions of data points. There are only 63 commonly-used status codes with 200 status codes typically being the most common in a database table. In a column with billions of status codes, you can achieve very high rates of compression.
Here are just a few examples of common log data fields that will have a high degree of repeatability:
- Country (or country code)
- Web browser and user agent (collecting end user data)
- Edge location (for CDN data)
- Request method (most will be GET or POST)
- Protocol type (such as HTTPS)
- Service (the service that generated the log data)
- Log status code (typically a numerical value to denote the severity of a log)
Of course, there are many fields in log data that won’t benefit from run-length encoding. Examples include specific IDs and IP addresses.
Run-length encoding should only be used on columns that benefit from it. Some columnar data stores like Hydrolix can apply specialized algorithms to different columns to maximize the benefits of compression. This can include applying techniques like run-length encoding only to specific columns.
Internet of Things (IoT) and Sensor Data
Many kinds of sensor data can have low variability, making the data perfect for run-length encoding. For example, consider a thermostat reading for a server room which should typically be in between 68 and 71 degrees Fahrenheit. The majority of readings should be in that range, leading to long runs that can be highly compressed with RLE.
Here are just a few examples of sensors that can have consistent readings over time:
- Motion sensors (may have long periods of time where no motion is detected)
- Light sensors (consistent readings of high or low light depending on time of day or night)
- Pressure sensors (where pressure must remain consistent)
Time Series Data
Time series data consists of data that’s ordered chronologically. It’s used for detecting patterns and trends over time and has many use cases from tracking weather to financial markets. Sensor data can also be depicted as a time series. Just as with sensor data, some time series data (but not all) will have low variability and many runs, making run-length encoding a viable option for compression.
Graphics Compression
Run-length encoding can be useful for many kinds of graphical compression, including images, some video, and even retro video games.
- Images with large uniform regions
- Video with high degrees of repeatability (such as surveillance video that has very few changes)
- Retro video games with limited color palettes
Benefits of Run-Length Encoding
There are multiple benefits of RLE, and they extend beyond compressing your data. Let’s take a closer look.
- High rates of compression: RLE can achieve high rates of compression for data that has low cardinality such as certain kinds of log data.
- Fast compression and decompression: Data compression often comes with a tradeoff—the amount of time it takes to compress and decompress. Some compression algorithms are slower, making them less ideal for real-time use cases. RLE is fast for low cardinality data, making it an effective compression algorithm for use cases where fast data retrieval is required.
- Simple to implement: RLE is an easy compression algorithm to implement and manage compared to other algorithms, especially ones that involve managing dictionaries, trees, and more complex data structures.
- Reduced storage footprint and costs: Compression has a number of end user benefits, including a dramatically lower storage footprint which in turn reduces storage costs.
- Faster data transfer over distributed networks: Solutions like Hydrolix which use distributed cloud storage transfer compressed data much more quickly simply because there is a smaller volume of data to transmit. As a result, RLE benefits both write (data ingest) and read (query) performance for low cardinality datasets.
Learn more about the benefits of compression for big data use cases.
Disadvantages of Run-Length Encoding
RLE is a simple algorithm, and it’s not nearly as flexible or sophisticated as compression algorithms such as LZ77, DEFLATE, or Huffman coding, which typically achieve better compression ratios across a range of different types of data.
Here are some of the disadvantages:
- Poor compression when data doesn’t repeat: Not surprisingly, compression is poor if there aren’t long runs of repeated values.
- Worst-case expansion: In the worst-case scenario, where values are all unique, the size of the data will actually be doubled in size because each unique value will be paired with the length of its “run” (1).
- Count errors can break encryption: Imagine that the first count in the field is off by one. This will break every single value in the field, making RLE brittle if there are any errors.
Despite its advantages, RLE still can still be an integral part of more complex compression algorithms, especially for use cases like log data where there can be many repeated values.
How Hydrolix Uses Run-Length Encoding
Run-length encoding is just one of many compression algorithms that Hydrolix uses to achieve 90%+ compression on large volumes of log data. Tables in Hydrolix consist of billions of rows, and because Hydrolix uses columnar storage, each of these columns can be compressed individually using specialized algorithms.
As discussed in the previous section on log data in columnar storage, many log data columns such as HTTP status code and request method can achieve high rates of compression because they are low cardinality. And this is in part because Hydrolix combines sorting and run-length encoding for these columns.
- Learn more about how Hydrolix compresses data using algorithms such as run-length encoding.
- Read about an engineering approach for high cardinality data that couldn’t be highly compressed, which includes a discussion of run-length encoding.
