One Billion Row Challenge - Part One: DuckDB
In part one, I'm going to explain the One Billion Row Challenge, then provide a solution using DuckDB and SQL.
A while ago, a friend of mine asked me, “Have you seen the One Billion Row Challenge?” I had no idea what it was. He’s a Free Pascal fan, so he sent me a link to the GitHub repository where the community challenge was running. So I started thinking about implementing a solution in several programming languages and comparing implementation complexity, syntax clarity, compiler optimizations, output size, etc. In this article, I’m going to explain the challenge first and then provide a solution using DuckDB and SQL.
What is the One Billion Row Challenge (AKA 1BRC)?#
There are many variations of the challenge on the internet. In this section, I’m going to explain the original challenge, but to keep it more challenging, I will use the ObjectPascal version from here on.
As far as I know, the 1BRC was started by Gunnar Morling in 2024 as a Java competition. However, it quickly evolved into a challenge for finding the absolute limits of modern hardware, and spread to many programming languages. The challenge is very simple: the input is a semicolon-separated text file where each line contains a weather station name and a floating-point temperature with one decimal place. Your program has to calculate min, mean and max temperature per station, sort the stations alphabetically, then print the result to stdout.
The hard part of the challenge is the dataset size. The dataset contains one billion rows and its size is around 13 gigabytes (for the original challenge). So generic code might take minutes to solve the problem, but with specific code and modern technologies like parallel programming, SIMD coding, asynchronous I/O and so on, it can be solved in seconds instead.
How do you get the dataset file?#
Actually, the dataset file isn’t downloadable, and it’s on you to generate the dataset. The competition organizer provides an application that is responsible for generating the dataset. For example, you can take a look at the generator entry point for the Java competition version, or the ObjectPascal version. Sometimes the generator’s output and the dataset’s criteria might differ from one organizer to another, so you should be aware of the rules that lead to the results. For example, the ObjectPascal version uses around 40K stations while the original dataset generator only generate 413 stations, though, the rules permit 10K.
Personally, I prefer the ObjectPascal version, since it is harder to solve, needs more complex algorithms, prevents developers from using dataset-specific tricks and is more like a real life challenge than the original one.
The dataset criteria#
The dataset has one billion rows in a Delimiter-Separated Values (DSV) format where the delimiter is a semicolon. The dataset is 14.7 GiB and contains 41,343 unique station names. It has two columns: the first column is the station name and the second column is the temperature.
The station name lengths are between 2 and 49 characters (See this).
SELECT max(length(column0)), min(length(column0)) FROM 'weather_stations.csv';The temperature values might be negative, have exactly one decimal place and range between -99.9 and 99.9, so the length of the temperature values is between 3 and 5 characters (See this).
SELECT max(length(column1)), min(length(column1)) FROM read_csv('OBD.csv', columns = {'column0': 'VARCHAR', 'column1': 'VARCHAR'});Generate the dataset#
To generate the dataset, you can clone 1brc-ObjectPascal and build the generator project with Lazarus IDE, then follow the tutorial to generate the dataset. However to make it easier I built the generator, so you can download it from SwitchCase GitHub Releases.
The 1brc-ObjectPascal README explains the generator parameters, so I’ll skip it and go straight to generating the dataset.
Okay, let’s actually generate the dataset. If you download the generator from SwitchCase GitHub Releases, there are two files: generator.exe and weather_stations.csv. The generator command shows how you can generate the one-billion-row dataset. By changing the –line-count or -n parameter, you can generate a smaller dataset for testing purposes.
.\generator -i weather_stations.csv -o OBD.csv -n 1_000_000_000The command output should look like the snippet below.
PS C:\> .\generator -i weather_stations.csv -o OBD.csv -n 1_000_000_000
Input Filename: "C:\weather_stations.csv"
Output Filename: "C:\OBD.csv"
Line Count: 1,000,000,000
Building Weather Stations...
Done: Processed 44,691 entries from a total of 41,343 weather stations in 125 ms
[##################################################] 100.00 % lines: 1,000,000,000, file size: 15,847,913,227, elapsed: 0 min, 20 sec
Done: file size: 15,847,913,227, elapsed: 0 min, 20 secThe DuckDB Solution#
The DuckDB CLI installation is documented in detail at DuckDB Command Line Client. Reading a CSV file using DuckDB is also documented at DuckDB CSV Import. So I’m going straight to the solution.
To solve the challenge, we should follow the steps below:
- Read the CSV file.
- Group stations by name.
- Calculate minimum, maximum and mean per group.
- Sort the result by station name.
SELECT column0, min(column1), max(column1), mean(column1)::DECIMAL(3, 1) FROM 'OBD.csv' ORDER BY column0 ORDER BY column0;The query is self-explanatory except for the casting to DECIMAL. The DECIMAL casting accepts two parameters: precision and scale. Precision defines the total number of digits and scale defines the number of digits after the decimal point.
┌──────────────────┬──────────────┬──────────────┬──────────────────────────────────────┐
│ column0 │ min(column1) │ max(column1) │ CAST(mean(column1) AS DECIMAL(3, 1)) │
│ varchar │ double │ double │ decimal(3,1) │
├──────────────────┼──────────────┼──────────────┼──────────────────────────────────────┤
│ A Coruña │ 28.4 │ 74.7 │ 51.5 │
│ A Yun Pa │ -31.2 │ 18.7 │ -6.2 │
│ Aabenraa │ -11.3 │ 51.4 │ 20.1 │
│ Aachen │ 0.5 │ 76.9 │ 38.9 │
│ Aadorf │ -70.0 │ -24.0 │ -46.9 │
│ Aalborg │ 4.0 │ 58.8 │ 31.5 │
│ Aalen │ 40.4 │ 82.5 │ 61.3 │
│ Aaley │ -71.7 │ 11.9 │ -29.8 │
│ Aalsmeer │ -49.4 │ 35.1 │ -7.2 │
│ Aalst │ -41.1 │ 38.7 │ -1.5 │
│ Aalten │ 39.2 │ 95.6 │ 67.3 │
│ Aarau │ -74.9 │ -37.8 │ -56.4 │
│ Aarhus │ -13.2 │ 28.5 │ 7.5 │
│ Aarschot │ -86.6 │ -34.8 │ -60.7 │
│ Aarsâl │ 5.5 │ 85.9 │ 45.7 │
│ Aartselaar │ 0.4 │ 69.4 │ 34.9 │
│ Aasiaat │ 18.6 │ 65.3 │ 42.0 │
│ Aba │ -33.9 │ 20.8 │ -6.4 │
│ Abadan │ -24.1 │ 31.4 │ 3.6 │
│ Abadiânia │ -37.5 │ 30.5 │ -3.6 │
│ · │ · │ · │ · │
│ · │ · │ · │ · │
│ · │ · │ · │ · │
│ ‘Ibrī │ -75.7 │ -24.9 │ -50.3 │
│ ‘Izbat al Burj │ -17.5 │ 64.5 │ 23.5 │
│ ‘Unayzah │ 14.0 │ 98.5 │ 56.2 │
│ ‘Utaybah │ 53.9 │ 90.4 │ 72.1 │
│ ‘Ālī Shahr │ 16.1 │ 77.1 │ 46.6 │
│ ‘Āmūdā │ -85.2 │ -30.9 │ -58.1 │
│ ’Ali Ben Sliman │ 40.4 │ 91.9 │ 66.0 │
│ ’Ayn Bni Mathar │ -86.9 │ -25.2 │ -56.0 │
│ ’Aïn Abessa │ -27.4 │ 29.2 │ 0.7 │
│ ’Aïn Abid │ -3.1 │ 38.9 │ 17.8 │
│ ’Aïn Arnat │ -66.0 │ 15.9 │ -25.3 │
│ ’Aïn Azel │ 45.0 │ 95.0 │ 70.0 │
│ ’Aïn Leuh │ -91.4 │ -51.6 │ -71.4 │
│ ’Aïn Roua │ -54.3 │ -8.3 │ -31.2 │
│ ’Aïn el Hammam │ -81.4 │ -7.4 │ -44.1 │
│ ’Tlat Bni Oukil │ 41.7 │ 88.0 │ 64.7 │
│ ’s-Gravendeel │ -17.0 │ 42.0 │ 12.5 │
│ ’s-Gravenzande │ -99.0 │ -34.6 │ -66.7 │
│ ’s-Heerenberg │ 23.0 │ 60.6 │ 41.8 │
│ ’s-Hertogenbosch │ -78.3 │ -1.1 │ -39.8 │
└──────────────────┴──────────────┴──────────────┴──────────────────────────────────────┘
41343 rows (40 shown) use .last to show entire result 4 columns
Run Time (s): real 27.036 user 357.531250 sys 26.890625There are three problems with the query result:
- The result shows a table instead of the output format the challenge wants. I’m going to keep the result as a table for readability.
- The floating-point addition is not accurate, so summing temperatures across one billion rows accumulates float drift.
- The DuckDB floating-point rounding is different from FreePascal.
To fix the accumulating float drift, I’m going to convert the floating-point values to integers by multiplying them by ten, since the temperatures have just one decimal place. The FreePascal baseline implementation uses ceiling for the floating-point rounding. The following snippet shows the query that fixes the last two problems.
WITH src AS ( SELECT column0 AS station, column1 AS temp, (column1 * 10)::BIGINT AS tenths FROM 'OBD.csv' ),
agg AS ( SELECT station, min(temp) AS mn, max(temp) AS mx, sum(tenths) AS tot, count(*) AS cnt FROM src ORDER BY station ),
fmt AS ( SELECT station, mn, ceil((tot::DOUBLE / cnt / 10) * 10)::BIGINT / 10.0 AS me, mx FROM agg )
SELECT * FROM fmt ORDER BY station;┌──────────────────┬────────┬────────┬────────┐
│ station │ mn │ me │ mx │
│ varchar │ double │ double │ double │
├──────────────────┼────────┼────────┼────────┤
│ A Coruña │ 28.4 │ 51.5 │ 74.7 │
│ A Yun Pa │ -31.2 │ -6.2 │ 18.7 │
│ Aabenraa │ -11.3 │ 20.2 │ 51.4 │
│ Aachen │ 0.5 │ 38.9 │ 76.9 │
│ Aadorf │ -70.0 │ -46.9 │ -24.0 │
│ Aalborg │ 4.0 │ 31.5 │ 58.8 │
│ Aalen │ 40.4 │ 61.4 │ 82.5 │
│ Aaley │ -71.7 │ -29.8 │ 11.9 │
│ Aalsmeer │ -49.4 │ -7.1 │ 35.1 │
│ Aalst │ -41.1 │ -1.5 │ 38.7 │
│ Aalten │ 39.2 │ 67.3 │ 95.6 │
│ Aarau │ -74.9 │ -56.3 │ -37.8 │
│ Aarhus │ -13.2 │ 7.6 │ 28.5 │
│ Aarschot │ -86.6 │ -60.6 │ -34.8 │
│ Aarsâl │ 5.5 │ 45.7 │ 85.9 │
│ Aartselaar │ 0.4 │ 34.9 │ 69.4 │
│ Aasiaat │ 18.6 │ 42.0 │ 65.3 │
│ Aba │ -33.9 │ -6.3 │ 20.8 │
│ Abadan │ -24.1 │ 3.6 │ 31.4 │
│ Abadiânia │ -37.5 │ -3.5 │ 30.5 │
│ · │ · │ · │ · │
│ · │ · │ · │ · │
│ · │ · │ · │ · │
│ ‘Ibrī │ -75.7 │ -50.3 │ -24.9 │
│ ‘Izbat al Burj │ -17.5 │ 23.6 │ 64.5 │
│ ‘Unayzah │ 14.0 │ 56.2 │ 98.5 │
│ ‘Utaybah │ 53.9 │ 72.2 │ 90.4 │
│ ‘Ālī Shahr │ 16.1 │ 46.6 │ 77.1 │
│ ‘Āmūdā │ -85.2 │ -58.1 │ -30.9 │
│ ’Ali Ben Sliman │ 40.4 │ 66.1 │ 91.9 │
│ ’Ayn Bni Mathar │ -86.9 │ -55.9 │ -25.2 │
│ ’Aïn Abessa │ -27.4 │ 0.8 │ 29.2 │
│ ’Aïn Abid │ -3.1 │ 17.9 │ 38.9 │
│ ’Aïn Arnat │ -66.0 │ -25.2 │ 15.9 │
│ ’Aïn Azel │ 45.0 │ 70.1 │ 95.0 │
│ ’Aïn Leuh │ -91.4 │ -71.3 │ -51.6 │
│ ’Aïn Roua │ -54.3 │ -31.2 │ -8.3 │
│ ’Aïn el Hammam │ -81.4 │ -44.0 │ -7.4 │
│ ’Tlat Bni Oukil │ 41.7 │ 64.7 │ 88.0 │
│ ’s-Gravendeel │ -17.0 │ 12.6 │ 42.0 │
│ ’s-Gravenzande │ -99.0 │ -66.6 │ -34.6 │
│ ’s-Heerenberg │ 23.0 │ 41.8 │ 60.6 │
│ ’s-Hertogenbosch │ -78.3 │ -39.7 │ -1.1 │
└──────────────────┴────────┴────────┴────────┘
41343 rows (40 shown) 4 columns
Run Time (s): real 32.290 user 394.984375 sys 26.125000If you want to generate the output the challenge expects, you can concatenate columns and generate a single-column, single-row result (see the snippet below).
WITH src AS ( SELECT column0 AS station, column1 AS temp, (column1 * 10)::BIGINT AS tenths FROM 'OBD.csv' ),
agg AS ( SELECT station, min(temp) AS mn, max(temp) AS mx, sum(tenths) AS tot, count(*) AS cnt FROM src ORDER BY station ),
fmt AS ( SELECT station, mn, ceil((tot::DOUBLE / cnt / 10) * 10)::BIGINT / 10.0 AS me, mx FROM agg )
SELECT '{' || string_agg(station || '=' || mn || '/' || me || '/' || mx,
', ' ORDER BY station) || '}'
FROM fmt;What’s coming next?#
This is the first in a series of articles. I’m going to implement solutions in Rust, C++ and other programming languages, then I will write a conclusion article to summarize the results and give my opinions on the languages and implementations.
▸ stay subscribed
Liked this?
Drop your email and you'll get the next post when it's published. No tracking, one-click unsubscribe.