3 ms·

Say you have a billion records in your table. If you want to filter the records on a column which has values that are on average 30 bytes, then an index on that

Say you have a billion records in your table. If you want to filter the records on a column which has values that are on average 30 bytes, then an index on that column would be 30GB (uncompressed). It becomes extremely impractical to hold those indices in memory if you have several / dozens / hundreds. The problem with row based database structures is that the data between any two rows can vary in length, so if scanning across rows on disk for a column's value, you need metadata that points at the start of each column. That means the process of scanning across the data on disk involves a _lot_ of jumping around; less of a problem on SSDs than it was on spinning platters, but still work. The alternate approach is to store columns together on disk. That means that when performing a query that filters based on values in a given column, you can scan sequential areas on disk, which is much much faster. Of course, if you now want to assemble rows based on your filter, you need to use the metadata about where related values are in each other column in order to assemble those rows, but hopefully you have a much smaller set of records that you need to do this over. (It's cheaper to assemble 10k matching rows across a set of columns than it is to jump across a billion unaligned columns to filter them in the first place.)

ollien 3y ago
One thing I've seen about other columnar databases (e.g. Clickhouse) is that they're bad at k/v style lookups. Why is that? Your explanation would make me think otherwise, as we would be able to quickly scan the columns using our sequential reads, ideally.
- smallerfish 3y ago
  1) If they're only using on disk indices, it'll be slower to look up any one record than it would be if the index was in memory (particularly true if a good chunk of the data was in memory also) 2) The operation of retrieving a full row of data is more expensive in a column based db than in a row based db, because in row based the data for the row is contiguous on disk. So row based is likely optimal if your data size works with that architecture. (And, to be clear, row based _can_ work with billions of rows, if you're thoughtful about what kind of querying you'll be doing against such tables, and how you maintain them.)
- NortySpock 3y ago
  Think of columnar data as being run-length compressed. (If you have 100 rows of "1 Fizz" followed by 200 rows of "1 Buzz", followed by one "1 Fizz" you can store that as "100:1:Fizz;200:1:Buzz;1:1:Fizz".) Then, a mere 30 bytes of IO + a quick sum tells you that you sold 101 Fizz and 200 Buzz from the widget factory this quarter. Maybe the first Fizz is how many you sold in the USA and the second Fizz is how many you sold in Canada, so it becomes easy to do by-region reporting. However, unpacking the column that has all your individual transaction IDs and linking it to the individual single sale of one Fizz takes a lot of lookups. So untangling individual transactions becomes slow (though not impossible).

ollien 3y ago

One thing I've seen about other columnar databases (e.g. Clickhouse) is that they're bad at k/v style lookups. Why is that? Your explanation would make me think otherwise, as we would be able to quickly scan the columns using our sequential reads, ideally.

smallerfish 3y ago
1) If they're only using on disk indices, it'll be slower to look up any one record than it would be if the index was in memory (particularly true if a good chunk of the data was in memory also) 2) The operation of retrieving a full row of data is more expensive in a column based db than in a row based db, because in row based the data for the row is contiguous on disk. So row based is likely optimal if your data size works with that architecture. (And, to be clear, row based _can_ work with billions of rows, if you're thoughtful about what kind of querying you'll be doing against such tables, and how you maintain them.)
NortySpock 3y ago
Think of columnar data as being run-length compressed. (If you have 100 rows of "1 Fizz" followed by 200 rows of "1 Buzz", followed by one "1 Fizz" you can store that as "100:1:Fizz;200:1:Buzz;1:1:Fizz".) Then, a mere 30 bytes of IO + a quick sum tells you that you sold 101 Fizz and 200 Buzz from the widget factory this quarter. Maybe the first Fizz is how many you sold in the USA and the second Fizz is how many you sold in Canada, so it becomes easy to do by-region reporting. However, unpacking the column that has all your individual transaction IDs and linking it to the individual single sale of one Fizz takes a lot of lookups. So untangling individual transactions becomes slow (though not impossible).