http://www.openlinksw.com/weblog/dav/dav-blog-1/
OpenLink Community Blog
A Collection of blogs by OpenLink Staff
OpenLink Software
kidehen@openlinksw.com
2012-02-11T04:32:10Z
Virtuoso Universal Server 05.12.3041
http://www.openlinksw.com/weblog/public/images/vbloglogo.gif
LOD2 Plenary and Review: Semanticist, Think Database!
http://www.openlinksw.com/blog/vdb/blog/?id=1700
2011-09-30T21:02:01Z
<p>Last week the <a href="http://lod2.eu/" id="link-id0x57d7368">LOD2 FP7 project</a> had its first review, preceded by its third plenary meeting.</p> <p>Before this, we did, <a href="http://www.openlinksw.com/weblog/oerling/?id=1683" id="link-id0x579c950">as promised</a>, get the column store and vectored execution capabilities of Virtuoso 7 Single-Server Edition extended to Virtuoso 7 Cluster Edition. More interesting still, we decoupled storage from the database server process, so now database files can migrate between server processes. This means that clusters are now elastic, i.e., new servers can be added to a cluster and the load can be redistributed without reloading the data.</p> <p>These things were long planned, but now are done. Measurements will be published in some weeks, as part of CWI's continued running of RDF store benchmarks, per the LOD2 plan.</p> <p>Doing the column store and elastic cluster is work enough, so I do not in general participate in support or consultancy or the like. This has some pros and cons. On the plus side, there is a relative lack of noise and a very clear idea of focus. Of course, this work is most highly applied, thus always informed by use cases, thus forgetting what ought to be done out there is not the problem. Rather, the problem is forgetting how things in fact <i>are</i> done as opposed to how they <i>could or should be</i> done.</p> <p>To cut a long story short, it has become clear to me that the DBMS must tell the application developer what to do. Of course, the application developer could also look at performance metrics, but they do not, and explaining these metrics is too much work and yields no lasting benefit. Developers will produce all kinds of performance diagnostic traces if requested, but going through this song and dance can also be avoided by the right automation.</p> <p>So, I will introduce two new product features called <i><b>Wazzup?</b></i> and <i><b>Saywhat?</b></i> </p> <p> <b>Wazzup?</b> is answered by a mood line, like "Heavily disk bound: 100G more memory will give 10x speedup" or "Network bound: Processing in larger batches will give 5x more throughput" and <b>Saywhat?</b> is answered by some commentary on the user's last action, for example "there is no ?order with o_totalprice < 0" or "there is no property O_misspelledtotallprrice."</p> <p> <b>Wazzup?</b> is about overall system state, and <b>Saywhat?</b> is about the user session, specifically query plans. But an explanation of a query plan is not understandable, so this will just point out some salient facts, like the reason why the answer comes out empty.</p> <p>The other thing that came to my attention is the fact that a user has no instinctive feel for <a href="http://dbpedia.org/page/Extract,_transform,_load" id="link-id0x527eb88">ETL</a>. A database person takes it for a self-evident truth that data is loaded in bulk, but the application developer does not think of that. Likewise, the line between warehousing and federating is not instinctively felt; actually the question is not even posed in these terms. So one will find Web protocols and end-points and glue code on the app server when one ought to have ETL and adequate hardware for running the consolidated database.</p> <p>Further, under-provisioning of equipment is endemic with semanticists. The Semantic Web gets a needlessly bad rap just because we find too much data on too little equipment. For example, I was surprised to learn that the Linked Geodata demo ran on only 16 GB RAM and 6 processor cores with 2 billion triples and 350 million points in a geo index. Now, even with our greatest space efficiency advances, there is no way this will run from memory.</p> <p>It is not that the Web 2.0 stack is necessarily efficient (we hear the wildest stories of lack of database understanding from that side too), but at least there is a culture of running with enough equipment. Surely when the web-scale data gear (e.g. Google Bigtable, Yahoo PNUTS, Amazon Dynamo) was new, by the operators' own admission there was no way for this to be particularly efficient, database-wise. Not if your eventual consistency is a client application to a shared MySQL back-end. For a lookup or single-record-update workload, who cares when there is enough hardware? For analytics, there is the <i>de facto</i> impossibility of doing big joins, but map reduce is for that, all offline. The big web houses have always known how to deal with data; it is the smaller Web 2.0 guys who patch systems together with duct tape and memcache. Even so, the online experience gets created.</p> <p>Semanticism has no part of this outlook, except maybe for Freebase, but then they are from California and now have been inside Google for a while.</p> <p>We quite understand that when one needs to get big data online, one makes a key-value store as a point solution, because this way one owns what one operates, and the time to market is a lot shorter than if one tried building all this inside a general-purpose DBMS. Besides, the people who can in fact do this almost do not exist, and even if one had a whole army of this rare breed, development is not very scalable in a tightly-integrated system like a high-performance DBMS. Still further, to even start, one needs to own the DBMS, meaning that the initial platform must be known through and through. This is an issue even though open source platforms exist.</p> <p>The graph data, semdata, schema-last, RDF, linked data enterprise -- whatever one calls it -- makes the bold proposition of bringing complex-query-at-scale to heterogeneous data. This is a database claim.</p> <p>In the meantime, test deployments are made in defiance of database best practices. This is a bit like test driving a race car in reverse gear and steering by looking in the rear-view mirror.</p> <p>There is also no short-term scalable way to educate people. At the LOD2 review, one comment was that an integrated project ought to clearly indicate how to set up the tool chain for good performance, specially as concerns interfaces between the tools. This is very true. Experience shows that developers of tools cannot accurately anticipate what usage patterns will emerge in the field. Therefore, we propose to do better than just documentation; we will make the server recognize the common sources of inefficiency and point the user to the right action.</p> <h3>Provisioning and usage patterns: The DBMS ought to know best.</h3> <p>Imagine the following conversation:</p> <p> <b>DBMS:</b> Your application does single-triple INSERTs over client-server protocol all day, from a single client. 57% of real time goes in client server latency, 40% in cluster interconnect latency, 2% in compiling the statements, and 1% in doing the work. Use array parameters or bulk load from a file.</p> <p> <b>Operator:</b> My developers use industry-standard Java class libraries with a service-oriented architecture and strictly enforced interfaces. This is called software engineering. Watch out ere you raise your voice against the canon.</p> <p> <i>[Some weeks later, after the load job has gone on for 10 days and gotten a third of the way, developers have discovered that JDBC has array parameters and are trying these.]</i> </p> <p> <b>DBMS:</b> 60% of real time goes into waiting for locks. 10% of transactions get aborted for deadlock. Transactions consist of an average of 10 client-server operations. Use stored procedures; acquire locks in predictable order; do SELECT FOR UPDATE. Throughput will be 4x higher if client-server operations are merged into a single operation. The transactions only INSERT; hence consider bulk load instead.</p> <p> <b>Operator</b>: We are using an enterprise-class three-tier architecture. It has "enterprise" in the name and all the big guys are using it, so it must be scalable. Besides, it is distributed transactions, and distributed computing is the wave of the future. You are a cluster yourself, so the pot's got no business calling the kettle black.</p> <p> <i>[After a while, the data gets loaded with bulk load, but now on a single stream.]</i> </p> <p> <b>DBMS</b>: CPU is at 400% for an INSERT workload; adding more parallel threads will get 4.5x better throughput.</p> <p> <i>[Some time has elapsed and there are Ajax client apps out there trying to use the data.]</i> </p> <p> <b>DBMS</b>: Will you really not give me another 140 GB RAM and 16 more cores?</p> <p> <b>Operator</b>: No, on general principles I will not, shut up.</p> <p> <b>DBMS</b>: Do you know that your page impression takes 3 seconds and anything over 0.25 seconds is visibly slow? 300 GB worth of distinct pages have been accessed in the last 24 hours for 160 GB of RAM. Latency will drop 10x by using SSD; 50x by increasing RAM.</p> <p> <b>Operator</b>: No dice, bucket. Shut up, besides, when I scroll through the data I always use for testing, I get it fast enough, you are just doing this out of greed and self-importance. You are a server among many, just like the mail server; you databases are just pretentious.</p> <p>Currently addressing any of the above sorts of issues takes a long time and involves mostly-avoidable support communication. Questions of this sort do occur. We can probably produce commentary like the above based on logging some 50 numbers, and making some 15 regularly-run reports over these. The patterns to watch out for are well known. No, we will not make a Zippy the Pinhead office assistant; a computer should not try to be cute. This one will talk only in terms of gains from adjusting the deployment or usage patterns.</p> <p>Now, suppose the operator said <i>yes</i> to the request for more cores and memory; then it would be up to the DBMS to deliver. This entails a capacity to redistribute itself automatically, and to give a quantitative report on the success of this measure. This means usage-based repartitioning of the data to equalize load over a cluster. The relevant metric in the above case is the drop in response time. On the other hand, the DBMS should also notice if there is clearly unused capacity.</p> <p>This all will be presented as a line in the status report, so there is no extra wizard or workload analyzer that one must remember to run. For programmatic use there are SQL views for the relevant reports.</p> <p>As for ETL, even if the DBMS can detect that it is not being done right, this does not mean that the user will know what to do. Therefore, for all the Web harvesting we support, as well as any import from local file system or Web services, with some RDF-ization, we will simply implement a proper ETL utility that will do things right. <b>Wazzup?</b> can just point the user to that if the workload looks like loading. This will have its own status report giving a load and transform rate and will point out what takes the longest, after everything is duly parallelized and made asynchronous.</p> <p>Beyond these lessons, there is more to say about the review and plenary, we will get to that a bit later. We did promise a new edition of the LOD cache in a couple of months, now on the clustered column-store platform. Look for advances in data discoverability.</p>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-09-30T17:02:01.000016-04:00
LOD2 Plenary and Review: Semanticist, Think Database!
http://www.openlinksw.com/weblog/oerling/?id=1698
2011-09-29T14:50:47Z
<p>Last week the <a href="http://lod2.eu/" id="link-id0x57d7368">LOD2 FP7 project</a> had its first review, preceded by its third plenary meeting.</p> <p>Before this, we did, <a href="http://www.openlinksw.com/weblog/oerling/?id=1683" id="link-id0x579c950">as promised</a>, get the column store and vectored execution capabilities of Virtuoso 7 Single-Server Edition extended to Virtuoso 7 Cluster Edition. More interesting still, we decoupled storage from the database server process, so now database files can migrate between server processes. This means that clusters are now elastic, i.e., new servers can be added to a cluster and the load can be redistributed without reloading the data.</p> <p>These things were long planned, but now are done. Measurements will be published in some weeks, as part of CWI's continued running of RDF store benchmarks, per the LOD2 plan.</p> <p>Doing the column store and elastic cluster is work enough, so I do not in general participate in support or consultancy or the like. This has some pros and cons. On the plus side, there is a relative lack of noise and a very clear idea of focus. Of course, this work is most highly applied, thus always informed by use cases, thus forgetting what ought to be done out there is not the problem. Rather, the problem is forgetting how things in fact <i>are</i> done as opposed to how they <i>could or should be</i> done.</p> <p>To cut a long story short, it has become clear to me that the DBMS must tell the application developer what to do. Of course, the application developer could also look at performance metrics, but they do not, and explaining these metrics is too much work and yields no lasting benefit. Developers will produce all kinds of performance diagnostic traces if requested, but going through this song and dance can also be avoided by the right automation.</p> <p>So, I will introduce two new product features called <i><b>Wazzup?</b></i> and <i><b>Saywhat?</b></i> </p> <p> <b>Wazzup?</b> is answered by a mood line, like "Heavily disk bound: 100G more memory will give 10x speedup" or "Network bound: Processing in larger batches will give 5x more throughput" and <b>Saywhat?</b> is answered by some commentary on the user's last action, for example "there is no ?order with o_totalprice < 0" or "there is no property O_misspelledtotallprrice."</p> <p> <b>Wazzup?</b> is about overall system state, and <b>Saywhat?</b> is about the user session, specifically query plans. But an explanation of a query plan is not understandable, so this will just point out some salient facts, like the reason why the answer comes out empty.</p> <p>The other thing that came to my attention is the fact that a user has no instinctive feel for <a href="http://dbpedia.org/page/Extract,_transform,_load" id="link-id0x527eb88">ETL</a>. A database person takes it for a self-evident truth that data is loaded in bulk, but the application developer does not think of that. Likewise, the line between warehousing and federating is not instinctively felt; actually the question is not even posed in these terms. So one will find Web protocols and end-points and glue code on the app server when one ought to have ETL and adequate hardware for running the consolidated database.</p> <p>Further, under-provisioning of equipment is endemic with semanticists. The Semantic Web gets a needlessly bad rap just because we find too much data on too little equipment. For example, I was surprised to learn that the Linked Geodata demo ran on only 16 GB RAM and 6 processor cores with 2 billion triples and 350 million points in a geo index. Now, even with our greatest space efficiency advances, there is no way this will run from memory.</p> <p>It is not that the Web 2.0 stack is necessarily efficient (we hear the wildest stories of lack of database understanding from that side too), but at least there is a culture of running with enough equipment. Surely when the web-scale data gear (e.g. Google Bigtable, Yahoo PNUTS, Amazon Dynamo) was new, by the operators' own admission there was no way for this to be particularly efficient, database-wise. Not if your eventual consistency is a client application to a shared MySQL back-end. For a lookup or single-record-update workload, who cares when there is enough hardware? For analytics, there is the <i>de facto</i> impossibility of doing big joins, but map reduce is for that, all offline. The big web houses have always known how to deal with data; it is the smaller Web 2.0 guys who patch systems together with duct tape and memcache. Even so, the online experience gets created.</p> <p>Semanticism has no part of this outlook, except maybe for Freebase, but then they are from California and now have been inside Google for a while.</p> <p>We quite understand that when one needs to get big data online, one makes a key-value store as a point solution, because this way one owns what one operates, and the time to market is a lot shorter than if one tried building all this inside a general-purpose DBMS. Besides, the people who can in fact do this almost do not exist, and even if one had a whole army of this rare breed, development is not very scalable in a tightly-integrated system like a high-performance DBMS. Still further, to even start, one needs to own the DBMS, meaning that the initial platform must be known through and through. This is an issue even though open source platforms exist.</p> <p>The graph data, semdata, schema-last, RDF, linked data enterprise -- whatever one calls it -- makes the bold proposition of bringing complex-query-at-scale to heterogeneous data. This is a database claim.</p> <p>In the meantime, test deployments are made in defiance of database best practices. This is a bit like test driving a race car in reverse gear and steering by looking in the rear-view mirror.</p> <p>There is also no short-term scalable way to educate people. At the LOD2 review, one comment was that an integrated project ought to clearly indicate how to set up the tool chain for good performance, specially as concerns interfaces between the tools. This is very true. Experience shows that developers of tools cannot accurately anticipate what usage patterns will emerge in the field. Therefore, we propose to do better than just documentation; we will make the server recognize the common sources of inefficiency and point the user to the right action.</p> <h3>Provisioning and usage patterns: The DBMS ought to know best.</h3> <p>Imagine the following conversation:</p> <p> <b>DBMS:</b> Your application does single-triple INSERTs over client-server protocol all day, from a single client. 57% of real time goes in client server latency, 40% in cluster interconnect latency, 2% in compiling the statements, and 1% in doing the work. Use array parameters or bulk load from a file.</p> <p> <b>Operator:</b> My developers use industry-standard Java class libraries with a service-oriented architecture and strictly enforced interfaces. This is called software engineering. Watch out ere you raise your voice against the canon.</p> <p> <i>[Some weeks later, after the load job has gone on for 10 days and gotten a third of the way, developers have discovered that JDBC has array parameters and are trying these.]</i> </p> <p> <b>DBMS:</b> 60% of real time goes into waiting for locks. 10% of transactions get aborted for deadlock. Transactions consist of an average of 10 client-server operations. Use stored procedures; acquire locks in predictable order; do SELECT FOR UPDATE. Throughput will be 4x higher if client-server operations are merged into a single operation. The transactions only INSERT; hence consider bulk load instead.</p> <p> <b>Operator</b>: We are using an enterprise-class three-tier architecture. It has "enterprise" in the name and all the big guys are using it, so it must be scalable. Besides, it is distributed transactions, and distributed computing is the wave of the future. You are a cluster yourself, so the pot's got no business calling the kettle black.</p> <p> <i>[After a while, the data gets loaded with bulk load, but now on a single stream.]</i> </p> <p> <b>DBMS</b>: CPU is at 400% for an INSERT workload; adding more parallel threads will get 4.5x better throughput.</p> <p> <i>[Some time has elapsed and there are Ajax client apps out there trying to use the data.]</i> </p> <p> <b>DBMS</b>: Will you really not give me another 140 GB RAM and 16 more cores?</p> <p> <b>Operator</b>: No, on general principles I will not, shut up.</p> <p> <b>DBMS</b>: Do you know that your page impression takes 3 seconds and anything over 0.25 seconds is visibly slow? 300 GB worth of distinct pages have been accessed in the last 24 hours for 160 GB of RAM. Latency will drop 10x by using SSD; 50x by increasing RAM.</p> <p> <b>Operator</b>: No dice, bucket. Shut up, besides, when I scroll through the data I always use for testing, I get it fast enough, you are just doing this out of greed and self-importance. You are a server among many, just like the mail server; you databases are just pretentious.</p> <p>Currently addressing any of the above sorts of issues takes a long time and involves mostly-avoidable support communication. Questions of this sort do occur. We can probably produce commentary like the above based on logging some 50 numbers, and making some 15 regularly-run reports over these. The patterns to watch out for are well known. No, we will not make a Zippy the Pinhead office assistant; a computer should not try to be cute. This one will talk only in terms of gains from adjusting the deployment or usage patterns.</p> <p>Now, suppose the operator said <i>yes</i> to the request for more cores and memory; then it would be up to the DBMS to deliver. This entails a capacity to redistribute itself automatically, and to give a quantitative report on the success of this measure. This means usage-based repartitioning of the data to equalize load over a cluster. The relevant metric in the above case is the drop in response time. On the other hand, the DBMS should also notice if there is clearly unused capacity.</p> <p>This all will be presented as a line in the status report, so there is no extra wizard or workload analyzer that one must remember to run. For programmatic use there are SQL views for the relevant reports.</p> <p>As for ETL, even if the DBMS can detect that it is not being done right, this does not mean that the user will know what to do. Therefore, for all the Web harvesting we support, as well as any import from local file system or Web services, with some RDF-ization, we will simply implement a proper ETL utility that will do things right. <b>Wazzup?</b> can just point the user to that if the workload looks like loading. This will have its own status report giving a load and transform rate and will point out what takes the longest, after everything is duly parallelized and made asynchronous.</p> <p>Beyond these lessons, there is more to say about the review and plenary, we will get to that a bit later. We did promise a new edition of the LOD cache in a couple of months, now on the clustered column-store platform. Look for advances in data discoverability.</p>
Orri Erling
oerling@openlinksw.com
2011-09-29T14:48:59-04:00
GDB for the Data Driven Age (STI Summit Position Paper)
http://www.openlinksw.com/blog/vdb/blog/?id=1697
2011-07-26T13:37:26Z
<p> <i><b>Note:</b> The following was written prior to the event, but was not posted until later due to human error.</i> </p> <p>The <a href="http://sti2.org/" id="link-id0x261e3798">Semantic Technology Institute</a> (<a href="http://sti2.org/" id="link-id0x243dac30">STI</a>) is organizing <a href="http://summit2011.sti2.org/" id="link-id0x25fc4e68">a meeting</a> around the questions of making semantic technology deliver on its promise. We were asked to present a position paper (reproduced below). This is another recap of our position on making graph databasing come of age. While the database technology matters are getting tackled, we are drawing closer to the question of deciding actually what kind of inference will be needed close to the data. My personal wish is to use this summit for clarifying exactly what is needed from the database in order to extract value from the data explosion. We have a good idea of what to do with queries but what is the exact requirement for transformation and alignment of schema and identifiers? What is the actual use case of inference, OWL or other, in this? It is time to get very concrete in terms of applications. We expect a mixed requirement but it is time to look closely at the details.</p> <h3>GDB for the Data Driven Age</h3> <p>Databases and knowledge representation both have decades of history, but to date the exchange of ideas and techniques between these disciplines has been limited. The intuition that there would be value in greater cooperation has not failed to occur to researchers on either side; after all, both sides deal with data. From this, we have seen deductive databases emerge, as well as more recently "database friendly" profiles of OWL.</p> <p>In this position paper we will examine what, in the most concrete terms, is needed in order to bring leading edge database technology together with expressive querying and reasoning. This draws on our experience in building <a href="http://virtuoso.openlinksw.com/" id="link-id0x240cdd28">Virtuoso</a>, one of today's leading <a href="http://dbpedia.org/page/Graph_database" id="link-id0x24ceaae0">graph data stores</a>. Following this, we argue for the creation of benchmarks and challenges that in fact do reflect reality and facilitate open and fair comparison of products and technologies.</p> <p>Data integration is often mentioned as the motivating use case for GDB, commonly popularized today as RDF. Database research has over the past few years produced great advances for business intelligence (i.e., complex queries and read-mostly workloads). These advances are typified by compressed columnar storage and architecture-conscious execution models, mostly based on the idea of always processing multiple sets of values in each operation (vectoring). With these techniques, raw performance with relatively simple schemas and regular data (e.g., TPC-H) is no longer a barrier to extracting value from data.</p> <p>A similar breakthrough has not been seen on the semantics side. Data integration still requires manual labor. Publishing GDB datasets is a good and necessary intermediate stage, but producing these datasets from diverse sources is not fundamentally different from doing the same work without GDB or RDF. Even so, GDB and RDF serve as a catalyst for a culture of publishing datasets.</p> <p>GDB, as a base model for integration, offers the following benefits over a purely relational result format: </p> <ul> <li>All entities have globally unique identifiers.</li> <li>Any statements may be associated ad hoc to any entities.</li> <li>These statements can be scoped into graphs according to their provenance, time, validity, etc.</li> </ul> <p>Obtaining this flexibility on a relational basis would simply require moving to an graph-like representation with essentially one-row-per-attribute. Indeed, we see key-value stores being used in online applications with high volatility of schema (e.g., social networks, search); and we also see relational applications making provisions for post-hoc addition of per-entity attributes (i.e., associating a bag of mixed non-first normal form data with entities). The benefits of a schema-last approach are recognized in many places.</p> <p>GDB seems <i>a priori</i> a fit for all these requirements, thus how will it claim its place as a solution?</p> <p>The first part of the answer lies in learning all the relevant database lessons. The second part lies in eliminating the impedance mismatch between querying and reasoning. The third and most important part consists of substantiating these claims in a manner that is understandable to the relevant publics, finally leading to the creation of a semantics-aware segment of the database industry. We will address each of these aspects in turn.</p> <h4>GDB and RDB</h4> <p>The problem is divided into storage format, execution, and query optimization. For the first two, Daniel Abadi's <a href="http://cs-www.cs.yale.edu/homes/dna/papers/abadiphd.pdf" id="link-id0x25ebd568">renowned Ph.D. thesis</a> holds most of the keys. Space efficiency is specially important for Linked Data, since data is often voluminous, and many datasets have to be brought together for integration. Access patterns are also unpredictable, with indexed-random-access predominating, as opposed to RDB BI workloads where sequential scans and hash joins represent the bulk of the work. However, we find that a sorted column-wise compressed representation of Linked Data with a single quad table for all statements gives excellent space efficiency and good random access as well as random insert speed. The space efficiency is close to par with the equivalent column-wise relational format, since three of the four columns of the quad table compress to almost nothing. As many sort orders as are necessary may be maintained, but we find that two are enough, with some extra data structures for dealing with queries where the predicate is unspecified. The details are found in VLDB 2010 Semdata workshop paper, <i><a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VirtDirectionsChallengesSemdata" id="link-id0x244a8010">Directions and Challenges for Semantically Linked Data</a></i>. Since GDB/RDF is a model typed at run time, the engine must support an "<code>ANY</code>" data type for columns and query variables, where values on successive rows may be of different types. This is a straightforward enhancement.</p> <p>Vectored execution is traditionally associated with column stores because the per-row access cost is relatively high, thus needing to access many nearby rows at a time in order to amortize the overhead. Aside this, vectored execution provides many opportunities for parallelism, from the instruction level all the way to threading and distributed execution on clusters, thus some form of execution on large numbers of concurrent query states is needed for RDF stores, just as it is needed for RDBMS"s.</p> <p>Query optimization for GDBMS is similar to that for RDBMS, except that the statistics can no longer be collected by column and table, but must rather apply to individual entities and ranges of a single quad table. This can be provided through run-time sampling of the database based on constants in the query being optimized. This may take into account trivial inference such as expanding properties into the set of their sub-properties and the like. Beyond this, interleaving execution and optimization (as in <a href="http://oai.cwi.nl/oai/asset/14193/14193B.pdf" id="link-id0x264cfd20">ROX</a>) seems to offer limitless possibilities, especially when inference is introduced, making optimizer statistics less predictive. </p> <p>In summary, starting with an RDBMS and going to GDB entails changes to all parts of the engine, but these changes are not fundamental. One does need to own the engine; however, otherwise the expertise for efficiently implementing these changes will not exist. Essentially any DBMS technique may be translated to a GDB use case, if its application can be decided at run-time. GDB may be schema-less, yet most datasets have fairly regular structure; the question is simply to reconstruct the needed statistics and schema information from the data on an as you go basis. Techniques with high up-front cost, like constructing specially ordered materializations for optimizing specific queries, are harder to deploy but still conceivable for GDB also.</p> <h4>RDB and Inference</h4> <p>Compared to the straightforwardly performance oriented world of database engines, the contours of the landscape become less defined when moving to inference. Databases, whether relational or schema-less all perform roughly the same functions but inference is more diverse. We include here also techniques like machine learning and meta-reasoning for guiding reasoning, although these might not strictly fit the definition.</p> <p>As we posit that data integration is the motivating use case for GDB as opposed to RDB (Relational Database Model), we must ask which modes of inference are actually required for data integration. Further, we need to ask whether these inferences ought to be applied as a preprocessing step (ETL or forward chaining), or as needed (backward chaining). Some low-hanging fruit can be collected by simply constructing class or property hierarchies; e.g., in the data at hand, the following properties have the meaning of company name, and the following classes have the meaning of company. We have found that such techniques can be efficiently supported at run-time, without materialization, if the support is simply built into the engine, which is in itself straightforward as long as one controls the engine. The same applies to trivial identity resolution, such as <code>owl:sameAs</code> or resolution of identity based on sharing an inverse-functional property value. These things take longer at run-time, but if one caches and reuses the result, one can get around materialization.</p> <p>We do not believe in weak statements of identity, as in <i>X is similar to Y,</i> since the meaning of similarity is entirely contextual. X and Y may or may not be interchangeable depending on the application; thus the statement on identity needs to be strong, but it must be easy to modify the grounds on which such a statement is made. This is a further argument for why one should not automatically materialize consequences of identity, particularly if dealing with web data where identity is especially problematic.</p> <p>Real-world problems are however harder than just bundling properties, classes, or instances into sets of interchangeable equivalents, which is all we have mentioned thus far. There are differences of modeling ("address as many columns in customer table" vs. "address normalized away under a contact entity"), normalization ("first name" and "last name" as one or more properties; national conventions on person names; tags as comma-separated in a string or as a one-to-many), incomplete data (one customer table has family income bracket, the other does not), diversity in units of measurement (Imperial vs. metric), variability in the definition of units (seven different things all called blood pressure), variability in unit conversions (currency exchange rates), to name a few. What a world!</p> <p>If data exists, the conversion questions are often answerable but their answer depends on context -- e.g., date of transaction for currency exchange rate; source of data for the definition of blood pressure.</p> <p>Alongside these, there remain issues of identity, e.g., depending on the perspective, a national subsidiary is or is not the same entity as the parent company, companies with the same name can be entirely unrelated in different jurisdictions.</p> <p>It appears that we may need a multi-level approach, combining different techniques for different phases of the integration process. We do not <i>a priori</i> believe that using SQL VIEWs for unit and modeling conversion, and then OWL for unifying terminology on top of this, were the whole solution. Even if this were the solution, the pipeline from the relational sources to SPARQL and OWL needs to be optimized for real-world BI information volumes, and the query language needs to be able to express the business questions and needs to interface with the reporting tools the analyst has come to expect.</p> <p>Our answer so far consists of a SPARQL extension with non-recursive rules, roughly equivalent to SQL VIEWs in expressive power, tightly integrated to the query engine. There is also limited support for recursion through transitive subqueries; thus one can compactly express things like "all parts of all assemblies and subassemblies must satisfy applicable safety requirements, where the requirements depend on the type of the part in question."</p> <p>This is only an intermediate step. We believe that a database-scale generic inference engine with at least Datalog power, with second-order extensions like computed predicates, is needed, executing inside the DBMS, benefiting from the whole array of optimizations database-science expects of execution engines, as part of the answer.</p> <p>This will not relieve the analyst of having to consider that the currency rates in effect at the time of conversion must be taken into account when calculating profits, but this will at least make expressing this and similar pieces of context more compact.</p> <p>We note that time-to-answer has historically won over raw performance. This was also the case for RDBMS when these were the fresh challenger to the CODASYL incumbents, just as was the case with the adoption of high-level languages. The key is that the raw performance must be sufficient for the real world task. With the adoption of the database lessons outlined in the previous section, we believe this to be the case for GDB (and thus, RDF).</p> <h4>Substantiating the Claims</h4> <p>Benchmarks have a stellar record for improving any metric they measure. The question is, how can we make a metric that measures GDB's ability to deliver on its claim to fame -- time-to-answer for big data -- with all the integration and other complexities this entails?</p> <p>So far, GDB benchmarks have consisted of workloads where RDBMS are clearly better (e.g., LUBM, or the Berlin SPARQL Benchmark). This does not remove their usefulness for GDB, but does not constitute a GDB selling point, either.</p> <p>We suggest a dual approach. The first part is demonstrating that GDB is scalable for BI: We take the industry standard decision support benchmark TPC-H, which is very favorable to RDB and quite unfavorable to GDB, and show that we can tackle the workload at reasonable cost. If TPC-H is all one wants, an RDBMS will stay a better fit, but then this benchmark does not capture any of the heterogeneity, schema evolution, or other such requirements faced by real-world data warehouses. This is still a qualification test, not the selling point.</p> <p>The issue of benchmark is inextricably tied to the issue of messaging. There must be a compelling story, with which the IT community can identify. Further, the benchmark must capture real-world challenges in the area of interest. With all this, the benchmark should not be too expensive to run. Here too, a multistage approach suggests itself.</p> <p>Our tentative answer to this question is the Social Intelligence Benchmark (SIB), developed together with CWI and other partners in the LOD2 consortium. This simulates a social network and combines an online workload with complex analytics. This benchmark should cover all of the target areas of the LOD2 project, so that the project itself generates its own metric of success. The project has clear data integration targets, especially as applies to Web and Linked Data. Questions of integration with enterprise sources need to be further developed; for example, comparing CRM data with extractions from the online conversation space for market research.</p> <p>Data integration will invariably involve human effort, and the area cannot be satisfactorily covered with metrics of scale and throughput alone. Development time, accuracy of results, and cost of maintenance are all factors. Furthermore, the task being modeled must correspond to reality, still without being too domain-specific or prohibitively time-consuming to implement.</p> <h4>Conclusions</h4> <p>The data driven world will increase rewards for efficiency in data integration. We believe that such efficiency crucially depends on semantics. Real world requirements just might throw the database and AI communities together with enough heat and pressure for fusion to ignite, allegorically speaking. Without a clear and present need, the geek world analog of electrostatic repulsion will keep the communities separate, as has been the case thus far, and no new, qualitatively-different element will arise.</p> <p>Efforts such as this STI Summit and the LOD2 Project are needed for setting directions and communicating the requirement to the research world. In our fusion analogy, this is the field which directs the nuclei to collide.</p> <p>Once there is an actual reaction that produces more than it consumes by a sufficient margin, regular business dynamics will take over, and we will have an industry with several products of comparable capability, as well as a set of metrics, all to the benefit of the end user.</p> <h4>References</h4> <ul> <li> <p>TPC-H <a href="http://www.tpc.org/tpch/" id="link-id0x25b910e8">results pages</a> </p> </li> <li> <p>Daniel Abadi's Ph.D. Thesis, <i>Query Execution in Column-Oriented Database Systems</i> ( <a href="http://cs-www.cs.yale.edu/homes/dna/papers/abadiphd.pdf" id="link-id0x25f8eeb0">PDF</a> )</p> </li> <li> <p>Our VLDB 2010 Semdata workshop paper, <i>Directions and Challenges for Semantically Linked Data</i> ( <a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VirtDirectionsChallengesSemdata" id="link-id0x25f88520">HTML</a> | <a href="http://virtuoso.openlinksw.com/whitepapers/Directions_and_Challenges_for_Semantically_Linked_Data.pdf" id="link-id0x271416b8">PDF</a> )</p> </li> <li> <p>CWI's <i>ROX: Run-time Optimization of XQueries</i> ( <a href="http://oai.cwi.nl/oai/asset/14193/14193B.pdf" id="link-id0x2699ac78">PDF</a> )</p> </li> <li> <p>The <a href="http://lod2.eu/" id="link-id0x25856fc8">LOD2 Project web site</a> </p> </li> </ul>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-07-26T09:40:34.000002-04:00
GDB for the Data Driven Age (STI Summit Position Paper)
http://www.openlinksw.com/weblog/oerling/?id=1696
2011-07-26T13:36:58Z
<p> <i><b>Note:</b> The following was written prior to the event, but was not posted until later due to human error.</i> </p> <p>The <a href="http://sti2.org/" id="link-id0x261e3798">Semantic Technology Institute</a> (<a href="http://sti2.org/" id="link-id0x243dac30">STI</a>) is organizing <a href="http://summit2011.sti2.org/" id="link-id0x25fc4e68">a meeting</a> around the questions of making semantic technology deliver on its promise. We were asked to present a position paper (reproduced below). This is another recap of our position on making graph databasing come of age. While the database technology matters are getting tackled, we are drawing closer to the question of deciding actually what kind of inference will be needed close to the data. My personal wish is to use this summit for clarifying exactly what is needed from the database in order to extract value from the data explosion. We have a good idea of what to do with queries but what is the exact requirement for transformation and alignment of schema and identifiers? What is the actual use case of inference, OWL or other, in this? It is time to get very concrete in terms of applications. We expect a mixed requirement but it is time to look closely at the details.</p> <h3>GDB for the Data Driven Age</h3> <p>Databases and knowledge representation both have decades of history, but to date the exchange of ideas and techniques between these disciplines has been limited. The intuition that there would be value in greater cooperation has not failed to occur to researchers on either side; after all, both sides deal with data. From this, we have seen deductive databases emerge, as well as more recently "database friendly" profiles of OWL.</p> <p>In this position paper we will examine what, in the most concrete terms, is needed in order to bring leading edge database technology together with expressive querying and reasoning. This draws on our experience in building <a href="http://virtuoso.openlinksw.com/" id="link-id0x240cdd28">Virtuoso</a>, one of today's leading <a href="http://dbpedia.org/page/Graph_database" id="link-id0x24ceaae0">graph data stores</a>. Following this, we argue for the creation of benchmarks and challenges that in fact do reflect reality and facilitate open and fair comparison of products and technologies.</p> <p>Data integration is often mentioned as the motivating use case for GDB, commonly popularized today as RDF. Database research has over the past few years produced great advances for business intelligence (i.e., complex queries and read-mostly workloads). These advances are typified by compressed columnar storage and architecture-conscious execution models, mostly based on the idea of always processing multiple sets of values in each operation (vectoring). With these techniques, raw performance with relatively simple schemas and regular data (e.g., TPC-H) is no longer a barrier to extracting value from data.</p> <p>A similar breakthrough has not been seen on the semantics side. Data integration still requires manual labor. Publishing GDB datasets is a good and necessary intermediate stage, but producing these datasets from diverse sources is not fundamentally different from doing the same work without GDB or RDF. Even so, GDB and RDF serve as a catalyst for a culture of publishing datasets.</p> <p>GDB, as a base model for integration, offers the following benefits over a purely relational result format: </p> <ul> <li>All entities have globally unique identifiers.</li> <li>Any statements may be associated ad hoc to any entities.</li> <li>These statements can be scoped into graphs according to their provenance, time, validity, etc.</li> </ul> <p>Obtaining this flexibility on a relational basis would simply require moving to an graph-like representation with essentially one-row-per-attribute. Indeed, we see key-value stores being used in online applications with high volatility of schema (e.g., social networks, search); and we also see relational applications making provisions for post-hoc addition of per-entity attributes (i.e., associating a bag of mixed non-first normal form data with entities). The benefits of a schema-last approach are recognized in many places.</p> <p>GDB seems <i>a priori</i> a fit for all these requirements, thus how will it claim its place as a solution?</p> <p>The first part of the answer lies in learning all the relevant database lessons. The second part lies in eliminating the impedance mismatch between querying and reasoning. The third and most important part consists of substantiating these claims in a manner that is understandable to the relevant publics, finally leading to the creation of a semantics-aware segment of the database industry. We will address each of these aspects in turn.</p> <h4>GDB and RDB</h4> <p>The problem is divided into storage format, execution, and query optimization. For the first two, Daniel Abadi's <a href="http://cs-www.cs.yale.edu/homes/dna/papers/abadiphd.pdf" id="link-id0x25ebd568">renowned Ph.D. thesis</a> holds most of the keys. Space efficiency is specially important for Linked Data, since data is often voluminous, and many datasets have to be brought together for integration. Access patterns are also unpredictable, with indexed-random-access predominating, as opposed to RDB BI workloads where sequential scans and hash joins represent the bulk of the work. However, we find that a sorted column-wise compressed representation of Linked Data with a single quad table for all statements gives excellent space efficiency and good random access as well as random insert speed. The space efficiency is close to par with the equivalent column-wise relational format, since three of the four columns of the quad table compress to almost nothing. As many sort orders as are necessary may be maintained, but we find that two are enough, with some extra data structures for dealing with queries where the predicate is unspecified. The details are found in VLDB 2010 Semdata workshop paper, <i><a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VirtDirectionsChallengesSemdata" id="link-id0x244a8010">Directions and Challenges for Semantically Linked Data</a></i>. Since GDB/RDF is a model typed at run time, the engine must support an "<code>ANY</code>" data type for columns and query variables, where values on successive rows may be of different types. This is a straightforward enhancement.</p> <p>Vectored execution is traditionally associated with column stores because the per-row access cost is relatively high, thus needing to access many nearby rows at a time in order to amortize the overhead. Aside this, vectored execution provides many opportunities for parallelism, from the instruction level all the way to threading and distributed execution on clusters, thus some form of execution on large numbers of concurrent query states is needed for RDF stores, just as it is needed for RDBMS"s.</p> <p>Query optimization for GDBMS is similar to that for RDBMS, except that the statistics can no longer be collected by column and table, but must rather apply to individual entities and ranges of a single quad table. This can be provided through run-time sampling of the database based on constants in the query being optimized. This may take into account trivial inference such as expanding properties into the set of their sub-properties and the like. Beyond this, interleaving execution and optimization (as in <a href="http://oai.cwi.nl/oai/asset/14193/14193B.pdf" id="link-id0x264cfd20">ROX</a>) seems to offer limitless possibilities, especially when inference is introduced, making optimizer statistics less predictive. </p> <p>In summary, starting with an RDBMS and going to GDB entails changes to all parts of the engine, but these changes are not fundamental. One does need to own the engine; however, otherwise the expertise for efficiently implementing these changes will not exist. Essentially any DBMS technique may be translated to a GDB use case, if its application can be decided at run-time. GDB may be schema-less, yet most datasets have fairly regular structure; the question is simply to reconstruct the needed statistics and schema information from the data on an as you go basis. Techniques with high up-front cost, like constructing specially ordered materializations for optimizing specific queries, are harder to deploy but still conceivable for GDB also.</p> <h4>RDB and Inference</h4> <p>Compared to the straightforwardly performance oriented world of database engines, the contours of the landscape become less defined when moving to inference. Databases, whether relational or schema-less all perform roughly the same functions but inference is more diverse. We include here also techniques like machine learning and meta-reasoning for guiding reasoning, although these might not strictly fit the definition.</p> <p>As we posit that data integration is the motivating use case for GDB as opposed to RDB (Relational Database Model), we must ask which modes of inference are actually required for data integration. Further, we need to ask whether these inferences ought to be applied as a preprocessing step (ETL or forward chaining), or as needed (backward chaining). Some low-hanging fruit can be collected by simply constructing class or property hierarchies; e.g., in the data at hand, the following properties have the meaning of company name, and the following classes have the meaning of company. We have found that such techniques can be efficiently supported at run-time, without materialization, if the support is simply built into the engine, which is in itself straightforward as long as one controls the engine. The same applies to trivial identity resolution, such as <code>owl:sameAs</code> or resolution of identity based on sharing an inverse-functional property value. These things take longer at run-time, but if one caches and reuses the result, one can get around materialization.</p> <p>We do not believe in weak statements of identity, as in <i>X is similar to Y,</i> since the meaning of similarity is entirely contextual. X and Y may or may not be interchangeable depending on the application; thus the statement on identity needs to be strong, but it must be easy to modify the grounds on which such a statement is made. This is a further argument for why one should not automatically materialize consequences of identity, particularly if dealing with web data where identity is especially problematic.</p> <p>Real-world problems are however harder than just bundling properties, classes, or instances into sets of interchangeable equivalents, which is all we have mentioned thus far. There are differences of modeling ("address as many columns in customer table" vs. "address normalized away under a contact entity"), normalization ("first name" and "last name" as one or more properties; national conventions on person names; tags as comma-separated in a string or as a one-to-many), incomplete data (one customer table has family income bracket, the other does not), diversity in units of measurement (Imperial vs. metric), variability in the definition of units (seven different things all called blood pressure), variability in unit conversions (currency exchange rates), to name a few. What a world!</p> <p>If data exists, the conversion questions are often answerable but their answer depends on context -- e.g., date of transaction for currency exchange rate; source of data for the definition of blood pressure.</p> <p>Alongside these, there remain issues of identity, e.g., depending on the perspective, a national subsidiary is or is not the same entity as the parent company, companies with the same name can be entirely unrelated in different jurisdictions.</p> <p>It appears that we may need a multi-level approach, combining different techniques for different phases of the integration process. We do not <i>a priori</i> believe that using SQL VIEWs for unit and modeling conversion, and then OWL for unifying terminology on top of this, were the whole solution. Even if this were the solution, the pipeline from the relational sources to SPARQL and OWL needs to be optimized for real-world BI information volumes, and the query language needs to be able to express the business questions and needs to interface with the reporting tools the analyst has come to expect.</p> <p>Our answer so far consists of a SPARQL extension with non-recursive rules, roughly equivalent to SQL VIEWs in expressive power, tightly integrated to the query engine. There is also limited support for recursion through transitive subqueries; thus one can compactly express things like "all parts of all assemblies and subassemblies must satisfy applicable safety requirements, where the requirements depend on the type of the part in question."</p> <p>This is only an intermediate step. We believe that a database-scale generic inference engine with at least Datalog power, with second-order extensions like computed predicates, is needed, executing inside the DBMS, benefiting from the whole array of optimizations database-science expects of execution engines, as part of the answer.</p> <p>This will not relieve the analyst of having to consider that the currency rates in effect at the time of conversion must be taken into account when calculating profits, but this will at least make expressing this and similar pieces of context more compact.</p> <p>We note that time-to-answer has historically won over raw performance. This was also the case for RDBMS when these were the fresh challenger to the CODASYL incumbents, just as was the case with the adoption of high-level languages. The key is that the raw performance must be sufficient for the real world task. With the adoption of the database lessons outlined in the previous section, we believe this to be the case for GDB (and thus, RDF).</p> <h4>Substantiating the Claims</h4> <p>Benchmarks have a stellar record for improving any metric they measure. The question is, how can we make a metric that measures GDB's ability to deliver on its claim to fame -- time-to-answer for big data -- with all the integration and other complexities this entails?</p> <p>So far, GDB benchmarks have consisted of workloads where RDBMS are clearly better (e.g., LUBM, or the Berlin SPARQL Benchmark). This does not remove their usefulness for GDB, but does not constitute a GDB selling point, either.</p> <p>We suggest a dual approach. The first part is demonstrating that GDB is scalable for BI: We take the industry standard decision support benchmark TPC-H, which is very favorable to RDB and quite unfavorable to GDB, and show that we can tackle the workload at reasonable cost. If TPC-H is all one wants, an RDBMS will stay a better fit, but then this benchmark does not capture any of the heterogeneity, schema evolution, or other such requirements faced by real-world data warehouses. This is still a qualification test, not the selling point.</p> <p>The issue of benchmark is inextricably tied to the issue of messaging. There must be a compelling story, with which the IT community can identify. Further, the benchmark must capture real-world challenges in the area of interest. With all this, the benchmark should not be too expensive to run. Here too, a multistage approach suggests itself.</p> <p>Our tentative answer to this question is the Social Intelligence Benchmark (SIB), developed together with CWI and other partners in the LOD2 consortium. This simulates a social network and combines an online workload with complex analytics. This benchmark should cover all of the target areas of the LOD2 project, so that the project itself generates its own metric of success. The project has clear data integration targets, especially as applies to Web and Linked Data. Questions of integration with enterprise sources need to be further developed; for example, comparing CRM data with extractions from the online conversation space for market research.</p> <p>Data integration will invariably involve human effort, and the area cannot be satisfactorily covered with metrics of scale and throughput alone. Development time, accuracy of results, and cost of maintenance are all factors. Furthermore, the task being modeled must correspond to reality, still without being too domain-specific or prohibitively time-consuming to implement.</p> <h4>Conclusions</h4> <p>The data driven world will increase rewards for efficiency in data integration. We believe that such efficiency crucially depends on semantics. Real world requirements just might throw the database and AI communities together with enough heat and pressure for fusion to ignite, allegorically speaking. Without a clear and present need, the geek world analog of electrostatic repulsion will keep the communities separate, as has been the case thus far, and no new, qualitatively-different element will arise.</p> <p>Efforts such as this STI Summit and the LOD2 Project are needed for setting directions and communicating the requirement to the research world. In our fusion analogy, this is the field which directs the nuclei to collide.</p> <p>Once there is an actual reaction that produces more than it consumes by a sufficient margin, regular business dynamics will take over, and we will have an industry with several products of comparable capability, as well as a set of metrics, all to the benefit of the end user.</p> <h4>References</h4> <ul> <li> <p>TPC-H <a href="http://www.tpc.org/tpch/" id="link-id0x25b910e8">results pages</a> </p> </li> <li> <p>Daniel Abadi's Ph.D. Thesis, <i>Query Execution in Column-Oriented Database Systems</i> ( <a href="http://cs-www.cs.yale.edu/homes/dna/papers/abadiphd.pdf" id="link-id0x25f8eeb0">PDF</a> )</p> </li> <li> <p>Our VLDB 2010 Semdata workshop paper, <i>Directions and Challenges for Semantically Linked Data</i> ( <a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VirtDirectionsChallengesSemdata" id="link-id0x25f88520">HTML</a> | <a href="http://virtuoso.openlinksw.com/whitepapers/Directions_and_Challenges_for_Semantically_Linked_Data.pdf" id="link-id0x271416b8">PDF</a> )</p> </li> <li> <p>CWI's <i>ROX: Run-time Optimization of XQueries</i> ( <a href="http://oai.cwi.nl/oai/asset/14193/14193B.pdf" id="link-id0x2699ac78">PDF</a> )</p> </li> <li> <p>The <a href="http://lod2.eu/" id="link-id0x25856fc8">LOD2 Project web site</a> </p> </li> </ul>
Orri Erling
oerling@openlinksw.com
2011-07-26T09:39:43-04:00
The 2011 STI Semantic Summit
http://www.openlinksw.com/blog/vdb/blog/?id=1695
2011-07-22T15:49:15Z
<p>I was recently at the <a href="http://www.openlinksw.com:80/www.sti2.org/events/2011-sti-semantic-summit" id="link-id0x2308d838">STI 2011 summit in Riga, Latvia</a>. This is a meeting of senior participants in the semantic web and sem tech scene, organized by <a href="http://www.openlinksw.com:80/www.sti2.org/" id="link-id0x25076168">STI</a> of <a href="http://dbpedia.org/page/Dieter_Fensel" id="link-id0x24d2e998">Dieter Fensel</a> fame, with board members like <a href="http://www.michaelbrodie.com/" id="link-id0x224b4b58">Michael Brodie</a>, <a href="http://www.iks-project.eu/community/people/mark-greaves" id="link-id0x2308d4a8">Mark Greaves</a>, and <a href="http://dbpedia.org/page/James_Hendler" id="link-id0x24c192d0">Jim Hendler</a>.</p> <p>This is substantially about the intersection of AI, knowledge representation, and databases. As we have said before, the database side has not been very prominent in these meetings in the past, but this time we had <a href="http://homepages.cwi.nl/~boncz/" id="link-id0x26654260">Peter Boncz</a> of CWI, of MonetDB and VectorWise fame, attending the proceedings.</p> <p>Will DB and AI finally meet? Well, they have met, but how do they get along? Before I try to answer this, let us look at some background.</p> <p>At present, CWI and <a href="http://www.openlinksw.com/" id="link-id0x24724fe0">OpenLink</a> are working together in the <a href="http://lod2.eu/" id="link-id0x24e20d90">LOD2 EU FP7 project</a>, around the general topic of bringing the best of <a href="http://dbpedia.org/page/Relational_database" id="link-id0x2475f128">Relational Database</a> (RDB) science to the <a href="http://dbpedia.org/page/Graph_database" id="link-id0x2474e988">Graph Database</a> (GDB) world. Virtuoso has for a few months had a column store capability (which is about to be made available for public preview). CWI has a long history of column store work, with MonetDB and Ingres VectorWise as results. OpenLink's column store implementation is separate in terms of code but is of course influenced by the work at CWI and other published column store results. The plan is to transplant the applicable CWI innovations into the graph context within Virtuoso. These improvements naturally also benefit Virtuoso RDB (SQL), but the LOD2 project is primarily concerned with GDB applications. The RDB yardstick for much of this work is <a href="http://dbpedia.org/resource/TPC-H" id="link-id0x22a96588">TPC-H</a>, of which we have made a GDB translation. CWI is uniquely qualified as concerns this in light of VectorWise holding some of the top places in the TPC-H charts.</p> <p>Even now, we do in fact run the 22 TPC-H queries in SPARQL against the Virtuoso column store. True, these run faster in SQL against relational tables but we have established a beach head. From this initial position, we can incrementally improve the GDB/SPARQL and RDB/SQL functions, and see how close to SQL we get with SPARQL. I will make a separate post commenting on the differences between SQL and SPARQL.</p> <p>So let's get back to Riga. Mark Greaves said in his opening comments that he would be sick if he once again heard complaining about how bad and un-scalable the tools were. From all the talks, I did get the overall impression that just better databasing for Graph Data is still needed. OK, we have 1-1/2 years of unreleased work just for that about to hit the street; advances are substantial. Along these lines, the people from <a href="http://www.bio2rdf.org/" id="link-id0x2315c088">Bio2RDF</a> pointed out that there still is a cost to publishing query services, specially for complex queries. Well, this cost will be substantially reduced.</p> <p>The takeaway from the meeting is that the most useful thing, for both our public and ourselves, is simply to keep advancing database tech for graph data. In the first instance, this is about launching what we already have; in the second, about going through the CWI record of innovation and adapting this to GDB.</p> <p>The thinking is that once query-answering on some tens-of-billions of triples is easily interactive no matter what question one asks, a tipping point will be reached, and GDB can efficiently play the role of data-melting-pot that has been envisioned for it.</p> <p>This is just a beginning, though. Michael Brodie has on a number of occasions pointed out that that (relational) database guys are only about performance with little or no regard to meaning or even questions of the applicability of the relational model. Peter Boncz then comments back that it can well be that the bulk of IT expenditure worldwide in fact goes into data integration. However, data integration is an "<a href="http://dbpedia.org/page/AI-complete" id="link-id0x24754170">AI-complete</a>" problem with infinite variety and consequent difficulty of measurement. So, making better database engines stands a much greater chance of success and has the nicety of relatively unambiguous metrics. </p> <p>Quite so. We are somewhere in the middle. I'd say that GDB is still at the stage where making better databases is a matter of make-or-break and not a matter of cutting already vanishingly-short response times just for the sake of it. We will have progress if we just keep at it; for now, performance is still a basic need and not a luxury.</p> <p>Now that there is all this potentially integrable data published as graphs (most commonly as RDF serializations), what do we do? Someone at the Riga meeting suggested we take a look across the tracks to the RDB world to see what is being done there for data integration. The question is raised, what does GDB have for data integration? The automatic answer that GDB and RDF have OWL is not adequate, as was rightly pointed out by many. Having schema-last, global identifiers, and some culture of vocabulary reuse is nice, but this is only a start. To cite an example, <code>owl:sameAs</code> will not work when entities simply do not align: One database models a product as a parts hierarchy; another does the same but now based on the materials used in the parts. One tree just has a node that is not in the other. Besides, things like string matching (as in extracting area codes from phone numbers) are common, and OWL specifically excludes any such functions.</p> <p>It is now time to look at what will come after all the database advances. In my talk I outlined some things that have or are about to get solutions:</p> <ul> <li> <p> <b>Database technology:</b> Applying advances from RDB (specifically columns, vectoring, and some adaptive query execution) will make GDB a possibility for data warehousing at some scale.</p> </li> <li> <p> <b>Benchmarks:</b> These advances will be demonstrable through benchmarking. There is a better suite of benchmarks with many variations of BSBM, an GDB-modified TPC-H, and the upcoming Social Intelligence Benchmark (SIBB) with actual graph data. There are the beginnings of an auditing process for result publishing, and a fair chance the semdata world will get its analog of the TPC.</p> </li> </ul> <p>After these basics are more or less in hand, we have a vista of more diverse questions:</p> <ul> <li> <p>What to do about inference? We do not want OWL or RIF for their own sake; instead we want whatever will declaratively facilitate making sense of data. This is an entirely use-case-driven question. If this can have a reasonably generic answer, we will build it into the engine. </p> </li> <li> <p>Data integration is highly diverse, and tool sets like IBM Infosphere have thousands of modules and functions for different aspects of the problem. To what degree does it make sense to put DI-oriented capabilities into a DBMS? </p> </li> <li> <p>Is it the case that SQL or SPARQL, plus or minus a few details, is as powerful as a language can be while staying application domain-agnostic? In other words, if more powerful reasoning is built into the query language, will the requirements vary so much between application domains that the work is not generally applicable? <a href="http://dbpedia.org/page/Datalog" id="link-id0x2403b2f0">Datalog</a> is general enough, but can we demonstrate substantially reduced time to answer with big data if this is built into the engine? <a href="http://boom.cs.berkeley.edu/" id="link-id0x23ed5730">Berkeley Orders Of Magnitude</a> claims this, even though their claim is not exactly in a database context. We need use cases to refine the actual requirement for inference.</p> </li> </ul> <p>In all these questions, we of necessity turn to the user community. In fact we do not follow the usage of these technologies as much as we ought to. One outcome of the Riga summit is a set of public challenges that will hopefully ameliorate this state of matters, to be released soon.</p> <p>The general feeling was that there is more going on on the data side than the AI side. The LOD movement proceeds and lightweight everything predominates, also for knowledge representation. There was some discussion about "pay as you go" integration. On the one hand, there is no up-front integration of information systems just for its own sake, so pay as you go is the only kind that exists, system by system, as the need becomes sufficient. On the other hand, each such integration is a process which has its distinct steps and maintenance and within itself it is planned, and thus pre-paid, so to speak. We need more work with the data itself to better understand the matter. The open government data should offer a playground for this and there will be a special challenge around this.</p> <p> <a href="http://schema.org/" id="link-id0x2475a708">Schema.org</a> and <a href="http://www.w3.org/TR/microdata/" id="link-id0x2a6f8b40">Microdata</a> got their share of discussion. As we see it, it is good that search engines make their pre-competitive data open. This is better than, for example, Google wanting retailers to put their catalogs in Google Base. We do not care about the specific syntax in which data is embedded; we support them all. Microdata converts easily to triples, and if one wants to make a tabular extraction for use with relational tools, this too is simple enough. Applications will have to do their own entity resolution, but this is independent of data publication format. </p> <p>All in all, the mood was positive. Mark Greaves noted in his closing remarks that there has been a 1000x increase in published GDB data over a few years. There is in fact a large quantity of technology for tackling almost any aspect of the LOD value chain, but people do not necessarily know about this nor is it easy to integrate. Still there would be great value in integration. Getting software to interoperate in a meaningful way is manual labor, so it might make sense to organize hackathons around this. While the STI Summit is for the senior people, there could be a parallel track of events for bringing the coders together to actually practice tool integration and interoperation.</p>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-07-22T11:49:15.000046-04:00
The 2011 STI Semantic Summit
http://www.openlinksw.com/weblog/oerling/?id=1694
2011-07-22T15:12:34Z
<p>I was recently at the <a href="http://www.openlinksw.com:80/www.sti2.org/events/2011-sti-semantic-summit" id="link-id0x2308d838">STI 2011 summit in Riga, Latvia</a>. This is a meeting of senior participants in the semantic web and sem tech scene, organized by <a href="http://www.openlinksw.com:80/www.sti2.org/" id="link-id0x25076168">STI</a> of <a href="http://dbpedia.org/page/Dieter_Fensel" id="link-id0x24d2e998">Dieter Fensel</a> fame, with board members like <a href="http://www.michaelbrodie.com/" id="link-id0x224b4b58">Michael Brodie</a>, <a href="http://www.iks-project.eu/community/people/mark-greaves" id="link-id0x2308d4a8">Mark Greaves</a>, and <a href="http://dbpedia.org/page/James_Hendler" id="link-id0x24c192d0">Jim Hendler</a>.</p> <p>This is substantially about the intersection of AI, knowledge representation, and databases. As we have said before, the database side has not been very prominent in these meetings in the past, but this time we had <a href="http://homepages.cwi.nl/~boncz/" id="link-id0x26654260">Peter Boncz</a> of CWI, of MonetDB and VectorWise fame, attending the proceedings.</p> <p>Will DB and AI finally meet? Well, they have met, but how do they get along? Before I try to answer this, let us look at some background.</p> <p>At present, CWI and <a href="http://www.openlinksw.com/" id="link-id0x24724fe0">OpenLink</a> are working together in the <a href="http://lod2.eu/" id="link-id0x24e20d90">LOD2 EU FP7 project</a>, around the general topic of bringing the best of <a href="http://dbpedia.org/page/Relational_database" id="link-id0x2475f128">Relational Database</a> (RDB) science to the <a href="http://dbpedia.org/page/Graph_database" id="link-id0x2474e988">Graph Database</a> (GDB) world. Virtuoso has for a few months had a column store capability (which is about to be made available for public preview). CWI has a long history of column store work, with MonetDB and Ingres VectorWise as results. OpenLink's column store implementation is separate in terms of code but is of course influenced by the work at CWI and other published column store results. The plan is to transplant the applicable CWI innovations into the graph context within Virtuoso. These improvements naturally also benefit Virtuoso RDB (SQL), but the LOD2 project is primarily concerned with GDB applications. The RDB yardstick for much of this work is <a href="http://dbpedia.org/resource/TPC-H" id="link-id0x22a96588">TPC-H</a>, of which we have made a GDB translation. CWI is uniquely qualified as concerns this in light of VectorWise holding some of the top places in the TPC-H charts.</p> <p>Even now, we do in fact run the 22 TPC-H queries in SPARQL against the Virtuoso column store. True, these run faster in SQL against relational tables but we have established a beach head. From this initial position, we can incrementally improve the GDB/SPARQL and RDB/SQL functions, and see how close to SQL we get with SPARQL. I will make a separate post commenting on the differences between SQL and SPARQL.</p> <p>So let's get back to Riga. Mark Greaves said in his opening comments that he would be sick if he once again heard complaining about how bad and un-scalable the tools were. From all the talks, I did get the overall impression that just better databasing for Graph Data is still needed. OK, we have 1-1/2 years of unreleased work just for that about to hit the street; advances are substantial. Along these lines, the people from <a href="http://www.bio2rdf.org/" id="link-id0x2315c088">Bio2RDF</a> pointed out that there still is a cost to publishing query services, specially for complex queries. Well, this cost will be substantially reduced.</p> <p>The takeaway from the meeting is that the most useful thing, for both our public and ourselves, is simply to keep advancing database tech for graph data. In the first instance, this is about launching what we already have; in the second, about going through the CWI record of innovation and adapting this to GDB.</p> <p>The thinking is that once query-answering on some tens-of-billions of triples is easily interactive no matter what question one asks, a tipping point will be reached, and GDB can efficiently play the role of data-melting-pot that has been envisioned for it.</p> <p>This is just a beginning, though. Michael Brodie has on a number of occasions pointed out that that (relational) database guys are only about performance with little or no regard to meaning or even questions of the applicability of the relational model. Peter Boncz then comments back that it can well be that the bulk of IT expenditure worldwide in fact goes into data integration. However, data integration is an "<a href="http://dbpedia.org/page/AI-complete" id="link-id0x24754170">AI-complete</a>" problem with infinite variety and consequent difficulty of measurement. So, making better database engines stands a much greater chance of success and has the nicety of relatively unambiguous metrics. </p> <p>Quite so. We are somewhere in the middle. I'd say that GDB is still at the stage where making better databases is a matter of make-or-break and not a matter of cutting already vanishingly-short response times just for the sake of it. We will have progress if we just keep at it; for now, performance is still a basic need and not a luxury.</p> <p>Now that there is all this potentially integrable data published as graphs (most commonly as RDF serializations), what do we do? Someone at the Riga meeting suggested we take a look across the tracks to the RDB world to see what is being done there for data integration. The question is raised, what does GDB have for data integration? The automatic answer that GDB and RDF have OWL is not adequate, as was rightly pointed out by many. Having schema-last, global identifiers, and some culture of vocabulary reuse is nice, but this is only a start. To cite an example, <code>owl:sameAs</code> will not work when entities simply do not align: One database models a product as a parts hierarchy; another does the same but now based on the materials used in the parts. One tree just has a node that is not in the other. Besides, things like string matching (as in extracting area codes from phone numbers) are common, and OWL specifically excludes any such functions.</p> <p>It is now time to look at what will come after all the database advances. In my talk I outlined some things that have or are about to get solutions:</p> <ul> <li> <p> <b>Database technology:</b> Applying advances from RDB (specifically columns, vectoring, and some adaptive query execution) will make GDB a possibility for data warehousing at some scale.</p> </li> <li> <p> <b>Benchmarks:</b> These advances will be demonstrable through benchmarking. There is a better suite of benchmarks with many variations of BSBM, an GDB-modified TPC-H, and the upcoming Social Intelligence Benchmark (SIBB) with actual graph data. There are the beginnings of an auditing process for result publishing, and a fair chance the semdata world will get its analog of the TPC.</p> </li> </ul> <p>After these basics are more or less in hand, we have a vista of more diverse questions:</p> <ul> <li> <p>What to do about inference? We do not want OWL or RIF for their own sake; instead we want whatever will declaratively facilitate making sense of data. This is an entirely use-case-driven question. If this can have a reasonably generic answer, we will build it into the engine. </p> </li> <li> <p>Data integration is highly diverse, and tool sets like IBM Infosphere have thousands of modules and functions for different aspects of the problem. To what degree does it make sense to put DI-oriented capabilities into a DBMS? </p> </li> <li> <p>Is it the case that SQL or SPARQL, plus or minus a few details, is as powerful as a language can be while staying application domain-agnostic? In other words, if more powerful reasoning is built into the query language, will the requirements vary so much between application domains that the work is not generally applicable? <a href="http://dbpedia.org/page/Datalog" id="link-id0x2403b2f0">Datalog</a> is general enough, but can we demonstrate substantially reduced time to answer with big data if this is built into the engine? <a href="http://boom.cs.berkeley.edu/" id="link-id0x23ed5730">Berkeley Orders Of Magnitude</a> claims this, even though their claim is not exactly in a database context. We need use cases to refine the actual requirement for inference.</p> </li> </ul> <p>In all these questions, we of necessity turn to the user community. In fact we do not follow the usage of these technologies as much as we ought to. One outcome of the Riga summit is a set of public challenges that will hopefully ameliorate this state of matters, to be released soon.</p> <p>The general feeling was that there is more going on on the data side than the AI side. The LOD movement proceeds and lightweight everything predominates, also for knowledge representation. There was some discussion about "pay as you go" integration. On the one hand, there is no up-front integration of information systems just for its own sake, so pay as you go is the only kind that exists, system by system, as the need becomes sufficient. On the other hand, each such integration is a process which has its distinct steps and maintenance and within itself it is planned, and thus pre-paid, so to speak. We need more work with the data itself to better understand the matter. The open government data should offer a playground for this and there will be a special challenge around this.</p> <p> <a href="http://schema.org/" id="link-id0x2475a708">Schema.org</a> and <a href="http://www.w3.org/TR/microdata/" id="link-id0x2a6f8b40">Microdata</a> got their share of discussion. As we see it, it is good that search engines make their pre-competitive data open. This is better than, for example, Google wanting retailers to put their catalogs in Google Base. We do not care about the specific syntax in which data is embedded; we support them all. Microdata converts easily to triples, and if one wants to make a tabular extraction for use with relational tools, this too is simple enough. Applications will have to do their own entity resolution, but this is independent of data publication format. </p> <p>All in all, the mood was positive. Mark Greaves noted in his closing remarks that there has been a 1000x increase in published GDB data over a few years. There is in fact a large quantity of technology for tackling almost any aspect of the LOD value chain, but people do not necessarily know about this nor is it easy to integrate. Still there would be great value in integration. Getting software to interoperate in a meaningful way is manual labor, so it might make sense to organize hackathons around this. While the STI Summit is for the senior people, there could be a parallel track of events for bringing the coders together to actually practice tool integration and interoperation.</p>
Orri Erling
oerling@openlinksw.com
2011-07-22T11:12:34.000002-04:00
Transaction Semantics in RDF and Relational Models
http://www.openlinksw.com/weblog/oerling/?id=1691
2011-03-22T23:55:43Z
<p>As a part of defining benchmark audit for testing <a class="auto-href" href="http://dbpedia.org/resource/ACID" id="link-id0x1eae93c0">ACID</a> properties on <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x1f0adbe0">RDF</a> stores, we will here examine different RDF scenarios where lack of concurrency control causes inconsistent results. In so doing, we consider common implementation techniques and implications as concern locking (pessimistic) and multi-version (optimistic) concurrency control schemes.</p> <p>In the following, we will talk in terms of triples, but the discussion can be trivially generalized to quads. We will use numbers for IRIs and literals. In most implementations, the internal representation for these is indeed a number (or at least some <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x1ea79630">data</a> type that has a well defined collation order). For ease of presentation, we consider a single index with key parts <code>SPO</code>. Any other index-like setting with any possible key order will have similar issues. </p> <h2>Insert (Create) and Delete </h2> <p> <code>INSERT</code> and <code>DELETE</code> as defined in <a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x1f335c60">SPARQL</a> are queries which generate a result set which is then used for instantiating triple patterns. We note that a <code>DELETE</code> may delete a triple which the <code>DELETE</code> has not read; thus the delete set is not a subset of the read set. The <a class="auto-href" href="http://dbpedia.org/resource/SQL" id="link-id0x1e99b4b8">SQL</a> equivalent is the </p> <blockquote> <code><pre>DELETE FROM table WHERE key IN ( SELECT key1 FROM other_table )</pre> </code> </blockquote> <p>expression, supposing it were implemented as a scan of <code>other_table</code> and an index lookup followed by <code>DELETE</code> on table. </p> <p>The meaning of <code>INSERT</code> is that the triples in question exist after the operation, and the meaning of <code>DELETE</code> is that said triples do not exist. In a transactional context, this means that the after-image of the transaction is guaranteed either to have or not-have said triples. </p> <p>Suppose that the triples <code>{ 1 0 0 }</code>, <code>{ 1 5 6 }</code>, and <code>{ 1 5 7 }</code> exist in the beginning. If we <code>DELETE { 1 ?x ?y }</code> and concurrently <code>INSERT { 1 2 4 . 1 2 3 . 1 3 5 }</code>, then whichever was considered to be first by the concurrency control of the DBMS would complete first, and the other after that. Thus the end state would either have no triples with subject <code>1</code> or would have the three just inserted. </p> <p>Suppose the <code>INSERT</code> inserts the first triple, <code>{ 1 2 4 }</code>. The <code>DELETE</code> at the same time reads all triples with subject <code>1</code>. The exclusive read waits for the uncommitted <code>INSERT</code>. The <code>INSERT</code> then inserts the second triple, <code>{ 1 2 3 }</code>. Depending on the isolation of the read, this either succeeds, since no <code>{ 1 2 3 }</code> was read, or causes a deadlock. The first corresponds to <code>REPEATABLE READ</code> isolation; the second to <code>SERIALIZABLE</code>.</p> <p>We would not get the desired end-state of either <i>all the inserted triples</i> or <i>no triples with subject <code>1</code></i> if the read or the <code>DELETE</code> were not serializable.</p> <p>Furthermore if a <code>DELETE</code> template produced a triple that did not exist in the pre-image, the <code>DELETE</code> semantics still imply that this also does not exist in the after-image, which implies serializability.</p> <h2>Read and Update</h2> <p>Let us consider the prototypical transaction example of transferring funds from one account to another. Two balances are updated, and a history record is inserted.</p> <p>The initial state is </p> <blockquote> <code><pre>a balance 10 b balance 10</pre></code> </blockquote> <p>We transfer <code>1</code> from <code>a</code> to <code>b</code>, and at the same time transfer <code>2</code> from <code>b</code> to <code>a</code>. The end state must have <code>a</code> at <code>11</code> and <code>b</code> at <code>9</code>.</p> <p>A relational database needs <code>REPEATABLE READ</code> isolation for this.</p> <p>With RDF, <code>txn1</code> reads that <code>a</code> has a <code>balance</code> of <code>10</code>. At the same time, <code>txn1</code> reads the <code>balance</code> of <code>a</code>. <code>txn2</code> waits because the read of <code>txn1</code> is exclusive. <code>txn1</code> proceeds and read the <code>balance</code> of <code>b</code>. It then updates the <code>balance</code> of <code>a</code> and <code>b</code>. </p> <p>All goes without the deadlock which is always cited in this scenario, because the locks are acquired in the same order. The act of updating the balance of <code>a</code>, since RDF does not really have an update-in-place, consists of deleting <code>{ a balance 10 }</code> and inserting <code>{ a balance 9 }</code>. This gets done and <code>txn1</code> commits. At this point, <code>txn2</code> proceeds after its wait on the row that stated <code>{ a balance 10 }</code>. This row is now gone, and <code>txn2</code> sees that <code>a</code> has no balance, which is quite possible in RDF's <a class="auto-href" href="http://dbpedia.org/resource/Database_schema" id="link-id0x1c933cf0">schema</a>-less model.</p> <p>We see that <code>REPEATABLE READ</code> is not adequate with RDF, even though it is with relational. The reason why there is no <code>UPDATE</code>-in-place is that the <code>PRIMARY KEY</code> of the triple includes all the parts, including the object. Even in a <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x1f3cc3c8">RDBMS</a>, an <code>UPDATE</code> of a primary key part amounts to a <code>DELETE</code>-plus-<code>INSERT</code>. One could here argue that an implementation might still <code>UPDATE</code>-in-place if the key order were not changed. This would resolve the special case of the accounts but not a more general case.</p> <p>Thus we see that the read of the balance must be <code>SERIALIZABLE</code>. This means that the read locks the space before the first balance, so that no insertion may take place. In this way the read of <code>txn2</code> waits on the lock that is conceptually before the first possible match of <code>{ a balance ?x }</code>.</p> <h2>locking order and OLTP </h2> <p>To implement <a class="auto-href" href="http://www.tpc.org/" id="link-id0x1e20f2e8">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/C%2B%2B" id="link-id0x1fa46718">C</a>, I would update the table with the highest cardinality first, and then all tables in descending order of cardinality. In this way, the locks with the highest likelihood for contention are held for the least time. If locking multiple rows of a table, these should be locked in a deterministic order, e.g., lowest key-value first. In this way, the workload would not deadlock. In actual fact, with clusters and parallel execution, the lock acquisition will not be guaranteed to be serial, so deadlocks do not entirely go away, but still may get fewer. Besides, any outside transaction might still lock in the wrong order and cause deadlocks, which is why the OLTP application must in any case be built to deal with the possibility of deadlock.</p> <p>This is the conventional relational view of the matter. In more recent times, in-memory schemes with deterministic lock acquisition (<a href="http://cs-www.cs.yale.edu/homes/dna/papers/determinism-vldb10.pdf" id="link-id0x1c5d9340">Abadi VLDB 2010</a>) or single-threaded atomic execution of transactions (<a href="http://bird.cs.tu-berlin.de:8008/birte2010/" id="link-id0x1ec0ed18">Uni Munich BIRTE workshop at VLDB2010</a>, <a href="http://www.voltdb.com/" id="link-id0x1ab6e380">VoltDB</a>) have been proposed. There the transaction is described as a stored procedure, possibly with extra annotations. These techniques might apply to RDF also. RDF is however an unlikely model for transaction-intensive applications, so we will not for now examine these further.</p> <p>RDBMS usually implement row-level locking. This means that once a column of a row has an uncommitted state, any other transaction is prevented from changing the row. This has no ready RDF equivalent. RDF is usually implemented as a row-per-triple system and applying row-level locking to this does not give the semantic one expects of a relational row. </p> <p>I would argue that it is not essential to enforce transactional guarantees in units of rows. The guarantees must apply between data that is <i>read</i> and <i>written</i> by a transaction. It does not need to apply to columns that the transaction does not reference. To take the TPC-C example, the <i>new order</i> transaction updates the stock level and the <i>delivery</i> transaction updates the delivery count on the stock table. In practice, a <i>delivery</i> and a <i>new order</i> falling on the same row of stock will lock each other out, but nothing in the semantics of the workload mandates this.</p> <p>It does not seem <i>a priori</i> necessary to recreate the row as a unit of concurrency control in RDF. One could say that a multi-attribute whole (such as an address) ought to be atomic for concurrency control, but then applications updating addresses will most likely read and update all the fields together even if only the street name changes.</p> <h2>Pessimistic Vs. Optimistic Concurrency Control </h2> <p>We have so far spoken only in terms of row-level locking, which is to my <a class="auto-href" href="http://dbpedia.org/resource/Knowledge" id="link-id0x1f1230a0">knowledge</a> the most widely used model in RDBMS, and one we implement ourselves. Some databases (e.g., <a class="auto-href" href="http://dbpedia.org/resource/MonetDB" id="link-id0x173a5538">MonetDB</a> and <a class="auto-href" href="http://www.ingres.com/vectorwise/" id="link-id0x16feb008">VectorWise</a>) implement optimistic concurrency control. The general idea is that each transaction has a read and write set and when a transaction commits, any other transactions whose read or write set intersects with the write set of the committing transaction are marked un-committable. Once a transaction thus becomes un-committable, it may presumably continue reading indefinitely but may no longer commit its updates. Optimistic concurrency is generally coupled with multi-version semantics where the pre-image of a transaction is a clean committed state of the database as of a specific point in time, i.e., snapshot isolation. </p> <p>To implement <code>SERIALIZABLE</code> isolation, i.e., the guarantee that if a transaction twice performs a <code>COUNT</code> the result will be the same, one locks also the row that precedes the set of selected rows and marks each lock so as to prevent an insert to the right of the lock in key order. The same thing may be done in an optimistic setting.</p> <p> <a href="http://event.cwi.nl/SIGMOD-RWE/2010/22-7f15a1/paper.pdf" id="link-id0x1d5de810">Positional Handling of Updates in Column Stores</a> [Heman, Zukowski, <a class="auto-href" href="http://dbpedia.org/resource/National_Research_Institute_for_Mathematics_and_Computer_Science" id="link-id0x1df9c990">CWI</a> science library] discusses management of multiple consecutive snapshots in some detail. The paper does not go into the details of different levels of isolation but nothing there suggests that serializability could not be supported. There is some complexity in marking the space between ordered rows as non-insertable across multiple versions but this should be feasible enough. </p> <p>The issue of optimistic Vs. pessimistic concurrency does not seem to be affected by the differences between RDF and relational models. We note that an OLTP workload can be made to run with very few transaction aborts (deadlocks) by properly ordering operations when using a locking scheme. The same does not work with optimistic concurrency since updates happen immediately and transaction aborts occur whenever the writes of one intersect the reads or writes of another, regardless of the order in which these were made.</p> <p>Developers seldom understand transactions; therefore DBMS should, within the limits of the possible, optimize locking order for locking schemes. A simple example is locking in key order when doing an operation on a set of values. A more complex variant would consist of analyzing data dependencies in stored procedures and reordering updates so as to get the highest cardinality tables first. We note that this latter trick also benefits optimistic schemes.</p> <p>In RDF, the same principles apply but distinguishing cardinality of an updated set will have to rely on statistics of predicate cardinality. Such are anyhow needed for query <a class="auto-href" href="http://dbpedia.org/resource/Program_optimization" id="link-id0x1f51d5d0">optimization</a>.</p> <h2>Eventual Consistency </h2> <p>Web scale systems that need to maintain consistent state across multiple data centers sometimes use "eventual consistency" schemes. <a class="auto-href" href="http://dbpedia.org/resource/Two-phase_commit_protocol" id="link-id0x1e3ba5d8">Two-phase-commit</a> becomes very inefficient as latency increases, thus strict transactional semantics have prohibitive cost if the system is more distributed than a cluster with a fast interconnect.</p> <p>Eventual consistency schemes (<a href="http://dbpedia.org/page/Dynamo_(storage_system)" id="link-id0x1f9db8f8">Amazon Dynamo</a>, <a href="http://research.yahoo.com/project/212" id="link-id0x1da3db80">Yahoo! PNUTS</a>) maintain history <a class="auto-href" href="http://dbpedia.org/resource/Information" id="link-id0x8bf48e8">information</a> on the record which is the unit of concurrency control. The record is typically a non-first normal form chunk of related data that it makes sense to store together from the application's viewpoint. Application logic can then be applied to reconciling differing copies of the same logical record. </p> <p>Such a scheme seems <i>a priori</i> ill-suited for RDF, where the natural unit of concurrency control would seem to be the quad. We first note that only recently changed (i.e., <code>DELETEd + INSERTed</code> quads, as there is no <code>UPDATE</code>-in-place) need history information. This history information can be stored away from the quad itself, thus not disrupting compression. When detecting that one site has <code>INSERTed</code> a quad that another has <code>DELETEd</code> in the same general time period, application logic can still be applied for reading related quads in order to arrive at a decision on how to reconcile two databases that have diverged. The same can apply to conflicting values of properties that for the application should be single-valued. Comparing time-stamped transaction logs on quads is not fundamentally different from comparing record histories in Dynamo or PNUTS.</p> <p>As we overcome the data size penalties that have until recently been associated with RDF, RDF becomes even more interesting as a data model for large online systems such as social network platforms where frequent application changes lead to volatility of schema. Key value stores are currently found in such applications, but they generally do not provide the query flexibility at which RDF excels. </p> <h2>Conclusions </h2> <p>We have gone over basic aspects of the endlessly complex and variable topic of transactions, and drawn parallels as well as outlined two basic differences between relational and RDF systems: What used to be <code>REPEATABLE READ</code> becomes <code>SERIALIZABLE</code>; and row-level locking becomes locking at the level of a single attribute value. For the rest, we see that the optimistic and pessimistic modes of concurrency control, as well as guidelines for writing transaction procedures, remain much the same.</p> <p>Based on this overview, it should be possible to design an ACID test for describing the ACID behavior of benchmarked systems. We do not intend to make transaction support a qualification requirement for an RDF benchmark, but information on transaction support will still be valuable in comparing different systems.</p>
Orri Erling
oerling@openlinksw.com
2011-03-22T18:24:20.000001-04:00
Transaction Semantics in RDF and Relational Models
http://www.openlinksw.com/blog/vdb/blog/?id=1692
2011-03-22T23:55:43Z
<p>As a part of defining benchmark audit for testing <a class="auto-href" href="http://dbpedia.org/resource/ACID" id="link-id0x1cfc6e38">ACID</a> properties on <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x1f1302b8">RDF</a> stores, we will here examine different RDF scenarios where lack of concurrency control causes inconsistent results. In so doing, we consider common implementation techniques and implications as concern locking (pessimistic) and multi-version (optimistic) concurrency control schemes.</p> <p>In the following, we will talk in terms of triples, but the discussion can be trivially generalized to quads. We will use numbers for IRIs and literals. In most implementations, the internal representation for these is indeed a number (or at least some <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x1728a9a8">data</a> type that has a well defined collation order). For ease of presentation, we consider a single index with key parts <code>SPO</code>. Any other index-like setting with any possible key order will have similar issues. </p> <h2>Insert (Create) and Delete </h2> <p> <code>INSERT</code> and <code>DELETE</code> as defined in <a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x16dee7f8">SPARQL</a> are queries which generate a result set which is then used for instantiating triple patterns. We note that a <code>DELETE</code> may delete a triple which the <code>DELETE</code> has not read; thus the delete set is not a subset of the read set. The <a class="auto-href" href="http://dbpedia.org/resource/SQL" id="link-id0x1e3afb78">SQL</a> equivalent is the </p> <blockquote> <code><pre>DELETE FROM table WHERE key IN ( SELECT key1 FROM other_table )</pre> </code> </blockquote> <p>expression, supposing it were implemented as a scan of <code>other_table</code> and an index lookup followed by <code>DELETE</code> on table. </p> <p>The meaning of <code>INSERT</code> is that the triples in question exist after the operation, and the meaning of <code>DELETE</code> is that said triples do not exist. In a transactional context, this means that the after-image of the transaction is guaranteed either to have or not-have said triples. </p> <p>Suppose that the triples <code>{ 1 0 0 }</code>, <code>{ 1 5 6 }</code>, and <code>{ 1 5 7 }</code> exist in the beginning. If we <code>DELETE { 1 ?x ?y }</code> and concurrently <code>INSERT { 1 2 4 . 1 2 3 . 1 3 5 }</code>, then whichever was considered to be first by the concurrency control of the DBMS would complete first, and the other after that. Thus the end state would either have no triples with subject <code>1</code> or would have the three just inserted. </p> <p>Suppose the <code>INSERT</code> inserts the first triple, <code>{ 1 2 4 }</code>. The <code>DELETE</code> at the same time reads all triples with subject <code>1</code>. The exclusive read waits for the uncommitted <code>INSERT</code>. The <code>INSERT</code> then inserts the second triple, <code>{ 1 2 3 }</code>. Depending on the isolation of the read, this either succeeds, since no <code>{ 1 2 3 }</code> was read, or causes a deadlock. The first corresponds to <code>REPEATABLE READ</code> isolation; the second to <code>SERIALIZABLE</code>.</p> <p>We would not get the desired end-state of either <i>all the inserted triples</i> or <i>no triples with subject <code>1</code></i> if the read or the <code>DELETE</code> were not serializable.</p> <p>Furthermore if a <code>DELETE</code> template produced a triple that did not exist in the pre-image, the <code>DELETE</code> semantics still imply that this also does not exist in the after-image, which implies serializability.</p> <h2>Read and Update</h2> <p>Let us consider the prototypical transaction example of transferring funds from one account to another. Two balances are updated, and a history record is inserted.</p> <p>The initial state is </p> <blockquote> <code><pre>a balance 10 b balance 10</pre></code> </blockquote> <p>We transfer <code>1</code> from <code>a</code> to <code>b</code>, and at the same time transfer <code>2</code> from <code>b</code> to <code>a</code>. The end state must have <code>a</code> at <code>11</code> and <code>b</code> at <code>9</code>.</p> <p>A relational database needs <code>REPEATABLE READ</code> isolation for this.</p> <p>With RDF, <code>txn1</code> reads that <code>a</code> has a <code>balance</code> of <code>10</code>. At the same time, <code>txn1</code> reads the <code>balance</code> of <code>a</code>. <code>txn2</code> waits because the read of <code>txn1</code> is exclusive. <code>txn1</code> proceeds and read the <code>balance</code> of <code>b</code>. It then updates the <code>balance</code> of <code>a</code> and <code>b</code>. </p> <p>All goes without the deadlock which is always cited in this scenario, because the locks are acquired in the same order. The act of updating the balance of <code>a</code>, since RDF does not really have an update-in-place, consists of deleting <code>{ a balance 10 }</code> and inserting <code>{ a balance 9 }</code>. This gets done and <code>txn1</code> commits. At this point, <code>txn2</code> proceeds after its wait on the row that stated <code>{ a balance 10 }</code>. This row is now gone, and <code>txn2</code> sees that <code>a</code> has no balance, which is quite possible in RDF's <a class="auto-href" href="http://dbpedia.org/resource/Database_schema" id="link-id0x1ebb94c8">schema</a>-less model.</p> <p>We see that <code>REPEATABLE READ</code> is not adequate with RDF, even though it is with relational. The reason why there is no <code>UPDATE</code>-in-place is that the <code>PRIMARY KEY</code> of the triple includes all the parts, including the object. Even in a <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x1ca86578">RDBMS</a>, an <code>UPDATE</code> of a primary key part amounts to a <code>DELETE</code>-plus-<code>INSERT</code>. One could here argue that an implementation might still <code>UPDATE</code>-in-place if the key order were not changed. This would resolve the special case of the accounts but not a more general case.</p> <p>Thus we see that the read of the balance must be <code>SERIALIZABLE</code>. This means that the read locks the space before the first balance, so that no insertion may take place. In this way the read of <code>txn2</code> waits on the lock that is conceptually before the first possible match of <code>{ a balance ?x }</code>.</p> <h2>locking order and OLTP </h2> <p>To implement <a class="auto-href" href="http://www.tpc.org/" id="link-id0x1e811d68">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/C%2B%2B" id="link-id0x1df9c990">C</a>, I would update the table with the highest cardinality first, and then all tables in descending order of cardinality. In this way, the locks with the highest likelihood for contention are held for the least time. If locking multiple rows of a table, these should be locked in a deterministic order, e.g., lowest key-value first. In this way, the workload would not deadlock. In actual fact, with clusters and parallel execution, the lock acquisition will not be guaranteed to be serial, so deadlocks do not entirely go away, but still may get fewer. Besides, any outside transaction might still lock in the wrong order and cause deadlocks, which is why the OLTP application must in any case be built to deal with the possibility of deadlock.</p> <p>This is the conventional relational view of the matter. In more recent times, in-memory schemes with deterministic lock acquisition (<a href="http://cs-www.cs.yale.edu/homes/dna/papers/determinism-vldb10.pdf" id="link-id0x1c5d9340">Abadi VLDB 2010</a>) or single-threaded atomic execution of transactions (<a href="http://bird.cs.tu-berlin.de:8008/birte2010/" id="link-id0x1ec0ed18">Uni Munich BIRTE workshop at VLDB2010</a>, <a href="http://www.voltdb.com/" id="link-id0x1ab6e380">VoltDB</a>) have been proposed. There the transaction is described as a stored procedure, possibly with extra annotations. These techniques might apply to RDF also. RDF is however an unlikely model for transaction-intensive applications, so we will not for now examine these further.</p> <p>RDBMS usually implement row-level locking. This means that once a column of a row has an uncommitted state, any other transaction is prevented from changing the row. This has no ready RDF equivalent. RDF is usually implemented as a row-per-triple system and applying row-level locking to this does not give the semantic one expects of a relational row. </p> <p>I would argue that it is not essential to enforce transactional guarantees in units of rows. The guarantees must apply between data that is <i>read</i> and <i>written</i> by a transaction. It does not need to apply to columns that the transaction does not reference. To take the TPC-C example, the <i>new order</i> transaction updates the stock level and the <i>delivery</i> transaction updates the delivery count on the stock table. In practice, a <i>delivery</i> and a <i>new order</i> falling on the same row of stock will lock each other out, but nothing in the semantics of the workload mandates this.</p> <p>It does not seem <i>a priori</i> necessary to recreate the row as a unit of concurrency control in RDF. One could say that a multi-attribute whole (such as an address) ought to be atomic for concurrency control, but then applications updating addresses will most likely read and update all the fields together even if only the street name changes.</p> <h2>Pessimistic Vs. Optimistic Concurrency Control </h2> <p>We have so far spoken only in terms of row-level locking, which is to my <a class="auto-href" href="http://dbpedia.org/resource/Knowledge" id="link-id0x1ebbf3f8">knowledge</a> the most widely used model in RDBMS, and one we implement ourselves. Some databases (e.g., <a class="auto-href" href="http://dbpedia.org/resource/MonetDB" id="link-id0x1e771f48">MonetDB</a> and <a class="auto-href" href="http://www.ingres.com/vectorwise/" id="link-id0x1f3b4830">VectorWise</a>) implement optimistic concurrency control. The general idea is that each transaction has a read and write set and when a transaction commits, any other transactions whose read or write set intersects with the write set of the committing transaction are marked un-committable. Once a transaction thus becomes un-committable, it may presumably continue reading indefinitely but may no longer commit its updates. Optimistic concurrency is generally coupled with multi-version semantics where the pre-image of a transaction is a clean committed state of the database as of a specific point in time, i.e., snapshot isolation. </p> <p>To implement <code>SERIALIZABLE</code> isolation, i.e., the guarantee that if a transaction twice performs a <code>COUNT</code> the result will be the same, one locks also the row that precedes the set of selected rows and marks each lock so as to prevent an insert to the right of the lock in key order. The same thing may be done in an optimistic setting.</p> <p> <a href="http://event.cwi.nl/SIGMOD-RWE/2010/22-7f15a1/paper.pdf" id="link-id0x1d5de810">Positional Handling of Updates in Column Stores</a> [Heman, Zukowski, <a class="auto-href" href="http://dbpedia.org/resource/National_Research_Institute_for_Mathematics_and_Computer_Science" id="link-id0x1e7644d8">CWI</a> science library] discusses management of multiple consecutive snapshots in some detail. The paper does not go into the details of different levels of isolation but nothing there suggests that serializability could not be supported. There is some complexity in marking the space between ordered rows as non-insertable across multiple versions but this should be feasible enough. </p> <p>The issue of optimistic Vs. pessimistic concurrency does not seem to be affected by the differences between RDF and relational models. We note that an OLTP workload can be made to run with very few transaction aborts (deadlocks) by properly ordering operations when using a locking scheme. The same does not work with optimistic concurrency since updates happen immediately and transaction aborts occur whenever the writes of one intersect the reads or writes of another, regardless of the order in which these were made.</p> <p>Developers seldom understand transactions; therefore DBMS should, within the limits of the possible, optimize locking order for locking schemes. A simple example is locking in key order when doing an operation on a set of values. A more complex variant would consist of analyzing data dependencies in stored procedures and reordering updates so as to get the highest cardinality tables first. We note that this latter trick also benefits optimistic schemes.</p> <p>In RDF, the same principles apply but distinguishing cardinality of an updated set will have to rely on statistics of predicate cardinality. Such are anyhow needed for query <a class="auto-href" href="http://dbpedia.org/resource/Program_optimization" id="link-id0x1f05c1a8">optimization</a>.</p> <h2>Eventual Consistency </h2> <p>Web scale systems that need to maintain consistent state across multiple data centers sometimes use "eventual consistency" schemes. <a class="auto-href" href="http://dbpedia.org/resource/Two-phase_commit_protocol" id="link-id0x1cebd340">Two-phase-commit</a> becomes very inefficient as latency increases, thus strict transactional semantics have prohibitive cost if the system is more distributed than a cluster with a fast interconnect.</p> <p>Eventual consistency schemes (<a href="http://dbpedia.org/page/Dynamo_(storage_system)" id="link-id0x1f9db8f8">Amazon Dynamo</a>, <a href="http://research.yahoo.com/project/212" id="link-id0x1da3db80">Yahoo! PNUTS</a>) maintain history <a class="auto-href" href="http://dbpedia.org/resource/Information" id="link-id0x1ec4dbc8">information</a> on the record which is the unit of concurrency control. The record is typically a non-first normal form chunk of related data that it makes sense to store together from the application's viewpoint. Application logic can then be applied to reconciling differing copies of the same logical record. </p> <p>Such a scheme seems <i>a priori</i> ill-suited for RDF, where the natural unit of concurrency control would seem to be the quad. We first note that only recently changed (i.e., <code>DELETEd + INSERTed</code> quads, as there is no <code>UPDATE</code>-in-place) need history information. This history information can be stored away from the quad itself, thus not disrupting compression. When detecting that one site has <code>INSERTed</code> a quad that another has <code>DELETEd</code> in the same general time period, application logic can still be applied for reading related quads in order to arrive at a decision on how to reconcile two databases that have diverged. The same can apply to conflicting values of properties that for the application should be single-valued. Comparing time-stamped transaction logs on quads is not fundamentally different from comparing record histories in Dynamo or PNUTS.</p> <p>As we overcome the data size penalties that have until recently been associated with RDF, RDF becomes even more interesting as a data model for large online systems such as social network platforms where frequent application changes lead to volatility of schema. Key value stores are currently found in such applications, but they generally do not provide the query flexibility at which RDF excels. </p> <h2>Conclusions </h2> <p>We have gone over basic aspects of the endlessly complex and variable topic of transactions, and drawn parallels as well as outlined two basic differences between relational and RDF systems: What used to be <code>REPEATABLE READ</code> becomes <code>SERIALIZABLE</code>; and row-level locking becomes locking at the level of a single attribute value. For the rest, we see that the optimistic and pessimistic modes of concurrency control, as well as guidelines for writing transaction procedures, remain much the same.</p> <p>Based on this overview, it should be possible to design an ACID test for describing the ACID behavior of benchmarked systems. We do not intend to make transaction support a qualification requirement for an RDF benchmark, but information on transaction support will still be valuable in comparing different systems.</p>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-03-22T18:24:26-04:00
RDF and Transactions
http://www.openlinksw.com/weblog/oerling/?id=1689
2011-03-22T22:52:56Z
<p>I will here talk about <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x235282b8">RDF</a> and transactions for developers in general. The next one talks about specifics and is for specialists.</p> <p>Transactions are certainly not the first thing that comes to mind when one hears "RDF". We have at times used a recruitment questionnaire where we ask applicants to define a transaction. Many vaguely remember that it is a unit of work, but usually not more than that. We sometimes get questions from users about why they get an error message that says "deadlock". "Deadlock" is what happens when multiple users concurrently update balances on multiple bank accounts in the wrong order. What does this have to do with RDF?</p> <p>There are in fact users who even use XA with a <a class="auto-href" href="http://virtuoso.openlinksw.com" id="link-id0x235e5938">Virtuoso</a>-based RDF application. <a class="auto-href" href="http://semanticweb.org/id/Franz_Inc" id="link-id0x28c09308">Franz</a> also has publicized their development of full <a class="auto-href" href="http://dbpedia.org/resource/ACID" id="link-id0x2365f710">ACID</a> capabilities for <a class="auto-href" href="http://semanticweb.org/id/AllegroGraph" id="link-id0x22caecb0">AllegroGraph</a>. RDF is a database <a class="auto-href" href="http://dbpedia.org/resource/Database_schema" id="link-id0x235f1f70">schema</a> model, and transactions will inevitably become an issue in databases.</p> <p>At the same time, the developer population trained with <a class="auto-href" href="http://dbpedia.org/resource/MySQL" id="link-id0x240f6a90">MySQL</a> and <a class="auto-href" href="http://dbpedia.org/resource/PHP" id="link-id0x238cd088">PHP</a> is not particularly transaction-aware. Transactions have gone out of style, declares the No-<a class="auto-href" href="http://dbpedia.org/resource/SQL" id="link-id0x232d9068">SQL</a> crowd. Well, it is not so much SQL they object to but ACID, i.e., transactional guarantees. We will talk more about this in the next post. The <a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x238c70a0">SPARQL</a> language and protocol do not go into transactions, except for expressing the wish that an <code>UPDATE</code> request to an end-point be atomic. But beware -- atomicity is a gateway drug, and soon one finds oneself on full ACID. </p> <p>If one says that a thing will either happen <i>in its entirety</i> or <i>not at all,</i> which is what (A) atomicity means, then the question arises of (I) isolation; that is, what happens if somebody else does something to the same <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x23eadf50">data</a> at the same time? Then comes the question of whether a thing, once having happened, will stay that way; i.e., (D) durability. Finally, there is (<a class="auto-href" href="http://dbpedia.org/resource/C%2B%2B" id="link-id0x23a1e280">C</a>) consistency, which means that the transaction's result must not contradict restrictions the database is supposed to enforce. RDF usually has no restrictions; thus consistency mostly means that the internal state of the DBMS must be consistent, e.g., different indices on triples/quads should contain the same data.</p> <p>There are, of course, database-like consistency criteria that one can express in RDF Schema and <a class="auto-href" href="http://dbpedia.org/resource/Web_Ontology_Language" id="link-id0x287b18e8">OWL</a>, concerning data types, mandatory presence of properties, or restrictions on cardinality (i.e., one may only have one spouse at a time, and the like). </p> <p>If one indeed did enforce them all, then RDF would be very like the relational model -- with all the restrictions, but without the 40 years of work on <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x2450b488">RDBMS</a> performance. For this reason, RDF use tends to involve data that is not structured enough to be a good fit for RDBMS.</p> <p>There is of course the OWL side, where consistency is important but is defined in such complex ways that they again are not a good fit for RDBMS. RDF could be seen to be split between the schema-last world and the <a class="auto-href" href="http://dbpedia.org/resource/Knowledge" id="link-id0x2324ac40">knowledge</a> representation world. I will here focus on the schema-last side.</p> <p>Transactions are relevant in RDF in two cases: 1. If data is trickle loaded in small chunks, one likes to know that the chunks do not get lost or corrupted; 2. If the application has any semantics that reserve resources, then these operations need transactions. The latter is not so common with RDF but examples include read-write situations, like checking if a seat is available and then reserving it. Transactionality guarantees that the same seat does not get reserved twice.</p> <p>Web people argue with some justification that since the four cardinal virtues of database never existed on the web to begin with, applying strict ACID to web data is beside the point, like locking the stable after the horse has long since run away. This may be so; yet the systems used for processing data, whether that data is dirty or not, benefit from predictable operation under concurrency and from not losing data.</p> <p>Analytics workloads are not primarily about transactions, but still need to specify what happens with updates. Analyzing data from measurements may not have concurrent updates, but there the transaction issue is replaced by the question of making explicit how the data was acquired and what processing has been applied to it before storage.</p> <p>As mentioned before, the <a class="auto-href" href="http://lod2.eu/" id="link-id0x28ac0250">LOD2</a> project is at the crossroads of RDF and database. I construe its mission to be the making of RDF into a respectable database discipline. Database respectability in turn is as good as inconceivable without addressing the very bedrock on which this science was founded: transactions.</p> <p>As previously argued, we need well-defined and auditable benchmarks. This again brings up the topic of transactions. Once we embark on the database benchmark route, there is no way around this. <a class="auto-href" href="http://www.tpc.org/" id="link-id0x284d2d80">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x280dcd40">H</a> mandates that the system under test support transactions, and the audit involves a test for this. We can do no less.</p> <p>This has led me to more closely examine the issue of RDF and transactions, and whether there exist differences between transactions applied to RDF and to relational data. </p> <p>As concerns Virtuoso, our position has been that one can get full ACID in Virtuoso, whether in SQL or SPARQL, by using a connected client (e.g., <a class="auto-href" href="http://dbpedia.org/resource/Open_Database_Connectivity" id="link-id0x235cecf0">ODBC</a>, <a class="auto-href" href="http://dbpedia.org/resource/Java_Database_Connectivity" id="link-id0x27c4a0c0">JDBC</a>, or the <a class="auto-href" href="http://jena.sourceforge.net/" id="link-id0x283a89a8">Jena</a> or <a class="auto-href" href="http://sourceforge.net/projects/sesame/" id="link-id0x284b3490">Sesame</a> frameworks), and setting the isolation options on the connection. Having taken this step, one then must take the next step, which consists of dealing with deadlocks; i.e., with concurrent utilization, it may happen that the database at any time notifies the client that the transaction got aborted and the client must retry.</p> <p>Web developers especially do not like this, because this is not what MySQL has taught them to expect. MySQL does have transactional back-ends like InnoDB, but often gets used without transactions.</p> <p>With the March 2011 Virtuoso releases, we have taken a closer look at transactions with RDF. It is more practical to reduce the possibility of errors than to require developers to pay attention. For this reason we have automated isolation settings for RDF, greatly reduced the incidence of deadlocks, and even incorporated automatic deadlock retries where applicable.</p> <p>If all users lock resources they need in the same order, there will be no deadlocks. This is what we do with RDF load in Virtuoso 7; thus any mix of concurrent <code>INSERTs</code> and <code>DELETEs</code>, if these are under a certain size (normally 10000 quads) are guaranteed never to fail due to locking. These could still fail due to running out of space, though. With previous versions, there always was a possibility of having an <code>INSERT</code> or <code>DELETE</code> fail because of deadlock with multiple users. Vectored <code>INSERT</code> and <code>DELETE</code> are sufficient for making web crawling or archive maintenance practically deadlock free, since there the primary transaction is the <code>INSERT</code> or <code>DELETE</code> of a small graph. </p> <p>Furthermore, since the <a class="auto-href" href="http://www.w3.org/TR/rdf-sparql-protocol/" id="link-id0x22ca4300">SPARQL protocol</a> has no way of specifying transactions consisting of multiple client-server exchanges, the SPARQL end-point may deal with deadlocks by itself. If all else fails, it can simply execute requests one after the other, thus eliminating any possibility of locking. We note that many statements will be intrinsically free of deadlocks by virtue of always locking in key order, but this cannot be universally guaranteed with arbitrary size operations; thus concurrent operations might still sometimes deadlock. Anyway, vectored execution as introduced in Virtuoso 7, besides getting easily double-speed random access, also greatly reduces deadlocks by virtue of ordering operations.</p> <p>In the next post we will talk about what transactions mean with RDF and whether there is any difference with the relational model.</p>
Orri Erling
oerling@openlinksw.com
2011-03-22T17:44:14-04:00
RDF and Transactions
http://www.openlinksw.com/blog/vdb/blog/?id=1690
2011-03-22T22:52:56Z
<p>I will here talk about <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x249bc940">RDF</a> and transactions for developers in general. The next one talks about specifics and is for specialists.</p> <p>Transactions are certainly not the first thing that comes to mind when one hears "RDF". We have at times used a recruitment questionnaire where we ask applicants to define a transaction. Many vaguely remember that it is a unit of work, but usually not more than that. We sometimes get questions from users about why they get an error message that says "deadlock". "Deadlock" is what happens when multiple users concurrently update balances on multiple bank accounts in the wrong order. What does this have to do with RDF?</p> <p>There are in fact users who even use XA with a <a class="auto-href" href="http://virtuoso.openlinksw.com" id="link-id0x22c8dbc8">Virtuoso</a>-based RDF application. <a class="auto-href" href="http://semanticweb.org/id/Franz_Inc" id="link-id0x27bd0c08">Franz</a> also has publicized their development of full <a class="auto-href" href="http://dbpedia.org/resource/ACID" id="link-id0x283985c8">ACID</a> capabilities for <a class="auto-href" href="http://semanticweb.org/id/AllegroGraph" id="link-id0x238ba438">AllegroGraph</a>. RDF is a database <a class="auto-href" href="http://dbpedia.org/resource/Database_schema" id="link-id0x2864fef8">schema</a> model, and transactions will inevitably become an issue in databases.</p> <p>At the same time, the developer population trained with <a class="auto-href" href="http://dbpedia.org/resource/MySQL" id="link-id0x284d2d80">MySQL</a> and <a class="auto-href" href="http://dbpedia.org/resource/PHP" id="link-id0x237230e8">PHP</a> is not particularly transaction-aware. Transactions have gone out of style, declares the No-<a class="auto-href" href="http://dbpedia.org/resource/SQL" id="link-id0x2920cc88">SQL</a> crowd. Well, it is not so much SQL they object to but ACID, i.e., transactional guarantees. We will talk more about this in the next post. The <a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x283f0588">SPARQL</a> language and protocol do not go into transactions, except for expressing the wish that an <code>UPDATE</code> request to an end-point be atomic. But beware -- atomicity is a gateway drug, and soon one finds oneself on full ACID. </p> <p>If one says that a thing will either happen <i>in its entirety</i> or <i>not at all,</i> which is what (A) atomicity means, then the question arises of (I) isolation; that is, what happens if somebody else does something to the same <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x238280f8">data</a> at the same time? Then comes the question of whether a thing, once having happened, will stay that way; i.e., (D) durability. Finally, there is (<a class="auto-href" href="http://dbpedia.org/resource/C%2B%2B" id="link-id0x276714b8">C</a>) consistency, which means that the transaction's result must not contradict restrictions the database is supposed to enforce. RDF usually has no restrictions; thus consistency mostly means that the internal state of the DBMS must be consistent, e.g., different indices on triples/quads should contain the same data.</p> <p>There are, of course, database-like consistency criteria that one can express in RDF Schema and <a class="auto-href" href="http://dbpedia.org/resource/Web_Ontology_Language" id="link-id0x28625a90">OWL</a>, concerning data types, mandatory presence of properties, or restrictions on cardinality (i.e., one may only have one spouse at a time, and the like). </p> <p>If one indeed did enforce them all, then RDF would be very like the relational model -- with all the restrictions, but without the 40 years of work on <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x249bf4f8">RDBMS</a> performance. For this reason, RDF use tends to involve data that is not structured enough to be a good fit for RDBMS.</p> <p>There is of course the OWL side, where consistency is important but is defined in such complex ways that they again are not a good fit for RDBMS. RDF could be seen to be split between the schema-last world and the <a class="auto-href" href="http://dbpedia.org/resource/Knowledge" id="link-id0x249504f8">knowledge</a> representation world. I will here focus on the schema-last side.</p> <p>Transactions are relevant in RDF in two cases: 1. If data is trickle loaded in small chunks, one likes to know that the chunks do not get lost or corrupted; 2. If the application has any semantics that reserve resources, then these operations need transactions. The latter is not so common with RDF but examples include read-write situations, like checking if a seat is available and then reserving it. Transactionality guarantees that the same seat does not get reserved twice.</p> <p>Web people argue with some justification that since the four cardinal virtues of database never existed on the web to begin with, applying strict ACID to web data is beside the point, like locking the stable after the horse has long since run away. This may be so; yet the systems used for processing data, whether that data is dirty or not, benefit from predictable operation under concurrency and from not losing data.</p> <p>Analytics workloads are not primarily about transactions, but still need to specify what happens with updates. Analyzing data from measurements may not have concurrent updates, but there the transaction issue is replaced by the question of making explicit how the data was acquired and what processing has been applied to it before storage.</p> <p>As mentioned before, the <a class="auto-href" href="http://lod2.eu/" id="link-id0x27d952d0">LOD2</a> project is at the crossroads of RDF and database. I construe its mission to be the making of RDF into a respectable database discipline. Database respectability in turn is as good as inconceivable without addressing the very bedrock on which this science was founded: transactions.</p> <p>As previously argued, we need well-defined and auditable benchmarks. This again brings up the topic of transactions. Once we embark on the database benchmark route, there is no way around this. <a class="auto-href" href="http://www.tpc.org/" id="link-id0x2359d2d0">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x28edb770">H</a> mandates that the system under test support transactions, and the audit involves a test for this. We can do no less.</p> <p>This has led me to more closely examine the issue of RDF and transactions, and whether there exist differences between transactions applied to RDF and to relational data. </p> <p>As concerns Virtuoso, our position has been that one can get full ACID in Virtuoso, whether in SQL or SPARQL, by using a connected client (e.g., <a class="auto-href" href="http://dbpedia.org/resource/Open_Database_Connectivity" id="link-id0x23a55698">ODBC</a>, <a class="auto-href" href="http://dbpedia.org/resource/Java_Database_Connectivity" id="link-id0x235cecf0">JDBC</a>, or the <a class="auto-href" href="http://jena.sourceforge.net/" id="link-id0x23213900">Jena</a> or <a class="auto-href" href="http://sourceforge.net/projects/sesame/" id="link-id0x277874d0">Sesame</a> frameworks), and setting the isolation options on the connection. Having taken this step, one then must take the next step, which consists of dealing with deadlocks; i.e., with concurrent utilization, it may happen that the database at any time notifies the client that the transaction got aborted and the client must retry.</p> <p>Web developers especially do not like this, because this is not what MySQL has taught them to expect. MySQL does have transactional back-ends like InnoDB, but often gets used without transactions.</p> <p>With the March 2011 Virtuoso releases, we have taken a closer look at transactions with RDF. It is more practical to reduce the possibility of errors than to require developers to pay attention. For this reason we have automated isolation settings for RDF, greatly reduced the incidence of deadlocks, and even incorporated automatic deadlock retries where applicable.</p> <p>If all users lock resources they need in the same order, there will be no deadlocks. This is what we do with RDF load in Virtuoso 7; thus any mix of concurrent <code>INSERTs</code> and <code>DELETEs</code>, if these are under a certain size (normally 10000 quads) are guaranteed never to fail due to locking. These could still fail due to running out of space, though. With previous versions, there always was a possibility of having an <code>INSERT</code> or <code>DELETE</code> fail because of deadlock with multiple users. Vectored <code>INSERT</code> and <code>DELETE</code> are sufficient for making web crawling or archive maintenance practically deadlock free, since there the primary transaction is the <code>INSERT</code> or <code>DELETE</code> of a small graph. </p> <p>Furthermore, since the <a class="auto-href" href="http://www.w3.org/TR/rdf-sparql-protocol/" id="link-id0x23eadf50">SPARQL protocol</a> has no way of specifying transactions consisting of multiple client-server exchanges, the SPARQL end-point may deal with deadlocks by itself. If all else fails, it can simply execute requests one after the other, thus eliminating any possibility of locking. We note that many statements will be intrinsically free of deadlocks by virtue of always locking in key order, but this cannot be universally guaranteed with arbitrary size operations; thus concurrent operations might still sometimes deadlock. Anyway, vectored execution as introduced in Virtuoso 7, besides getting easily double-speed random access, also greatly reduces deadlocks by virtue of ordering operations.</p> <p>In the next post we will talk about what transactions mean with RDF and whether there is any difference with the relational model.</p>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-03-22T17:44:21-04:00
Benchmarks, Redux (part 15): BSBM Test Driver Enhancements
http://www.openlinksw.com/weblog/oerling/?id=1684
2011-03-22T22:32:28Z
<p>This article covers the changes we have made to the <a class="auto-href" href="http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/spec/index.html" id="link-id0x283a2528">BSBM</a> test driver during our series of experiments.</p> <ul> <li> <p> <b>Drill-down mode</b> - For queries that have a product type as parameter, the test driver will invoke the query multiple times with each time a random subtype of the product type of the previous invocation. The starting point of the drill-down is an a random type from a settable level in the hierarchy. The rationale for the drill-down mode is that depending on the parameter choice, there can be 1000x differences in query run time. Thus run times of consecutive query mixes will be incomparable unless we guarantee that each mix has a predictable number of queries with a product type from each level in the hierarchy.</p> </li> <li> <b>Permutation of query mix</b> - In the BI workload, the queries are run in a random order on each thread in multiuser mode. Doing exactly the same thing on many threads is not realistic for large queries. The <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x23880860">data</a> access patterns must be spread out in order to evaluate how bulk IO is organized with differing concurrent demands. The permutations are deterministic on consecutive runs and do not depend on the non-deterministic timing of concurrent activities. For queries with a drill-down, the individual executions that make up the drill-down are still consecutive.</li> <li> <p> <b>New metrics</b> - The BI Power is the geometric mean of query run times scaled to queries per hour and multiplied by the scale factor, where 100 Mt is considered the unit scale. The BI Throughput is the arithmetic mean of the run times scaled to QPH and adjusted to scale as with the Power metric. These are analogous to the <a class="auto-href" href="http://www.tpc.org/" id="link-id0x28ccd3f8">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x29ad25c8">H</a> Power and Throughput metrics. </p> <p>The <i>Power</i> is defined as</p> <blockquote>(scale_factor / 284826) * 3600 / ((t0 * t1 * ... * tn) ^(1 / n)) </blockquote> <p>The <i>Throughput</i> is defined as</p> <blockquote>(scale_factor / 284826) * 3600 / ((t0 + t2 + ... + tn) / n)</blockquote> <p>The magic number 284826 is the scale that generates approximately 100 million triples (100 Mt). We consider this "scale one." The reason for the multiplication is that scores at different scales should get similar numbers, otherwise 10x larger scale would result roughly in 10x lower throughput with the BI queries.</p> <p>We also show the percentage each query represents from the total time the test driver waits for responses. </p> </li> <li> <p> <b>Deadlock retry</b> - When running update mixes, it is possible that a transaction gets aborted by a deadlock. We have made a retry logic for this.</p> </li> <li> <p> <b>Cluster mode</b> - Cluster databases may have multiple interchangeable <a class="auto-href" href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x236532c8">HTTP</a> listeners. With this mode, one can specify multiple end-points so a multi-user workload can divide itself evenly over these.</p> </li> <li> <p> <b>Identifying matter</b> - A version number was added to test driver output. Use of the new switches is also indicated in the test driver output.</p> </li> <li> <p> <b>SUT <a class="auto-href" href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x249c8f68">CPU</a></b> - In comparing results it is crucial to differentiate between in memory runs and IO bound runs. To make this easier, we have added an option to report server CPU times over the timed portion (excluding warm-ups). A pluggable self-script determines the CPU times for the system; thus clusters can be handled, too. The time is given as a sum of the time the server processes have aged during the run and as a percentage over the wall-clock time.</p> </li> </ul> <p>These changes will soon be available <a href="http://blogs.usnet.private:8893/RPC2" id="link-id0x1f9a57c0">as a diff</a> and <a href="http://blogs.usnet.private:8893/RPC2" id="link-id0x1f2fea08">as a source tree</a>. This version is labeled <b><code>BSBM Test Driver 1.1-opl</code></b>; the <b><code>-opl</code></b> signifies OpenLink additions. </p> <p>We invite FU Berlin to include these enhancements into their Source Forge repository of the BSBM test driver. There is more precise documentation of these options in the README file in the above distribution.</p> <p>The next planned upgrade of the test driver concerns adding support for "<a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x23de9eb8">RDF</a>-H", the RDF adaptation of the industry standard TPC-H decision support benchmark for <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x22cca4e0">RDBMS</a>.</p> <h3> <i>Benchmarks, Redux</i> Series</h3> <ul> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1658" id="link-id0x1db2be00">Benchmarks, Redux (part 1): On RDF Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1660" id="link-id0x1dfcc038">Benchmarks, Redux (part 2): A Benchmarking Story</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1663" id="link-id0x197c26d0">Benchmarks, Redux (part 3): Virtuoso 7 vs 6 on BSBM Load and Explore</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1665" id="link-id0x1d149cf0">Benchmarks, Redux (part 4): Benchmark Tuning Questionnaire</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1667" id="link-id0x1ab69450">Benchmarks, Redux (part 5): BSBM and I/O; HDDs and SSDs </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1669" id="link-id0x1e67d688">Benchmarks, Redux (part 6): BSBM and I/O, continued</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1dad87c8">Benchmarks, Redux (part 7): What Does BSBM Explore Measure?</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1673" id="link-id0x1cc73830">Benchmarks, Redux (part 8): BSBM Explore and Update </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1675" id="link-id0x1d6879a8">Benchmarks, Redux (part 9): BSBM With Cluster</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1677" id="link-id0x1dfae510">Benchmarks, Redux (part 10): LOD2 and the Benchmark Process</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1678" id="link-id0x1ef052a0">Benchmarks, Redux (part 11): The Substance of Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1dadddb0">Benchmarks, Redux (part 12): Our Own BSBM Results Report</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1e662ef0">Benchmarks, Redux (part 13): BSBM BI Modifications </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1df6fa70">Benchmarks, Redux (part 14): BSBM BI Mix </a> </li> <li> Benchmarks, Redux (part 15): BSBM Test Driver Enhancements <i>(this post)</i> </li> </ul>
Orri Erling
oerling@openlinksw.com
2011-03-22T17:04:29-04:00
Benchmarks, Redux (part 15): BSBM Test Driver Enhancements
http://www.openlinksw.com/blog/vdb/blog/?id=1688
2011-03-22T22:32:28Z
<p>This article covers the changes we have made to the <a class="auto-href" href="http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/spec/index.html" id="link-id0x2361bf18">BSBM</a> test driver during our series of experiments.</p> <ul> <li> <p> <b>Drill-down mode</b> - For queries that have a product type as parameter, the test driver will invoke the query multiple times with each time a random subtype of the product type of the previous invocation. The starting point of the drill-down is an a random type from a settable level in the hierarchy. The rationale for the drill-down mode is that depending on the parameter choice, there can be 1000x differences in query run time. Thus run times of consecutive query mixes will be incomparable unless we guarantee that each mix has a predictable number of queries with a product type from each level in the hierarchy.</p> </li> <li> <b>Permutation of query mix</b> - In the BI workload, the queries are run in a random order on each thread in multiuser mode. Doing exactly the same thing on many threads is not realistic for large queries. The <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x2834cec8">data</a> access patterns must be spread out in order to evaluate how bulk IO is organized with differing concurrent demands. The permutations are deterministic on consecutive runs and do not depend on the non-deterministic timing of concurrent activities. For queries with a drill-down, the individual executions that make up the drill-down are still consecutive.</li> <li> <p> <b>New metrics</b> - The BI Power is the geometric mean of query run times scaled to queries per hour and multiplied by the scale factor, where 100 Mt is considered the unit scale. The BI Throughput is the arithmetic mean of the run times scaled to QPH and adjusted to scale as with the Power metric. These are analogous to the <a class="auto-href" href="http://www.tpc.org/" id="link-id0x236c5158">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x28814950">H</a> Power and Throughput metrics. </p> <p>The <i>Power</i> is defined as</p> <blockquote>(scale_factor / 284826) * 3600 / ((t0 * t1 * ... * tn) ^(1 / n)) </blockquote> <p>The <i>Throughput</i> is defined as</p> <blockquote>(scale_factor / 284826) * 3600 / ((t0 + t2 + ... + tn) / n)</blockquote> <p>The magic number 284826 is the scale that generates approximately 100 million triples (100 Mt). We consider this "scale one." The reason for the multiplication is that scores at different scales should get similar numbers, otherwise 10x larger scale would result roughly in 10x lower throughput with the BI queries.</p> <p>We also show the percentage each query represents from the total time the test driver waits for responses. </p> </li> <li> <p> <b>Deadlock retry</b> - When running update mixes, it is possible that a transaction gets aborted by a deadlock. We have made a retry logic for this.</p> </li> <li> <p> <b>Cluster mode</b> - Cluster databases may have multiple interchangeable <a class="auto-href" href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x240f9008">HTTP</a> listeners. With this mode, one can specify multiple end-points so a multi-user workload can divide itself evenly over these.</p> </li> <li> <p> <b>Identifying matter</b> - A version number was added to test driver output. Use of the new switches is also indicated in the test driver output.</p> </li> <li> <p> <b>SUT <a class="auto-href" href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x249b7208">CPU</a></b> - In comparing results it is crucial to differentiate between in memory runs and IO bound runs. To make this easier, we have added an option to report server CPU times over the timed portion (excluding warm-ups). A pluggable self-script determines the CPU times for the system; thus clusters can be handled, too. The time is given as a sum of the time the server processes have aged during the run and as a percentage over the wall-clock time.</p> </li> </ul> <p>These changes will soon be available <a href="http://blogs.usnet.private:8893/RPC2" id="link-id0x1f9a57c0">as a diff</a> and <a href="http://blogs.usnet.private:8893/RPC2" id="link-id0x1f2fea08">as a source tree</a>. This version is labeled <b><code>BSBM Test Driver 1.1-opl</code></b>; the <b><code>-opl</code></b> signifies OpenLink additions. </p> <p>We invite FU Berlin to include these enhancements into their Source Forge repository of the BSBM test driver. There is more precise documentation of these options in the README file in the above distribution.</p> <p>The next planned upgrade of the test driver concerns adding support for "<a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x2865ac68">RDF</a>-H", the RDF adaptation of the industry standard TPC-H decision support benchmark for <a class="auto-href" href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x23597bb0">RDBMS</a>.</p> <h3> <i>Benchmarks, Redux</i> Series</h3> <ul> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1658" id="link-id0x1db2be00">Benchmarks, Redux (part 1): On RDF Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1660" id="link-id0x1dfcc038">Benchmarks, Redux (part 2): A Benchmarking Story</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1663" id="link-id0x197c26d0">Benchmarks, Redux (part 3): Virtuoso 7 vs 6 on BSBM Load and Explore</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1665" id="link-id0x1d149cf0">Benchmarks, Redux (part 4): Benchmark Tuning Questionnaire</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1667" id="link-id0x1ab69450">Benchmarks, Redux (part 5): BSBM and I/O; HDDs and SSDs </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1669" id="link-id0x1e67d688">Benchmarks, Redux (part 6): BSBM and I/O, continued</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1dad87c8">Benchmarks, Redux (part 7): What Does BSBM Explore Measure?</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1673" id="link-id0x1cc73830">Benchmarks, Redux (part 8): BSBM Explore and Update </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1675" id="link-id0x1d6879a8">Benchmarks, Redux (part 9): BSBM With Cluster</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1677" id="link-id0x1dfae510">Benchmarks, Redux (part 10): LOD2 and the Benchmark Process</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1678" id="link-id0x1ef052a0">Benchmarks, Redux (part 11): The Substance of Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1dadddb0">Benchmarks, Redux (part 12): Our Own BSBM Results Report</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1e662ef0">Benchmarks, Redux (part 13): BSBM BI Modifications </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1df6fa70">Benchmarks, Redux (part 14): BSBM BI Mix </a> </li> <li> Benchmarks, Redux (part 15): BSBM Test Driver Enhancements <i>(this post)</i> </li> </ul>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-03-22T17:04:43-04:00
Benchmarks, Redux (part 14): BSBM BI Mix
http://www.openlinksw.com/weblog/oerling/?id=1683
2011-03-22T22:31:32Z
<p>In this post, we look at how we run the <a class="auto-href" href="http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/spec/index.html" id="link-id0x23be8d28">BSBM</a>-BI mix. We consider the 100 Mt and 1000 Mt scales with <a class="auto-href" href="http://virtuoso.openlinksw.com" id="link-id0x23b69e40">Virtuoso</a> 7 using the same hardware and software as in the previous posts. The changes to workload and metric are given in the previous post.</p> <p>Our intent here is to look at whether the metric works, and to see what results will look like in general. We are as much testing the benchmark as we are testing the system-under-test (SUT). The results shown here will likely not be comparable with future ones because we will most likely change the composition of the workload since it seems a bit out of balance. Anyway, for the sake of disclosure, we attach the query templates. The test driver we used will be made available soon, so the interested may still try a comparison with their systems. If you practice with this workload for the coming races, the effort will surely not be wasted.</p> <p>Once we have come up with a rules document, we will redo all that we have published so far by-the-book, and have it audited as part of the <a class="auto-href" href="http://lod2.eu/" id="link-id0x23a74c40">LOD2</a> service we plan for this (see previous posts in this series). This will introduce comparability; but before we get that far with the BI workload, the workload needs to evolve a bit.</p> <p>Below we show samples of test driver output; the whole output is <a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/BenchmarksReduxSupportingFiles/br.tar.gz" id="link-id0x1b703ad8">downloadable</a>.</p> <p>100 Mt Single User</p> <blockquote> <code><pre> bsbm/testdriver -runs 1 -w 0 -idir /bs/1 -drill \ -ucf bsbm/usecases/businessIntelligence/<a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x247b7e08">sparql</a>.txt \ -dg <a class="auto-href" href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x232a86b0">http</a>://bsbm.org http://localhost:8604/sparql </pre> </code> </blockquote> <blockquote> <code><pre> 0: 43348.14ms, total: 43440ms Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 43.3481s / 43.3481s Elapsed runtime: 43.348 seconds QMpH: 83.049 query mixes per hour CQET: 43.348 seconds average runtime of query mix CQET (geom.): 43.348 seconds geometric mean runtime of query mix AQET (geom.): 0.492 seconds geometric mean runtime of query Throughput: 1494.874 BSBM-BI throughput: qph*scale BI Power: 7309.820 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>100 Mt 8 User </p> <blockquote> <code><pre> Thread 6: query mix 3: 195793.09ms, total: 196086.18ms Thread 8: query mix 0: 197843.84ms, total: 198010.50ms Thread 7: query mix 4: 201806.28ms, total: 201996.26ms Thread 2: query mix 5: 221983.93ms, total: 222105.96ms Thread 4: query mix 7: 225127.55ms, total: 225317.49ms Thread 3: query mix 6: 225860.49ms, total: 226050.17ms Thread 5: query mix 2: 230884.93ms, total: 231067.61ms Thread 1: query mix 1: 237836.61ms, total: 237959.11ms Benchmark run completed in 237.985427s Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 195.7931s / 237.8366s Total runtime (sum): 1737.137 seconds Elapsed runtime: 1737.137 seconds QMpH: 121.016 query mixes per hour CQET: 217.142 seconds average runtime of query mix CQET (geom.): 216.603 seconds geometric mean runtime of query mix AQET (geom.): 2.156 seconds geometric mean runtime of query Throughput: 2178.285 BSBM-BI throughput: qph*scale BI Power: 1669.745 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>1000 Mt Single User</p> <blockquote> <code><pre> 0: 608707.03ms, total: 608768ms Scale factor: 2848260 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 608.7070s / 608.7070s Elapsed runtime: 608.707 seconds QMpH: 5.914 query mixes per hour CQET: 608.707 seconds average runtime of query mix CQET (geom.): 608.707 seconds geometric mean runtime of query mix AQET (geom.): 5.167 seconds geometric mean runtime of query Throughput: 1064.552 BSBM-BI throughput: qph*scale BI Power: 6967.325 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>1000 Mt 8 User </p> <blockquote> <code><pre> bsbm/testdriver -runs 8 -mt 8 -w 0 -idir /bs/10 -drill \ -ucf bsbm/usecases/businessIntelligence/sparql.txt \ -dg http://bsbm.org http://localhost:8604/sparql </pre> </code> </blockquote> <blockquote> <code><pre> Thread 3: query mix 4: 2211275.25ms, total: 2211371.60ms Thread 4: query mix 0: 2212316.87ms, total: 2212417.99ms Thread 8: query mix 3: 2275942.63ms, total: 2276058.03ms Thread 5: query mix 5: 2441378.35ms, total: 2441448.66ms Thread 6: query mix 7: 2804001.05ms, total: 2804098.81ms Thread 2: query mix 2: 2808374.66ms, total: 2808473.71ms Thread 1: query mix 6: 2839407.12ms, total: 2839510.63ms Thread 7: query mix 1: 2889199.23ms, total: 2889263.17ms Benchmark run completed in 2889.302566s Scale factor: 2848260 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 2211.2753s / 2889.1992s Total runtime (sum): 20481.895 seconds Elapsed runtime: 20481.895 seconds QMpH: 9.968 query mixes per hour CQET: 2560.237 seconds average runtime of query mix CQET (geom.): 2544.284 seconds geometric mean runtime of query mix AQET (geom.): 13.556 seconds geometric mean runtime of query Throughput: 1794.205 BSBM-BI throughput: qph*scale BI Power: 2655.678 BSBM-BI Power: qph*scale (geom) Metrics for Query: 1 Count: 8 times executed in whole run Time share 2.120884% of total execution time AQET: 54.299656 seconds (arithmetic mean) AQET(geom.): 34.607302 seconds (geometric mean) QPS: 0.13 Queries per second minQET/maxQET: 11.71547600s / 148.65379700s Metrics for Query: 2 Count: 8 times executed in whole run Time share 0.207382% of total execution time AQET: 5.309462 seconds (arithmetic mean) AQET(geom.): 2.737696 seconds (geometric mean) QPS: 1.34 Queries per second minQET/maxQET: 0.78729800s / 25.80948200s Metrics for Query: 3 Count: 8 times executed in whole run Time share 17.650472% of total execution time AQET: 451.893890 seconds (arithmetic mean) AQET(geom.): 410.481088 seconds (geometric mean) QPS: 0.02 Queries per second minQET/maxQET: 171.07262500s / 721.72939200s Metrics for Query: 5 Count: 32 times executed in whole run Time share 6.196565% of total execution time AQET: 39.661685 seconds (arithmetic mean) AQET(geom.): 6.849882 seconds (geometric mean) QPS: 0.18 Queries per second minQET/maxQET: 0.15696500s / 189.00906200s Metrics for Query: 6 Count: 8 times executed in whole run Time share 0.119916% of total execution time AQET: 3.070136 seconds (arithmetic mean) AQET(geom.): 2.056059 seconds (geometric mean) QPS: 2.31 Queries per second minQET/maxQET: 0.41524400s / 7.55655300s Metrics for Query: 7 Count: 40 times executed in whole run Time share 1.577963% of total execution time AQET: 8.079921 seconds (arithmetic mean) AQET(geom.): 1.342079 seconds (geometric mean) QPS: 0.88 Queries per second minQET/maxQET: 0.02205800s / 40.27761500s Metrics for Query: 8 Count: 40 times executed in whole run Time share 72.126818% of total execution time AQET: 369.323481 seconds (arithmetic mean) AQET(geom.): 114.431863 seconds (geometric mean) QPS: 0.02 Queries per second minQET/maxQET: 5.94377300s / 1824.57867400s </pre> </code> </blockquote> <p>The <a class="auto-href" href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x249ce740">CPU</a> for the multiuser runs stays above 1500% for the whole run. The CPU for the single user 100 Mt run is 630%; for the 1000 Mt run, this is 574%. This can be improved since the queries usually have a lot of <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x2871b1f0">data</a> to work on. But final <a class="auto-href" href="http://dbpedia.org/resource/Program_optimization" id="link-id0x22c95b90">optimization</a> is not our goal yet; we are just surveying the race track. The difference between a warm single user run and a cold single user run is about 15% with data on SSD; with data on disk, this would be more. The numbers shown are with warm <a class="auto-href" href="http://dbpedia.org/resource/Cache" id="link-id0x22ca4300">cache</a>. The single-user and multi-user Throughput difference, 1064 single-user vs. 1794 multi-user, is about what one would expect from the CPU utilization.</p> <p>With these numbers, the CPU does not appear badly memory-bound, else the increase would be less; also core multi-threading seems to bring some benefit. If the single-user run was at 800%, the Throughput would be 1488. The speed in excess of this may be attributed to core multi-threading, although we must remember that not every query mix is exactly the same length, so the figure is not exact. Core multi-threading does not seem to hurt, at the very least. Comparison of the same numbers with the column store will be interesting since it misses the cache a lot less and accordingly has better SMP scaling. The <a class="auto-href" href="http://dbpedia.org/resource/Intel_Corporation" id="link-id0x28814950">Intel</a> Nehalem memory subsystem is really pretty good.</p> <p> </p> <p>For reference, we show a run with Virtuoso 6 at 100Mt. </p> <blockquote> <code><pre> 0: 424754.40ms, total: 424829ms Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 424.7544s / 424.7544s Elapsed runtime: 424.754 seconds QMpH: 8.475 query mixes per hour CQET: 424.754 seconds average runtime of query mix CQET (geom.): 424.754 seconds geometric mean runtime of query mix AQET (geom.): 1.097 seconds geometric mean runtime of query Throughput: 152.559 BSBM-BI throughput: qph*scale BI Power: 3281.150 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>and 8 user </p> <blockquote> <code><pre> Thread 5: query mix 3: 616997.86ms, total: 617042.83ms Thread 7: query mix 4: 625522.18ms, total: 625559.09ms Thread 3: query mix 7: 626247.62ms, total: 626304.96ms Thread 1: query mix 0: 629675.17ms, total: 629724.98ms Thread 4: query mix 6: 667633.36ms, total: 667670.07ms Thread 8: query mix 2: 674206.07ms, total: 674256.72ms Thread 6: query mix 5: 695020.21ms, total: 695052.29ms Thread 2: query mix 1: 701824.67ms, total: 701864.91ms Benchmark run completed in 701.909341s Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 616.9979s / 701.8247s Total runtime (sum): 5237.127 seconds Elapsed runtime: 5237.127 seconds QMpH: 41.031 query mixes per hour CQET: 654.641 seconds average runtime of query mix CQET (geom.): 653.873 seconds geometric mean runtime of query mix AQET (geom.): 2.557 seconds geometric mean runtime of query Throughput: 738.557 BSBM-BI throughput: qph*scale BI Power: 1408.133 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>Having the numbers, let us look at the metric and its scaling. We take the geometric mean of the single-user Power and the multiuser Throughput.</p> <blockquote> <code><pre> 100 Mt: sqrt ( 7771 * 2178 ); = 4114 1000 Mt: sqrt ( 6967 * 1794 ); = 3535 </pre> </code> </blockquote> <p>Scaling seems to work; the results are in the same general ballpark. The real times for the 1000 Mt run are a bit over 10x the times for the 100Mt run, as expected. The relative percentages of the queries are about the same on both scales, with the drill-down in Q8 alone being 77% and 72% respectively. The Q8 drill-down starts at the root of the product hierarchy. If we made this start one level from the top, its share would drop. This seems reasonable.</p> <p>Conversely, Q2 is out of place, with far too little share of the time. It takes a product as a starting point and shows a list of products with common features, sorted by descending count of common features. This would more appropriately be applied to a leaf product category instead, measuring how many of the products in the category have the top 20 features found in this category, to name an example.</p> <p>Also there should be more queries.</p> <p>At present it appears that BSBM-BI is definitely runnable, but a cursory look suffices to show that the workload needs more development and variety. We remember that I dreamt up the business questions last fall without much analysis, and that these questions were subsequently translated to SPARQL by FU Berlin. So, on one hand, BSBM-BI is of crucial importance because it is the first attempt at doing a benchmark with long running queries in SPARQL. On the other hand, BSBM-BI is not very good as a benchmark; <a class="auto-href" href="http://www.tpc.org/" id="link-id0x23227ce0">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x279c6700">H</a> is a lot better. This stands to reason, as TPC-H has had years and years of development and participation by many people.</p> <p>Benchmark queries are trick questions: For example, TPC-H Q18 cannot be done without changing an <code>IN</code> into a <code>JOIN</code> with the <code>IN</code> subquery in the outer loop and doing streaming aggregation. Q13 cannot be done without a well-optimized <code><a class="auto-href" href="http://dbpedia.org/resource/Hash_join" id="link-id0x238cbf88">HASH JOIN</a></code> which besides must be partitioned at the larger scales.</p> <p>Having such trick questions in an important benchmark eventually results in everybody doing the optimizations that the benchmark clearly calls for. Making benchmarks thus entails a responsibility ultimately to the end user, because an irrelevant benchmark might in the worst case send developers chasing things that are beside the point.</p> <p>In the following, we will look at what BSBM-BI requires from the database and how these requirements can be further developed and extended.</p> <p>BSBM-BI does not have any clear trick questions, at least not premeditatedly. BSBM-BI just requires a cost model that can guess the fanout of a <code>JOIN</code> and the cardinality of a <code>GROUP BY</code>; it is enough to distinguish smaller from greater; the guess does not otherwise have to be very good. Further, the queries are written in the benchmark text so that joining from left to right would work, so not even a cost-based optimizer is strictly needed. I did however have to add some cardinality statistics to get reasonable <code>JOIN</code> order since we always reorder the query regardless of the source formulation.</p> <p>BSBM-BI does have variable selectivity from the drill-downs; thus these may call for different <code>JOIN</code> orders for different parameter values. I have not looked into whether this really makes a difference, though.</p> <p>There are places in BSBM-BI where using a <code>HASH JOIN</code> makes sense. We do not use <code>HASH JOINs</code> with <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x235d8d88">RDF</a> because there is an index for everything and making a <code>HASH JOIN</code> in the wrong place can have a large up-front cost, so one is more robust against cost model errors if one does not do <code>HASH JOINs</code>. This said, a <code>HASH JOIN</code> in the right place is a lot better than an index lookup. With TPC-H Q13, our best <code>HASH JOIN</code> is over 2x better than the best <code>INDEX</code>-based <code>JOIN</code>, both being well tuned. For questions like "count the hairballs made in <a class="auto-href" href="http://dbpedia.org/resource/Germany" id="link-id0x2358ae60">Germany</a> reviewed by Japanese Hello Kitty fans," where two ends of a <code>JOIN</code> path are fairly selective doing the other as a <code>HASH JOIN</code> is good. This can, if the <code>JOIN</code> is always cardinality-reducing, even be merged inside an <code>INDEX</code> lookup. We have such capabilities since we have been for a while gearing up for the relational races, but are not using any of these with BSBM-BI, although they would be useful.</p> <p>Let us see the profile for a single user 100 Mt run.</p> <p>The database activity summary is --</p> <p> <code>select db_activity (0, 'http');</code> </p> <p> <code> 161.3M rnd 210.2M seq 0 same seg 104.5M same pg 45.08M same par 0 disk 0 spec disk 0B / 0 messages 2.393K fork</code> </p> <p>See the post "<a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1b1f3068">What Does BSBM Explore Measure</a>" for an explanation of the numbers. We see that there is more sequential access than random and the random has fair locality with over half on the same page as the previous and a lot of the rest falling under the same parent. Funnily enough, the explore mix has more locality. Running with a longer vector size would probably increase performance by getting better locality. There is an optimization that adjusts vector size on the fly if locality is not sufficient but this is not being used here. So we manually set vector size to 100000 instead of the default 10000. We get --</p> <p> <code> 172.4M rnd 220.8M seq 0 same seg 149.6M same pg 10.99M same par 21 disk 861 spec disk 0B / 0 messages 754 fork</code> </p> <p>The throughput goes from 1494 to 1779. We see more hits on the same page, as expected. We do not make this setting a default since it raises the cost for small queries; therefore the vector size must be self-adjusting -- besides, expecting a DBA to tune this is not reasonable. We will just have to correctly tune the self-adjust logic, and we have again clear gains.</p> <p>Let us now go back to the first run with vector size 10000.</p> <p>The top of the CPU <code>oprofile</code> is as follows:</p> <blockquote> <code><pre> 722309 15.4507 cmpf_iri64n_iri64n 434791 9.3005 cmpf_iri64n_iri64n_anyn_iri64n 294712 6.3041 itc_next_set 273488 5.8501 itc_vec_split_search 203970 4.3631 itc_dive_transit 199687 4.2714 itc_page_rcf_search 181614 3.8848 dc_itc_append_any 173043 3.7015 itc_bm_vec_row_check 146727 3.1386 cmpf_int64n 128224 2.7428 itc_vec_row_check 113515 2.4282 dk_alloc 97296 2.0812 page_wait_access 62523 1.3374 qst_vec_get_int64 59014 1.2623 itc_next_set_parent 53589 1.1463 sslr_qst_get 48003 1.0268 ds_add 46641 0.9977 dk_free_tree 44551 0.9530 kc_var_col 43650 0.9337 page_col_cmp_1 35297 0.7550 cmpf_iri64n_iri64n_anyn_gt_lt 34589 0.7399 dv_compare 25864 0.5532 cmpf_iri64n_anyn_iri64n_iri64n_lte 23088 0.4939 dk_free </pre> </code> </blockquote> <p>The top 10 are all index traversal, with the key compare for two leading IRI keys in the lead, corresponding to a lookup with <code>P</code> and <code>S</code> given. The one after that is with all parts given, corresponding to an existence test. The existence tests could probably be converted to <code>HASH JOIN</code> lookups to good advantage. Aggregation and arithmetic are absent. We should probably add a query like TPC-H Q1 that does nothing but these two. Considering the overall profile, <code>GROUP BY</code> seems to be around 3%. We should probably put in a query that makes a very large number of groups and could make use of streaming aggregation, i.e., take advantage of a situation where aggregation input comes already grouped by the grouping columns.</p> <p>A BI use case should offer no problem with including arithmetic, but there are not that many numbers in the BSBM set. Some code sections in the queries with conditional execution and costly tests inside <code>ANDs</code> and <code>ORs</code> would be good. TPC-H has such in Q21 and Q19. An <code>OR</code> with existences where there would be gain from good guesses of a subquery's selectivity would be appropriate. Also, there should be conditional expressions somewhere with a lot of data, like the <code>CASE-WHEN</code> in TPC-H Q12.</p> <p>We can make BSBM-BI more interesting by putting in the above. Also we will have to see where we can profit from <code>HASH JOIN</code>, both small and large. There should be such places in the workload already so this is a matter of just playing a bit more.</p> <p>This post amounts to a cheat sheet for the BSBM-BI runs a bit farther down the road. By then we should be operational with the column store and Virtuoso 7 Cluster, though, so not everything is yet on the table.</p> <h3> <i>Benchmarks, Redux</i> Series</h3> <ul> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1658" id="link-id0x1fd1d4e0">Benchmarks, Redux (part 1): On RDF Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1660" id="link-id0x1d5b07d8">Benchmarks, Redux (part 2): A Benchmarking Story</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1663" id="link-id0x1dfe6c48">Benchmarks, Redux (part 3): Virtuoso 7 vs 6 on BSBM Load and Explore</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1665" id="link-id0x197fce30">Benchmarks, Redux (part 4): Benchmark Tuning Questionnaire</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1667" id="link-id0x1fbf4210">Benchmarks, Redux (part 5): BSBM and I/O; HDDs and SSDs </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1669" id="link-id0x1beeb1e0">Benchmarks, Redux (part 6): BSBM and I/O, continued</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1d7e1818">Benchmarks, Redux (part 7): What Does BSBM Explore Measure?</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1673" id="link-id0x1dfc1730">Benchmarks, Redux (part 8): BSBM Explore and Update </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1675" id="link-id0x1ea819a8">Benchmarks, Redux (part 9): BSBM With Cluster</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1677" id="link-id0x1ec73da0">Benchmarks, Redux (part 10): LOD2 and the Benchmark Process</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1678" id="link-id0x1fbdce90">Benchmarks, Redux (part 11): The Substance of Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x19928618">Benchmarks, Redux (part 12): Our Own BSBM Results Report</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1f3d8710">Benchmarks, Redux (part 13): BSBM-BI Modifications </a> </li> <li> Benchmarks, Redux (part 14): BSBM-BI Mix <i>(this post)</i> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1e627400">Benchmarks, Redux (part 15): BSBM Test Driver Enhancements </a> </li> </ul>
Orri Erling
oerling@openlinksw.com
2011-03-22T17:04:20.000001-04:00
Benchmarks, Redux (part 14): BSBM BI Mix
http://www.openlinksw.com/blog/vdb/blog/?id=1687
2011-03-22T22:31:32Z
<p>In this post, we look at how we run the <a class="auto-href" href="http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/spec/index.html" id="link-id0x236dcda8">BSBM</a>-BI mix. We consider the 100 Mt and 1000 Mt scales with <a class="auto-href" href="http://virtuoso.openlinksw.com" id="link-id0x284893c0">Virtuoso</a> 7 using the same hardware and software as in the previous posts. The changes to workload and metric are given in the previous post.</p> <p>Our intent here is to look at whether the metric works, and to see what results will look like in general. We are as much testing the benchmark as we are testing the system-under-test (SUT). The results shown here will likely not be comparable with future ones because we will most likely change the composition of the workload since it seems a bit out of balance. Anyway, for the sake of disclosure, we attach the query templates. The test driver we used will be made available soon, so the interested may still try a comparison with their systems. If you practice with this workload for the coming races, the effort will surely not be wasted.</p> <p>Once we have come up with a rules document, we will redo all that we have published so far by-the-book, and have it audited as part of the <a class="auto-href" href="http://lod2.eu/" id="link-id0x23724860">LOD2</a> service we plan for this (see previous posts in this series). This will introduce comparability; but before we get that far with the BI workload, the workload needs to evolve a bit.</p> <p>Below we show samples of test driver output; the whole output is <a href="http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/BenchmarksReduxSupportingFiles/br.tar.gz" id="link-id0x1b703ad8">downloadable</a>.</p> <p>100 Mt Single User</p> <blockquote> <code><pre> bsbm/testdriver -runs 1 -w 0 -idir /bs/1 -drill \ -ucf bsbm/usecases/businessIntelligence/<a class="auto-href" href="http://dbpedia.org/resource/SPARQL" id="link-id0x2385eb48">sparql</a>.txt \ -dg <a class="auto-href" href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x22e2f508">http</a>://bsbm.org http://localhost:8604/sparql </pre> </code> </blockquote> <blockquote> <code><pre> 0: 43348.14ms, total: 43440ms Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 43.3481s / 43.3481s Elapsed runtime: 43.348 seconds QMpH: 83.049 query mixes per hour CQET: 43.348 seconds average runtime of query mix CQET (geom.): 43.348 seconds geometric mean runtime of query mix AQET (geom.): 0.492 seconds geometric mean runtime of query Throughput: 1494.874 BSBM-BI throughput: qph*scale BI Power: 7309.820 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>100 Mt 8 User </p> <blockquote> <code><pre> Thread 6: query mix 3: 195793.09ms, total: 196086.18ms Thread 8: query mix 0: 197843.84ms, total: 198010.50ms Thread 7: query mix 4: 201806.28ms, total: 201996.26ms Thread 2: query mix 5: 221983.93ms, total: 222105.96ms Thread 4: query mix 7: 225127.55ms, total: 225317.49ms Thread 3: query mix 6: 225860.49ms, total: 226050.17ms Thread 5: query mix 2: 230884.93ms, total: 231067.61ms Thread 1: query mix 1: 237836.61ms, total: 237959.11ms Benchmark run completed in 237.985427s Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 195.7931s / 237.8366s Total runtime (sum): 1737.137 seconds Elapsed runtime: 1737.137 seconds QMpH: 121.016 query mixes per hour CQET: 217.142 seconds average runtime of query mix CQET (geom.): 216.603 seconds geometric mean runtime of query mix AQET (geom.): 2.156 seconds geometric mean runtime of query Throughput: 2178.285 BSBM-BI throughput: qph*scale BI Power: 1669.745 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>1000 Mt Single User</p> <blockquote> <code><pre> 0: 608707.03ms, total: 608768ms Scale factor: 2848260 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 608.7070s / 608.7070s Elapsed runtime: 608.707 seconds QMpH: 5.914 query mixes per hour CQET: 608.707 seconds average runtime of query mix CQET (geom.): 608.707 seconds geometric mean runtime of query mix AQET (geom.): 5.167 seconds geometric mean runtime of query Throughput: 1064.552 BSBM-BI throughput: qph*scale BI Power: 6967.325 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>1000 Mt 8 User </p> <blockquote> <code><pre> bsbm/testdriver -runs 8 -mt 8 -w 0 -idir /bs/10 -drill \ -ucf bsbm/usecases/businessIntelligence/sparql.txt \ -dg http://bsbm.org http://localhost:8604/sparql </pre> </code> </blockquote> <blockquote> <code><pre> Thread 3: query mix 4: 2211275.25ms, total: 2211371.60ms Thread 4: query mix 0: 2212316.87ms, total: 2212417.99ms Thread 8: query mix 3: 2275942.63ms, total: 2276058.03ms Thread 5: query mix 5: 2441378.35ms, total: 2441448.66ms Thread 6: query mix 7: 2804001.05ms, total: 2804098.81ms Thread 2: query mix 2: 2808374.66ms, total: 2808473.71ms Thread 1: query mix 6: 2839407.12ms, total: 2839510.63ms Thread 7: query mix 1: 2889199.23ms, total: 2889263.17ms Benchmark run completed in 2889.302566s Scale factor: 2848260 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 2211.2753s / 2889.1992s Total runtime (sum): 20481.895 seconds Elapsed runtime: 20481.895 seconds QMpH: 9.968 query mixes per hour CQET: 2560.237 seconds average runtime of query mix CQET (geom.): 2544.284 seconds geometric mean runtime of query mix AQET (geom.): 13.556 seconds geometric mean runtime of query Throughput: 1794.205 BSBM-BI throughput: qph*scale BI Power: 2655.678 BSBM-BI Power: qph*scale (geom) Metrics for Query: 1 Count: 8 times executed in whole run Time share 2.120884% of total execution time AQET: 54.299656 seconds (arithmetic mean) AQET(geom.): 34.607302 seconds (geometric mean) QPS: 0.13 Queries per second minQET/maxQET: 11.71547600s / 148.65379700s Metrics for Query: 2 Count: 8 times executed in whole run Time share 0.207382% of total execution time AQET: 5.309462 seconds (arithmetic mean) AQET(geom.): 2.737696 seconds (geometric mean) QPS: 1.34 Queries per second minQET/maxQET: 0.78729800s / 25.80948200s Metrics for Query: 3 Count: 8 times executed in whole run Time share 17.650472% of total execution time AQET: 451.893890 seconds (arithmetic mean) AQET(geom.): 410.481088 seconds (geometric mean) QPS: 0.02 Queries per second minQET/maxQET: 171.07262500s / 721.72939200s Metrics for Query: 5 Count: 32 times executed in whole run Time share 6.196565% of total execution time AQET: 39.661685 seconds (arithmetic mean) AQET(geom.): 6.849882 seconds (geometric mean) QPS: 0.18 Queries per second minQET/maxQET: 0.15696500s / 189.00906200s Metrics for Query: 6 Count: 8 times executed in whole run Time share 0.119916% of total execution time AQET: 3.070136 seconds (arithmetic mean) AQET(geom.): 2.056059 seconds (geometric mean) QPS: 2.31 Queries per second minQET/maxQET: 0.41524400s / 7.55655300s Metrics for Query: 7 Count: 40 times executed in whole run Time share 1.577963% of total execution time AQET: 8.079921 seconds (arithmetic mean) AQET(geom.): 1.342079 seconds (geometric mean) QPS: 0.88 Queries per second minQET/maxQET: 0.02205800s / 40.27761500s Metrics for Query: 8 Count: 40 times executed in whole run Time share 72.126818% of total execution time AQET: 369.323481 seconds (arithmetic mean) AQET(geom.): 114.431863 seconds (geometric mean) QPS: 0.02 Queries per second minQET/maxQET: 5.94377300s / 1824.57867400s </pre> </code> </blockquote> <p>The <a class="auto-href" href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x2809d998">CPU</a> for the multiuser runs stays above 1500% for the whole run. The CPU for the single user 100 Mt run is 630%; for the 1000 Mt run, this is 574%. This can be improved since the queries usually have a lot of <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x22cf75b8">data</a> to work on. But final <a class="auto-href" href="http://dbpedia.org/resource/Program_optimization" id="link-id0x238b94c8">optimization</a> is not our goal yet; we are just surveying the race track. The difference between a warm single user run and a cold single user run is about 15% with data on SSD; with data on disk, this would be more. The numbers shown are with warm <a class="auto-href" href="http://dbpedia.org/resource/Cache" id="link-id0x23ad8c08">cache</a>. The single-user and multi-user Throughput difference, 1064 single-user vs. 1794 multi-user, is about what one would expect from the CPU utilization.</p> <p>With these numbers, the CPU does not appear badly memory-bound, else the increase would be less; also core multi-threading seems to bring some benefit. If the single-user run was at 800%, the Throughput would be 1488. The speed in excess of this may be attributed to core multi-threading, although we must remember that not every query mix is exactly the same length, so the figure is not exact. Core multi-threading does not seem to hurt, at the very least. Comparison of the same numbers with the column store will be interesting since it misses the cache a lot less and accordingly has better SMP scaling. The <a class="auto-href" href="http://dbpedia.org/resource/Intel_Corporation" id="link-id0x23568308">Intel</a> Nehalem memory subsystem is really pretty good.</p> <p> </p> <p>For reference, we show a run with Virtuoso 6 at 100Mt. </p> <blockquote> <code><pre> 0: 424754.40ms, total: 424829ms Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Seed: 808080 Number of query mix runs (without warmups): 1 times min/max Querymix runtime: 424.7544s / 424.7544s Elapsed runtime: 424.754 seconds QMpH: 8.475 query mixes per hour CQET: 424.754 seconds average runtime of query mix CQET (geom.): 424.754 seconds geometric mean runtime of query mix AQET (geom.): 1.097 seconds geometric mean runtime of query Throughput: 152.559 BSBM-BI throughput: qph*scale BI Power: 3281.150 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>and 8 user </p> <blockquote> <code><pre> Thread 5: query mix 3: 616997.86ms, total: 617042.83ms Thread 7: query mix 4: 625522.18ms, total: 625559.09ms Thread 3: query mix 7: 626247.62ms, total: 626304.96ms Thread 1: query mix 0: 629675.17ms, total: 629724.98ms Thread 4: query mix 6: 667633.36ms, total: 667670.07ms Thread 8: query mix 2: 674206.07ms, total: 674256.72ms Thread 6: query mix 5: 695020.21ms, total: 695052.29ms Thread 2: query mix 1: 701824.67ms, total: 701864.91ms Benchmark run completed in 701.909341s Scale factor: 284826 Explore Endpoints: 1 Update Endpoints: 1 Drilldown: on Number of warmup runs: 0 Number of clients: 8 Seed: 808080 Number of query mix runs (without warmups): 8 times min/max Querymix runtime: 616.9979s / 701.8247s Total runtime (sum): 5237.127 seconds Elapsed runtime: 5237.127 seconds QMpH: 41.031 query mixes per hour CQET: 654.641 seconds average runtime of query mix CQET (geom.): 653.873 seconds geometric mean runtime of query mix AQET (geom.): 2.557 seconds geometric mean runtime of query Throughput: 738.557 BSBM-BI throughput: qph*scale BI Power: 1408.133 BSBM-BI Power: qph*scale (geom) </pre> </code> </blockquote> <p>Having the numbers, let us look at the metric and its scaling. We take the geometric mean of the single-user Power and the multiuser Throughput.</p> <blockquote> <code><pre> 100 Mt: sqrt ( 7771 * 2178 ); = 4114 1000 Mt: sqrt ( 6967 * 1794 ); = 3535 </pre> </code> </blockquote> <p>Scaling seems to work; the results are in the same general ballpark. The real times for the 1000 Mt run are a bit over 10x the times for the 100Mt run, as expected. The relative percentages of the queries are about the same on both scales, with the drill-down in Q8 alone being 77% and 72% respectively. The Q8 drill-down starts at the root of the product hierarchy. If we made this start one level from the top, its share would drop. This seems reasonable.</p> <p>Conversely, Q2 is out of place, with far too little share of the time. It takes a product as a starting point and shows a list of products with common features, sorted by descending count of common features. This would more appropriately be applied to a leaf product category instead, measuring how many of the products in the category have the top 20 features found in this category, to name an example.</p> <p>Also there should be more queries.</p> <p>At present it appears that BSBM-BI is definitely runnable, but a cursory look suffices to show that the workload needs more development and variety. We remember that I dreamt up the business questions last fall without much analysis, and that these questions were subsequently translated to SPARQL by FU Berlin. So, on one hand, BSBM-BI is of crucial importance because it is the first attempt at doing a benchmark with long running queries in SPARQL. On the other hand, BSBM-BI is not very good as a benchmark; <a class="auto-href" href="http://www.tpc.org/" id="link-id0x23872a10">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x28487d98">H</a> is a lot better. This stands to reason, as TPC-H has had years and years of development and participation by many people.</p> <p>Benchmark queries are trick questions: For example, TPC-H Q18 cannot be done without changing an <code>IN</code> into a <code>JOIN</code> with the <code>IN</code> subquery in the outer loop and doing streaming aggregation. Q13 cannot be done without a well-optimized <code><a class="auto-href" href="http://dbpedia.org/resource/Hash_join" id="link-id0x24974830">HASH JOIN</a></code> which besides must be partitioned at the larger scales.</p> <p>Having such trick questions in an important benchmark eventually results in everybody doing the optimizations that the benchmark clearly calls for. Making benchmarks thus entails a responsibility ultimately to the end user, because an irrelevant benchmark might in the worst case send developers chasing things that are beside the point.</p> <p>In the following, we will look at what BSBM-BI requires from the database and how these requirements can be further developed and extended.</p> <p>BSBM-BI does not have any clear trick questions, at least not premeditatedly. BSBM-BI just requires a cost model that can guess the fanout of a <code>JOIN</code> and the cardinality of a <code>GROUP BY</code>; it is enough to distinguish smaller from greater; the guess does not otherwise have to be very good. Further, the queries are written in the benchmark text so that joining from left to right would work, so not even a cost-based optimizer is strictly needed. I did however have to add some cardinality statistics to get reasonable <code>JOIN</code> order since we always reorder the query regardless of the source formulation.</p> <p>BSBM-BI does have variable selectivity from the drill-downs; thus these may call for different <code>JOIN</code> orders for different parameter values. I have not looked into whether this really makes a difference, though.</p> <p>There are places in BSBM-BI where using a <code>HASH JOIN</code> makes sense. We do not use <code>HASH JOINs</code> with <a class="auto-href" href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x23cbf908">RDF</a> because there is an index for everything and making a <code>HASH JOIN</code> in the wrong place can have a large up-front cost, so one is more robust against cost model errors if one does not do <code>HASH JOINs</code>. This said, a <code>HASH JOIN</code> in the right place is a lot better than an index lookup. With TPC-H Q13, our best <code>HASH JOIN</code> is over 2x better than the best <code>INDEX</code>-based <code>JOIN</code>, both being well tuned. For questions like "count the hairballs made in <a class="auto-href" href="http://dbpedia.org/resource/Germany" id="link-id0x249d3e28">Germany</a> reviewed by Japanese Hello Kitty fans," where two ends of a <code>JOIN</code> path are fairly selective doing the other as a <code>HASH JOIN</code> is good. This can, if the <code>JOIN</code> is always cardinality-reducing, even be merged inside an <code>INDEX</code> lookup. We have such capabilities since we have been for a while gearing up for the relational races, but are not using any of these with BSBM-BI, although they would be useful.</p> <p>Let us see the profile for a single user 100 Mt run.</p> <p>The database activity summary is --</p> <p> <code>select db_activity (0, 'http');</code> </p> <p> <code> 161.3M rnd 210.2M seq 0 same seg 104.5M same pg 45.08M same par 0 disk 0 spec disk 0B / 0 messages 2.393K fork</code> </p> <p>See the post "<a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1b1f3068">What Does BSBM Explore Measure</a>" for an explanation of the numbers. We see that there is more sequential access than random and the random has fair locality with over half on the same page as the previous and a lot of the rest falling under the same parent. Funnily enough, the explore mix has more locality. Running with a longer vector size would probably increase performance by getting better locality. There is an optimization that adjusts vector size on the fly if locality is not sufficient but this is not being used here. So we manually set vector size to 100000 instead of the default 10000. We get --</p> <p> <code> 172.4M rnd 220.8M seq 0 same seg 149.6M same pg 10.99M same par 21 disk 861 spec disk 0B / 0 messages 754 fork</code> </p> <p>The throughput goes from 1494 to 1779. We see more hits on the same page, as expected. We do not make this setting a default since it raises the cost for small queries; therefore the vector size must be self-adjusting -- besides, expecting a DBA to tune this is not reasonable. We will just have to correctly tune the self-adjust logic, and we have again clear gains.</p> <p>Let us now go back to the first run with vector size 10000.</p> <p>The top of the CPU <code>oprofile</code> is as follows:</p> <blockquote> <code><pre> 722309 15.4507 cmpf_iri64n_iri64n 434791 9.3005 cmpf_iri64n_iri64n_anyn_iri64n 294712 6.3041 itc_next_set 273488 5.8501 itc_vec_split_search 203970 4.3631 itc_dive_transit 199687 4.2714 itc_page_rcf_search 181614 3.8848 dc_itc_append_any 173043 3.7015 itc_bm_vec_row_check 146727 3.1386 cmpf_int64n 128224 2.7428 itc_vec_row_check 113515 2.4282 dk_alloc 97296 2.0812 page_wait_access 62523 1.3374 qst_vec_get_int64 59014 1.2623 itc_next_set_parent 53589 1.1463 sslr_qst_get 48003 1.0268 ds_add 46641 0.9977 dk_free_tree 44551 0.9530 kc_var_col 43650 0.9337 page_col_cmp_1 35297 0.7550 cmpf_iri64n_iri64n_anyn_gt_lt 34589 0.7399 dv_compare 25864 0.5532 cmpf_iri64n_anyn_iri64n_iri64n_lte 23088 0.4939 dk_free </pre> </code> </blockquote> <p>The top 10 are all index traversal, with the key compare for two leading IRI keys in the lead, corresponding to a lookup with <code>P</code> and <code>S</code> given. The one after that is with all parts given, corresponding to an existence test. The existence tests could probably be converted to <code>HASH JOIN</code> lookups to good advantage. Aggregation and arithmetic are absent. We should probably add a query like TPC-H Q1 that does nothing but these two. Considering the overall profile, <code>GROUP BY</code> seems to be around 3%. We should probably put in a query that makes a very large number of groups and could make use of streaming aggregation, i.e., take advantage of a situation where aggregation input comes already grouped by the grouping columns.</p> <p>A BI use case should offer no problem with including arithmetic, but there are not that many numbers in the BSBM set. Some code sections in the queries with conditional execution and costly tests inside <code>ANDs</code> and <code>ORs</code> would be good. TPC-H has such in Q21 and Q19. An <code>OR</code> with existences where there would be gain from good guesses of a subquery's selectivity would be appropriate. Also, there should be conditional expressions somewhere with a lot of data, like the <code>CASE-WHEN</code> in TPC-H Q12.</p> <p>We can make BSBM-BI more interesting by putting in the above. Also we will have to see where we can profit from <code>HASH JOIN</code>, both small and large. There should be such places in the workload already so this is a matter of just playing a bit more.</p> <p>This post amounts to a cheat sheet for the BSBM-BI runs a bit farther down the road. By then we should be operational with the column store and Virtuoso 7 Cluster, though, so not everything is yet on the table.</p> <h3> <i>Benchmarks, Redux</i> Series</h3> <ul> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1658" id="link-id0x1fd1d4e0">Benchmarks, Redux (part 1): On RDF Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1660" id="link-id0x1d5b07d8">Benchmarks, Redux (part 2): A Benchmarking Story</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1663" id="link-id0x1dfe6c48">Benchmarks, Redux (part 3): Virtuoso 7 vs 6 on BSBM Load and Explore</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1665" id="link-id0x197fce30">Benchmarks, Redux (part 4): Benchmark Tuning Questionnaire</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1667" id="link-id0x1fbf4210">Benchmarks, Redux (part 5): BSBM and I/O; HDDs and SSDs </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1669" id="link-id0x1beeb1e0">Benchmarks, Redux (part 6): BSBM and I/O, continued</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1d7e1818">Benchmarks, Redux (part 7): What Does BSBM Explore Measure?</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1673" id="link-id0x1dfc1730">Benchmarks, Redux (part 8): BSBM Explore and Update </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1675" id="link-id0x1ea819a8">Benchmarks, Redux (part 9): BSBM With Cluster</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1677" id="link-id0x1ec73da0">Benchmarks, Redux (part 10): LOD2 and the Benchmark Process</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1678" id="link-id0x1fbdce90">Benchmarks, Redux (part 11): The Substance of Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x19928618">Benchmarks, Redux (part 12): Our Own BSBM Results Report</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1f3d8710">Benchmarks, Redux (part 13): BSBM-BI Modifications </a> </li> <li> Benchmarks, Redux (part 14): BSBM-BI Mix <i>(this post)</i> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1e627400">Benchmarks, Redux (part 15): BSBM Test Driver Enhancements </a> </li> </ul>
Virtuso Data Space Bot
kidehen@openlinksw.com
2011-03-22T17:04:38-04:00
Benchmarks, Redux (part 13): BSBM BI Modifications
http://www.openlinksw.com/weblog/oerling/?id=1682
2011-03-22T22:30:44Z
<p>In this post we introduce changes to the <a class="auto-href" href="http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/spec/index.html" id="link-id0x23cb6710">BSBM</a> BI queries and metric. These changes are motivated by prevailing benchmark practice and by our experiences in optimizing for the BSBM BI workload.</p> <p>We will publish results according to the definitions given here and recommend that any interested parties do likewise. The rationales are given in the text.</p> <h3>Query Mix</h3> <p>We have removed Q4 from the mix because it is quadratic to the scale factor. The other queries are roughly <code>n * log (n)</code>. </p> <h3>Parameter Substitution </h3> <p>All queries that take a product type as parameter are run in flights of several query invocations where the product type goes from broader to more specific. The initial product type specifies either the root product type or an immediate subtype of this, and the last in the drill-down is a leaf type.</p> <p>The rationale for this is that the choice of product type may make several orders of magnitude difference in the run time of a query. In order to make consecutive query mixes roughly comparable in execution time, all mixes should have a predictable number of query invocations with product types of each level.</p> <h3>Query Order </h3> <p>In the BI mix, when running multiple concurrent clients, each query mix is submitted in a random order. Queries which do drill-downs always have the steps of the drill-down as consecutive in the session, but the query templates are permuted. This is done so as to make less likely that there were two concurrent queries accessing exactly the same <a class="auto-href" href="http://dbpedia.org/resource/Data" id="link-id0x244a3d88">data</a>. In this way, scans cannot be trivially shared between queries -- but there are still opportunities for reuse of results and adapting execution to working set, e.g., starting with what is in memory.</p> <h3>Metrics </h3> <p>We use a <a class="auto-href" href="http://www.tpc.org/" id="link-id0x23880db8">TPC</a>-<a class="auto-href" href="http://dbpedia.org/resource/TPC-H" id="link-id0x29201c58">H</a>-like metric. This metric consists of a single-user part and a multi-user part, called respectively <i>Power</i> and <i>Throughput.</i> The <i>Power</i> metric is a geometric mean of query run-time. The <i>Throughput</i> is the total run-time divided by the number of queries completed. After taking the mean, the time is converted into queries-per-hour. This time is then multiplied by the scale factor divided by the scale factor for 100 Mt. In other words, we consider the 100 Mt data set as the unit scale.</p> <p>The <i>Power</i> is defined as</p> <blockquote>( scale_factor / 284826 ) * 3600 / ( ( t1 * t1 * ... * tn ) ^ ( 1 / n ) ) </blockquote> <p>The <i>Throughput</i> is defined as</p> <blockquote>( scale_factor / 284826 ) * 3600 / ( ( t1 + t2 + ... + tn ) / n ) </blockquote> <p>The magic number <b><code>284826</code></b> is the scale that generates approximately 100 million triples (100 Mt). We consider this scale "one". The reason for the multiplication is that scores at different scales should get similar numbers; otherwise 10x larger scale would result roughly in 10x lower throughput with the BI queries.</p> <p>The <i>Composite</i> metric is the geometric mean of the <i>Power</i> and <i>Throughput</i> metrics. A complete report shows both <i>Power</i> and <i>Throughput</i> metrics, as well as individual query times for all queries. The rationale for using a geometric mean is to give an equal importance to long and short queries. Halving the execution time of either a long query or a short query will have the same effect on the metric. This is good for encouraging research into all aspects of query processing. On the other hand, real-life users are more interested in halving the time of queries that take one hour than of queries that take one second; therefore, the throughput metric considers run times.</p> <p>Taking the geometric mean of the two metrics gives more weight to the lower of the two than an arithmetic mean, hence we pay more attention to the worse of the two.</p> <p>Single-user and multi-user metrics are separate because of the relative importance of intra-query parallelization in BI workloads: There may not be large numbers of concurrent users, yet queries are still complex, and it is important to have maximum parallelization. Therefore the metric rewards single-user performance.</p> <p>In the next post we will look at the use of this metric and the actual content of BSBM BI.</p> <h3> <i>Benchmarks, Redux</i> Series</h3> <ul> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1658" id="link-id0x1b02d528">Benchmarks, Redux (part 1): On RDF Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1660" id="link-id0x1d65f740">Benchmarks, Redux (part 2): A Benchmarking Story</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1663" id="link-id0x1a797860">Benchmarks, Redux (part 3): Virtuoso 7 vs 6 on BSBM Load and Explore</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1665" id="link-id0x1d3538e0">Benchmarks, Redux (part 4): Benchmark Tuning Questionnaire</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1667" id="link-id0x1e566f60">Benchmarks, Redux (part 5): BSBM and I/O; HDDs and SSDs </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1669" id="link-id0x1dedffd8">Benchmarks, Redux (part 6): BSBM and I/O, continued</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1671" id="link-id0x1eb11528">Benchmarks, Redux (part 7): What Does BSBM Explore Measure?</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1673" id="link-id0x1db46c38">Benchmarks, Redux (part 8): BSBM Explore and Update </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1675" id="link-id0x1c8174e8">Benchmarks, Redux (part 9): BSBM With Cluster</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1677" id="link-id0x1dfa9338">Benchmarks, Redux (part 10): LOD2 and the Benchmark Process</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=1678" id="link-id0x1e6dd7b0">Benchmarks, Redux (part 11): The Substance of Benchmarks</a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1d154bb0">Benchmarks, Redux (part 12): Our Own BSBM Results Report</a> </li> <li> Benchmarks, Redux (part 13): BSBM BI Modifications <i>(this post)</i> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1f242ae0">Benchmarks, Redux (part 14): BSBM BI Mix </a> </li> <li> <a href="http://www.openlinksw.com/weblog/oerling/?id=" id="link-id0x1ebf2f98">Benchmarks, Redux (part 15): BSBM Test Driver Enhancements </a> </li> </ul>
Orri Erling
oerling@openlinksw.com
2011-03-22T17:04:14-04:00