4 ms·

Then he's criticising the applicability of column stores to a mode of use for which they're not designed. ah, ok. That makes sense, agreed. Here is question t

by jsrn 17y ago

Then he's criticising the applicability of column stores to a mode of use for which they're not designed. ah, ok. That makes sense, agreed. Here is question to you - not directly concerning the article - If we talk about all those new (or not so new) hash databases (a.k.a. "key/value stores" like Amazon Simple db, Google's equivalent which they make available with Google App Engine, Berkeley DB etc.) and if we talk about OLTP: I have been thinking lateley that those stores that often require the programmer to denormalize and trade relational features for performance could soon become largely irrelevant SSDs, and soon (OLTP databases are often not that big in my experience [compared to OLAP databases], many should fit into an SSD today). In contrast to column stores those key/value stores are explicitely marketed for transaction processing (if a RDBMS doesn't scale enough). As I understand it, most of the time performance and scaling problems with relational databases result from the database being disk bound - a problem that should largely vanish with SSDs. Do you agree?

frig 17y ago
Yeah, that guy's writing is muddled and obscure, but I think your points are closer to (what I think is) his intended point: 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. Clearly this is a sensible strategy for optimizing a datastore for certain workloads: at the moment that strategy delivers material performance improvements in the scenarios it's designed for (material enough that if the performance of your system on those workloads is economically important to you, it's worth the cost to build or buy a system that'd significantly speed things up). What I think he's saying is that 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): - in a storage medium with heavy seek times, the engineering effort to implement a column store (instead of just using an off-the-shelf rdbms) can pay off in a somewhat broad range of usages - in ssd-ish storage media, the engineering effort isn't going to be worth the benefit, most of the time, compared to just using a stock rdbms The mention of the TRM fits into this picture of his intended claim. If you're not familiar the TRM is a mystery shrouded in an enigma: a bunch of big, credible names in the database world claimed have invented a radical new way of implementing the backend of a relational database that would've offered radically better performance characteristics (essentially it made joins so unbelievably 'cheap' that it was no longer necessary to denormalize for performance; supposedly the more-normalized you went the better TRM would perform). The issue with the TRM (transrelational model) is that: - the supposed core concept is patented, but doesn't explain en toto how it'd work (for obvious reason) - there's a ton of secrecy and ndas and so on surrounding anyone and everyone who got a good glimpse of the full picture -- the core inventors seem extremely protective of their ip, to the point pretty much nothing material has leaked about it's supposed workings - the company that was supposedly doing the first commercial implementation folded, ostensibly for non-technical reasons but again it's so secretive no one really knows what happened So it's a big mystery. There's basically a couple schools of thought on it: - it does actually work, but a comedy of errors / business climate / personality conflicts / whatever have prevented it from either being commercially implemented or from having a fuller picture of its workings disclosed publicly. Things have been quiet since then due to the protectiveness and penchant for secrecy on part of the principals. - it looked good on paper, but in doing the actual implementation some unavoidable complication turned up that prevented it from obtaining the needed performance (either at the time -- 2005ish -- or forever). The big names associated with it have kept quiet since then partly out of embarrassment (publicly endorsing a flop, kinda like hawking endorsing a free energy machine) and partly again out of concern for the principals' protectiveness - it was some kind of hypey thing that blew up in their faces; essentially a belief they could attract funding and customers by virtue of their reputations and claims of a revolutionary approach, combined with a belief that they could do an awesome-enough imlpementation of a non-revolutionary datastore approach -- basically do a best-practices, clean-room build of the current state of the art -- that no one would be the wiser I tend to think the second option is the likeliest story. All of that is a long windup for a very quick pitch: Assuming the TRM wasn't just bunk it would then be one of two things: - heroic engineering to bring revolutionary performance gains to systems built around disk-based storage - some kind of heroic datastore engineering that'd work better with a more ram-like storage system (eg ssds) That's a bit of a non-answer answer, but the connection to his main line of reasoning is something like: - if it's the former, then it's another example of heroic engineering made irrelevant by ssds, as even a 'traditional' rdbms can be made similarly performant on an ssd without all that effort; this is my take on the author's opinion - if it's the latter, then maybe there's something to be gleaned from it; I don't think this is what the author thinks So, yeah: from reading the rest of his blog (posts are wordy, but there's not that many of them) I think he's got the following idea: - implementing a traditional rdbms is hard, but mainly b/c of all the work you have to do to make it not perform like a dog under - ssds radically shake up the assumed performance contours of your persistent storage, enough so that a lot of the specifics designing an rdbms for performance might change - additionally, this guy has the impression this implementation might be "easy"; that is, a lot less work to do compared to writing a traditional rdbms from scratch There you have it, I think.
- neilc 17y 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 17y 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.
AlisdairO 17y ago
OLTP workloads will certainly be accelerated by SSDs. They tend to involve a lot of random reads/writes, and the former in particular are massively accelerated by SSDs. The latter seem to be getting better as the technology matures. I think there is a question mark over SSD durability during very large quantities of random writes - they erase/rewrite a whole load of data for each small change, so those figures about the amount of data you can write to the disk before it fails might be approached unexpectedly rapidly. Anyway, basically, yes, SSDs are ideal for OLTP, and will likely be fast enough that you can cut back on denormalisation significantly. The trading of the features of traditional RDBMSs (ACID vs BASE, etc) is often an artifact of database distribution, however, and that won't change with the introduction of SSDs. OLTP databases that are small enough to fit on one of today's SSDs shouldn't really be a problem for a half-decent existing relational DBMS anyway. Stonebraker was actually involved in a paper that talks about OLTP in main memory, and I would commend that to you: http://cs-www.cs.yale.edu/homes/dna/vldb07hstore.pdf http://cs-www.cs.yale.edu/homes/dna/vldb07hstore.pdf . Main memory has some similar-ish characteristics to SSDs (lowish latency, high transfer rate), so it might be of interest. Sorry if this post is a bit confused, just getting it in before I fall asleep ;).

by jsrn 17y ago

frig 17y ago

Yeah, that guy's writing is muddled and obscure, but I think your points are closer to (what I think is) his intended point: 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. Clearly this is a sensible strategy for optimizing a datastore for certain workloads: at the moment that strategy delivers material performance improvements in the scenarios it's designed for (material enough that if the performance of your system on those workloads is economically important to you, it's worth the cost to build or buy a system that'd significantly speed things up). What I think he's saying is that 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): - in a storage medium with heavy seek times, the engineering effort to implement a column store (instead of just using an off-the-shelf rdbms) can pay off in a somewhat broad range of usages - in ssd-ish storage media, the engineering effort isn't going to be worth the benefit, most of the time, compared to just using a stock rdbms The mention of the TRM fits into this picture of his intended claim. If you're not familiar the TRM is a mystery shrouded in an enigma: a bunch of big, credible names in the database world claimed have invented a radical new way of implementing the backend of a relational database that would've offered radically better performance characteristics (essentially it made joins so unbelievably 'cheap' that it was no longer necessary to denormalize for performance; supposedly the more-normalized you went the better TRM would perform). The issue with the TRM (transrelational model) is that: - the supposed core concept is patented, but doesn't explain en toto how it'd work (for obvious reason) - there's a ton of secrecy and ndas and so on surrounding anyone and everyone who got a good glimpse of the full picture -- the core inventors seem extremely protective of their ip, to the point pretty much nothing material has leaked about it's supposed workings - the company that was supposedly doing the first commercial implementation folded, ostensibly for non-technical reasons but again it's so secretive no one really knows what happened So it's a big mystery. There's basically a couple schools of thought on it: - it does actually work, but a comedy of errors / business climate / personality conflicts / whatever have prevented it from either being commercially implemented or from having a fuller picture of its workings disclosed publicly. Things have been quiet since then due to the protectiveness and penchant for secrecy on part of the principals. - it looked good on paper, but in doing the actual implementation some unavoidable complication turned up that prevented it from obtaining the needed performance (either at the time -- 2005ish -- or forever). The big names associated with it have kept quiet since then partly out of embarrassment (publicly endorsing a flop, kinda like hawking endorsing a free energy machine) and partly again out of concern for the principals' protectiveness - it was some kind of hypey thing that blew up in their faces; essentially a belief they could attract funding and customers by virtue of their reputations and claims of a revolutionary approach, combined with a belief that they could do an awesome-enough imlpementation of a non-revolutionary datastore approach -- basically do a best-practices, clean-room build of the current state of the art -- that no one would be the wiser I tend to think the second option is the likeliest story. All of that is a long windup for a very quick pitch: Assuming the TRM wasn't just bunk it would then be one of two things: - heroic engineering to bring revolutionary performance gains to systems built around disk-based storage - some kind of heroic datastore engineering that'd work better with a more ram-like storage system (eg ssds) That's a bit of a non-answer answer, but the connection to his main line of reasoning is something like: - if it's the former, then it's another example of heroic engineering made irrelevant by ssds, as even a 'traditional' rdbms can be made similarly performant on an ssd without all that effort; this is my take on the author's opinion - if it's the latter, then maybe there's something to be gleaned from it; I don't think this is what the author thinks So, yeah: from reading the rest of his blog (posts are wordy, but there's not that many of them) I think he's got the following idea: - implementing a traditional rdbms is hard, but mainly b/c of all the work you have to do to make it not perform like a dog under - ssds radically shake up the assumed performance contours of your persistent storage, enough so that a lot of the specifics designing an rdbms for performance might change - additionally, this guy has the impression this implementation might be "easy"; that is, a lot less work to do compared to writing a traditional rdbms from scratch There you have it, I think.

neilc 17y 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 17y 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.

AlisdairO 17y ago

OLTP workloads will certainly be accelerated by SSDs. They tend to involve a lot of random reads/writes, and the former in particular are massively accelerated by SSDs. The latter seem to be getting better as the technology matures. I think there is a question mark over SSD durability during very large quantities of random writes - they erase/rewrite a whole load of data for each small change, so those figures about the amount of data you can write to the disk before it fails might be approached unexpectedly rapidly. Anyway, basically, yes, SSDs are ideal for OLTP, and will likely be fast enough that you can cut back on denormalisation significantly. The trading of the features of traditional RDBMSs (ACID vs BASE, etc) is often an artifact of database distribution, however, and that won't change with the introduction of SSDs. OLTP databases that are small enough to fit on one of today's SSDs shouldn't really be a problem for a half-decent existing relational DBMS anyway. Stonebraker was actually involved in a paper that talks about OLTP in main memory, and I would commend that to you: http://cs-www.cs.yale.edu/homes/dna/vldb07hstore.pdf http://cs-www.cs.yale.edu/homes/dna/vldb07hstore.pdf . Main memory has some similar-ish characteristics to SSDs (lowish latency, high transfer rate), so it might be of interest. Sorry if this post is a bit confused, just getting it in before I fall asleep ;).