4 ms·

I stumbled upon Google's whitepaper on Dremel. IIRC it explained how to store the data in columnar format, but I didn't quite get how that translated into quick

I stumbled upon Google's whitepaper on Dremel. IIRC it explained how to store the data in columnar format, but I didn't quite get how that translated into quick queries. Happen to know where I can look to better understand how it works?

TallGuyShort 11y ago
I'll take a stab at explaining it myself: "transactional queries" are faster in a traditional format because they access many columns in few rows. For instance, if you want to log in to a website, you access the username, password, and possibly other authentication factors for a single user: this ends up being faster if you can go to the user's row, and then read all those fields in a contiguous scan. "Analytical queries" are faster in a column-based format, because you're doing things like computing the correlation between 2 variables. Instead of looking at many columns in a specific row, you're looking at most of the data in a few columns. So instead of reading a whole row at once, it would be nice to skip the columns you don't care about and just grab big chunks of two or three columns. Does that make sense? edit: For a long time I was confused about why HBase was described as a columnar data store when access was still pretty row-based. I think the reason is because you group columns into column families which can be stored and retrieved separately, so you still get some of the benefit of a true column-oriented store.
- vdm 11y ago
  > For a long time I was confused about why HBase was described as a columnar data store when access was still pretty row-based The term was overloaded by column-family stores, which were often referred to as just 'column stores', probably by people who were not aware of systems like Vertica and MonetDB. http://dbmsmusings.blogspot.co.uk/2010/03/distinguishing-two-major-types-of_29.html http://dbmsmusings.blogspot.co.uk/2010/03/distinguishing-two...
infinite8s 11y ago
This is a good high level overview from Twitter (who created Parquet): https://blog.twitter.com/2013/dremel-made-simple-with-parquet https://blog.twitter.com/2013/dremel-made-simple-with-parque...
ww520 11y ago
Column-based table store the values of each column together. Two properties make them suitable for fast query against a column: data locality and compressible data. Since the column values are stored together, more of them can be crammed into a data page. Querying the data of a column can process much more data per page load than row-based, whereas a row-based table's data page has all other columns. The values of a column can be stored in a sorted order, which is highly compressible, enabling cramming even more data into a data page. You can get much more data with each data page loading. E.g. The column Name is stored as sorted along with the associated row id. Name, (row id) -------------- Joan, (101) Joanna, (307) John, (15) John, (32) John, (6) Johnson, (31) Johnson, (44) The duplicate names can be stored as one: Name, (row id) -------------- Joan, (101) Joanna, (307) John, (15,32,6) Johnson, (31,44) Prefix encoding can further compress the sorted data: Name, (row id) -------------- Joan, (101) 4+na, (307) 2+hn, (15,32,6) 4+son, (31,44) Now imagine the query: select count(Name) from Table. Scanning the Name column values only touches 4 records right next to each other in a data page and adds up each record's reference row ids. Select Name from Table where Name like "John%" would do a binary search down the sorted names, load two records 2+hn and 4+son, and expand them into 5 names.

TallGuyShort 11y ago

I'll take a stab at explaining it myself: "transactional queries" are faster in a traditional format because they access many columns in few rows. For instance, if you want to log in to a website, you access the username, password, and possibly other authentication factors for a single user: this ends up being faster if you can go to the user's row, and then read all those fields in a contiguous scan. "Analytical queries" are faster in a column-based format, because you're doing things like computing the correlation between 2 variables. Instead of looking at many columns in a specific row, you're looking at most of the data in a few columns. So instead of reading a whole row at once, it would be nice to skip the columns you don't care about and just grab big chunks of two or three columns. Does that make sense? edit: For a long time I was confused about why HBase was described as a columnar data store when access was still pretty row-based. I think the reason is because you group columns into column families which can be stored and retrieved separately, so you still get some of the benefit of a true column-oriented store.

vdm 11y ago
> For a long time I was confused about why HBase was described as a columnar data store when access was still pretty row-based The term was overloaded by column-family stores, which were often referred to as just 'column stores', probably by people who were not aware of systems like Vertica and MonetDB. http://dbmsmusings.blogspot.co.uk/2010/03/distinguishing-two-major-types-of_29.html http://dbmsmusings.blogspot.co.uk/2010/03/distinguishing-two...

infinite8s 11y ago

This is a good high level overview from Twitter (who created Parquet): https://blog.twitter.com/2013/dremel-made-simple-with-parquet https://blog.twitter.com/2013/dremel-made-simple-with-parque...

ww520 11y ago

Column-based table store the values of each column together. Two properties make them suitable for fast query against a column: data locality and compressible data. Since the column values are stored together, more of them can be crammed into a data page. Querying the data of a column can process much more data per page load than row-based, whereas a row-based table's data page has all other columns. The values of a column can be stored in a sorted order, which is highly compressible, enabling cramming even more data into a data page. You can get much more data with each data page loading. E.g. The column Name is stored as sorted along with the associated row id. Name, (row id) -------------- Joan, (101) Joanna, (307) John, (15) John, (32) John, (6) Johnson, (31) Johnson, (44) The duplicate names can be stored as one: Name, (row id) -------------- Joan, (101) Joanna, (307) John, (15,32,6) Johnson, (31,44) Prefix encoding can further compress the sorted data: Name, (row id) -------------- Joan, (101) 4+na, (307) 2+hn, (15,32,6) 4+son, (31,44) Now imagine the query: select count(Name) from Table. Scanning the Name column values only touches 4 records right next to each other in a data page and adds up each record's reference row ids. Select Name from Table where Name like "John%" would do a binary search down the sorted names, load two records 2+hn and 4+son, and expand them into 5 names.