4 ms·

Column-oriented dbs are essentially a "heroic engineering" way to optimize a datastore for a particular workload -- continuous-read-heavy-batch-processing -- by

by neilc 18y ago

Column-oriented dbs are essentially a "heroic engineering" way to optimize a datastore for a particular workload -- continuous-read-heavy-batch-processing -- by engineering around the performance peculiarities of traditional hard drives. Another way to view this is simply that column stores are a more appropriate storage technique for read-intensive workloads on magnetic disks. When you characterize column stores as "engineering around" the "pecularities" of HDDs, you make it seem like column stores are a workaround and row stores are the "natural" approach, which I don't think is the case. Implementing a column store from scratch is not significantly harder/easier than building a row store from scratch, AFAIK (albeit there is probably more expertise on how to do the latter). the rise of ssd may make this engineering effort essentially useless outside of a handful of niches (essentially, the niches reduce to: data volumes too large to economically fit into ssd within the foreseeable future) Given the daunting rise of data volumes in the data warehousing market, that makes for a pretty big niche. It will be a long time before SSDs are cost effective for the DW market, I think.

frig 18y ago
There's something of an argument for naturalness wrt rows-versus-columns, but it's not conclusive. When it's developed it's usually stated as that a column store encompasses a multiplication of metadata (eg: suppose each row has some kind of row id; you want to support lookup of the value in a given column for a given row; thus in a rowstore you minimally only need one lookup aide (to get you to where that row is) to handle a lookup for any column, but in a column store you arguably need one lookup aide per column (to tell you how to find the point in that column's column store where the value for that row is). It's never been an amazingly compelling argument to me, either, but there it is; the whole thing strikes me as 'semantical confusion', as what we're really talking about (row-vs-column) is a consequence of not taking the relational model to its logical conclusion: - a "table" like this: the table T with row = (unique #, column A, column B, column C, ..., column ) - is really a materialized view of this view (V): table_A has row (unique #, column A), ...,table_N has (unique #, column N); V = join table_A,...,table_N on 'unique #' in the obvious way ...and a column-oriented data store is just a DB that stores data in a more-fully normalized form (often with tricks to minimize or eliminate the need to include the unique# in some or all of the table_Is, keeping just some sort of index). OR: the distinction between row and column stores -- at a high enough level of abstraction -- boils down to questions of how fully-normalized the physical storage's data model is vis-a-vis how normalized the user-facing data model is. In the hard-disk world your choice of physical layout matters a lot; it's possible the evolution of ssds will make the difference between 'row' and 'column' orientation a lot less material (as we've already talked about). The really crazy thing you could consider doing is go one step further and do something like: say T = (unique #, customer_name, library_size (integer)). (library size is like 'how many books does this dude own') Step 1: T -> V like above ( table_a = (unique #, customer_name), table_b = (unique #, library_size)) Step 2: - let table_c = (unique_library_size #, library_size), constructed from table_b as basically 'select distinct library_size into table_c' - then let table_b' = (unique #, unique_library_size #) (and a similar transform for table_a, but we'll stick with table_b for now) Doing this is crazy talk on a disk-based system: you're adding a lookup, but for what? But if lookups are essentially free, this has the potential to heavily cut down on the amount of data you need to store (in cases where you have N rows but only K << N distinct values) even before you start applying the obvious compression techniques to the stored data. As datasets grow very large, it'll often be the case that we have K << N; this won't be the case for, eg, google's index of web page contents, but for something like 'how many cases of X did walmart W sell on day D' or 'how many billable seconds was call #1234567 on date DDMMYYYY' it's hard to imagine K isn't << N much of the time for some of the columns. I think that's what the author's trying to very obliquely get at; petabytes might be a stretch, but with sufficiently-cheap lookups a lot of compression-by-indirection may become feasible, which might let you really reduce the amount of persistent storage you need, which'd make ssds extend into workloads you might expect to remain out of cost-effectiveness for much longer. Speculative; heck yes.
- neilc 18y ago
  if lookups are essentially free, this has the potential to heavily cut down on the amount of data you need to store Assuming that the size of unique_library_size # is smaller than library_size. That's unlikely to be true for this example, but I get what you're driving at. However, column stores basically do this already: for example, you might store the library_size column ordered by size, and then compress it using either RLE or differential encoding (data item i is stored as a delta against data item i-1).
  - frig 18y ago
    Oh agreed, (I was assuming I could easily use eg 20 unpadded bits or whatnot for unique_library_size # but not necessarily get away with it easily for library_size; when that's the case it's always true that unique_library_size # needs less storage than library_size). Edit: to correct...it's always true that unique_libary_size # needs less storage than library_size except under very unlikely circumstances (...circumstances which get ruled out anyways if you do a more-granular calculation for when this strategy would make sense to consider).

by neilc 18y ago

frig 18y ago

There's something of an argument for naturalness wrt rows-versus-columns, but it's not conclusive. When it's developed it's usually stated as that a column store encompasses a multiplication of metadata (eg: suppose each row has some kind of row id; you want to support lookup of the value in a given column for a given row; thus in a rowstore you minimally only need one lookup aide (to get you to where that row is) to handle a lookup for any column, but in a column store you arguably need one lookup aide per column (to tell you how to find the point in that column's column store where the value for that row is). It's never been an amazingly compelling argument to me, either, but there it is; the whole thing strikes me as 'semantical confusion', as what we're really talking about (row-vs-column) is a consequence of not taking the relational model to its logical conclusion: - a "table" like this: the table T with row = (unique #, column A, column B, column C, ..., column ) - is really a materialized view of this view (V): table_A has row (unique #, column A), ...,table_N has (unique #, column N); V = join table_A,...,table_N on 'unique #' in the obvious way ...and a column-oriented data store is just a DB that stores data in a more-fully normalized form (often with tricks to minimize or eliminate the need to include the unique# in some or all of the table_Is, keeping just some sort of index). OR: the distinction between row and column stores -- at a high enough level of abstraction -- boils down to questions of how fully-normalized the physical storage's data model is vis-a-vis how normalized the user-facing data model is. In the hard-disk world your choice of physical layout matters a lot; it's possible the evolution of ssds will make the difference between 'row' and 'column' orientation a lot less material (as we've already talked about). The really crazy thing you could consider doing is go one step further and do something like: say T = (unique #, customer_name, library_size (integer)). (library size is like 'how many books does this dude own') Step 1: T -> V like above ( table_a = (unique #, customer_name), table_b = (unique #, library_size)) Step 2: - let table_c = (unique_library_size #, library_size), constructed from table_b as basically 'select distinct library_size into table_c' - then let table_b' = (unique #, unique_library_size #) (and a similar transform for table_a, but we'll stick with table_b for now) Doing this is crazy talk on a disk-based system: you're adding a lookup, but for what? But if lookups are essentially free, this has the potential to heavily cut down on the amount of data you need to store (in cases where you have N rows but only K << N distinct values) even before you start applying the obvious compression techniques to the stored data. As datasets grow very large, it'll often be the case that we have K << N; this won't be the case for, eg, google's index of web page contents, but for something like 'how many cases of X did walmart W sell on day D' or 'how many billable seconds was call #1234567 on date DDMMYYYY' it's hard to imagine K isn't << N much of the time for some of the columns. I think that's what the author's trying to very obliquely get at; petabytes might be a stretch, but with sufficiently-cheap lookups a lot of compression-by-indirection may become feasible, which might let you really reduce the amount of persistent storage you need, which'd make ssds extend into workloads you might expect to remain out of cost-effectiveness for much longer. Speculative; heck yes.

neilc 18y ago
if lookups are essentially free, this has the potential to heavily cut down on the amount of data you need to store Assuming that the size of unique_library_size # is smaller than library_size. That's unlikely to be true for this example, but I get what you're driving at. However, column stores basically do this already: for example, you might store the library_size column ordered by size, and then compress it using either RLE or differential encoding (data item i is stored as a delta against data item i-1).
- frig 18y ago
  Oh agreed, (I was assuming I could easily use eg 20 unpadded bits or whatnot for unique_library_size # but not necessarily get away with it easily for library_size; when that's the case it's always true that unique_library_size # needs less storage than library_size). Edit: to correct...it's always true that unique_libary_size # needs less storage than library_size except under very unlikely circumstances (...circumstances which get ruled out anyways if you do a more-granular calculation for when this strategy would make sense to consider).