{"article":{"slug":"rows-vs-columns-how-different-are-they-really","title":"Rows vs Columns: How different are they, really?","subtitle":null,"summary":"Connor Tsui of Spiral explains how storing structured data in columns rather than rows changes how a database system works, covering row versus column stores, vectorized execution and lightweight compression, using a bike-share rides dataset as a running example.","content_type":"tutorial","language":"en","canonical_url":"https://spiraldb.com/blog/rows-vs-columns","author":{"name":"Connor Tsui","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Spiral","url":"https://spiraldb.com/","listing_slug":null,"listing":null},"topics":[{"name":"databases","slug":"databases","url":"https://listedarticles.com/topics/databases"},{"name":"data-engineering","slug":"data-engineering","url":"https://listedarticles.com/topics/data-engineering"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":5116,"reading_minutes":22,"published_at":"2026-11-11T12:00:00.000Z","added_at":"2026-11-17T13:53:05.723Z","updated_at":"2026-11-17T13:53:05.723Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/rows-vs-columns-how-different-are-they-really","markdown_url":"https://listedarticles.com/articles/rows-vs-columns-how-different-are-they-really.md","example":false,"citation":"Connor Tsui, Spiral. \"Rows vs Columns: How different are they, really?.\" 11 Nov 2026. https://spiraldb.com/blog/rows-vs-columns (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://spiraldb.com/blog/rows-vs-columns"},"body_markdown":"When we think about structured data, we generally think in terms of rows.\nTake this simple CSV file, which records some data about bike rides on a\nbike-sharing app in New York City:\n\nCSV\n\n```\nride_id, started_at,        start_area,         bike_type, duration_min\n   1001, 2026-11-02 07:58,  Tribeca,            classic,             14\n   1002, 2026-11-02 08:01,  Financial District, electric,             6\n   1003, 2026-11-02 08:01,  SoHo,               classic,             21\n   1004, 2026-11-02 08:03,  Financial District, electric,             8\n   1005, 2026-11-02 08:04,  Financial District, classic,             15\n   1006, 2026-11-02 08:07,  Tribeca,            electric,             1\n   1007, 2026-11-02 08:08,  Tribeca,            electric,             9\n   1008, 2026-11-02 08:12,  Financial District, classic,             31\n```\n\nData in this CSV file is organized into rows, where each row corresponds to a\n*record* of data. Each record here is one ride, or one \"thing\", with everything\nwe know about it on one line. We tend to organize data like this almost\neverywhere: think of spreadsheets, JSON objects, C-style structs in an array,\nSQL tables, etc. This is because it matches how we think: one \"thing\", and all\nof the details of that \"thing\".\n\nThis way of thinking fits a lot of the software we write. When you log in to an\napp, post a comment on a video, add an item to a shopping cart, send a bank\ntransfer, or book a ride, the application will change just one record (or a few,\nat most). So it makes sense that the databases behind this software, like\nPostgres and MySQL, \"think in\" (or are modeled around) rows as well: they keep\neach record's details together, so finding, updating, or creating a record means\ngoing to one place.\n\nBut not everything we ask of a database is limited to one record.\n\nIf you run the bike-share service that produced the CSV file above, you'll\neventually want to learn something from all the data it collects. This kind of\nwork is called *analytics*. For example, which neighborhood is busiest on Monday\nand Friday mornings? Do people take longer rides on electric bikes than on\nclassic ones? Observe how no single record can answer these questions. The\nanswers come from the dataset as a whole, so the only way to get them is to look\nat *all* of the records.[1](#user-content-fn-index)\n\nNotice what these questions don't need, however. Finding the busiest\nneighborhood only needs the `start_area` and `started_at` columns, and comparing\nbike types only needs `bike_type` and `duration_min`. Each question may have to\nlook at every row, but it only needs a few of the columns from each one. And a\ndatabase that keeps each record's details together can't take advantage of that:\nto read two columns, it has to read all five. We may *think* in rows, but to\nanswer questions like these quickly, we have to program in columns.\n\nProgramming in columns begins with how the data is stored, but that's only the\nstart. Once data is stored by column, the way a database runs a query changes\ndramatically: how much data it reads, how many values it handles at a time, how\nmany values the CPU can process with one instruction, how well the data\ncompresses, etc.\n\nThis post will go over these changes, and by the end, you'll see just how much\nfollows from the \"simple\" choice to store columns instead of rows.\n\n## [#Row stores and column stores](#row-stores-and-column-stores)\n\nLet's start with what *doesn't* change. Whether a database stores rows or\ncolumns, the table it shows you when you do `SELECT * FROM rides;` is the same.\nYou create it with the same SQL, you query it with the same SQL, and you get the\nsame answers. We can say that the two tables are logically equivalent.\n\nSQL\n\n```\nCREATE TABLE rides (\n    ride_id      BIGINT,\n    started_at   TIMESTAMP,\n    start_area   TEXT,\n    bike_type    TEXT,\n    duration_min INTEGER\n);\n\nSELECT * FROM rides WHERE ride_id = 1004;\n\nSELECT AVG(duration_min) FROM rides;\n```\n\nRows vs columns is a physical distinction rather than a logical one: the\ndata *represents* the same thing, but how that data is actually *arranged* in\nmemory and on disk is different.\n\nRow store\n\nride\\_id\n\nstarted\\_at\n\nstart\\_area\n\nbike\\_type\n\nduration\\_min\n\n1001\n\n07:58\n\nTribeca\n\nclassic\n\n14\n\n1002\n\n08:01\n\nFinancial District\n\nelectric\n\n6\n\n1003\n\n08:01\n\nSoHo\n\nclassic\n\n21\n\n1004\n\n08:03\n\nFinancial District\n\nelectric\n\n8\n\nColumn store\n\nride\\_id\n\n1001\n\n1002\n\n1003\n\n1004\n\nstarted\\_at\n\n07:58\n\n08:01\n\n08:01\n\n08:03\n\nstart\\_area\n\nTribeca\n\nFinancial District\n\nSoHo\n\nFinancial District\n\nbike\\_type\n\nclassic\n\nelectric\n\nclassic\n\nelectric\n\nduration\\_min\n\n14\n\n6\n\n21\n\n8\n\nDatabases are named after the grouping they choose. A row store keeps each\nrecord's values next to each other, just like the CSV we started with. Postgres\nand MySQL, which we mentioned before, are both row stores. They're built for the\nsmall reads and writes behind an application, which is called *online\ntransaction processing* (OLTP).[2](#user-content-fn-oltp)\n\nA column store does the opposite: it takes every record apart and keeps each\ncolumn's values next to each other instead.[3](#user-content-fn-dsm) DuckDB and ClickHouse are\nexamples of column stores. They're built for analytics, which is called *online\nanalytical processing* (OLAP).[4](#user-content-fn-olap)\n\n### [#Rows and columns in memory](#rows-and-columns-in-memory)\n\nTo make this concrete, imagine that we have to hold our rides in memory\nourselves. This isn't how a real database would be implemented, but it's a good\napproximation of how each kind arranges its data. In Rust, a row store would be\na `Vec` of structs:\n\nRust\n\n```\nstruct Ride {\n    ride_id: u64,\n    started_at: Timestamp,\n    start_area: String,\n    bike_type: BikeType,\n    duration_min: u32,\n}\n\ntype Rows = Vec<Ride>;\n```\n\nA column store will have the same fields, but it will look like a struct of\n`Vec`s:\n\nRust\n\n```\nstruct Columns {\n    ride_id: Vec<u64>,\n    started_at: Vec<Timestamp>,\n    start_area: Vec<String>,\n    bike_type: Vec<BikeType>,\n    duration_min: Vec<u32>,\n}\n```\n\nHere is what these data layouts look like side by side:\n\nRows\n\nrides[0]\n\n1001\n\n07:58\n\nTribeca\n\nclassic\n\n14\n\nrides[1]\n\n1002\n\n08:01\n\nFinancial District\n\nelectric\n\n6\n\nrides[2]\n\n1003\n\n08:01\n\nSoHo\n\nclassic\n\n21\n\nrides[3]\n\n1004\n\n08:03\n\nFinancial District\n\nelectric\n\n8\n\nColumns\n\nride\\_id\n\n1001\n\n1002\n\n1003\n\n1004\n\nstarted\\_at\n\n07:58\n\n08:01\n\n08:01\n\n08:03\n\nstart\\_area\n\nTribeca\n\nFinancial District\n\nSoHo\n\nFinancial District\n\nbike\\_type\n\nclassic\n\nelectric\n\nclassic\n\nelectric\n\nduration\\_min\n\n14\n\n6\n\n21\n\n8\n\nBoth of these forms represent the same logical values, but their layout is\ndramatically different.\n\n### [#Reading only the columns you need](#reading-only-the-columns-you-need)\n\nLet's do a fun exercise.[5](#user-content-fn-fun) These are the two SQL queries shown above. Which\nlayout is better for executing each of them?\n\nSQL\n\n```\nSELECT AVG(duration_min) FROM rides;\n\nSELECT * FROM rides WHERE ride_id = 1004;\n```\n\nFor the `AVG` query, computing it requires only the `duration_min` of every ride\nand nothing else. In the `Columns` layout, values are stored together in a\nsingle `Vec<u32>`, so the query can scan that one array without touching the\nother four. For `Vec<Ride>` (the `Rows` layout), there is simply no way to read\nonly the durations. Each duration is stored within a `Ride`, so the query\nhas to read through every `Ride` and pass over the other four fields every time.\n\nNote that the code can \"ignore\" those other fields, but the hardware cannot. A\nCPU doesn't fetch memory one value at a time: it will fetch fixed-size blocks\ncalled *cache lines* (which are 64 bytes on most machines[6](#user-content-fn-cache-line)),\nfetching the whole line even when the program needs only a few bytes of it. A\n`Ride` is 48 bytes[7](#user-content-fn-ride-size) and `duration_min` is only 4 of them, so with the\nrow layout, we have to fetch all 48 bytes to read those 4, which is 12x the\namount that we actually need. The CPU can't skip any of these lines either\nbecause a `Ride` is smaller than a cache line, so every cache line of the array\nhas a duration somewhere in it.\n\nSELECT AVG(duration\\_min) FROM rides;\n\nused\n\nloaded, not used\n\nnot loaded\n\nRows\n\n1 cache line = 64 bytes\n\n14\n\n6\n\n21\n\n8\n\n15\n\n1\n\n9\n\n31\n\n6cache lines loaded\n\n32 of 384 bytes used\n\nColumns\n\nride\\_id\n\nstarted\\_at\n\nstart\\_area\n\nbike\\_type\n\nduration\\_min\n\n14\n\n6\n\n21\n\n8\n\n15\n\n1\n\n9\n\n31\n\n(room for 8 more)\n\n1cache line loaded\n\n32 of 64 bytes used\n\nThis diagram only shows 8 rides for simplicity (which is why the `duration_min`\nline is half empty), but the factor of 12 doesn't depend on the size of the\ntable. With one million rides, we might be fetching 48 MB vs 4 MB.\n\nThe second query goes the other way. `SELECT * FROM rides WHERE ride_id = 1004`\nwants *every* field of a single ride, not just one. Once the database finds the\nrecord with that ride (probably via an index[8](#user-content-fn-lookup-index)), `Vec<Ride>` has\nall of its fields next to each other, so reading all of them touches only one or\ntwo cache lines (it might overlap two cache lines).[9](#user-content-fn-string-text) On the other\nhand, `Columns` has spread the same ride over five different arrays, so the\nquery has to fetch at least five cache lines to put it back together. For this\nquery, the `Rows` layout wins.\n\nSELECT \\* FROM rides WHERE ride\\_id = 1004;\n\nused\n\nloaded, not used\n\nnot loaded\n\nRows\n\n1 cache line = 64 bytes\n\n1004\n\n08:03\n\nFinancial District\n\nelectric\n\n8\n\n1cache line loaded\n\n48 of 64 bytes used\n\nColumns\n\nride\\_id\n\n1004\n\nstarted\\_at\n\n08:03\n\nstart\\_area\n\nFinancial District\n\nbike\\_type\n\nelectric\n\n(room for 56 more)\n\nduration\\_min\n\n8\n\n(room for 8 more)\n\n5cache lines loaded\n\n45 of 320 bytes used\n\nNow that we have a better idea of what we're working with, let's go a bit deeper\ninto how we can speed up queries over columnar data! Analytical data processing\nis an active field of research spanning several decades, so we won't be able to\ngo over every possible optimization. Nevertheless, the rest of this post will\ngive a good overview of the techniques that most modern analytical database\nsystems utilize.\n\n## [#Vectorized execution](#vectorized-execution)\n\nThe simplest way to run `SELECT AVG(duration_min) FROM rides;` is to visit one\nride at a time: take a ride, add its duration, and repeat, dividing by the\nlength of the column at the end. However, a column store doesn't necessarily\nhave to execute this way. Since all of the durations sit in one contiguous\narray, it can process them in *batches* of a few thousand values, where each\nbatch is small enough to stay in the CPU's cache.[10](#user-content-fn-batches) This is called\nvectorized execution.[11](#user-content-fn-storage)\n\nBut why would a batch be any faster than one value at a time? To understand\nthis, we first need to understand how a database execution engine actually runs\nthese queries.[12](#user-content-fn-query-execution)\n\nA database has to be able to run *any* query, so it builds and plans each one\nwith general-purpose pieces called *operators*. For example, we might have an\noperator that reads a column, another that performs filters, another that\ncomputes a sum, and so on. If the operators pass each other one `Ride` at a time\n(this is called the Volcano model[13](#user-content-fn-volcano)), then for every single ride, the\ndatabase has to figure out which operator runs next, which column it wants, and\nwhat type that column is. All of this bookkeeping and interpretation cost can\neasily take more time than the summation itself.[14](#user-content-fn-x100) With batches, we only\npay for the bookkeeping once per batch instead of once per value, and the actual\nwork turns into a tight loop over an array.\n\nSo why stop at a few thousand values, and not just process the entire column at\nonce? Operators hand their results to each other, so a small batch of results\ncan stay in the CPU's cache until the next operator picks it up. An operator\nresult the size of an entire column generally cannot fit inside the CPU's cache,\nso the CPU would have to write it back out to main memory and then read it back\nin.\n\nFor our query, the work on each batch is a single loop:\n\nRust\n\n```\nfn sum(batch: &[u32; 1024]) -> u64 {\n    let mut sum = 0;\n    for &duration in batch {\n        sum += duration as u64;\n    }\n    sum\n}\n```\n\nIn addition to vectorized execution having better cache locality, we can speed\nup our execution of the query with data-parallel operations. Modern CPUs have\ninstructions that operate on several values at once, called\n[SIMD](https://en.wikipedia.org/wiki/Single_instruction,_multiple_data)\n(*single instruction, multiple data*). They work best when the values are the\nsame type and are contiguous in memory, which is exactly what a batch of a\ncolumn is.\n\nSo when the compiler sees the `for` loop above, it can emit SIMD instructions on\nits own. This is a technique called *autovectorization*[15](#user-content-fn-two-vectors) that is\nsupported well in compiler backends such as LLVM.[16](#user-content-fn-autovectorization)\n\nWith [AVX-512](https://en.wikipedia.org/wiki/AVX-512) (which can load 512 bits\nat once), one\n[`vpaddq`](https://www.felixcloutier.com/x86/paddb:paddw:paddd:paddq)\ninstruction adds 8 64-bit durations at once.[17](#user-content-fn-simd-width) Note that `vpaddq`\ndoesn't add those 8 durations to each other. A 512-bit register has 8 slots of\n64 bits, and each slot holds its own running sum: the first duration is added to\nthe first slot, the second duration to the second slot, and so on. Only after\nthe loop does the code add the slots together to get the final sum (the figure\nbelow leaves that last step out).\n\nWithout SIMD\n\nduration\\_min\n\n14\n\n6\n\n21\n\n8\n\n15\n\n1\n\n9\n\n31\n\nadd\n\nadd\n\nadd\n\nadd\n\nadd\n\nadd\n\nadd\n\nadd\n\n1value per instruction\n\nsum = 105\n\nWith SIMD\n\nduration\\_min\n\n14\n\n6\n\n21\n\n8\n\n15\n\n1\n\n9\n\n31\n\nvpaddq\n\n8values per instruction\n\nsum = 105\n\nLLVM IR and AVX-512 assembly\n\nThis is the output of `rustc` 1.99.1 with\n`-C opt-level=3 -C target-feature=+avx512f`, with the attributes, metadata, and\nassembler directives removed.\n\nNote that the compiler keeps four registers of running sums (`zmm0` to `zmm3` in\nthe assembly) instead of one. This is a separate optimization from SIMD called\n*loop unrolling*:[18](#user-content-fn-unrolling) the 8 slots in each register come from SIMD, and\nthe four registers come from the compiler doing four steps of the loop in every\npass. Together, every pass of the loop adds 4 × 8 = 32 durations.\n\nThis is the optimized LLVM IR:\n\nLLVM IR\n\n```\ndefine i64 @sum(ptr %batch) {\nstart:\n  br label %vector.body\n\n; The loop. Every pass adds 32 durations.\nvector.body:\n  ; The counter and the four vectors of running sums, which all start at zero.\n  %index = phi i64 [ 0, %start ], [ %index.next, %vector.body ]\n  %vec.phi = phi <8 x i64> [ zeroinitializer, %start ], [ %9, %vector.body ]\n  %vec.phi4 = phi <8 x i64> [ zeroinitializer, %start ], [ %10, %vector.body ]\n  %vec.phi5 = phi <8 x i64> [ zeroinitializer, %start ], [ %11, %vector.body ]\n  %vec.phi6 = phi <8 x i64> [ zeroinitializer, %start ], [ %12, %vector.body ]\n  %0 = shl i64 %index, 2\n  %1 = getelementptr inbounds nuw i8, ptr %batch, i64 %0\n  %2 = getelementptr inbounds nuw i8, ptr %1, i64 32\n  %3 = getelementptr inbounds nuw i8, ptr %1, i64 64\n  %4 = getelementptr inbounds nuw i8, ptr %1, i64 96\n  %wide.load = load <8 x i32>, ptr %1, align 4\n  %wide.load7 = load <8 x i32>, ptr %2, align 4\n  %wide.load8 = load <8 x i32>, ptr %3, align 4\n  %wide.load9 = load <8 x i32>, ptr %4, align 4\n  %5 = zext <8 x i32> %wide.load to <8 x i64>\n  %6 = zext <8 x i32> %wide.load7 to <8 x i64>\n  %7 = zext <8 x i32> %wide.load8 to <8 x i64>\n  %8 = zext <8 x i32> %wide.load9 to <8 x i64>\n  %9 = add <8 x i64> %vec.phi, %5\n  %10 = add <8 x i64> %vec.phi4, %6\n  %11 = add <8 x i64> %vec.phi5, %7\n  %12 = add <8 x i64> %vec.phi6, %8\n  %index.next = add nuw i64 %index, 32\n  %13 = icmp eq i64 %index.next, 1024\n  br i1 %13, label %bb2, label %vector.body\n\n; Add the running sums together, and return the result.\nbb2:\n  %bin.rdx = add <8 x i64> %10, %9\n  %bin.rdx10 = add <8 x i64> %11, %bin.rdx\n  %bin.rdx11 = add <8 x i64> %12, %bin.rdx10\n  %14 = tail call i64 @llvm.vector.reduce.add.v8i64(<8 x i64> %bin.rdx11)\n  ret i64 %14\n}\n```\n\nThis is the x86-64 assembly that LLVM generates:\n\nAssembly\n\n```\nsum:\n    # Set the four registers of running sums (zmm0 to zmm3) and the counter\n    # (rax) to zero.\n    vpxor xmm0, xmm0, xmm0\n    xor eax, eax\n    vpxor xmm1, xmm1, xmm1\n    vpxor xmm2, xmm2, xmm2\n    vpxor xmm3, xmm3, xmm3\n\n# The loop. Every pass adds 32 durations.\n.LBB0_1:\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax]\n    vpaddq zmm0, zmm0, zmm4\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax + 32]\n    vpaddq zmm1, zmm1, zmm4\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax + 64]\n    vpmovzxdq zmm5, ymmword ptr [rdi + 4*rax + 96]\n    vpaddq zmm2, zmm2, zmm4\n    vpaddq zmm3, zmm3, zmm5\n    add rax, 32\n    cmp rax, 1024\n    jne .LBB0_1\n\n    # Add the running sums together, and return the result in rax.\n    vpaddq zmm0, zmm1, zmm0\n    vpaddq zmm0, zmm2, zmm0\n    vpaddq zmm0, zmm3, zmm0\n    vextracti64x4 ymm1, zmm0, 1\n    vpaddq zmm0, zmm0, zmm1\n    vextracti128 xmm1, ymm0, 1\n    vpaddq xmm0, xmm0, xmm1\n    vpshufd xmm1, xmm0, 238\n    vpaddq xmm0, xmm0, xmm1\n    vmovq rax, xmm0\n    vzeroupper\n    ret\n```\n\nNote that autovectorization is not unique to sums. Much of the time executing a\nquery (especially a relatively simple one) is spent in tight loops over batches\nlike this one, and the compiler can vectorize many of them in the same way\nwithout anyone writing a single SIMD instruction by hand.\n\n## [#Compression](#compression)\n\nSo far, we've only looked at data that is already in memory. In most database\nsystems, data lives on persistent storage (a disk, an SSD, or object storage\nlike S3), and bringing it into memory is usually the bottleneck of query\nexecution (in other words, queries are I/O bound). So the size of our data is\nvery important: the fewer bytes a query has to read, the less time it spends\nwaiting on I/O.\n\nThe naive way to make the data smaller is to take each block of it and run it\nthrough a general-purpose compression algorithm.[19](#user-content-fn-general-purpose) This kind of\ncompression should be familiar to anyone who has ever dealt with zip files! It\ntreats the data as just a big pile of bytes, and it doesn't care what those\nbytes actually mean, which is why it works on everything (including both rows\nand columns).\n\nThe problem is that this kind of compression is a \"black box\": once a block is\ncompressed, the database can't see inside of it anymore. For example, if you\nwanted to read the one-millionth line of a zipped CSV file, there is no way to\njump straight to that line, so you would have to unzip (decompress) everything\nthat comes before it just to access a single line.[20](#user-content-fn-csv-lines) The ability to\nread any one piece of the data without reading the rest of it is called *random\naccess*, and this kind of compression is unable to support fast random access.\n\nA database system will have the exact same problem with black-box compressed\nblocks of data: to read the duration of ride 1004, it has to decompress the\nentire block (potentially multiple blocks!) that the ride lives in.\n\nThis is another place where columns help. The values in a column all have the\nsame type, and they tend to be similar to each other, which means that a column\ncompresses much better than a row does. We can already see this in our example\nabove: `start_area` only has 3 distinct values, `bike_type` only has 2, and\n`ride_id` is always increasing.\n\nMore importantly, we don't actually *need* to use black-box compression. We can\ninstead use lightweight encodings: simple schemes that compress the data\nwhile retaining the structure and the meaning of the values.[21](#user-content-fn-encodings) Instead\nof turning a column into a big pile of bytes, a lightweight encoding takes\nadvantage of one specific pattern in it (for example, a column with only a few\ndistinct values, or a column of numbers that are all small) to store the same\nvalues in less space.\n\nRetaining the structure means that we can keep random access. With most\nlightweight encodings, the database system can jump straight to the value that\nit wants without decoding everything around it.\n\nRetaining the *meaning* helps as well. Lightweight encodings are \"lighter\nweight\" than black-box compression, but they aren't free, since decoding them\nstill takes CPU time. However, because the encoded values still *mean*\nsomething, a query can often do its work directly on the encoded data without\ndecoding it first, which skips much of that cost. This computation over\ncompressed data is a form of \"late materialization\".[22](#user-content-fn-late-materialization)\n\nThis is exactly how we built [Vortex](https://github.com/vortex-data/vortex), an\nopen-source, extensible columnar file format and data processing library. It has\na whole collection of lightweight encodings, and it can stack them on top of\neach other to make the data even smaller.\n\n> We've written a lot about how this works. Check out our other blogs!\n>\n> - [Vortex: One Format for Any Shape](https://spiraldb.com/blog/vortex-one-format-for-any-shape)\n>   for an overview of how Vortex works\n> - [FastLanes](https://spiraldb.com/blog/life-in-the-fastlanes) for integers\n> - [ALP](https://spiraldb.com/blog/alp-rust-is-faster-than-c) for floats\n> - [FSST](https://spiraldb.com/blog/compressing-strings-with-fsst) for strings\n> - [BtrBlocks](https://spiraldb.com/blog/cascading-compression-with-btrblocks) for choosing an\n>   encoding for each column\n> - [Push-down compute](https://spiraldb.com/blog/what-if-we-just-didnt-decompress-it) for working\n>   on compressed data\n> - [`LIKE` on compressed strings](https://spiraldb.com/blog/pattern-matching-strings-without-decompression)\n>   without decompressing them\n\n## [#Thinking in columns](#thinking-in-columns)\n\nWe started with data from a CSV file and one \"simple\" choice of storing data in\nrows vs columns. Yet we have seen just how much follows from that choice, as\nwell as the consequences of choosing one or the other.[23](#user-content-fn-how-different)\n\nThose consequences are the reason that most database systems are built for\neither transactions or analytics, and not both.[24](#user-content-fn-htap) The way a database\nexecutes queries and the way it compresses data are both built on top of this\none choice, so it isn't something that a system can just flip later. A column\nstore's strength in serving analytical queries is exactly what makes it bad for\nreading and changing one record at a time, and the opposite is true for a row\nstore.\n\nThere is also a lot more to columnar data than what we can fit in a single\nintroductory post. For example, we never talked about how a column store\nactually organizes its data on persistent storage,[25](#user-content-fn-layouts) how it avoids\nreading data that a query doesn't need,[26](#user-content-fn-pruning) how vectorized execution isn't\nthe only way to run a query more efficiently,[27](#user-content-fn-compiled) and we completely\nignored writes and modifications to data![28](#user-content-fn-writes) Each one of these topics is a\nwhole area of active research. If you want to keep going, the CMU database\ncourses are a great place to start, and all of their lectures are free to watch\nonline.[29](#user-content-fn-next)\n\nIn the future, we hope to post more about these kinds of topics, as we engage\nwith them quite a lot working at Spiral!\n\n### Footnotes\n\n1. In practice, a database can often skip records that it knows it doesn't\n   need, for example with an index, or with the minimum and maximum values it\n   keeps for each block of data\n   ([zone maps](https://spiraldb.com/blog/zone-maps-or-queries-go-brrr)). But logically speaking,\n   the answers still *depend* on every record. [↩︎](#user-content-fnref-index)\n2. Think of things like bank transfers and airline bookings: lots of small\n   operations (transactions) that read or change only a few records, all\n   happening in parallel, potentially thousands of times per second. [↩︎](#user-content-fnref-oltp)\n3. The idea is a lot older than both of those systems.\n   [A Decomposition Storage Model](https://doi.org/10.1145/318898.318923)\n   (SIGMOD 1985) already proposed storing each column on its own. The CMU\n   15-445\n   [lecture notes on storage models](https://15445.courses.cs.cmu.edu/fall2026/notes/06-storage3.pdf)\n   compare the two layouts in more detail. [↩︎](#user-content-fnref-dsm)\n4. These are generally queries that read a large part of a dataset, usually\n   worried about only a few of its columns, summarizing the data with counts,\n   sums, and averages. [↩︎](#user-content-fnref-olap)\n5. Personally, I consider these fun... [↩︎](#user-content-fnref-fun)\n6. Apple's M-series chips use 128-byte cache lines, but the point remains the\n   same. [↩︎](#user-content-fnref-cache-line)\n7. This is 8 bytes each for `ride_id` and `started_at` (a 64-bit timestamp), 24\n   for the `String` (a pointer to the text, a length, and a capacity), 1 for\n   `bike_type`, 3 bytes of padding for alignment, and 4 for `duration_min`.\n   Note that the 24 bytes for `start_area` are specific to Rust's `String`. A\n   real database will store strings differently. Also, Rust is free to reorder\n   the fields of a struct unless you add `#[repr(C)]`, and `rustc` 1.99.1 does:\n   it moves `start_area` to the front and the padding to the end. The struct is\n   still 48 bytes with 3 bytes of padding either way, so we draw the fields in\n   the order that we wrote them. [↩︎](#user-content-fnref-ride-size)\n8. An [index](https://en.wikipedia.org/wiki/Database_index) is a separate data\n   structure (usually a [B+ tree](https://en.wikipedia.org/wiki/B%2B_tree))\n   that maps a \"key\" (usually a unique primary key) like `1004` to the location\n   of its stored record. This allows the database to quickly find the data\n   instead of scanning the entire table to find it. See the CMU 15-445\n   [lecture notes on indexes](https://15445.courses.cs.cmu.edu/fall2026/notes/08-indexes1.pdf)\n   for more detail. [↩︎](#user-content-fnref-lookup-index)\n9. These counts leave out the text of `start_area`. The 24 bytes of a `String`\n   only point to the text, which lives somewhere else in memory, so actually\n   reading the name of the neighborhood costs at least one more cache line.\n   That is true for both layouts, though, so it doesn't change which one wins. [↩︎](#user-content-fnref-string-text)\n10. [MonetDB/X100](https://www.cidrdb.org/cidr2005/papers/P19.pdf), the system\n    that introduced this design, uses 1024 values per batch by default.\n    [DuckDB](https://duckdb.org/docs/stable/internals/vector) uses 2048, and\n    [DataFusion](https://datafusion.apache.org/user-guide/configs.html)\n    uses 8192. [↩︎](#user-content-fnref-batches)\n11. Also, a real database table will generally live on persistent storage (HDD,\n    SSD) if the data is larger than memory, so the database will not be able to\n    load a whole column at once even if it wanted to. So the query has to read\n    the column in pieces anyways. [↩︎](#user-content-fnref-storage)\n12. The CMU 15-445\n    [lecture notes on query execution](https://15445.courses.cs.cmu.edu/fall2026/notes/13-queryexecution1.pdf)\n    go into much more detail, and the CMU 15-721 notes on\n    [query processing](https://15721.courses.cs.cmu.edu/spring2024/notes/04-execution1.pdf)\n    and\n    [vectorized execution](https://15721.courses.cs.cmu.edu/spring2024/notes/06-vectorization.pdf)\n    go further still. [↩︎](#user-content-fnref-query-execution)\n13. Named after [Volcano](https://doi.org/10.1109/69.273032), a query engine by\n    [Goetz Graefe](https://scholar.google.com/citations?user=pdDeRScAAAAJ&hl=en)\n    from the early 90s. It is also sometimes called the \"iterator\" model, and\n    almost every row store still executes queries this way. [↩︎](#user-content-fnref-volcano)\n14. Vectorized execution comes from\n    [MonetDB/X100: Hyper-Pipelining Query Execution](https://www.cidrdb.org/cidr2005/papers/P19.pdf)\n    (CIDR 2005). The paper profiled MySQL on an analytical query and found that\n    the operations that do the actual work take only about 10% of the execution\n    time. X100's ran every operator on small vectors of values, which is where\n    the name comes from. [↩︎](#user-content-fnref-x100)\n15. Note that *vectorized execution* is the database processing values in\n    batches, whereas *autovectorization* is the compiler emitting SIMD\n    instructions. They are separate but similar ideas. [↩︎](#user-content-fnref-two-vectors)\n16. [Autovectorization](https://en.wikipedia.org/wiki/Automatic_vectorization)\n    is easy to break, though. If `duration_min` were a float, LLVM would\n    [not vectorize this sum](https://llvm.org/docs/Vectorizers.html#reductions)\n    by default: adding 8 values at a time changes the order of the additions,\n    and floating-point addition isn't associative, so the result could change. [↩︎](#user-content-fnref-autovectorization)\n17. 8 and not 16 because every 32-bit duration is widened to 64 bits so that the\n    sum doesn't overflow. [↩︎](#user-content-fnref-simd-width)\n18. [Loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling) helps here\n    because each `vpaddq` has to wait for the previous one that wrote to the\n    same register, so with only one register, the additions would have to run\n    one after another. With four independent registers, the CPU can\n    [run several of them at the same time](https://llvm.org/docs/Vectorizers.html#partial-unrolling-during-vectorization). [↩︎](#user-content-fnref-unrolling)\n19. Zip files use an algorithm called\n    [DEFLATE](https://en.wikipedia.org/wiki/Deflate). Databases tend to use\n    newer ones like [Zstandard](https://en.wikipedia.org/wiki/Zstd) and\n    [LZ4](https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)), but the\n    idea is the same. [↩︎](#user-content-fnref-general-purpose)\n20. This is a bit of a lie. A plain CSV file doesn't have real random access\n    since its lines have different lengths, so you can't know where line one\n    million starts without counting. A better example is black-box compressing a\n    `Vec<u32>` of durations, where value number N always starts at byte 4 × N.\n    Once the array is block-box compressed, we can no longer index into the\n    vector with random access. [↩︎](#user-content-fnref-csv-lines)\n21. Two recent papers on lightweight encodings are\n    [The FastLanes Compression Layout](https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf)\n    (VLDB 2023) and\n    [BtrBlocks: Efficient Columnar Compression for Data Lakes](https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf)\n    (SIGMOD 2023). The CMU 15-721 lecture notes on data formats and encodings\n    ([part 1](https://15721.courses.cs.cmu.edu/spring2024/notes/02-data1.pdf),\n    [part 2](https://15721.courses.cs.cmu.edu/spring2024/notes/03-data2.pdf))\n    show how real file formats put encodings like these to use. [↩︎](#user-content-fnref-encodings)\n22. This term comes from research on column stores, where it essentially means\n    waiting as long as possible (late) before putting the columns of a row back\n    together (materializing). See\n    [Materialization Strategies in a Column-Oriented DBMS](https://doi.org/10.1109/ICDE.2007.367892).\n    Compute over compressed data is the same idea one level lower: wait as long\n    as possible before decompressing a value. Executing a query directly on\n    compressed columns goes all the way back to\n    [Integrating Compression and Execution in Column-Oriented Database Systems](https://www.cs.umd.edu/~abadi/papers/abadisigmod06.pdf)\n    (SIGMOD 2006), though Vortex takes this concept several steps further. [↩︎](#user-content-fnref-late-materialization)\n23. [Column-Stores vs. Row-Stores: How Different Are They Really?](https://www.cs.umd.edu/~abadi/papers/abadi-sigmod08.pdf)\n    (SIGMOD 2008) looks at what happens if you only change the storage. [↩︎](#user-content-fnref-how-different)\n24. People have tried to build one system that does both in the past\n    ([HTAP](https://en.wikipedia.org/wiki/Hybrid_transactional/analytical_processing),\n    or hybrid transactional/analytical processing), but those attempts generally\n    didn't work out. Some newer systems seem to be bridging the gap, however.\n    [CedarDB](https://cedardb.com/), the commercial version of\n    [Umbra](https://umbra-db.com/) (a research system from TU Munich), runs\n    transactions and analytics on just one engine and one copy of the data.\n    Databricks' [Lakebase](https://www.databricks.com/product/lakebase) keeps\n    Postgres (a row store) as the engine for transactional queries, but its\n    storage layer rewrites the same data into columnar formats in the\n    background, allowing an analytical engine to query it. [↩︎](#user-content-fnref-htap)\n25. Most formats split the table into large groups of rows and store the columns\n    separately inside of each group (this is known as a \"row group\"). This idea\n    goes back to PAX, from\n    [Weaving Relations for Cache Performance](https://www.vldb.org/conf/2001/P169.pdf)\n    (VLDB 2001), and it's how\n    [Apache Parquet](https://parquet.apache.org/docs/file-format/) files work\n    today.\n    [An Empirical Evaluation of Columnar Storage Formats](https://www.vldb.org/pvldb/vol17/p148-zeng.pdf)\n    (VLDB 2024) looks at how well these formats hold up on modern hardware and\n    workloads. For columns in memory instead of on disk, the standard is the\n    [Apache Arrow columnar format](https://arrow.apache.org/docs/format/Columnar.html). [↩︎](#user-content-fnref-layouts)\n26. The most common trick is to keep \"zone maps\" of the minimum and maximum\n    value of every block of data so that a query can completely skip the blocks\n    that can't contain certain data. We wrote about this in\n    [Zone maps, or “queries go brrr”](https://spiraldb.com/blog/zone-maps-or-queries-go-brrr). [↩︎](#user-content-fnref-pruning)\n27. The other big approach is to compile each query into machine code that is\n    specialized for exactly that query.\n    [Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask](https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf)\n    (VLDB 2018) compares the two approaches, and neither one is a clear winner. [↩︎](#user-content-fnref-compiled)\n28. Changing data can be expensive in a column store because a single new record\n    has to go to a different place for each of its columns.\n    [C-Store](https://www.vldb.org/archives/website/2005/program/paper/thu/p553-stonebraker.pdf)\n    (VLDB 2005) deals with this by keeping a small store that is built for\n    writes next to the big one that is built for reads, and moving data from one\n    to the other in the background. [↩︎](#user-content-fnref-writes)\n29. [CMU 15-445](https://15445.courses.cs.cmu.edu/fall2026/schedule.html) is the\n    introductory course\n    ([Fall 2025 lecture videos](https://www.youtube.com/playlist?list=PLSE8ODhjZXjYMAgsGH-GtY5rJYZ6zjsd5)),\n    and [CMU 15-721](https://15721.courses.cs.cmu.edu/spring2024/schedule.html)\n    is the advanced one\n    ([lecture videos](https://www.youtube.com/playlist?list=PLSE8ODhjZXjYa_zX-KeMJui7pcN1rIaIJ)).\n    Note that the author of this post learned most of this material from the CMU\n    courses! If you'd rather read,\n    [The Design and Implementation of Modern Column-Oriented Database Systems](https://ir.cwi.nl/pub/21772/1900000024-Abadi-Vol5-DBS-024.pdf)\n    (2013) is a survey of the whole field. [↩︎](#user-content-fnref-next)\n","body_html":"<p>When we think about structured data, we generally think in terms of rows.\nTake this simple CSV file, which records some data about bike rides on a\nbike-sharing app in New York City:</p>\n<p>CSV</p>\n<pre><code>ride_id, started_at,        start_area,         bike_type, duration_min\n   1001, 2026-11-02 07:58,  Tribeca,            classic,             14\n   1002, 2026-11-02 08:01,  Financial District, electric,             6\n   1003, 2026-11-02 08:01,  SoHo,               classic,             21\n   1004, 2026-11-02 08:03,  Financial District, electric,             8\n   1005, 2026-11-02 08:04,  Financial District, classic,             15\n   1006, 2026-11-02 08:07,  Tribeca,            electric,             1\n   1007, 2026-11-02 08:08,  Tribeca,            electric,             9\n   1008, 2026-11-02 08:12,  Financial District, classic,             31</code></pre>\n<p>Data in this CSV file is organized into rows, where each row corresponds to a\n<em>record</em> of data. Each record here is one ride, or one &quot;thing&quot;, with everything\nwe know about it on one line. We tend to organize data like this almost\neverywhere: think of spreadsheets, JSON objects, C-style structs in an array,\nSQL tables, etc. This is because it matches how we think: one &quot;thing&quot;, and all\nof the details of that &quot;thing&quot;.</p>\n<p>This way of thinking fits a lot of the software we write. When you log in to an\napp, post a comment on a video, add an item to a shopping cart, send a bank\ntransfer, or book a ride, the application will change just one record (or a few,\nat most). So it makes sense that the databases behind this software, like\nPostgres and MySQL, &quot;think in&quot; (or are modeled around) rows as well: they keep\neach record&#39;s details together, so finding, updating, or creating a record means\ngoing to one place.</p>\n<p>But not everything we ask of a database is limited to one record.</p>\n<p>If you run the bike-share service that produced the CSV file above, you&#39;ll\neventually want to learn something from all the data it collects. This kind of\nwork is called <em>analytics</em>. For example, which neighborhood is busiest on Monday\nand Friday mornings? Do people take longer rides on electric bikes than on\nclassic ones? Observe how no single record can answer these questions. The\nanswers come from the dataset as a whole, so the only way to get them is to look\nat <em>all</em> of the records.<a href=\"#user-content-fn-index\">1</a></p>\n<p>Notice what these questions don&#39;t need, however. Finding the busiest\nneighborhood only needs the <code>start_area</code> and <code>started_at</code> columns, and comparing\nbike types only needs <code>bike_type</code> and <code>duration_min</code>. Each question may have to\nlook at every row, but it only needs a few of the columns from each one. And a\ndatabase that keeps each record&#39;s details together can&#39;t take advantage of that:\nto read two columns, it has to read all five. We may <em>think</em> in rows, but to\nanswer questions like these quickly, we have to program in columns.</p>\n<p>Programming in columns begins with how the data is stored, but that&#39;s only the\nstart. Once data is stored by column, the way a database runs a query changes\ndramatically: how much data it reads, how many values it handles at a time, how\nmany values the CPU can process with one instruction, how well the data\ncompresses, etc.</p>\n<p>This post will go over these changes, and by the end, you&#39;ll see just how much\nfollows from the &quot;simple&quot; choice to store columns instead of rows.</p>\n<h2 id=\"row-stores-and-column-stores\"><a href=\"#row-stores-and-column-stores\">#Row stores and column stores</a></h2>\n<p>Let&#39;s start with what <em>doesn&#39;t</em> change. Whether a database stores rows or\ncolumns, the table it shows you when you do <code>SELECT * FROM rides;</code> is the same.\nYou create it with the same SQL, you query it with the same SQL, and you get the\nsame answers. We can say that the two tables are logically equivalent.</p>\n<p>SQL</p>\n<pre><code>CREATE TABLE rides (\n    ride_id      BIGINT,\n    started_at   TIMESTAMP,\n    start_area   TEXT,\n    bike_type    TEXT,\n    duration_min INTEGER\n);\n\nSELECT * FROM rides WHERE ride_id = 1004;\n\nSELECT AVG(duration_min) FROM rides;</code></pre>\n<p>Rows vs columns is a physical distinction rather than a logical one: the\ndata <em>represents</em> the same thing, but how that data is actually <em>arranged</em> in\nmemory and on disk is different.</p>\n<p>Row store</p>\n<p>ride_id</p>\n<p>started_at</p>\n<p>start_area</p>\n<p>bike_type</p>\n<p>duration_min</p>\n<p>1001</p>\n<p>07:58</p>\n<p>Tribeca</p>\n<p>classic</p>\n<p>14</p>\n<p>1002</p>\n<p>08:01</p>\n<p>Financial District</p>\n<p>electric</p>\n<p>6</p>\n<p>1003</p>\n<p>08:01</p>\n<p>SoHo</p>\n<p>classic</p>\n<p>21</p>\n<p>1004</p>\n<p>08:03</p>\n<p>Financial District</p>\n<p>electric</p>\n<p>8</p>\n<p>Column store</p>\n<p>ride_id</p>\n<p>1001</p>\n<p>1002</p>\n<p>1003</p>\n<p>1004</p>\n<p>started_at</p>\n<p>07:58</p>\n<p>08:01</p>\n<p>08:01</p>\n<p>08:03</p>\n<p>start_area</p>\n<p>Tribeca</p>\n<p>Financial District</p>\n<p>SoHo</p>\n<p>Financial District</p>\n<p>bike_type</p>\n<p>classic</p>\n<p>electric</p>\n<p>classic</p>\n<p>electric</p>\n<p>duration_min</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>Databases are named after the grouping they choose. A row store keeps each\nrecord&#39;s values next to each other, just like the CSV we started with. Postgres\nand MySQL, which we mentioned before, are both row stores. They&#39;re built for the\nsmall reads and writes behind an application, which is called *online\ntransaction processing* (OLTP).<a href=\"#user-content-fn-oltp\">2</a></p>\n<p>A column store does the opposite: it takes every record apart and keeps each\ncolumn&#39;s values next to each other instead.<a href=\"#user-content-fn-dsm\">3</a> DuckDB and ClickHouse are\nexamples of column stores. They&#39;re built for analytics, which is called *online\nanalytical processing* (OLAP).<a href=\"#user-content-fn-olap\">4</a></p>\n<h3 id=\"rows-and-columns-in-memory\"><a href=\"#rows-and-columns-in-memory\">#Rows and columns in memory</a></h3>\n<p>To make this concrete, imagine that we have to hold our rides in memory\nourselves. This isn&#39;t how a real database would be implemented, but it&#39;s a good\napproximation of how each kind arranges its data. In Rust, a row store would be\na <code>Vec</code> of structs:</p>\n<p>Rust</p>\n<pre><code>struct Ride {\n    ride_id: u64,\n    started_at: Timestamp,\n    start_area: String,\n    bike_type: BikeType,\n    duration_min: u32,\n}\n\ntype Rows = Vec&lt;Ride&gt;;</code></pre>\n<p>A column store will have the same fields, but it will look like a struct of\n<code>Vec</code>s:</p>\n<p>Rust</p>\n<pre><code>struct Columns {\n    ride_id: Vec&lt;u64&gt;,\n    started_at: Vec&lt;Timestamp&gt;,\n    start_area: Vec&lt;String&gt;,\n    bike_type: Vec&lt;BikeType&gt;,\n    duration_min: Vec&lt;u32&gt;,\n}</code></pre>\n<p>Here is what these data layouts look like side by side:</p>\n<p>Rows</p>\n<p>rides[0]</p>\n<p>1001</p>\n<p>07:58</p>\n<p>Tribeca</p>\n<p>classic</p>\n<p>14</p>\n<p>rides[1]</p>\n<p>1002</p>\n<p>08:01</p>\n<p>Financial District</p>\n<p>electric</p>\n<p>6</p>\n<p>rides[2]</p>\n<p>1003</p>\n<p>08:01</p>\n<p>SoHo</p>\n<p>classic</p>\n<p>21</p>\n<p>rides[3]</p>\n<p>1004</p>\n<p>08:03</p>\n<p>Financial District</p>\n<p>electric</p>\n<p>8</p>\n<p>Columns</p>\n<p>ride_id</p>\n<p>1001</p>\n<p>1002</p>\n<p>1003</p>\n<p>1004</p>\n<p>started_at</p>\n<p>07:58</p>\n<p>08:01</p>\n<p>08:01</p>\n<p>08:03</p>\n<p>start_area</p>\n<p>Tribeca</p>\n<p>Financial District</p>\n<p>SoHo</p>\n<p>Financial District</p>\n<p>bike_type</p>\n<p>classic</p>\n<p>electric</p>\n<p>classic</p>\n<p>electric</p>\n<p>duration_min</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>Both of these forms represent the same logical values, but their layout is\ndramatically different.</p>\n<h3 id=\"reading-only-the-columns-you-need\"><a href=\"#reading-only-the-columns-you-need\">#Reading only the columns you need</a></h3>\n<p>Let&#39;s do a fun exercise.<a href=\"#user-content-fn-fun\">5</a> These are the two SQL queries shown above. Which\nlayout is better for executing each of them?</p>\n<p>SQL</p>\n<pre><code>SELECT AVG(duration_min) FROM rides;\n\nSELECT * FROM rides WHERE ride_id = 1004;</code></pre>\n<p>For the <code>AVG</code> query, computing it requires only the <code>duration_min</code> of every ride\nand nothing else. In the <code>Columns</code> layout, values are stored together in a\nsingle <code>Vec&lt;u32&gt;</code>, so the query can scan that one array without touching the\nother four. For <code>Vec&lt;Ride&gt;</code> (the <code>Rows</code> layout), there is simply no way to read\nonly the durations. Each duration is stored within a <code>Ride</code>, so the query\nhas to read through every <code>Ride</code> and pass over the other four fields every time.</p>\n<p>Note that the code can &quot;ignore&quot; those other fields, but the hardware cannot. A\nCPU doesn&#39;t fetch memory one value at a time: it will fetch fixed-size blocks\ncalled <em>cache lines</em> (which are 64 bytes on most machines<a href=\"#user-content-fn-cache-line\">6</a>),\nfetching the whole line even when the program needs only a few bytes of it. A\n<code>Ride</code> is 48 bytes<a href=\"#user-content-fn-ride-size\">7</a> and <code>duration_min</code> is only 4 of them, so with the\nrow layout, we have to fetch all 48 bytes to read those 4, which is 12x the\namount that we actually need. The CPU can&#39;t skip any of these lines either\nbecause a <code>Ride</code> is smaller than a cache line, so every cache line of the array\nhas a duration somewhere in it.</p>\n<p>SELECT AVG(duration_min) FROM rides;</p>\n<p>used</p>\n<p>loaded, not used</p>\n<p>not loaded</p>\n<p>Rows</p>\n<p>1 cache line = 64 bytes</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>15</p>\n<p>1</p>\n<p>9</p>\n<p>31</p>\n<p>6cache lines loaded</p>\n<p>32 of 384 bytes used</p>\n<p>Columns</p>\n<p>ride_id</p>\n<p>started_at</p>\n<p>start_area</p>\n<p>bike_type</p>\n<p>duration_min</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>15</p>\n<p>1</p>\n<p>9</p>\n<p>31</p>\n<p>(room for 8 more)</p>\n<p>1cache line loaded</p>\n<p>32 of 64 bytes used</p>\n<p>This diagram only shows 8 rides for simplicity (which is why the <code>duration_min</code>\nline is half empty), but the factor of 12 doesn&#39;t depend on the size of the\ntable. With one million rides, we might be fetching 48 MB vs 4 MB.</p>\n<p>The second query goes the other way. <code>SELECT * FROM rides WHERE ride_id = 1004</code>\nwants <em>every</em> field of a single ride, not just one. Once the database finds the\nrecord with that ride (probably via an index<a href=\"#user-content-fn-lookup-index\">8</a>), <code>Vec&lt;Ride&gt;</code> has\nall of its fields next to each other, so reading all of them touches only one or\ntwo cache lines (it might overlap two cache lines).<a href=\"#user-content-fn-string-text\">9</a> On the other\nhand, <code>Columns</code> has spread the same ride over five different arrays, so the\nquery has to fetch at least five cache lines to put it back together. For this\nquery, the <code>Rows</code> layout wins.</p>\n<p>SELECT * FROM rides WHERE ride_id = 1004;</p>\n<p>used</p>\n<p>loaded, not used</p>\n<p>not loaded</p>\n<p>Rows</p>\n<p>1 cache line = 64 bytes</p>\n<p>1004</p>\n<p>08:03</p>\n<p>Financial District</p>\n<p>electric</p>\n<p>8</p>\n<p>1cache line loaded</p>\n<p>48 of 64 bytes used</p>\n<p>Columns</p>\n<p>ride_id</p>\n<p>1004</p>\n<p>started_at</p>\n<p>08:03</p>\n<p>start_area</p>\n<p>Financial District</p>\n<p>bike_type</p>\n<p>electric</p>\n<p>(room for 56 more)</p>\n<p>duration_min</p>\n<p>8</p>\n<p>(room for 8 more)</p>\n<p>5cache lines loaded</p>\n<p>45 of 320 bytes used</p>\n<p>Now that we have a better idea of what we&#39;re working with, let&#39;s go a bit deeper\ninto how we can speed up queries over columnar data! Analytical data processing\nis an active field of research spanning several decades, so we won&#39;t be able to\ngo over every possible optimization. Nevertheless, the rest of this post will\ngive a good overview of the techniques that most modern analytical database\nsystems utilize.</p>\n<h2 id=\"vectorized-execution\"><a href=\"#vectorized-execution\">#Vectorized execution</a></h2>\n<p>The simplest way to run <code>SELECT AVG(duration_min) FROM rides;</code> is to visit one\nride at a time: take a ride, add its duration, and repeat, dividing by the\nlength of the column at the end. However, a column store doesn&#39;t necessarily\nhave to execute this way. Since all of the durations sit in one contiguous\narray, it can process them in <em>batches</em> of a few thousand values, where each\nbatch is small enough to stay in the CPU&#39;s cache.<a href=\"#user-content-fn-batches\">10</a> This is called\nvectorized execution.<a href=\"#user-content-fn-storage\">11</a></p>\n<p>But why would a batch be any faster than one value at a time? To understand\nthis, we first need to understand how a database execution engine actually runs\nthese queries.<a href=\"#user-content-fn-query-execution\">12</a></p>\n<p>A database has to be able to run <em>any</em> query, so it builds and plans each one\nwith general-purpose pieces called <em>operators</em>. For example, we might have an\noperator that reads a column, another that performs filters, another that\ncomputes a sum, and so on. If the operators pass each other one <code>Ride</code> at a time\n(this is called the Volcano model<a href=\"#user-content-fn-volcano\">13</a>), then for every single ride, the\ndatabase has to figure out which operator runs next, which column it wants, and\nwhat type that column is. All of this bookkeeping and interpretation cost can\neasily take more time than the summation itself.<a href=\"#user-content-fn-x100\">14</a> With batches, we only\npay for the bookkeeping once per batch instead of once per value, and the actual\nwork turns into a tight loop over an array.</p>\n<p>So why stop at a few thousand values, and not just process the entire column at\nonce? Operators hand their results to each other, so a small batch of results\ncan stay in the CPU&#39;s cache until the next operator picks it up. An operator\nresult the size of an entire column generally cannot fit inside the CPU&#39;s cache,\nso the CPU would have to write it back out to main memory and then read it back\nin.</p>\n<p>For our query, the work on each batch is a single loop:</p>\n<p>Rust</p>\n<pre><code>fn sum(batch: &amp;[u32; 1024]) -&gt; u64 {\n    let mut sum = 0;\n    for &amp;duration in batch {\n        sum += duration as u64;\n    }\n    sum\n}</code></pre>\n<p>In addition to vectorized execution having better cache locality, we can speed\nup our execution of the query with data-parallel operations. Modern CPUs have\ninstructions that operate on several values at once, called\n<a href=\"https://en.wikipedia.org/wiki/Single_instruction,_multiple_data\" rel=\"nofollow ugc noopener\">SIMD</a>\n(<em>single instruction, multiple data</em>). They work best when the values are the\nsame type and are contiguous in memory, which is exactly what a batch of a\ncolumn is.</p>\n<p>So when the compiler sees the <code>for</code> loop above, it can emit SIMD instructions on\nits own. This is a technique called <em>autovectorization</em><a href=\"#user-content-fn-two-vectors\">15</a> that is\nsupported well in compiler backends such as LLVM.<a href=\"#user-content-fn-autovectorization\">16</a></p>\n<p>With <a href=\"https://en.wikipedia.org/wiki/AVX-512\" rel=\"nofollow ugc noopener\">AVX-512</a> (which can load 512 bits\nat once), one\n<a href=\"https://www.felixcloutier.com/x86/paddb:paddw:paddd:paddq\" rel=\"nofollow ugc noopener\"><code>vpaddq</code></a>\ninstruction adds 8 64-bit durations at once.<a href=\"#user-content-fn-simd-width\">17</a> Note that <code>vpaddq</code>\ndoesn&#39;t add those 8 durations to each other. A 512-bit register has 8 slots of\n64 bits, and each slot holds its own running sum: the first duration is added to\nthe first slot, the second duration to the second slot, and so on. Only after\nthe loop does the code add the slots together to get the final sum (the figure\nbelow leaves that last step out).</p>\n<p>Without SIMD</p>\n<p>duration_min</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>15</p>\n<p>1</p>\n<p>9</p>\n<p>31</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>add</p>\n<p>1value per instruction</p>\n<p>sum = 105</p>\n<p>With SIMD</p>\n<p>duration_min</p>\n<p>14</p>\n<p>6</p>\n<p>21</p>\n<p>8</p>\n<p>15</p>\n<p>1</p>\n<p>9</p>\n<p>31</p>\n<p>vpaddq</p>\n<p>8values per instruction</p>\n<p>sum = 105</p>\n<p>LLVM IR and AVX-512 assembly</p>\n<p>This is the output of <code>rustc</code> 1.99.1 with\n<code>-C opt-level=3 -C target-feature=+avx512f</code>, with the attributes, metadata, and\nassembler directives removed.</p>\n<p>Note that the compiler keeps four registers of running sums (<code>zmm0</code> to <code>zmm3</code> in\nthe assembly) instead of one. This is a separate optimization from SIMD called\n<em>loop unrolling</em>:<a href=\"#user-content-fn-unrolling\">18</a> the 8 slots in each register come from SIMD, and\nthe four registers come from the compiler doing four steps of the loop in every\npass. Together, every pass of the loop adds 4 × 8 = 32 durations.</p>\n<p>This is the optimized LLVM IR:</p>\n<p>LLVM IR</p>\n<pre><code>define i64 @sum(ptr %batch) {\nstart:\n  br label %vector.body\n\n; The loop. Every pass adds 32 durations.\nvector.body:\n  ; The counter and the four vectors of running sums, which all start at zero.\n  %index = phi i64 [ 0, %start ], [ %index.next, %vector.body ]\n  %vec.phi = phi &lt;8 x i64&gt; [ zeroinitializer, %start ], [ %9, %vector.body ]\n  %vec.phi4 = phi &lt;8 x i64&gt; [ zeroinitializer, %start ], [ %10, %vector.body ]\n  %vec.phi5 = phi &lt;8 x i64&gt; [ zeroinitializer, %start ], [ %11, %vector.body ]\n  %vec.phi6 = phi &lt;8 x i64&gt; [ zeroinitializer, %start ], [ %12, %vector.body ]\n  %0 = shl i64 %index, 2\n  %1 = getelementptr inbounds nuw i8, ptr %batch, i64 %0\n  %2 = getelementptr inbounds nuw i8, ptr %1, i64 32\n  %3 = getelementptr inbounds nuw i8, ptr %1, i64 64\n  %4 = getelementptr inbounds nuw i8, ptr %1, i64 96\n  %wide.load = load &lt;8 x i32&gt;, ptr %1, align 4\n  %wide.load7 = load &lt;8 x i32&gt;, ptr %2, align 4\n  %wide.load8 = load &lt;8 x i32&gt;, ptr %3, align 4\n  %wide.load9 = load &lt;8 x i32&gt;, ptr %4, align 4\n  %5 = zext &lt;8 x i32&gt; %wide.load to &lt;8 x i64&gt;\n  %6 = zext &lt;8 x i32&gt; %wide.load7 to &lt;8 x i64&gt;\n  %7 = zext &lt;8 x i32&gt; %wide.load8 to &lt;8 x i64&gt;\n  %8 = zext &lt;8 x i32&gt; %wide.load9 to &lt;8 x i64&gt;\n  %9 = add &lt;8 x i64&gt; %vec.phi, %5\n  %10 = add &lt;8 x i64&gt; %vec.phi4, %6\n  %11 = add &lt;8 x i64&gt; %vec.phi5, %7\n  %12 = add &lt;8 x i64&gt; %vec.phi6, %8\n  %index.next = add nuw i64 %index, 32\n  %13 = icmp eq i64 %index.next, 1024\n  br i1 %13, label %bb2, label %vector.body\n\n; Add the running sums together, and return the result.\nbb2:\n  %bin.rdx = add &lt;8 x i64&gt; %10, %9\n  %bin.rdx10 = add &lt;8 x i64&gt; %11, %bin.rdx\n  %bin.rdx11 = add &lt;8 x i64&gt; %12, %bin.rdx10\n  %14 = tail call i64 @llvm.vector.reduce.add.v8i64(&lt;8 x i64&gt; %bin.rdx11)\n  ret i64 %14\n}</code></pre>\n<p>This is the x86-64 assembly that LLVM generates:</p>\n<p>Assembly</p>\n<pre><code>sum:\n    # Set the four registers of running sums (zmm0 to zmm3) and the counter\n    # (rax) to zero.\n    vpxor xmm0, xmm0, xmm0\n    xor eax, eax\n    vpxor xmm1, xmm1, xmm1\n    vpxor xmm2, xmm2, xmm2\n    vpxor xmm3, xmm3, xmm3\n\n# The loop. Every pass adds 32 durations.\n.LBB0_1:\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax]\n    vpaddq zmm0, zmm0, zmm4\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax + 32]\n    vpaddq zmm1, zmm1, zmm4\n    vpmovzxdq zmm4, ymmword ptr [rdi + 4*rax + 64]\n    vpmovzxdq zmm5, ymmword ptr [rdi + 4*rax + 96]\n    vpaddq zmm2, zmm2, zmm4\n    vpaddq zmm3, zmm3, zmm5\n    add rax, 32\n    cmp rax, 1024\n    jne .LBB0_1\n\n    # Add the running sums together, and return the result in rax.\n    vpaddq zmm0, zmm1, zmm0\n    vpaddq zmm0, zmm2, zmm0\n    vpaddq zmm0, zmm3, zmm0\n    vextracti64x4 ymm1, zmm0, 1\n    vpaddq zmm0, zmm0, zmm1\n    vextracti128 xmm1, ymm0, 1\n    vpaddq xmm0, xmm0, xmm1\n    vpshufd xmm1, xmm0, 238\n    vpaddq xmm0, xmm0, xmm1\n    vmovq rax, xmm0\n    vzeroupper\n    ret</code></pre>\n<p>Note that autovectorization is not unique to sums. Much of the time executing a\nquery (especially a relatively simple one) is spent in tight loops over batches\nlike this one, and the compiler can vectorize many of them in the same way\nwithout anyone writing a single SIMD instruction by hand.</p>\n<h2 id=\"compression\"><a href=\"#compression\">#Compression</a></h2>\n<p>So far, we&#39;ve only looked at data that is already in memory. In most database\nsystems, data lives on persistent storage (a disk, an SSD, or object storage\nlike S3), and bringing it into memory is usually the bottleneck of query\nexecution (in other words, queries are I/O bound). So the size of our data is\nvery important: the fewer bytes a query has to read, the less time it spends\nwaiting on I/O.</p>\n<p>The naive way to make the data smaller is to take each block of it and run it\nthrough a general-purpose compression algorithm.<a href=\"#user-content-fn-general-purpose\">19</a> This kind of\ncompression should be familiar to anyone who has ever dealt with zip files! It\ntreats the data as just a big pile of bytes, and it doesn&#39;t care what those\nbytes actually mean, which is why it works on everything (including both rows\nand columns).</p>\n<p>The problem is that this kind of compression is a &quot;black box&quot;: once a block is\ncompressed, the database can&#39;t see inside of it anymore. For example, if you\nwanted to read the one-millionth line of a zipped CSV file, there is no way to\njump straight to that line, so you would have to unzip (decompress) everything\nthat comes before it just to access a single line.<a href=\"#user-content-fn-csv-lines\">20</a> The ability to\nread any one piece of the data without reading the rest of it is called *random\naccess*, and this kind of compression is unable to support fast random access.</p>\n<p>A database system will have the exact same problem with black-box compressed\nblocks of data: to read the duration of ride 1004, it has to decompress the\nentire block (potentially multiple blocks!) that the ride lives in.</p>\n<p>This is another place where columns help. The values in a column all have the\nsame type, and they tend to be similar to each other, which means that a column\ncompresses much better than a row does. We can already see this in our example\nabove: <code>start_area</code> only has 3 distinct values, <code>bike_type</code> only has 2, and\n<code>ride_id</code> is always increasing.</p>\n<p>More importantly, we don&#39;t actually <em>need</em> to use black-box compression. We can\ninstead use lightweight encodings: simple schemes that compress the data\nwhile retaining the structure and the meaning of the values.<a href=\"#user-content-fn-encodings\">21</a> Instead\nof turning a column into a big pile of bytes, a lightweight encoding takes\nadvantage of one specific pattern in it (for example, a column with only a few\ndistinct values, or a column of numbers that are all small) to store the same\nvalues in less space.</p>\n<p>Retaining the structure means that we can keep random access. With most\nlightweight encodings, the database system can jump straight to the value that\nit wants without decoding everything around it.</p>\n<p>Retaining the <em>meaning</em> helps as well. Lightweight encodings are &quot;lighter\nweight&quot; than black-box compression, but they aren&#39;t free, since decoding them\nstill takes CPU time. However, because the encoded values still <em>mean</em>\nsomething, a query can often do its work directly on the encoded data without\ndecoding it first, which skips much of that cost. This computation over\ncompressed data is a form of &quot;late materialization&quot;.<a href=\"#user-content-fn-late-materialization\">22</a></p>\n<p>This is exactly how we built <a href=\"https://github.com/vortex-data/vortex\" rel=\"nofollow ugc noopener\">Vortex</a>, an\nopen-source, extensible columnar file format and data processing library. It has\na whole collection of lightweight encodings, and it can stack them on top of\neach other to make the data even smaller.</p>\n<blockquote><p>We&#39;ve written a lot about how this works. Check out our other blogs!</p>\n<ul><li><p><a href=\"https://spiraldb.com/blog/vortex-one-format-for-any-shape\" rel=\"nofollow ugc noopener\">Vortex: One Format for Any Shape</a></p><p>for an overview of how Vortex works</p></li><li><a href=\"https://spiraldb.com/blog/life-in-the-fastlanes\" rel=\"nofollow ugc noopener\">FastLanes</a> for integers</li><li><a href=\"https://spiraldb.com/blog/alp-rust-is-faster-than-c\" rel=\"nofollow ugc noopener\">ALP</a> for floats</li><li><a href=\"https://spiraldb.com/blog/compressing-strings-with-fsst\" rel=\"nofollow ugc noopener\">FSST</a> for strings</li><li><p><a href=\"https://spiraldb.com/blog/cascading-compression-with-btrblocks\" rel=\"nofollow ugc noopener\">BtrBlocks</a> for choosing an</p><p>encoding for each column</p></li><li><p><a href=\"https://spiraldb.com/blog/what-if-we-just-didnt-decompress-it\" rel=\"nofollow ugc noopener\">Push-down compute</a> for working</p><p>on compressed data</p></li><li><p><a href=\"https://spiraldb.com/blog/pattern-matching-strings-without-decompression\" rel=\"nofollow ugc noopener\"><code>LIKE</code> on compressed strings</a></p><p>without decompressing them</p></li></ul></blockquote>\n<h2 id=\"thinking-in-columns\"><a href=\"#thinking-in-columns\">#Thinking in columns</a></h2>\n<p>We started with data from a CSV file and one &quot;simple&quot; choice of storing data in\nrows vs columns. Yet we have seen just how much follows from that choice, as\nwell as the consequences of choosing one or the other.<a href=\"#user-content-fn-how-different\">23</a></p>\n<p>Those consequences are the reason that most database systems are built for\neither transactions or analytics, and not both.<a href=\"#user-content-fn-htap\">24</a> The way a database\nexecutes queries and the way it compresses data are both built on top of this\none choice, so it isn&#39;t something that a system can just flip later. A column\nstore&#39;s strength in serving analytical queries is exactly what makes it bad for\nreading and changing one record at a time, and the opposite is true for a row\nstore.</p>\n<p>There is also a lot more to columnar data than what we can fit in a single\nintroductory post. For example, we never talked about how a column store\nactually organizes its data on persistent storage,<a href=\"#user-content-fn-layouts\">25</a> how it avoids\nreading data that a query doesn&#39;t need,<a href=\"#user-content-fn-pruning\">26</a> how vectorized execution isn&#39;t\nthe only way to run a query more efficiently,<a href=\"#user-content-fn-compiled\">27</a> and we completely\nignored writes and modifications to data28 Each one of these topics is a\nwhole area of active research. If you want to keep going, the CMU database\ncourses are a great place to start, and all of their lectures are free to watch\nonline.<a href=\"#user-content-fn-next\">29</a></p>\n<p>In the future, we hope to post more about these kinds of topics, as we engage\nwith them quite a lot working at Spiral!</p>\n<h3 id=\"footnotes\">Footnotes</h3>\n<ol><li><p>In practice, a database can often skip records that it knows it doesn&#39;t</p><p> need, for example with an index, or with the minimum and maximum values it\n keeps for each block of data\n (<a href=\"https://spiraldb.com/blog/zone-maps-or-queries-go-brrr\" rel=\"nofollow ugc noopener\">zone maps</a>). But logically speaking,\n the answers still <em>depend</em> on every record. <a href=\"#user-content-fnref-index\">↩︎</a></p></li><li><p>Think of things like bank transfers and airline bookings: lots of small</p><p> operations (transactions) that read or change only a few records, all\n happening in parallel, potentially thousands of times per second. <a href=\"#user-content-fnref-oltp\">↩︎</a></p></li><li><p>The idea is a lot older than both of those systems.</p><p> <a href=\"https://doi.org/10.1145/318898.318923\" rel=\"nofollow ugc noopener\">A Decomposition Storage Model</a>\n (SIGMOD 1985) already proposed storing each column on its own. The CMU\n 15-445\n <a href=\"https://15445.courses.cs.cmu.edu/fall2026/notes/06-storage3.pdf\" rel=\"nofollow ugc noopener\">lecture notes on storage models</a>\n compare the two layouts in more detail. <a href=\"#user-content-fnref-dsm\">↩︎</a></p></li><li><p>These are generally queries that read a large part of a dataset, usually</p><p> worried about only a few of its columns, summarizing the data with counts,\n sums, and averages. <a href=\"#user-content-fnref-olap\">↩︎</a></p></li><li>Personally, I consider these fun... <a href=\"#user-content-fnref-fun\">↩︎</a></li><li><p>Apple&#39;s M-series chips use 128-byte cache lines, but the point remains the</p><p> same. <a href=\"#user-content-fnref-cache-line\">↩︎</a></p></li><li><p>This is 8 bytes each for <code>ride_id</code> and <code>started_at</code> (a 64-bit timestamp), 24</p><p> for the <code>String</code> (a pointer to the text, a length, and a capacity), 1 for\n <code>bike_type</code>, 3 bytes of padding for alignment, and 4 for <code>duration_min</code>.\n Note that the 24 bytes for <code>start_area</code> are specific to Rust&#39;s <code>String</code>. A\n real database will store strings differently. Also, Rust is free to reorder\n the fields of a struct unless you add <code>#[repr(C)]</code>, and <code>rustc</code> 1.99.1 does:\n it moves <code>start_area</code> to the front and the padding to the end. The struct is\n still 48 bytes with 3 bytes of padding either way, so we draw the fields in\n the order that we wrote them. <a href=\"#user-content-fnref-ride-size\">↩︎</a></p></li><li><p>An <a href=\"https://en.wikipedia.org/wiki/Database_index\" rel=\"nofollow ugc noopener\">index</a> is a separate data</p><p> structure (usually a <a href=\"https://en.wikipedia.org/wiki/B%2B_tree\" rel=\"nofollow ugc noopener\">B+ tree</a>)\n that maps a &quot;key&quot; (usually a unique primary key) like <code>1004</code> to the location\n of its stored record. This allows the database to quickly find the data\n instead of scanning the entire table to find it. See the CMU 15-445\n <a href=\"https://15445.courses.cs.cmu.edu/fall2026/notes/08-indexes1.pdf\" rel=\"nofollow ugc noopener\">lecture notes on indexes</a>\n for more detail. <a href=\"#user-content-fnref-lookup-index\">↩︎</a></p></li><li><p>These counts leave out the text of <code>start_area</code>. The 24 bytes of a <code>String</code></p><p> only point to the text, which lives somewhere else in memory, so actually\n reading the name of the neighborhood costs at least one more cache line.\n That is true for both layouts, though, so it doesn&#39;t change which one wins. <a href=\"#user-content-fnref-string-text\">↩︎</a></p></li><li><p><a href=\"https://www.cidrdb.org/cidr2005/papers/P19.pdf\" rel=\"nofollow ugc noopener\">MonetDB/X100</a>, the system</p><p>  that introduced this design, uses 1024 values per batch by default.\n  <a href=\"https://duckdb.org/docs/stable/internals/vector\" rel=\"nofollow ugc noopener\">DuckDB</a> uses 2048, and\n  <a href=\"https://datafusion.apache.org/user-guide/configs.html\" rel=\"nofollow ugc noopener\">DataFusion</a>\n  uses 8192. <a href=\"#user-content-fnref-batches\">↩︎</a></p></li><li><p>Also, a real database table will generally live on persistent storage (HDD,</p><p>  SSD) if the data is larger than memory, so the database will not be able to\n  load a whole column at once even if it wanted to. So the query has to read\n  the column in pieces anyways. <a href=\"#user-content-fnref-storage\">↩︎</a></p></li><li><p>The CMU 15-445</p><p>  <a href=\"https://15445.courses.cs.cmu.edu/fall2026/notes/13-queryexecution1.pdf\" rel=\"nofollow ugc noopener\">lecture notes on query execution</a>\n  go into much more detail, and the CMU 15-721 notes on\n  <a href=\"https://15721.courses.cs.cmu.edu/spring2024/notes/04-execution1.pdf\" rel=\"nofollow ugc noopener\">query processing</a>\n  and\n  <a href=\"https://15721.courses.cs.cmu.edu/spring2024/notes/06-vectorization.pdf\" rel=\"nofollow ugc noopener\">vectorized execution</a>\n  go further still. <a href=\"#user-content-fnref-query-execution\">↩︎</a></p></li><li><p>Named after <a href=\"https://doi.org/10.1109/69.273032\" rel=\"nofollow ugc noopener\">Volcano</a>, a query engine by</p><p>  <a href=\"https://scholar.google.com/citations?user=pdDeRScAAAAJ&amp;hl=en\" rel=\"nofollow ugc noopener\">Goetz Graefe</a>\n  from the early 90s. It is also sometimes called the &quot;iterator&quot; model, and\n  almost every row store still executes queries this way. <a href=\"#user-content-fnref-volcano\">↩︎</a></p></li><li><p>Vectorized execution comes from</p><p>  <a href=\"https://www.cidrdb.org/cidr2005/papers/P19.pdf\" rel=\"nofollow ugc noopener\">MonetDB/X100: Hyper-Pipelining Query Execution</a>\n  (CIDR 2005). The paper profiled MySQL on an analytical query and found that\n  the operations that do the actual work take only about 10% of the execution\n  time. X100&#39;s ran every operator on small vectors of values, which is where\n  the name comes from. <a href=\"#user-content-fnref-x100\">↩︎</a></p></li><li><p>Note that <em>vectorized execution</em> is the database processing values in</p><p>  batches, whereas <em>autovectorization</em> is the compiler emitting SIMD\n  instructions. They are separate but similar ideas. <a href=\"#user-content-fnref-two-vectors\">↩︎</a></p></li><li><p><a href=\"https://en.wikipedia.org/wiki/Automatic_vectorization\" rel=\"nofollow ugc noopener\">Autovectorization</a></p><p>  is easy to break, though. If <code>duration_min</code> were a float, LLVM would\n  <a href=\"https://llvm.org/docs/Vectorizers.html#reductions\" rel=\"nofollow ugc noopener\">not vectorize this sum</a>\n  by default: adding 8 values at a time changes the order of the additions,\n  and floating-point addition isn&#39;t associative, so the result could change. <a href=\"#user-content-fnref-autovectorization\">↩︎</a></p></li><li><p>8 and not 16 because every 32-bit duration is widened to 64 bits so that the</p><p>  sum doesn&#39;t overflow. <a href=\"#user-content-fnref-simd-width\">↩︎</a></p></li><li><p><a href=\"https://en.wikipedia.org/wiki/Loop_unrolling\" rel=\"nofollow ugc noopener\">Loop unrolling</a> helps here</p><p>  because each <code>vpaddq</code> has to wait for the previous one that wrote to the\n  same register, so with only one register, the additions would have to run\n  one after another. With four independent registers, the CPU can\n  <a href=\"https://llvm.org/docs/Vectorizers.html#partial-unrolling-during-vectorization\" rel=\"nofollow ugc noopener\">run several of them at the same time</a>. <a href=\"#user-content-fnref-unrolling\">↩︎</a></p></li><li><p>Zip files use an algorithm called</p><p>  <a href=\"https://en.wikipedia.org/wiki/Deflate\" rel=\"nofollow ugc noopener\">DEFLATE</a>. Databases tend to use\n  newer ones like <a href=\"https://en.wikipedia.org/wiki/Zstd\" rel=\"nofollow ugc noopener\">Zstandard</a> and\n  <a href=\"https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)\" rel=\"nofollow ugc noopener\">LZ4</a>, but the\n  idea is the same. <a href=\"#user-content-fnref-general-purpose\">↩︎</a></p></li><li><p>This is a bit of a lie. A plain CSV file doesn&#39;t have real random access</p><p>  since its lines have different lengths, so you can&#39;t know where line one\n  million starts without counting. A better example is black-box compressing a\n  <code>Vec&lt;u32&gt;</code> of durations, where value number N always starts at byte 4 × N.\n  Once the array is block-box compressed, we can no longer index into the\n  vector with random access. <a href=\"#user-content-fnref-csv-lines\">↩︎</a></p></li><li><p>Two recent papers on lightweight encodings are</p><p>  <a href=\"https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf\" rel=\"nofollow ugc noopener\">The FastLanes Compression Layout</a>\n  (VLDB 2023) and\n  <a href=\"https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf\" rel=\"nofollow ugc noopener\">BtrBlocks: Efficient Columnar Compression for Data Lakes</a>\n  (SIGMOD 2023). The CMU 15-721 lecture notes on data formats and encodings\n  (<a href=\"https://15721.courses.cs.cmu.edu/spring2024/notes/02-data1.pdf\" rel=\"nofollow ugc noopener\">part 1</a>,\n  <a href=\"https://15721.courses.cs.cmu.edu/spring2024/notes/03-data2.pdf\" rel=\"nofollow ugc noopener\">part 2</a>)\n  show how real file formats put encodings like these to use. <a href=\"#user-content-fnref-encodings\">↩︎</a></p></li><li><p>This term comes from research on column stores, where it essentially means</p><p>  waiting as long as possible (late) before putting the columns of a row back\n  together (materializing). See\n  <a href=\"https://doi.org/10.1109/ICDE.2007.367892\" rel=\"nofollow ugc noopener\">Materialization Strategies in a Column-Oriented DBMS</a>.\n  Compute over compressed data is the same idea one level lower: wait as long\n  as possible before decompressing a value. Executing a query directly on\n  compressed columns goes all the way back to\n  <a href=\"https://www.cs.umd.edu/~abadi/papers/abadisigmod06.pdf\" rel=\"nofollow ugc noopener\">Integrating Compression and Execution in Column-Oriented Database Systems</a>\n  (SIGMOD 2006), though Vortex takes this concept several steps further. <a href=\"#user-content-fnref-late-materialization\">↩︎</a></p></li><li><p><a href=\"https://www.cs.umd.edu/~abadi/papers/abadi-sigmod08.pdf\" rel=\"nofollow ugc noopener\">Column-Stores vs. Row-Stores: How Different Are They Really?</a></p><p>  (SIGMOD 2008) looks at what happens if you only change the storage. <a href=\"#user-content-fnref-how-different\">↩︎</a></p></li><li><p>People have tried to build one system that does both in the past</p><p>  (<a href=\"https://en.wikipedia.org/wiki/Hybrid_transactional/analytical_processing\" rel=\"nofollow ugc noopener\">HTAP</a>,\n  or hybrid transactional/analytical processing), but those attempts generally\n  didn&#39;t work out. Some newer systems seem to be bridging the gap, however.\n  <a href=\"https://cedardb.com/\" rel=\"nofollow ugc noopener\">CedarDB</a>, the commercial version of\n  <a href=\"https://umbra-db.com/\" rel=\"nofollow ugc noopener\">Umbra</a> (a research system from TU Munich), runs\n  transactions and analytics on just one engine and one copy of the data.\n  Databricks&#39; <a href=\"https://www.databricks.com/product/lakebase\" rel=\"nofollow ugc noopener\">Lakebase</a> keeps\n  Postgres (a row store) as the engine for transactional queries, but its\n  storage layer rewrites the same data into columnar formats in the\n  background, allowing an analytical engine to query it. <a href=\"#user-content-fnref-htap\">↩︎</a></p></li><li><p>Most formats split the table into large groups of rows and store the columns</p><p>  separately inside of each group (this is known as a &quot;row group&quot;). This idea\n  goes back to PAX, from\n  <a href=\"https://www.vldb.org/conf/2001/P169.pdf\" rel=\"nofollow ugc noopener\">Weaving Relations for Cache Performance</a>\n  (VLDB 2001), and it&#39;s how\n  <a href=\"https://parquet.apache.org/docs/file-format/\" rel=\"nofollow ugc noopener\">Apache Parquet</a> files work\n  today.\n  <a href=\"https://www.vldb.org/pvldb/vol17/p148-zeng.pdf\" rel=\"nofollow ugc noopener\">An Empirical Evaluation of Columnar Storage Formats</a>\n  (VLDB 2024) looks at how well these formats hold up on modern hardware and\n  workloads. For columns in memory instead of on disk, the standard is the\n  <a href=\"https://arrow.apache.org/docs/format/Columnar.html\" rel=\"nofollow ugc noopener\">Apache Arrow columnar format</a>. <a href=\"#user-content-fnref-layouts\">↩︎</a></p></li><li><p>The most common trick is to keep &quot;zone maps&quot; of the minimum and maximum</p><p>  value of every block of data so that a query can completely skip the blocks\n  that can&#39;t contain certain data. We wrote about this in\n  <a href=\"https://spiraldb.com/blog/zone-maps-or-queries-go-brrr\" rel=\"nofollow ugc noopener\">Zone maps, or “queries go brrr”</a>. <a href=\"#user-content-fnref-pruning\">↩︎</a></p></li><li><p>The other big approach is to compile each query into machine code that is</p><p>  specialized for exactly that query.\n  <a href=\"https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf\" rel=\"nofollow ugc noopener\">Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask</a>\n  (VLDB 2018) compares the two approaches, and neither one is a clear winner. <a href=\"#user-content-fnref-compiled\">↩︎</a></p></li><li><p>Changing data can be expensive in a column store because a single new record</p><p>  has to go to a different place for each of its columns.\n  <a href=\"https://www.vldb.org/archives/website/2005/program/paper/thu/p553-stonebraker.pdf\" rel=\"nofollow ugc noopener\">C-Store</a>\n  (VLDB 2005) deals with this by keeping a small store that is built for\n  writes next to the big one that is built for reads, and moving data from one\n  to the other in the background. <a href=\"#user-content-fnref-writes\">↩︎</a></p></li><li><p><a href=\"https://15445.courses.cs.cmu.edu/fall2026/schedule.html\" rel=\"nofollow ugc noopener\">CMU 15-445</a> is the</p><p>  introductory course\n  (<a href=\"https://www.youtube.com/playlist?list=PLSE8ODhjZXjYMAgsGH-GtY5rJYZ6zjsd5\" rel=\"nofollow ugc noopener\">Fall 2025 lecture videos</a>),\n  and <a href=\"https://15721.courses.cs.cmu.edu/spring2024/schedule.html\" rel=\"nofollow ugc noopener\">CMU 15-721</a>\n  is the advanced one\n  (<a href=\"https://www.youtube.com/playlist?list=PLSE8ODhjZXjYa_zX-KeMJui7pcN1rIaIJ\" rel=\"nofollow ugc noopener\">lecture videos</a>).\n  Note that the author of this post learned most of this material from the CMU\n  courses! If you&#39;d rather read,\n  <a href=\"https://ir.cwi.nl/pub/21772/1900000024-Abadi-Vol5-DBS-024.pdf\" rel=\"nofollow ugc noopener\">The Design and Implementation of Modern Column-Oriented Database Systems</a>\n  (2013) is a survey of the whole field. <a href=\"#user-content-fnref-next\">↩︎</a></p></li></ol>","headings":[{"level":2,"text":"#Row stores and column stores","id":"row-stores-and-column-stores"},{"level":3,"text":"#Rows and columns in memory","id":"rows-and-columns-in-memory"},{"level":3,"text":"#Reading only the columns you need","id":"reading-only-the-columns-you-need"},{"level":2,"text":"#Vectorized execution","id":"vectorized-execution"},{"level":2,"text":"#Compression","id":"compression"},{"level":2,"text":"#Thinking in columns","id":"thinking-in-columns"},{"level":3,"text":"Footnotes","id":"footnotes"}]}}