http://www.openlinksw.com/weblog/oerling/
Orri Erling's Weblog
Orri Erling
oerling@openlinksw.com
2009-11-07T21:46:51Z
Virtuoso Universal Server 05.12.3041
http://www.openlinksw.com/weblog/public/images/vbloglogo.gif
European Commission and the Data Overflow
http://www.openlinksw.com/weblog/oerling/?id=1585
2009-10-27T18:29:51Z
<p>The European Commission recently circulated a questionnaire to selected experts on what could be done for the future of big <a href="http://dbpedia.org/resource/Data" id="link-id0x79cfe58">data</a>.</p> <p>Since the <a href="http://cordis.europa.eu/fp7/ict/content-knowledge/consultation_en.html" id="link-id1191c0f8">questionnaire is public</a>, I am publishing my answers below.</p> <ol type="1" start="1"> <li> <p> <b>Data and data types</b> </p> <ol type="a" start="1"> <li> <p> <b>What volumes of data are we dealing with today? What is the growth rate? Where can we expect to be in 2015? </b> </p> <p>Private data warehouses of corporations have more than doubled yearly for the past years; hundreds of TB is not exceptional. This will continue. The real shift is in structured data being published in increasing quantities with a minimum level of integrate-ability through use of <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x7d7e7a0">RDF</a> and <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x7f2a788">linked data</a> principles. There are rewards for use of standard vocabularies and identifiers through search engines recognizing such data. There is convergence around <a href="http://dbpedia.org/resource/DBpedia" id="link-id0x7dfbca8">DBpedia</a> identifiers for real-world entities, e.g., most things that would be in the news.</p> <p>This also means that internal data processes and silos may be enriched with this content. There is consequent pressure for accommodating more diversity of data, with more flexible <a href="http://dbpedia.org/resource/Database_schema" id="link-id0x7babaf8">schema</a>.</p> <p>Ultimately, all content presently stored in RDBs and presented in public accessible dynamic web pages will end up on the web of linked data. Examples are product catalogs, price lists, event schedules and the like.</p> <p>The volume of the well known linked data sets is around 10 billion statements. With the above mentioned trends, growth by two or three orders of magnitude by 2015 seems reasonable, This is so especially if explicit semantics are extracted from the document web and if there is some further progress in the precision/recall of such extraction.</p> <p>Relevant sections of this mass of data are a potential addition to any present or future analytics application.</p> <p>Since arbitrary analytics over the database which is the web cannot be economically provided by a centralized search engine, a cloud model may be used for on-demand selection of relevant data and mixing it with private data. This will drive database innovation for the next years even more than the continued classical warehouse growth.</p> <p>Science data is another driver of the data overflow. For example, faster gene sequencing, more accurate measurements in high energy physics, better imaging, and remote sensing will produce large volumes of data. This data has highly regular structure but labeling this data with source and lineage calls for a flexible, schema-last, self-describing model, such as RDF and linked data. Data and <a href="http://dbpedia.org/resource/Metadata" id="link-id0x96ce60">metadata</a> should travel together but may have different data models.</p> <p>By and large, the metadata of science data will be another stream to the web of linked data, at least to the degree it is publicly accessible. Restricted circles can and likely will implement similar ideas.</p> </li> <li> <p> <b>What types of data can we deal with intelligently due to their inherent structure (geospatial, temporal, social or <a href="http://dbpedia.org/resource/Knowledge" id="link-id0x7e8e248">knowledge</a> graphs, 3D, sensor streams...)?</b> </p> <p>All the above types should be supported inside one DBMS so as to allow efficient querying combining conditions on all these types of data, e.g., <i>photos of sunsets taken last summer in Ibiza, with over 20 megapixels, by people I know.</i> </p> <p>Note that the test for being a sunset is an operation on the image blob that should be taken to the data; the images cannot be economically transferred.</p> <p>Interleaving of all database functions and types becomes increasingly important.</p> </li> </ol> </li> <li> <p> <b>Industries, communities</b> </p> <ol type="a" start="1"> <li> <p> <b>Who is producing these data and why? Could they do it better? How?</b> </p> <p>Right now, projects such as <a href="http://www.bio2rdf.org/" id="link-id0x43bd098">Bio2RDF</a>, <a href="http://neurocommons.org/page/Main_Page" id="link-id0x5c074b0">Neurocommons</a>, and DBPedia produce this data. The processes are in place and are reasonable. Incremental improvement is to be expected. These processes, along with the <a href="http://www.w3.org/DesignIssues/LinkedData.html" id="link-id0x72131d0">linked data meme</a> generally taking off, drive demand for better <a href="http://dbpedia.org/resource/Natural_language_processing" id="link-id0x71e7798">NLP</a> (<a href="http://dbpedia.org/resource/Natural_language_processing" id="link-id0x7e0e2f0">Natural Language Processing</a>), e.g., <a href="http://dbpedia.org/resource/Entity" id="link-id0x71ab500">entity</a> and relationship extraction, especially extraction that can produce instance data in given ontologies (e.g., events) using common identifiers (e.g., DBPedia URIs).</p> <p>Mapping of RDBs to RDF is possible, and a W3C working group is developing standards for this. The required baseline level has been reached; the rest is a matter of automating deployment. Within the enterprise, there are advantages to be gained for <a href="http://dbpedia.org/resource/Information" id="link-id0x7a8e9a8">information</a> integration; e.g., all entities in the CRM space can be integrated with all email and support tickets through giving everything a <a href="http://dbpedia.org/resource/Uniform_Resource_Identifier" id="link-id0x599f630">URI</a>. Some of this information may even be published on an <a href="http://dbpedia.org/resource/Extranet" id="link-id0x2a28f98">extranet</a> for self-service and web-service interfaces. This has been done at small scales and the rest is a matter of spreading adoption and lowering the entry barrier. Incremental progress will take place, eventually resulting in qualitatively better integration along the value chain when adoption is sufficiently widespread.</p> </li> <li> <p> <b>Who is consuming these data and why? Could they do it better? How?</b> </p> <p>Consumers are various. The greatest need is for tools that summarize complex data and allow getting a bird's eye view of what data is in the first instance available. Consuming the data is hindered by the user not even necessarily knowing what data there is. This is somewhat new, as traditionally the business analyst did know the schema of the warehouse and was proficient with <a href="http://dbpedia.org/resource/SQL" id="link-id0x5999558">SQL</a> report generators and statistics packages.</p> <p>Where Web 2.0 made the <i>citizen journalist</i>, the web of linked data will make the <i>citizen analyst</i>. For this to happen, with benefits for individuals, enterprises, and governments alike, more work in user interfaces, knowledge discovery, and query composition will be useful. We may envision a "meshup economy" where data is plentiful, but the unit of value and exchange is the smart report that crystallizes actionable value from this ocean.</p> </li> <li> <p> <b>What industrial sectors in Europe could become more competitive if they became much better at managing data?</b> </p> <p>Any sector could benefit. Early adopters are seen in the biomedical field and to an extent in media. </p> </li> <li> <p> <b>Is the regulation landscape imposing constraints (privacy, compliance ...) that don't have today good tool support?</b> </p> <p>The regulation landscape drives database demand through data retention requirements and the like.</p> <p>With data integration, especially with privacy-sensitive data (as in medicine), there are issues of whether one dares put otherwise-shareable information online. Regulation is needed to protect individuals, but integration should still be possible for science.</p> <p>For this, we see a need for progress in applying policy-based approaches (e.g., row level security) to relatively schema-last data such as RDF. This is possible but needs some more work. Also, creating on-the-fly-anonymizing views on data might help.</p> <p>More research is needed for reconciling the need for security with the advantages of broad-based <i>ad hoc</i> integration. Ideally, data should be intelligent, aware of its origins and classification and cautious of whom it interacts with, all of this supported under the covers so that the user could ask anything but the data might refuse to answer or might restrict answers according to the user's profile. This is a tall order and implementing something of the sort is an open question.</p> </li> <li> <p> <b>What are the main practical problem identified for individuals and organizations? Please give examples and tell us about the main obstacles and barriers.</b> </p> <p>We have come across the following:</p> <ul> <li>Knowing that the data exists in the first place.</li> <li>If the data is found, figuring out the provenance, units and precision of measurement, identifiers, and the like.</li> <li>Compatible subject matter but incompatible representation: For example, one has numbers on a map with different maps for different points in time; another has time series of instrument data with geo-location for the instrument. It is only to be expected that the time interval between measurements is not the same. So there is need for a lot of one-off programming to align data.</li> </ul> <p>Other problems have to do with sheer volume, i.e., transfer of data even in a local area network is too slow, let alone over a wide area network. Computation needs to go to the data, and databases need to support this.</p> </li> </ol> </li> <li> <p> <b>Services, software stacks, protocols, standards, benchmarks</b> </p> <ol type="a" start="1"> <li> <p> <b>What combinations of components are needed to deal with these problems?</b> </p> <p>Recent times have seen a proliferation of special purpose databases. Since the data needs of the future are about combining data with maximum agility and minimum performance hit, there is need to gather the currently-separate functionality into an integrated system with sufficient flexibility. We see some of this in integration of map-reduce and scale-out databases. The former antagonists have become partners. Vertica, <a href="http://dbpedia.org/resource/Greenplum" id="link-id0x45ecfa0">Greenplum</a>, and OpenLink <a href="http://virtuoso.openlinksw.com" id="link-id0x7f73fc8">Virtuoso</a> are example of DBMS featuring work in this direction.</p> <p>Interoperability and at least <i>de facto</i> standards in ways of doing this will emerge.</p> </li> <li> <p> <b>What data exchange and processing mechanisms will be needed to work across platforms and programming languages?</b> </p> <p> <a href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x776a1a0">HTTP</a>, <a href="http://dbpedia.org/resource/XML" id="link-id0x2a4e8d0">XML</a>, and RDF are in fact very verbose, yet these are the formats and models that have uptake. Thus, these will continue to be used even though one might think binary formats to be more efficient.</p> <p>There are of course science data set standards that are more compressed and these will continue, hopefully adding a practice of rich metadata in RDF.</p> <p>For internals of systems, MPI and TCP/IP with proprietary optimized wire formats will continue. Inter-system communication will likely continue to be HTTP, XML, and RDF as appropriate.</p> </li> <li> <p> <b>What data environments are today so wastefully messy that they would benefit from the development of standards?</b> </p> <p>RDF and <a href="http://dbpedia.org/resource/Web_Ontology_Language" id="link-id0x2a35960">OWL</a> are not messy but they could use some more performance; we are working on this. <a href="http://dbpedia.org/resource/SPARQL" id="link-id0x12362e8">SPARQL</a> is finally acquiring the capabilities of a serious query language, so things are slowly coming together.</p> <p>Community process for developing application domain specific vocabularies works quite well, even though one could argue it is <i>ad hoc</i> and not up to what a modeling purist might wish.</p> <p>Top-down imposition of standards has a mixed history, with long and expensive development and sometimes no or little uptake, consider some WS* standards for example.</p> </li> <li> <p> <b>What kind of performance is expected or required of these systems? Who will measure it reliably? How?</b> </p> <p>Relational databases have a history of substantial investment in <a href="http://dbpedia.org/resource/Program_optimization" id="link-id0x7b2d7c8">optimization</a> and some of them are very good for what they do, e.g., the newer generation of analytics databases.</p> <p>The very large schema-last, no-SQL, sometimes eventually consistent key-value stores have a somewhat shorter history but do fill a real need.</p> <p>These trends will merge: Extreme scale, schema-last, complex queries, even more complex inference, custom code for in-database machine learning and other bulk processing.</p> <p>We find RDF augmented with some binary types at this crossroads. This point of the design space will have to provide performance roughly on the level of today's best relational solution for workloads that fit the relational model. The added cost of schema-last and inference must come down. We are working on this. Research work such as carried out with <a href="http://dbpedia.org/resource/MonetDB" id="link-id0x794ee48">MonetDB</a> gives clues as to how these aims can be reached.</p> <p>The separation of query language and inference is artificial. After the concepts are mature, these functions will merge and execute close to the data; there are clear evolutionary pressures in this direction.</p> <p>Benchmarks are key. Some gain can be had even from repurposing standard relational benchmarks like <a href="http://www.tpc.org/" id="link-id0x7d45c58">TPC</a>-<a href="http://dbpedia.org/resource/TPC-H" id="link-id0x45b0198">H</a>. But the TPC-H rules do not allow official reporting of such.</p> <p>Development of benchmarks for RDF, complex queries, and inference is needed. A bold challenge to the community, it should be rooted in real-life integration needs and involve high heterogeneity. A key-value store benchmark might also be conceived. A transaction benchmark like TPC-<a href="http://dbpedia.org/resource/C%2B%2B" id="link-id0x7e32178">C</a> might be the basis, maybe augmented with massive user-generated content like reviews and blogs.</p> <p>If benchmarks exist and are not too easy nor inaccessibly difficult nor too expensive to run — think of the high end TPC-C results — then TPC-style rules and processes would be quite adequate. The threshold to publish should be lowered: Everybody runs the TPC workloads internally but few publish.</p> <p>Some EC initiative for benchmarking could make sense, similar to the TREC initiative of the US government. Industry should be consulted for the specific content; possibly the answers to the present questionnaire can provide an approximate direction.</p> <p>Benchmarks should be run by software vendors on their own systems, tuned by themselves. But there should be a process of disclosure and auditing; the TPC rules give an example. Compliance should not be too expensive or time consuming. Some community development for automating these things would be a worthwhile target for EC funding.</p> </li> </ol> </li> <li> <p> <b>Usability and training</b> </p> <ol type="a" start="1"> <li> <p> <b>How difficult will it be for a developer of average competence to deploy components whose core is based on rather deep computer science? Do we all need to understand Monads and Continuations? What can be done to make it ever easier?</b> </p> <p>In the database world, huge advances in technology have taken place behind a relatively simple and stable interface: SQL. For the linked data <a href="http://dbpedia.org/resource/Giant_Global_Graph" id="link-id0x7e01618">web</a>, the same will take place behind SPARQL.</p> <p>Beyond these, for example, programming with MPI with good utilization of a cluster platform for an arbitrary algorithm, is quite difficult. The casual amateur is hereby warned.</p> <p>There is no single solution. For automatic parallelization, since explicit, programmatic parallelization of things with MPI for example is very unscalable in terms of required skill, we should favor declarative and/or functional approaches.</p> <p>Developing a debugger and explanation engine for rule-based and description-logics-based inference would be an idea.</p> <p>For procedural workloads, things like Erlang may be good in cases and are not overly difficult in principle, especially if there are good debugging facilities.</p> <p>For shipping functions in a cluster or cloud, the <a href="http://www.eecs.berkeley.edu/Research/Projects/Data/105733.html" id="link-id0x43665a8">BOOM</a> (<a href="http://www.eecs.berkeley.edu/Research/Projects/Data/105733.html" id="link-id0x7718f00">Berkeley Orders Of Magnitude</a>) approach or logic programming with explicit specification of compute location seem promising, surely more flexible than map-reduce. The question is whether a <a href="http://dbpedia.org/resource/PHP" id="link-id0x7d64f68">PHP</a> developer can be made to do logic programming.</p> <p>This bridge will be crossed only with actual need and even then reluctantly. We may look at the Web 2.0 practice of sharding <a href="http://dbpedia.org/resource/MySQL" id="link-id0xbab1ae98">MySQL</a>, inconvenient as this may be, for an example. There is inertia and thus re-architecting is a constant process that is generally in reaction to facts, <i>post hoc</i>, often a point solution. One could argue that planning ahead would be smarter but by and large the world does not work so.</p> <p>One part of the answer is an infinitely-scalable SQL database that expands and shrinks in the clouds, with the usual semantics, maybe optional eventual consistency and built-in map reduce. If such a thing is inexpensive enough and syntax-level-compatible with present installed base, many developers do not have to learn very much more.</p> <p>This is maybe good for the bread-and-butter IT, but European competitiveness should not rest on this. Therefore we wish to go for bold new application types for which the client-server database application is not the model. Data-centric languages like BOOM, if they can be made very efficient and have good debugging support, are attractive there. These do require more intellectual investment but that is not a problem since the less-inquisitive part of the developer community is served by the first part of the answer.</p> </li> <li> <p> <b>How is a developer of average skills going to learn about these new advanced tools? How can we plan for excellent documentation and training, community mentoring, exchange of good practices, etc... across all EU countries?</b> </p> <p>For the most part, developers do not learn things for the sake of learning. When they have learned something and it is adequate, they stay with it for the most part and are even reluctant to engage in cross-camps interaction. The research world is often similarly insular. A new inflection in the application landscape is needed to drive learning. This inflection is provided by the <a href="https://wiki.mozilla.org/Labs/Ubiquity" id="link-id0x770df38">ubiquity</a> of mobile devices, sensor data, explicit semantics, NLP concept extraction, web of linked data, and such factors.</p> <p>RDFa is a good example of a new technique piggybacking on something everybody uses, namely HTML. These new things should, within possibility, be deployed in the usual technology stack, <a href="http://en.wikipedia.org/wiki/LAMP_%28software_bundle%29" id="link-id0x55596a8">LAMP</a> or Java. Of course these do not have to be LAMP or Java or HTML or HTTP themselves but they must manifest through these.</p> <p>A lot of the <a href="http://dbpedia.org/resource/Semantic_Web" id="link-id0x3d5378">semantic web</a> potential can be realized within the client-server database application model, thus no fundamental re-architecting, just some new data types and queries.</p> <p>For data- or processing-intensive tasks, an on-demand hookup to cloud-based servers with Erlang and/or BOOM for programming model would be easy enough to learn and utilize.</p> <p>The question is one of providing challenges. Addressing actual challenges with these techniques will lead to maturity, documentation, examples, and training. With virtual, Europe-wide distributed teams a reality in many places, Europe-wide dissemination is no longer insurmountable.</p> <p>As the data overflow proceeds, its victims will multiply and create demand for solutions. The EC could here encourage research project use cases gaining an extended life past the end of research projects, possibly being maintained and multiplied and spun off.</p> <p>If such things could be mutated into self-sustaining service businesses with pay-per-use revenue, say through a cloud SaaS business model, still primarily leveraging an open source technology stack, we could have self-propagating and self-supporting models for exploiting advanced IT. This would create interest, and interest would drive training and dissemination.</p> <p>The problem is creating the pull.</p> </li> </ol> </li> <li> <p> <b>Challenges</b> </p> <ol type="a" start="1"> <li> <p> <b>What should be, in this domain, the equivalent of the Netflix challenge, Ansari X Prize, <a href="http://dbpedia.org/resource/Google" id="link-id0x6a6c2b0">Google</a> Lunar X Prize, etc. ... ?</b> </p> <p>The EC itself no doubt suffers from data overflow in one function or another. Unless security/secrecy prohibits, simply publishing a large data set and a description of what operations should be done on it would be a start. The more real the data, the better — reality is consistently more complex and surprising than imagination. Since many interesting problems touch on fraud detection and law enforcement, there may be some security obstacles for using these application domains as subject matters of open challenges.</p> <p>Once there is a good benchmark, as discussed above, there can be some prize money allocated for the winners, specially if the race is tight.</p> <p>The Semantic Web Challenge and the Billion Triples Challenge exist and are useful as such, but do not seem to have any huge impact.</p> <p>The incentives should be sufficient and part of the expenses arising from running for such challenges could be funded. Otherwise investing in existing business development will be more interesting to industry. Some industry participation seems necessary; we would wish academia and industry to work closer. Also, having industry supply the baseline guarantees that academia actually does further the state of the art. This is not always certain.</p> <p>If challenges are based on actual problems, whether of the EC, its member governments, or private entities, and winning the challenge may lead to a contract for supplying an actual solution, these will naturally become more interesting for consortia involving integrators, specialist software vendors, and academia. Such a model would build actual capacity to deploy leading edge technologies in production, which is sorely needed.</p> </li> <li> <p> <b>What should one do to set up such a challenge, administer, and monitor it?</b> </p> <p>The EC should probably circulate a call for actual problem scenarios involving big data. If the matter of the overflow is as dire as represented, cases should be easy to find. A few should be selected and then anonymized if needed.</p> <p>The party with the use case would benefit by having hopefully the best work on it. The contestants would benefit from having real world needs guide R&D. The EC would not have to do very much, except possibly use some money for funding the best proposals. The winner would possibly get a large account and related sales and service income. The contestants would have to be teams possibly involving many organizations; for example, development and first-line services and support could come from different companies along a systems integrator model such as is widely used in the US.</p> <p>There may be a good benchmark at the time, possibly resulting from FP7 itself. In such a case, the EC could offer a prize for winners. Details would have to be worked out case by case. Such a challenge could be repeated a few times, as benchmark-driven progress in databases or TREC for example have taken some years to reach a point of slowdown in progress.</p> <p>Administrating such an activity should not be prohibitive, as most of the expertise can be found with the stakeholders.</p> </li> </ol> </li> </ol>
Orri Erling
oerling@openlinksw.com
2009-10-27T14:57:28.000002-04:00
VLDB 2009 Web Scale Data Management Panel (5 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1582
2009-09-01T16:24:17Z
<blockquote> <p> <i>"The universe of cycles is not exactly one of literal cycles, but rather one of spirals," mused <a href="http://db.cs.berkeley.edu/jmh/" id="link-id117455a0">Joe Hellerstein</a> of UC Berkeley.</i> </p> <p> <i>"Come on, let's all drop some <a href="http://dbpedia.org/resource/ACID" id="link-id16b3db50">ACID</a>," interjected another.</i> </p> <p> <i>"It is not that we end up repeating the exact same things, rather even if some patterns seem to repeat, they do so at a higher level, enhanced by the experience gained," continued Joe.</i> </p> </blockquote> <p>Thus did the Web Scale <a href="http://dbpedia.org/resource/Data" id="link-id11061ae0">Data</a> Management panel conclude.</p> <p>Whether successive generations are made wiser by the ones that have gone before may be argued either way.</p> <p>The cycle in question was that of developers discovering ACID in the 1960s, i.e. Atomicity, Consistency, Integrity, Durability. Thus did the DBMS come into being. Then DBMSs kept becoming more complex until, as there will be a counter-force to each force, came the <a href="http://dbpedia.org/resource/Meme" id="link-id11076cc8">meme</a> of key value stores and BASE, no multiple-row transactions, eventual consistency, no query language but scaling to thousands of computers. So now, the DBMS community asks itself what went wrong.</p> <p>In the words of one panelist, another demonstrated a "shocking familiarity with the subject matter of substance abuse" when he called for the DBMS community to get on a <a href="http://dbpedia.org/resource/Twelve-step_program" id="link-id15d954a8">12 step program</a> and to look where addiction to certain ideas, among which ACID, had brought its life. Look at yourself: The influential papers in what ought to be your space by rights are coming from the OS community: <a href="http://dbpedia.org/resource/Google" id="link-id166675f0">Google</a> Bigtable, Amazon Dynamo, want more? When you ought to drive, you give excuses and play catch up! Stop denial, drop <a href="http://dbpedia.org/resource/SQL" id="link-id1105adf0">SQL</a>, drop ACID!</p> <p>The web developers have revolted against the time-honored principles of the DBMS. This is true. Sharded <a href="http://dbpedia.org/resource/MySQL" id="link-id1221c230">MySQL</a> is not the ticket — or is it? Must they rediscover the virtues of ACID, just like the previous generation did?</p> <p>Nothing under the sun is new. As in music and fashion, trends keep cycling also in science and engineering.</p> <p>But seriously, does the full-featured DBMS scale to web scale? <a href="http://dbpedia.org/resource/Microsoft" id="link-id10ffcaf8">Microsoft</a> says the Azure version of SQL server does. <a href="http://dbpedia.org/resource/Yahoo%21" id="link-id16b3f138">Yahoo</a> says they want no SQL but <a href="http://dbpedia.org/resource/Hadoop" id="link-id11046ef0">Hadoop</a> and <a href="http://research.yahoo.com/node/2304" id="link-id110a0040">PNUTS</a>.</p> <p>Twitter, Facebook, and other web names got their own discussion. Why do they not go to serious DBMS vendors for their data but make their own, like Facebook with Hive?</p> <p>Who can divine the mind of the web developer? What makes them go to <a href="http://www.danga.com/memcached/" id="link-id1109e280">memcached</a>, manually sharded MySQL, and <a href="http://dbpedia.org/resource/MapReduce" id="link-id1107cd60">MapReduce</a>, walking away from the 40 years of technology invested in declarative query and ACID? What is this highly visible but hard to grasp <a href="http://dbpedia.org/resource/Entity" id="link-id1105b6b8">entity</a>? My guess is that they want something they can understand, at least at the beginning. A DBMS, especially on a cluster, is complicated, and it is not so easy to say how it works and how its performance is determined. The big brands, if deployed on a thousand PCs, would also be prohibitively expensive. But if all you do with the DBMS is single row selects and updates, it is no longer so scary, but you end up doing all the distributed things in a middle layer, and abandoning expressive queries, transactions, and database-supported transparency of location. But at least now you know how it works and what it is good/not good for.</p> <p>This would be the case for those who make a conscious choice. But by and large the choice is not deliberate; it is something one drifts into: The application gains popularity; the single <a href="http://en.wikipedia.org/wiki/LAMP_%28software_bundle%29" id="link-iddc68d28">LAMP</a> can no longer keep all in memory; you need a second MySQL in the LAMP and you decide that users A–M go left and N–Z right (horizontal partitioning). This siren of sharding beckons you and all is good until you hit the reef of re-architecting. Memcached and duct-tape help, like aspirin helps with hangover, but the root cause of the headache lies unaddressed.</p> <p>The conclusion was that there ought to be something incrementally scalable from the get-go. Low cost of entry and built-in scale-out. No, the web developers do not hate SQL; they just have gotten the idea that it does not scale. But they would really wish it to. So, DBMS people, show there is life in you yet.</p> <p>Joe Hellerstein was the philosopher and paradigmatician of the panel. His team had developed a protocol-compatible Hadoop in a few months using a declarative logic programming style approach. His claim was that developers made the market. Thus, for writing applications against web scale data, there would have to be data centric languages. Why not? These are discussed in <a href="http://www.eecs.berkeley.edu/Research/Projects/Data/105733.html" id="link-id110ba0e0">Berkeley Orders Of Magnitude</a> (<a href="http://www.eecs.berkeley.edu/Research/Projects/Data/105733.html" id="link-id16aab768">BOOM</a>).</p> <p>I come from <a href="http://en.wikipedia.org/wiki/Lisp_%28programming_language%29" id="link-id10f2cd68">Lisp</a> myself, way back. I have since abandoned any desire to tell anybody what they ought to program in. This is a bit like religion: Attempting to impose or legislate or ram it on somebody just results in anything from lip service to rejection to war. The appeal exerted by the diverse language/paradigm -isms on their followers seems to be based on hitting a simplification of reality that coincides with a problem in the air. MapReduce is an example of this. <a href="http://dbpedia.org/resource/PHP" id="link-ide22cdd0">PHP</a> is another. A quick fix for a present need: Scripting web servers (PHP) or processing tons of files (MapReduce). The full database is not as quick a fix, even though it has many desirable features. It is also not as easy to tell what happens inside one, so MapReduce may give a greater feeling of control.</p> <p>Totally self-managing, dynamically-scalable <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id152864b0">RDF</a> would be a fix for not having to design or administer databases: Since it would be indexed on everything, complex queries would be possible; no full database scans would stop everything. For the mid-size segment of web sites this might be a fit. For the extreme ends of the spectrum, the choice is likely something custom built and much less expressive.</p> <p>The BOOM rule language for data-centric programming would be something very easy for us to implement, in fact we will get something of the sort essentially for free when we do the rule support already planned.</p> <p>The question is, can one induce web developers to do logic? The history is one of procedures, both in LAMP and MapReduce. On the other hand, the query languages that were ever universally adopted were declarative, i.e., keyword search and SQL. There certainly is a quest for an application model for the cloud space beyond just migrating apps. We'll see. More on this another time.</p>
Orri Erling
oerling@openlinksw.com
2009-09-02T12:05:20.000001-04:00
VLDB 2009 Yahoo Keynote (4 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1577
2009-09-01T16:04:36Z
<p> <a href="http://dbpedia.org/resource/Raghu_Ramakrishnan" id="link-id0x19076030">Raghu Ramakrishnan</a> of <a href="http://dbpedia.org/resource/Yahoo%21" id="link-id0x47142b8">Yahoo</a>! gave a keynote about <a href="http://research.yahoo.com/node/2304" id="link-id0x186c1288">PNUTS</a>, the Yahoo solution for managing massive user <a href="http://dbpedia.org/resource/Data" id="link-id0x4e966e0">data</a>, from front page preferences to mail to social networks.</p> <p>Dynamic scale, wide area replication, and high availability are the issues. Transactions on multiple records, complex queries, and absolute consistency at all times are traded off. Also, the programming interfaces are lower level than with <a href="http://dbpedia.org/resource/SQL" id="link-id0x23e68948">SQL</a>. Replication and consistency rules are choices for the application developer; the platform offers some basic alternatives. Implementation-wise, there is a <a href="http://dbpedia.org/resource/MySQL" id="link-id0x182cead8">MySQL</a> back-end and all the partitioning, query routing, replication, and balancing take place in a layer of front-ends.</p> <p>Now what do we say to this?</p> <p>In the Yahoo! case, even if complex queries were possible, which they are not, one would probably keep them off the online system since latency and availability are everything. A latency of some tens of milliseconds is however acceptable, which is not so terrible for single record operations: There is time for a couple of messages on the data center network and even maybe for a disk read.</p> <p>PNUTS is probably the fastest way of getting to the desired beachhead of simple access to data at infinite scale in multiple geographies. In the identical situation, I might have done something similar.</p> <p>But we are in a different situation, concerned with complex queries, a highly-normalized <a href="http://dbpedia.org/resource/Database_schema" id="link-id0x197b7948">schema</a>-last situation, i.e., index on everything, large objects normalized away, as is done in <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x385a900">RDF</a>. Then we are also in the relational situation. Infinite scale, fault tolerance, and wide-area replication do come up regularly in user needs. The applications for which people would like RDF are not only complex reasoning things but very big <a href="http://dbpedia.org/resource/Metadata" id="link-id0x25a30d98">metadata</a> stores for user generated content, social networks, and the like.</p> <p>Which of the PNUTS principles could we apply?</p> <ul> <li> <p> <b>Division in tablets:</b> When a partition of the data grows too big, it should split.</p> </li> <li> <p> <b>Migration of partitions:</b> as capacity/demand change, partitions should migrate so as to equalize load.</p> </li> <li> <p> <b>High availability:</b> This is divided in two — on one hand inside the data center; on the other between data centers. Inside the data center, storing partitions in duplicate and running them synchronously is possible. This is manifestly impossible in wide area settings, though. For this, we need a log-shipping style of asynchronous replication. But how does one deal with split networks and transfer of replication mastery?</p> </li> </ul> <p>PNUTS determines the master copy record by record. This makes sense when the record, for example, corresponds to a user. For RDF, doing this by the triple would be prohibitive. Doing this by the graph, or by the subject of a set of triples across all graphs, would be better. We would agree with PNUTS that transferring mastery by the storage chunk is not desired, as the chunk will contain arbitrary unrelated data.</p> <p> </p> <p>The eventual consistency mechanisms can be generalized to RDF readily enough. In a social RDF application, the graph is the most likely unit of data ownership and update authorization, so the graph would also be the unit of eventual consistency. Keeping a separate data structure listing recent inserts/deletes to a graph with timestamps would serve for establishing consistency. The size of this would be a small fraction of the size of the graph.</p> <p>RDF cannot do anything without joining between partitions, whereas for PNUTS the join between partitions is an application matter. But then PNUTS does have an extra step of RPC between the PNUTS infrastructure and the back-end. Doing query routing in the back-end gets rid of this. RDF does remain more dependent on even performance and short interconnect latencies, though. It also likely takes more space. But the essential consistency and availability features can be generalized to it, providing the merge of semi-structured data at infinite scale and availability with complex query.</p> <p>At any rate, repartitioning-on-demand and partition-migration remain the key agenda items for us, confirmed over and over at VLDB.</p>
Orri Erling
oerling@openlinksw.com
2009-09-01T17:32:35.000002-04:00
VLDB 2009 TPC Workshop (3 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1576
2009-09-01T15:51:09Z
<p>Michael <a href="http://dbpedia.org/resource/Michael_Stonebraker" id="link-id0x15e5efe0">Stonebraker</a> gave the keynote at the <a href="http://www.tpc.org/" id="link-id0x18cee5f0">TPC</a> workshop. His message was that the TPC, at the venerable age of 21, was already a decade late in reinventing itself. From the height of relevance at the time of the debit/credit benchmark twenty years back, it was slipping into the sunset of irrelevance unless it paid attention.</p> <p>Now we are great fans of the TPC and while we have not published results by the TPC book, we have extensively used TPC material for guiding <a href="http://dbpedia.org/resource/Program_optimization" id="link-id0x4e55368">optimization</a>, as has pretty much everybody else.</p> <p>It is true that the rules encourage unrealistic configurations. The emphasis on random access from disk that is built into the rules leads to disk configurations that are very improbable in practice, such as 1PB of disks for 3TB of <a href="http://dbpedia.org/resource/Data" id="link-id0x191cd880">data</a>, just so there are enough disk arms in parallel. Stonebraker also pointed out that replication and failover were ubiquitous in real life and that roll forward from logs was unrealistic as a recovery model since it took so long. Benchmarks should therefore include replication.</p> <p>Further, Stonebraker challenged the TPC to go for the new frontier, which he described as the huge data sets in science and on big web sites. Scientists, the ones who would save our planet from the diverse ills confronting it, do not like relational databases. They avoid them when can. They want arrays for physics, and graphs for biology and chemistry. <a href="http://dbpedia.org/resource/MapReduce" id="link-id0x53f6040">MapReduce</a> is eating database's lunch; what will you do about this?</p> <p>I later suggested incorporating an <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x18902070">RDF</a> <a href="http://dbpedia.org/resource/Metadata" id="link-id0x3990af8">metadata</a> benchmark into the TPC suite. We'll see about this; we'll first have to come up with a suitable one. There is a great deal of pressure for making good RDF benchmarks but this is not yet in the center of the mainstream that TPC tends to cover.</p> <p>TPC's own talk was about the life cycle of benchmarks. A benchmark begins a bit ahead of the mainstream, with a problem that is difficult but not so difficult as to be uncommon. When the solution to this problem becomes commonplace, the benchmark's relevance gradually drops.</p> <p>There was a talk on robustness of query plans which was well to the point. Indeed, there are performance cliffs at certain points; for example, when passing from memory-only to disk-pageable data structures, or when switching from indexed access to table scans, or from loop to hash joins. Quite so. The analysis I really would have liked to see would have been one of what happens when passing from single server to a cluster, and from local joins to cross-partition ones. Also contrasting of <a href="http://dbpedia.org/resource/Cache" id="link-id0x1942aca8">cache</a> fusion and partitioning. We have our own data and experience but we find we don't have time to measure all the other systems.</p> <p>Anyway it is good to raise the question of smooth and predictable performance.</p>
Orri Erling
oerling@openlinksw.com
2009-09-01T17:32:30-04:00
Some Interesting VLDB 2009 Papers (2 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1575
2009-09-01T15:46:14Z
<h3> <a href="http://dbpedia.org/resource/Intel_Corporation" id="link-id0x3588e30">Intel</a> on <a href="http://dbpedia.org/resource/Hash_join" id="link-id0x1bc77c90">Hash Join</a> </h3> <p>Intel and <a href="http://dbpedia.org/resource/Oracle_Database" id="link-id0x2f1d4d8">Oracle</a> had measured hash and sort merge joins on Intel Core i7. The result was that hash join with both tables partitioned to match <a href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x55b2b70">CPU</a> <a href="http://dbpedia.org/resource/Cache" id="link-id0x2a4fef8">cache</a> was still the best but that sort/merge would catch up with more <a href="http://dbpedia.org/resource/SIMD" id="link-id0x4fe8670">SIMD</a> instructions in the future.</p> <p>We should probably experiment with this but the most important partitioning of hash joins is still between cluster nodes. Within the process, we will see. The tradeoff of doing all in cache-sized partitions is larger intermediate results which in turn will impact the working set of disk pages in RAM. For one-off queries this is OK; for online use this has an effect.</p> <h3>1000 TABLE Queries</h3> <p> <a href="http://dbpedia.org/resource/SAP_AG" id="link-id0x55a1018">SAP</a> presented a paper about <a href="http://dbpedia.org/resource/Federated_database_system" id="link-id0x5500758">federating relational databases</a>. Queries would be expressed against VIEWs defined over remote TABLEs, UNIONed together and so forth. Traditional methods of <a href="http://dbpedia.org/resource/Program_optimization" id="link-id0x4f038f0">optimization</a> would run out of memory; a single 1000 TABLE plan is already a big thing. Enumerating multiple variations of such is not possible in practice. So the solution was to plan in two stages — first arrange the subqueries and derived TABLEs, and then do the JOIN orders locally. Further, local JOIN orders could even be adjusted at run time based on the actual <a href="http://dbpedia.org/resource/Data" id="link-id0x41d3560">data</a>. Nice.</p> <h3>Oracle Subqueries and New Implementation of LOBs</h3> <p>Oracle presented some new <a href="http://dbpedia.org/resource/SQL" id="link-id0x39ad838">SQL</a> optimizations, combining and inlining subqueries and derived TABLEs. We do fairly similar things and might extend the repertoire of tricks in the direction outlined by Oracle as and when the need presents itself. This further confirms that SQL and other query optimization is really an incremental collection of specially recognized patterns. We still have not found any other way of doing it.</p> <p>Another interesting piece by Oracle was about their re-implementation of large object support, where they compared LOB loading to file system and raw device speeds.</p> <h3> <a href="http://dbpedia.org/resource/Amadeus_CRS" id="link-id0x3aa1378">Amadeus CRS</a> booking system, steady query time for arbitrary single table queries</h3> <p>There was a paper about a memory-resident database that could give steady time for any kind of single-table scan query. The innovation was to not use indices, but to have one partition of the table per processor core, all in memory. Then each core would have exactly two cursors — one reading, the other writing. The write cursor should keep ahead of the read cursor. Like this, there would be no read/write contention on pages, no locking, no multiple threads splitting a tree at different points, none of the complexity of a multithreaded database engine. Then, when the cursor would hit a row, it would look at the set of queries or updates and add the result to the output if there was a result. The data indexes the queries, not the other way around. We have done something similar for detecting changes in a full text corpus but never thought of doing queries this way.</p> <p>Well, we are all about JOINs so this is not for us, but it deserves a mention for being original and clever. And indeed, anything one can ask about a table will likely be served with great predictability.</p> <h3> <a href="http://dbpedia.org/resource/Greenplum" id="link-id0x3670360">Greenplum</a> </h3> <p> <a href="http://dbpedia.org/resource/Google" id="link-id0x2c5dfb8">Google</a>'s chief economist said that the winning career choice would be to pick a scarce skill that made value from something that was plentiful. For the 2010s this career is that of the statistician/data analyst. We've said it before — the next web is analytics for all. The Greenplum talk was divided between the Fox use case, with 200TB of data about ads, web site traffic, and other things, growing 5TB a day. The message was that cubes and drill down are passé, that it is about complex statistical methods that have to run in the database, that the new kind of geek is the data geek, whose vocation it is to consume and spit out data, discover things in it, and so forth.</p> <p>The technical part was about Greenplum, a SQL database running on a cluster with a <a href="http://dbpedia.org/resource/PostgreSQL" id="link-id0x4e15798">PostgreSQL</a> back-end. The interesting points were embedding <a href="http://dbpedia.org/resource/MapReduce" id="link-id0x4fd3e00">MapReduce</a> into SQL, and using relational tables for arrays and complex data types — pretty much what we also do. Greenplum emphasized scale-out and found column orientation more like a nice-to-have.</p> <h3> <a href="http://dbpedia.org/resource/MonetDB" id="link-id0x416d288">MonetDB</a>, optimizing database for CPU cache</h3> <p>The MonetDB people from <a href="http://dbpedia.org/resource/National_Research_Institute_for_Mathematics_and_Computer_Science" id="link-id0x4ebedb0">CWI</a> in Amsterdam gave a 10 year best paper award talk about optimizing database for CPU cache. The key point was that if data is stored as columns, it ought also to be transferred as columns inside the execution engine. Materialize big chunks of state to cut down on interpretation overhead and use cache to best effect. They vector for CPU cache; we vector for scale-out, since the only way to ship operations is to ship many at a time. So we might as well vector also in single servers. This could be worth an experiment. Also we regularly visit the topic of <a href="http://dbpedia.org/resource/Column-oriented_DBMS" id="link-id0x4d34cb0">column storage</a>. But we are not yet convinced that it would be better than row-style covering indices for <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x4d55d78">RDF</a> quads. But something could certainly be tried, given time.</p>
Orri Erling
oerling@openlinksw.com
2009-09-01T17:32:24.000004-04:00
VLDB 2009 (1 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1574
2009-09-01T15:30:37Z
<p>I was at the <a href="http://vldb2009.org/" id="link-id0x6700588">VLDB 2009</a> conference in Lyon, France. I will in the next few posts discuss some of the prominent themes and how they relate to our products or to <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x69386a8">RDF</a> and <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x7537ce0">Linked Data</a>.</p> <p>Firstly, RDF was as good as absent from the presentations and discussions we saw. There were a few mentions in the panel on structured <a href="http://dbpedia.org/resource/Data" id="link-id0x1c201ed0">data</a> on the web, however RDF was not in any way seen to be essential for this. There were also a couple of RDF mentions in questions at other sessions, but that was about it.</p> <p>It is a common perception that RDF and database people do not talk with each other. Evidence seems to bear this out.</p> <p>As a database developer I did get a lot of readily applicable ideas from the VLDB talks. These run across the whole range of DBMS topics, from <a href="http://dbpedia.org/resource/Data_compression" id="link-id0x1b802010">key compression</a> and <a href="http://dbpedia.org/resource/SQL" id="link-id0x48bc820">SQL</a> <a href="http://dbpedia.org/resource/Program_optimization" id="link-id0x218bd558">optimization</a>, to <a href="http://dbpedia.org/resource/Column-oriented_DBMS" id="link-id0x238a39c8">column storage</a>, <a href="http://dbpedia.org/resource/Central_processing_unit" id="link-id0x6694538">CPU</a> <a href="http://dbpedia.org/resource/Cache" id="link-id0x4895568">cache</a> optimization, and the like. In this sense, VLDB is directly relevant to all we do. In a conversation, someone was mildly confused that I should on one hand mention I was doing RDF, and on the other hand also be concerned about database performance. These things are not seen to belong together, even though making RDF do something useful certainly depends on a great deal of database optimization.</p> <p>The question of all questions — that of infinite scale-out with complex queries, resilience, replication, and full database semantics — was strongly in the air.</p> <p>But it was in the air more as a question than as an answer. Not very much at all was said about the performance of distributed query plans, of <a href="http://dbpedia.org/resource/Two-phase_commit_protocol" id="link-id0x7a4b208">2pc</a> (<a href="http://dbpedia.org/resource/Two-phase_commit_protocol" id="link-id0x1a0e8ac8">two-phase commit</a>), of the impact of interconnect latency, and such things. On the other hand, people were talking quite liberally about optimizing CPU cache and local multi-core execution, not to mention SQL plans and rewrites. Also, almost nothing was said about transactions.</p> <p>Still, there is bound to be a great deal of work in scale-out of complex workloads by any number of players. Either these things are all figured out and considered self-evidently trivial, or they are so hot that people will go there only by way of allusion and vague reference. I think it is the latter.</p> <p>By and large, we were confirmed in our understanding that infinite scale-out on the go, with redundancy, is the ticket, especially if one can offer complex queries and transactional semantics coupled with instant data loading and <a href="http://dbpedia.org/resource/Database_schema" id="link-id0x23a0c590">schema</a>-last.</p> <p>Column storage and cache optimizations seem to come right after these.</p> <p>Certainly the database space is diversifying.</p> <p> <a href="http://dbpedia.org/resource/MapReduce" id="link-id0x185e6370">MapReduce</a> was discussed quite a bit, as an intruder into what would be the database turf. We have no great problem with MapReduce; we do that in SQL procedures if one likes to program in this way. <a href="http://dbpedia.org/resource/Greenplum" id="link-id0x1ad96d68">Greenplum</a> also seems to have come by the same idea.</p> <p>As said before, RDF and RDF reasoning were ignored. Do these actually offer something to the database side? Certainly for search, discovery, integration, and resource discovery, linked data has evident advantages.</p> <p>Two points of the design space — the warehouse, and the web-scale key-value store — got a lot of attention. Would I do either in RDF? RDF is a slightly different design space point, like key-value with complex queries — on the surface, a fusion of the two. As opposed to RDF, the relational warehouse gains from fixed data-types and task-specific layout, whether row or column. The key-value store gains from having a concept of a semi-structured record, a bit like the RDF subject of a triple, but now with ad-hoc (if any) secondary indices, and inline blobs. The latter is much simpler and more compact than the generic RDF subject with graphs and all, and can be easily treated as a unit of version control and replication mastering. RDF, being more generic and more normalized, is representationally neither as ad-hoc nor as compact.</p> <p>But RDF will be the natural choice when complex queries and ad-hoc schema meet, for example in web-wide integrations of application data.</p> <p>There seems to be a huge divide in understanding between database-developing people and those who would be using databases. On one side, this has led to a back-to-basics movement with no SQL, no <a href="http://dbpedia.org/resource/ACID" id="link-id0x2ec4088">ACID</a>, key-value pairs instead of schema, MapReduce instead of fancy but hard-to-follow parallel execution plans. On the other side, the database space specializes more and more; it is no longer simply transactions vs. analytics, but many more points of specialization.</p> <p>Some frustration can be sensed in the ivory towers of science when it is seen that the ones most in need of database understanding in fact have the least. <a href="http://dbpedia.org/resource/Google" id="link-id0x7748540">Google</a>, <a href="http://dbpedia.org/resource/Yahoo%21" id="link-id0x1ba44020">Yahoo</a>!, and <a href="http://dbpedia.org/resource/Microsoft" id="link-id0x5788710">Microsoft</a> know what they are doing, with or without SQL, but the medium-size or fast-growing web sites seem to be in confusion when <a href="http://en.wikipedia.org/wiki/LAMP_%28software_bundle%29" id="link-id0x18098f18">LAMP</a> or <a href="http://dbpedia.org/resource/Ruby_programming_language" id="link-id0x4844138">Ruby</a> or the scripting-du-jour can no longer cut it.</p> <p>Can somebody using a database be expected to understand how it works? I would say no, not in general. Can a database be expected to unerringly self-configure based on workload? Sure, a database can suggest layouts, but it ought not restructure itself on the spur of the moment under full load.</p> <p>It is safe to say that the community at large no longer believes in "one size fits all". Since there is no general solution, there is a fragmented space of specific solutions. We will be looking at some of these issues in the following posts.</p>
Orri Erling
oerling@openlinksw.com
2009-09-01T16:53:20-04:00
Provenance and Reification in Virtuoso
http://www.openlinksw.com/weblog/oerling/?id=1572
2009-09-01T14:44:08Z
<p>These days, <a href="http://dbpedia.org/resource/Data" id="link-id0x4a44870">data</a> provenance is a big topic across the board, ranging from the <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x4e10e60">linked data</a> <a href="http://dbpedia.org/resource/Giant_Global_Graph" id="link-id0x4738350">web</a>, to <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x1fe33310">RDF</a> in general, to any kind of data integration, with or without RDF. Especially with scientific data we encounter the need for metadata and provenance, repeatability of experiments, etc. Data without context is worthless, yet the producers of said data do not always have a model or budget for metadata. And if they do, the approach is often a proprietary relational schema with web services in front.</p> <p>RDF and linked data principles could evidently be a great help. This is a large topic that goes into the culture of doing science and will deserve a more extensive treatment down the road.</p> <p>For now, I will talk about possible ways of dealing with provenance annotations in <a href="http://virtuoso.openlinksw.com" id="link-id0x36581e8">Virtuoso</a> at a fairly technical level.</p> <p>If data comes many-triples-at-a-time from some source (e.g., library catalogue, user of a social network), then it is often easiest to put the data from each source/user into its own graph. Annotations can then be made on the graph. The graph IRI will simply occur as the subject of a triple in the same or some other graph. For example, all such annotations could go into a special annotations graph.</p> <p>On the query side, having lots of distinct graphs does not have to be a problem if the index scheme is the right one, i.e., the 4 index scheme <a href="http://docs.openlinksw.com/virtuoso/rdfperformancetuning.html#rdfperfindexes" id="link-id142a0798">discussed in the Virtuoso documentation</a>. If the query does not specify a graph, then triples in any graph will be considered when evaluating the query.</p> <p>One could write queries like —</p> <blockquote> <code><pre>SELECT ?pub WHERE { GRAPH ?g { ?person foaf:knows ?contact } ?contact foaf:name "Alice" . ?g xx:has_publisher ?pub }</pre> </code> </blockquote> <p>This would return the publishers of graphs that assert that somebody knows Alice.</p> <p>Of course, the <a href="http://www.w3.org/TR/2004/REC-rdf-primer-20040210/#reification" id="link-id14fa9488">RDF reification vocabulary</a> can be used as-is to say things about single triples. It is however very inefficient and is not supported by any specific optimization. Further, reification does not seem to get used very much; thus there is no great pressure to specially optimize it.</p> <p>If we have to say things about specific triples and this occurs frequently (i.e., for more than 10% or so of the triples), then modifying the quad table becomes an option. For all its inefficiency, the RDF reification vocabulary is applicable if reification is a rarity.</p> <p>Virtuoso's <code>RDF_QUAD</code> table can be altered to have more columns. The problem with this is that space usage is increased and the RDF loading and query functions will not know about the columns. A <a href="http://dbpedia.org/resource/SQL" id="link-id0x4b1d938">SQL</a> update statement can be used to set values for these additional columns if one knows the <code>G,S,P,O</code>. </p> <p>Suppose we annotated each quad with the user who inserted it and a timestamp. These would be columns in the <code>RDF_QUAD</code> table. The next choice would be whether these were primary key parts or dependent parts. If primary key parts, these would be non-<code>NULL</code> and would occur on every index. The same quad would exist for each distinct user and time this quad had been inserted. For loading functions to work, these columns would need a default. In practice, we think that having such metadata as a dependent part is more likely, so that <code>G,S,P,O</code> are the unique identifier of the quad. Whether one would then include these columns on indices other than the primary key would depend on how frequently they were accessed.</p> <p>In <a href="http://dbpedia.org/resource/SPARQL" id="link-id0x472afb0">SPARQL</a>, one could use an extension syntax like —</p> <blockquote> <code><pre>SELECT * WHERE { ?person foaf:knows ?connection OPTION ( time ?ts ) . ?connection foaf:name "Alice" . FILTER ( ?ts > "2009-08-08"^^xsd:datetime ) }</pre> </code> </blockquote> <p>This would return everybody who knows Alice since a date more recent than 2009-08-08. This presupposes that the quad table has been extended with a datetime column.</p> <p>The <code>OPTION (time ?ts)</code> syntax is not presently supported but we can easily add something of the sort if there is user demand for it. In practice, this would be an extension mechanism enabling one to access extension columns of <code>RDF_QUAD</code> via a column <code>?variable</code> syntax in the <code>OPTION</code> clause.</p> <p>If quad metadata were not for every quad but still relatively frequent, another possibility would be making a separate table with a key of <code>GSPO</code> and a dependent part of <code>R</code>, where <code>R</code> would be the reification <a href="http://dbpedia.org/resource/Uniform_Resource_Identifier" id="link-id0x365b190">URI</a> of the quad. Reification statements would then be made with <code>R</code> as a subject. This would be more compact than the reification vocabulary and would not modify the <code>RDF_QUAD</code> table. The syntax for referring to this could be something like —</p> <blockquote> <code><pre>SELECT * WHERE { ?person foaf:knows ?contact OPTION ( reify ?r ) . ?r xx:assertion_time ?ts . ?contact foaf:name "Alice" . FILTER ( ?ts > "2008-8-8"^^xsd:datetime ) }</pre> </code> </blockquote> <p>We could even recognize the reification vocabulary and convert it into the reify option if this were really necessary. But since it is so unwieldy I don't think there would be huge demand. Who knows? You tell us.</p>
Orri Erling
oerling@openlinksw.com
2009-09-01T11:20:44-04:00
More On Parallel RDF/Text Query Evaluation
http://www.openlinksw.com/weblog/oerling/?id=1570
2009-08-19T17:28:50Z
<p>We have received some more questions about <a href="http://virtuoso.openlinksw.com" id="link-id0x266cd288">Virtuoso</a>'s parallel query evaluation model.</p> <p>In answer, we will here explain how we do search engine style processing by writing <a href="http://dbpedia.org/resource/SPARQL" id="link-id0x23c628b8">SPARQL</a>. There is no need for custom procedural code because the query optimizer does all the partitioning and the equivalent of map reduce.</p> <p>The point is that what used to require programming can often be done in a generic query language. The technical detail is that the implementation must be smart enough with respect to parallelizing queries for this to be of practical benefit. But by combining these two things, we are a step closer to the web being the database.</p> <p>I will here show how we do some joins combining full text, <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x22ff08b0">RDF</a> conditions, and aggregates and <code>ORDER BY</code>. The sample task is finding the top 20 entities with New York in some attribute value. Then we specify the search further by only taking actors associated with New York. The results are returned in the order of a composite of <a href="http://dbpedia.org/resource/Entity" id="link-id0x22da5258">entity</a> rank and text match score.</p> <p>The basic query is:</p> <blockquote> <code><pre> SELECT ( <a href="http://dbpedia.org/resource/SQL" id="link-id0x237a6530">sql</a>:s_sum_page ( <sql:vector_agg> ( <bif:vector> ( ?c1 , ?sm ) ), bif:vector ( 'new', 'york' ) ) ) AS ?res WHERE { { SELECT ( <SHORT_OR_LONG::>(?s1) ) AS ?c1 ( <sql:S_SUM> ( <SHORT_OR_LONG::IRI_RANK> ( ?s1 ) , <SHORT_OR_LONG::> ( ?s1textp ) , <SHORT_OR_LONG::> ( ?o1 ) , ?sc ) ) AS ?sm WHERE { ?s1 ?s1textp ?o1 . ?o1 bif:contains "new AND york" OPTION ( SCORE ?sc ) } ORDER BY DESC ( <sql:sum_rank> (( <sql:S_SUM> ( <SHORT_OR_LONG::IRI_RANK> ( ?s1 ) , <SHORT_OR_LONG::> ( ?s1textp ) , <SHORT_OR_LONG::> ( ?o1 ) , ?sc ) )) ) LIMIT 20 } } </pre> </code> </blockquote> <p>This takes some explaining. The basic part is</p> <blockquote> <code><pre>{ ?s1 ?s1textp ?o1 . ?o1 bif:contains "new AND york" OPTION ( SCORE ?sc ) }</pre> </code> </blockquote> <p>This just makes tuples where <code>?s1</code> is the object, <code>?s1textp</code> the property, and <code>?o1</code> the literal which contains "New York". For a single <code>?s1</code>, there can of course be many properties which all contain "New York".</p> <p>The rest of the query gathers all the "New York" containing properties of an entity into a single aggregate, and then gets the entity ranks of all such entities.</p> <p>After this, the aggregates are sorted by a sum of the entity rank and a combined text score calculated based on the individual text match scores between "New York" and the strings containing "New York". The text hit score is higher if the words repeat often and in close proximity.</p> <p>The <code>s_sum</code> function is a user-defined aggregate which takes 4 arguments: The rank of the subject of the triple; the predicate of the triple containing the text; the object of the triple containing the text; and the text match score.</p> <p>These are grouped by the subject of the triple. After this, these are sorted by <code>sum_score</code> of the aggregate constructed with <code>s_sum</code>. The <code>sum_score</code> is a SQL function combining the entity rank with the text scores of the different literals.</p> <p>This executes as one would expect: All partitions make a text index lookup, retrieving the object of the triple. The text index entries of an object are stored in the same partition as the object. But the entity rank is a property of the subject and is partitioned by the subject. Also the <code>GROUP BY</code> is by the subject. Thus the <a href="http://dbpedia.org/resource/Data" id="link-id0x24381030">data</a> is produced from all partitions, then streamed into the receiving partitions, determined by the subject. This partition can then get the score and group the matches by the subject. Since all these partial aggregates are partitioned by the subject, there is no need to merge them; thus, the top <code>k</code> sort can be done for each partition separately. Finally, the top 20 of each partition are merged into the global top 20. This is then passed to a final function <code>s_sum_page</code> that turns this all into an <a href="http://dbpedia.org/resource/XML" id="link-id0x2363d6c0">XML</a> fragment that can be processed with XSLT for inclusion on a web page.</p> <p>This differs from the text search engine in that the query pipeline can contain arbitrary cross-partition joins. Also, the string "New York" is a common label that occurs in many distinct entities. Thus one text match, to one document, in the case the containing only the string "New York" will get many entities, likely all from different partitions.</p> <p>So, if we only want actors with a mention of "New York", we need to get the inner part of the query as:</p> <blockquote> <code><pre>{ ?s1 ?s1textp ?o1 . ?o1 bif:contains "new AND york" OPTION ( SCORE ?sc ) . ?s1 a <<a href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x237110b8">http</a>://<a href="http://umbel.org/about/" id="link-id0x2318e198">umbel</a>.org/umbel/sc/Actor> }</pre> </code> </blockquote> <p>Whether an entity is an actor can be checked in the same partition as the rank of the entity. Thus the query plan gets this check right before getting the rank. This is natural since there is no point in getting the rank of something that is not an actor.</p> <p>The <code><short_or_long::sql:func></code> notation means that we call <code>func</code>, which is a SQL stored procedure with the arguments in their internal form. Thus, if a variable bound to an IRI is passed, the <code>short_or_long</code> specifies that it is passed as its internal ID and is not converted into its text form. This is essential, since there is no point getting the text of half a million IRIs when only 20 at most will be shown in the end.</p> <p>Now, when we run this on a collection of 4.5 billion triples of <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x24381160">linked data</a>, once we have the working set, we can get the top 20 "New York" occurrences, with text summaries and all, in just 1.1s, with 12 of 16 cores busy. (The hardware is two boxes with two quad-core Xeon 5345 each.)</p> <p>If we run this query in two parallel sessions, we get both results in 1.9s, with 14 of 16 cores busy. This gets about 200K "New York" strings, which becomes about 400K entities with New York somewhere, for which a rank then has to be retrieved. After this, all the possibly-many occurrences of New York in the title, text, and other properties of the entity are aggregated together, resolving into some 220K groups. These are then sorted. This is internally over 1.5 million random lookups and some 40MB of traffic between processes. Restricting the type of the entity to actor drops the execution time of one query to 0.8s because there are then fewer ranks to retrieve and less data to aggregate and sort.</p> <p>By adding partitions and cores, we scale horizontally, as evaluating the query involves almost no central control, even though data are swapped between partitions. There is some flow control to avoid constructing overly-large intermediate results but generally partitions run independently and asynchronously. In the above case, there is just one fence at the point where all aggregates are complete, so that they can be sorted; otherwise, all is asynchronous.</p> <p>Doing <code>JOINs</code> between partitions and partitioned <code>GROUP BY</code>/<code>ORDER BY</code> is pretty regular database stuff. Applying this to RDF is a most natural thing.</p> <p>If we do not parallelize the user-defined aggregate for grouping all the "New York" occurrences, the query takes 8s instead of 1.1s. If we could not put SQL procedures as user-defined aggregates to be parallelized with the query, we'd have to either bring all the data to a central point before the top k, which would destroy performance, or we would have to do procedures with explicit parallel procedure calls which is hard to write, surely too hard for <i>ad hoc</i> queries.</p> <a href="http://bit.ly/4jAVHC" id="link-id114d58f0">Results of live execution</a> may not be complete on initial load, as this link includes a "Virtuoso Anytime" timeout of 10 seconds. Running against a cold cache, these results may take much longer to return; a warm cache will deliver response times along the lines of those discussed above. <p>Engineering matters. If we wish to commoditize queries on a lot of data, such intelligence in the DBMS is necessary; it is very unscalable to require people to do procedural code or give query parallelization hints. If you need to optimize a workload of 10 different transactions, this is of course possible and even desirable, but for the infinity of all search or analysis, this will not happen.</p>
Orri Erling
oerling@openlinksw.com
2009-08-19T14:00:29.000002-04:00
Updated hardware improves LUBM 8000 load rate in Virtuoso 6
http://www.openlinksw.com/weblog/oerling/?id=1568
2009-08-14T19:01:30Z
<p>We repeated the <a href="http://www.openlinksw.com/dataspace/oerling/weblog/Orri%20Erling%27s%20Blog/1562" id="link-id173d3068">earlier LUBM 8000 experiment</a> on a newer machine, with 2 x Xeon 5520 and 72G 1333MHz memory, and once again with the 2 machines as a networked cluster. Otherwise the settings were the same.</p> <p>The load rate is now 160,739 triples-per-second.</p> <table> <tr> <th></th> <td> </td> <th align="center"><a href="http://virtuoso.openlinksw.com" id="link-id0x199b9740">Virtuoso</a> 6 <br /> (previous run)</th> <td> </td> <th align="center">Virtuoso 6 <br /> (new run)</th> <td> </td> <th align="center">Virtuoso 6 <br /> (newest run)</th> </tr> <tr> <td align="left">blades</td> <td> </td> <td align="center">1 </td> <td> </td> <td align="center">1 </td> <td> </td> <td align="center">2</td> </tr> <tr> <td align="left">processors</td> <td> </td> <td align="center">2 x Xeon 5410</td> <td> </td> <td align="center">2 x Xeon 5520</td> <td> </td> <td align="center"> 2 x Xeon 5520 <br />+ <br />2 x Xeon 5410 <br />with 1x1GigE <br />interconnect </td> </tr> <tr> <td align="left">memory</td> <td> </td> <td align="center"> 16G 667 MHz</td> <td> </td> <td align="center">72G 1333 MHz</td> <td> </td> <td align="center">72G 1333 MHz <br />+ <br /> 16G 667 MHz <br /> respectively</td> </tr> <tr> <td align="left">reported load rate<br />triples-per-second</td> <td> </td> <td align="center"> 110,532 </td> <td> </td> <td align="center"> 160,739 </td> <td> </td> <td align="center"> 214,188 </td> </tr> </table> <p>Again, if others talk about loading LUBM, so must we. Otherwise, this metric is rather uninteresting.</p>
Orri Erling
oerling@openlinksw.com
2009-08-15T15:27:25-04:00
Single Virtuoso host loads 110,500 triples-per-second on LUBM 8000
http://www.openlinksw.com/weblog/oerling/?id=1562
2009-06-29T16:12:34Z
<p>LUBM load speed still seems to be a metric that is quoted in comparisons of <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id142df6e8">RDF</a> stores. Consequently, we too measured the load time of LUBM 8000, 1,068-million triples, on the newest <a href="http://virtuoso.openlinksw.com" id="link-id1389dfa0">Virtuoso</a>.</p> <p>The real time for the load was 161m 3s. The rate was 110,532 triples-per-second. The hardware was one machine with 2 x Xeon 5410 (quad core, 2.33 GHz) and 16G 667 MHz RAM. The software was Virtuoso 6 Cluster, configured into 8 partitions (processes) — one partition per CPU core. Each partition had its database striped over 6 disks total; the 6 disks on the system were shared between the 8 database processes.</p> <p>The load was done on 8 streams, one per server process. At the beginning of the load, the CPU usage was 740% with no disk; at the end, it was around 700% with 25% disk wait. 100% counts here for one CPU core or one disk being constantly busy.</p> <p>The RDF store was configured with the default two indices over quads, these being GSPO and OGPS. Text indexing of literals was not enabled. No materialization of entailed triples was made.</p> <p>We think that LUBM loading is not a realistic benchmark for the world but since other people publish such numbers, so do we.</p>
Orri Erling
oerling@openlinksw.com
2009-08-15T16:06:42.000001-04:00
Comparing Virtuoso Performance on Different Processors
http://www.openlinksw.com/weblog/oerling/?id=1557
2009-05-28T14:54:59Z
<p>Over the years we have run <a href="http://virtuoso.openlinksw.com" id="link-id0xd420b90">Virtuoso</a> on different hardware. We will here give a few figures that help identify the best price point for machines running Virtuoso.</p> <p>Our test is very simple: <i>Load 20 warehouses of <a href="http://dbpedia.org/resource/TPC-C" id="link-id0xdaaec90">TPC-C</a> <a href="http://dbpedia.org/resource/Data" id="link-id0xca1b7e0">data</a>, and then run one client per warehouse for 10,000 new orders</i>. The way this is set up, disk I/O does not play a role and lock contention between the clients is minimal.</p> <p>The test essentially has 20 server and 20 client threads running the same workload in parallel. The load time gives the single thread number; the 20 clients run gives the multi-threaded number. The test uses about 2-3 GB of data, so all is in RAM but is large enough not to be all in processor cache.</p> <p>All times reported are real times, starting from the start of the first client and ending with the completion of the last client.</p> <p>Do not confuse these results with official TPC-C. The measurement protocols are entirely incomparable.</p> <style type="text/css"> TABLE { background: none; border: none } TH { text-align: center; font-weight: bold } TR.top { background: } TD { text-align: center; border: none } </style> <table align="center" cellspacing="10"> <tr> <th>Test</th> <th>Platform</th> <th>Load<br />(seconds)</th> <th>Run<br />(seconds)</th> <th>GHz / cores / threads</th> </tr> <tr> <td>1</td> <td>Amazon <a href="http://aws.amazon.com/ec2/" id="link-id0xdaab030">EC2</a> Extra Large<br />(4 virtual cores)</td> <td>340</td> <td>42</td> <td>1.2 GHz? / 4 / 1</td> </tr> <tr> <td>1</td> <td>Amazon EC2 Extra Large<br />(4 virtual cores)</td> <td>305</td> <td>43.3</td> <td>1.2 GHz? / 4 / 1</td> </tr> <tr> <td>2</td> <td>1 x dual-core AMD 5900</td> <td>263</td> <td>58.2</td> <td>2.9 GHz / 2 / 1</td> </tr> <tr> <td>3</td> <td>2 x dual-core Xeon 5130 ("Woodcrest")</td> <td>245</td> <td>35.7</td> <td>2.0 GHz / 4 / 1</td> </tr> <tr> <td>4</td> <td>2 x quad-core Xeon 5410 ("Harpertown")</td> <td>237</td> <td>18.0</td> <td>2.33 GHz / 8 / 1</td> </tr> <tr> <td>5</td> <td>2 x quad-core Xeon 5520 ("Nehalem")</td> <td>162</td> <td>18.3</td> <td>2.26 GHz / 8 / 2</td> </tr> </table> <p>We tried two different EC2 instances to see if there would be variation. The variation was quite small. The tested EC2 instances costs 20 US cents per hour. The AMD dual-core costs 550 US dollars with 8G. The 3 Xeon configurations are Supermicro boards with 667MHz memory for the Xeon 5130 ("Woodcrest") and Xeon 5410 ("Harpertown"), and 800MHz memory for the Nehalem. The Xeon systems cost between 4000 and 7000 US dollars, with 5000 for a configuration with 2 x Xeon 5520 ("Nehalem"), 72 GB RAM, and 8 x 500 GB SATA disks.</p> <p> <i>Caveat: Due to slow memory (we could not get faster within available time), the results for the Nehalem do not take full advantage of its principal edge over the previous generation, i.e., memory subsystem. We'll see another time with faster memories.</i> </p> <p>The operating systems were various 64 bit Linux distributions.</p> <p>We did some further measurements comparing Harpertown and Nehalem processors. The Nehalem chip was a bit faster for a slightly lower clock but we did not see any of the twofold and greater differences advertised by Intel.</p> <p>We tried some <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0xce85438">RDF</a> operations on the two last systems:</p> <table align="center" cellspacing="10"> <tr> <th>operation</th> <th> Harpertown</th> <th>Nehalem</th> </tr> <tr> <th>Build text index for <a href="http://dbpedia.org/resource/DBpedia" id="link-id0xab826a8">DBpedia</a></th> <td>1080s</td> <td>770s</td> </tr> <tr> <th><a href="http://dbpedia.org/resource/Entity" id="link-id0xcbb9938">Entity</a> Rank iteration</th> <td>263s</td> <td>251s</td> </tr> </table> <p>Then we tried to see if the core multithreading of Nehalem could be seen anywhere. To this effect, we ran the Fibonacci function in <a href="http://dbpedia.org/resource/SQL" id="link-id0xcd62218">SQL</a> to serve as an example of an all in-cache integer operation. 16 concurrent operations took exactly twice as long as 8 concurrent ones, as expected.</p> <p>For something that used memory, we took a count of RDF quads on two different indices, getting the same count. The database was a cluster setup with one process per core, so a count involved one thread per core. The counts in series took 5.02s and in parallel they took 4.27s.</p> <p>Then we took a more memory intensive piece that read the RDF quads table in the order of one index and for each row checked that there is the equal row on another, differently-partitioned index. This is a cross-partition join. One of the indices is read sequentially and the other at random. The throughput can be reported as random-lookups-per-second. The data was English DBpedia, about 140M triples. One such query takes a couple of minutes with a 650% CPU utilization. Running multiple such queries should show effects of core multithreading since we expect frequent cache misses.</p> <ol> <li>On the host OS of the Nehalem system — <table align="center" cellspacing="10"> <tr> <th>n</th> <th>cpu%</th> <th>rows per second</th> </tr> <tr> <th>1 query</th> <td>503</td> <td>906,413</td> </tr> <tr> <th>2 queries</th> <td>1263</td> <td>1,578,585</td> </tr> <tr> <th>3 queries</th> <td>1204</td> <td>1,566,849</td> </tr> </table> </li> <li>In a VM under Xen, on the Nehalem system — <table align="center" cellspacing="10"> <tr> <th>n</th> <th>cpu%</th> <th>rows per second</th> </tr> <tr> <th>1 query</th> <td>652</td> <td>799,293</td> </tr> <tr> <th>2 queries</th> <td>1266</td> <td>1,486,710</td> </tr> <tr> <th>3 queries</th> <td>1222</td> <td>1,484,093</td> </tr> </table> </li> <li> On the host OS of the Harpertown system — <table align="center" cellspacing="10"> <tr> <th>n</th> <th>cpu%</th> <th>rows per second</th> </tr> <tr> <th>1 query</th> <td> 648 </td> <td> 1,041,448 </td> </tr> <tr> <th>2 queries</th> <td> 708 </td> <td> 1,124,866 </td> </tr> </table> </li> </ol> <p>The CPU percentages are as reported by the OS: user + system CPU divided by real time.</p> <p>So, Nehalem is in general somewhat faster, around 20-30%, than Harpertown. The effect of core multithreading can be noticed but is not huge, another 20% or so for situations with more threads than cores. The join where Harpertown did better could be attributed to its larger cache — 12 MB vs 8 MB.</p> <p>We see that Xen has a measurable but not prohibitive overhead; count a little under 10% for everything, also tasks with no I/O. The VM was set up to have all CPU for the test and the queries did not do disk I/O.</p> <p>The executables were compiled with <code>gcc</code> with default settings. Specifying <code>-march=nocona</code> (Core 2 target) dropped the cross-partition join time mentioned above from 128s to 122s on Harpertown. We did not try this on Nehalem but presume the effect would be the same, since the out-of-order unit is not much different. We did not do anything about process-to-memory affinity on Nehalem, which is a non-uniform architecture. We would expect this to increase performance since we have many equal size processes with even load.</p> <p>The mainstay of the Nehalem value proposition is a better memory subsystem. Since the unit we got was at 800 MHz memory, we did not see any great improvement. So if you buy Nehalem, you should make sure it is with 1333 MHz memory, else the best case will not be over 50% over a 667 MHz Core 2-based Xeon.</p> <p>Nehalem remains a better deal for us because of more memory per board. One Nehalem box with 72 GB costs less than two Harpertown boxes with 32 GB and offers almost the same performance. Having a lot of memory in a small space is key. With faster memory, it might even outperform two Harpertown boxes, but this remains to be seen.</p> <p>If space were not a constraint, we could make a cluster of 12 small workstations for the price of our largest system and get still more memory and more processor power per unit of memory. The Nehalem box was almost 4x faster than the AMD box but then it has 9x the memory, so the CPU to memory ratio might be better with the smaller boxes.</p>
Orri Erling
oerling@openlinksw.com
2009-05-28T11:15:39-04:00
Social Web Camp (#5 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1554
2009-04-30T16:14:02Z
<p>(Last of five posts related to the <a href="http://www2009.org/" id="link-id0xd28c860">WWW 2009</a> conference, held the week of April 20, 2009.) </p> <p>The social networks camp was interesting, with a special meeting around Twitter. Half jokingly, we (that is, the OpenLink folks attending) concluded that societies would never be completely classless, although mobility between, as well as criteria for membership in, given classes would vary with time and circumstance. Now, there would be a new class division between people for whom micro-blogging is obligatory and those for whom it is an option.</p> <p>By my experience, a great deal is possible in a short time, but this possibility depends on focus and concentration. These are increasingly rare. I am a great believer in core competence and focus. This is not only for geeks — one can have a lot of breadth-of-scope but this too depends on not getting sidetracked by constant <a href="http://dbpedia.org/resource/Information" id="link-id0x10019a70">information</a> overload.</p> <p>Insofar as personal success depends on constant reaction to online social media, this comes at a cost in time and focus and this cost will have to be managed somehow, for example by automation or outsourcing. But if the social media is only automated fronts twitting and re-twitting among themselves, a bit like electronic trading systems do with securities, with or without human operators, the value of the medium decreases.</p> <p>There are contradictory requirements. On one hand, what is said in electronic media is essentially permanent, so one had best only say things that are well considered. On the other hand, one must say these things without adequate time for reflection or analysis. To cope with this, one must have a well-rehearsed position that is compacted so that it fits in a short format and is easy to remember and unambiguous to express. A culture of pre-cooked fast-food advertising cuts down on depth. Real-world things are complex and multifaceted. Besides, prevalent patterns of communication train the brain for a certain mode of functioning. If we train for rapid-fire 140-character messaging, we optimize one side but probably at the expense of another. In the meantime, the world continues developing increased complexity by all kinds of emergent effects. Connectivity is good but don't get lost in it.</p> <p>There is <a href="https://www.cia.gov/library/center-for-the-study-of-intelligence/csi-publications/books-and-monographs/psychology-of-intelligence-analysis/index.html" id="link-id170cb010">a CIA memorandum about how analysts misinterpret data and see what they want to see</a>. This is a relevant resource for understanding some psychology of perception and memory. With the information overload, largely driven by user generated content, interpreting fragmented and variously-biased real-time information is not only for the analyst but for everyone who needs to intelligently function in cyber-social space.</p> <p>I participated in discussions on security and privacy and on mobile social networks and context.</p> <p>For privacy, the main thing turned out to be whether people should be protected from themselves. Should information expire? Will it get buried by itself under huge volumes of new content? Well, for purposes of visibility, it will certainly get buried and will require constant management to stay visible. But for purposes of future finding of dirt, it will stay findable for those who are looking.</p> <p>There is also the corollary of setting security for resources, like documents, versus setting security for statements, i.e., structured data like social networks. As I have blogged before, policies <a id="link-id14aaff90">à la</a> <a href="http://dbpedia.org/resource/SQL" id="link-id0x10b058d0">SQL</a> do not work well when schema is fluid and end-users can't be expected to formulate or understand these. Remember <a href="http://dbpedia.org/resource/Ted_Nelson" id="link-id0x145b3070">Ted Nelson</a>? A user interface should be such that a beginner understands it in 10 seconds in an emergency. The user interaction question is how to present things so that the user understands who will have access to what content. Also, users should themselves be able to check what potentially sensitive information can be found out about them. A service along the lines of Garlic's Data Patrol should be a part of the social web infrastructure of the future.</p> <p>People at MIT have developed AIR (Accountability In <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x10dec8f8">RDF</a>) for expressing policies about what can be done with data and for explaining why access is denied if it is denied. However, if we at all look at the history of secrets, it is rather seldom that one hears that access to information about X is restricted to compartment so-and-so; it is much more common to hear that there is no X. I would say that a policy system that just leaves out information that is not supposed to be available will please the users more. This is not only so for organizations; it is fully plausible that an individual might not wish to expose even the existence of some selected inner circle of friends, their parties together, or whatever.</p> <p>In conclusion, there is no self-evident solution for careless use of social media. A site that requires people to confirm multiple times that they know what they are doing when publishing a photo will not get much use. We will see.</p> <p>For mobility, there was some talk about the context of usage. Again, this is difficult. For different contexts, one would for example disclose one's location at the granularity of the city; for some other purposes, one would say which conference room one is in.</p> <p>Embarrassing social situations may arise if mobile devices are too clever: If information about travel is pushed into the social network, one would feel like having to explain why one does not call on such-and-such a person and so on. Too much initiative in the mobile phone seems like a recipe for problems.</p> <p>There is a thin line between convenience and having IT infrastructure rule one's life. The complexities and subtleties of social situations ought not to be reduced to the level of if-then rules. People and their interactions are more complex than they themselves often realize. A system is not its own metasystem, as Gödel put it. Similarly, human self-<a href="http://dbpedia.org/resource/Knowledge" id="link-id0xd7b1808">knowledge</a>, let alone knowledge about another, is by this very principle only approximate. Not to forget what psychology tells us about state-dependent recall and of how circumstance can evoke patterns of behavior before one even notices. The history of expert systems did show that people do not do very well at putting their skills in the form of if-then rules. Thus automating sociality past a certain point seems a problematic proposition.</p>
Orri Erling
oerling@openlinksw.com
2009-04-30T12:51:49-04:00
Web Science and Keynotes at WWW 2009 (#4 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1551
2009-04-30T16:00:22Z
<p>(Fourth of five posts related to the <a href="http://www2009.org/" id="link-id0x1232b550">WWW 2009</a> conference, held the week of April 20, 2009.) </p> <p>There was quite a bit of talk about what web science could or ought to be. I will here comment a bit on the <a href="http://www2009.org/panels.html" id="link-id1514ec30">panels</a> and <a href="http://www2009.org/keynote_abs.html" id="link-id11a5d620">keynotes</a>, in no special order. </p> <p>In the web science panel, Tim Berners-Lee said that the deliverable of the web science initiative could be a way of making sense of all the world's <a href="http://dbpedia.org/resource/Data" id="link-id0xe01cd68">data</a> once the web had transformed into a database capable of answering arbitrary queries.</p> <p>Michael Brodie of Verizon said that one deliverable would be a well considered understanding of the issue of counter-terrorism and civil liberties: Everything, including terrorism, operates on the platform of the web. How do we understand an issue that is not one of privacy, intelligence, jurisprudence, or sociology, but of all these and more?</p> <p>I would add to this that it is not only a matter of governments keeping and analyzing vast amounts of private data, but of basically anybody who wants to do this being able to do so, even if at a smaller scale. In a way, the data web brings formerly government-only capabilities to the public, and is thus a democratization of intelligence and analytics. The citizen blogger increased the accountability of the press; the citizen analyst may have a similar effect. This is trickier though. We remember Jefferson's words about vigilance and the price of freedom. But vigilance is harder today, not because <a href="http://dbpedia.org/resource/Information" id="link-id0x130558b8">information</a> is not there but because there is so much of it, with diverse spins put on it.</p> <p>Tim B-L said at another panel that it seemed as if the new capabilities, especially the web as a database, were coming just in time to help us cope with the problems confronting the planet. With this, plus having everybody online, we would have more information, more creativity, more of everything at our disposal.</p> <p>I'd have to say that the web is dual use: The bulk of traffic may contribute to distraction more than to awareness, but then the same infrastructure and the social behaviors it supports may also create unprecedented value and in the best of cases also transparency. I have to think of "For whosoever hath, to him shall be given." [Matthew 13:12] This can mean many things; here I am talking about whoever hath a drive for <a href="http://dbpedia.org/resource/Knowledge" id="link-id0x16032470">knowledge</a>.</p> <p>The web is both equalizing and polarizing: The equality is in the access; the polarity in the use made thereof. For a huge amount of noise there will be some crystallization of value that could not have arisen otherwise. Developments have unexpected effects. I would not have anticipated that gaming should advance supercomputing, for example.</p> <p>Wendy Hall gave a dinner speech about communities and conferences; how the original hypertext conferences, with lots of representation of the humanities, became the techie WWW conference series; and how now we have the pendulum swinging back to more diversity with the web science conferences. So it is with life. Aside from the facts that there are trends and pendulum effects, and that paths that cross usually cross again, it is very hard to say exactly how these things play out.</p> <p>At the "20 years of web" panel, there was a round of questions on how different people had been surprised by the web. Surprises ranged from the web's actual scalability to its rapid adoption and the culture of "if I do my part, others will do theirs." On the minus side, the emergence of spam and phishing were mentioned as unexpected developments.</p> <p>Questions of simplicity and complexity got a lot of attention, along with network effects. When things hit the right simplicity at the right place (e.g., HTML and <a href="http://dbpedia.org/resource/Hypertext_Transfer_Protocol" id="link-id0x1069cc18">HTTP</a>, which hypertext-wise were nothing special), there is a tipping point.</p> <p>No barrier of entry, not too much modeling, was repeated quite a bit, also in relation to <a href="http://dbpedia.org/resource/Semantic_Web" id="link-id0x15d2c200">semantic web</a> and ontology design. There is a magic of emergent effects when the pieces are simple enough: Organic chemistry out of a couple of dozen elements; all the world's information online with a few tags of markup and a couple of protocol verbs. But then this is where the real complexity starts — one half of it in the transport, the other in the applications, yet a narrow interface between the two.</p> <p>This then begs the question of content- and application-aware networks. The preponderance of opinion was for separation of powers — keep carriers and content apart.</p> <p>Michael Brodie commented in the questions to the first panel that simplicity was greatly overrated, that the world was in fact very complex. It seems to me that that any field of human endeavor develops enough complexity to fully occupy the cleverest minds who undertake said activity. The life-cycle between simplicity and complexity seems to be a universal feature. It is a bit like the Zen idea that "for the beginner, rivers are rivers and mountains are mountains, for the student these are imponderable mysteries of bewildering complexity and transcendent dimension but for the master these are again rivers and mountains." One way of seeing this is that the master, in spite of the actual complexity and interrelatedness of all things, sees where these complexities are significant and where not and knows to communicate concerning these as fits the situation.</p> <p>There is no fixed formula for saying where complexities and simplicities fit, relevance of detail is forever contextual. For technological systems, we find that there emerge relatively simple interfaces on either side of which there is huge complexity: The x86 instruction set, TCP/IP, <a href="http://dbpedia.org/resource/SQL" id="link-id0x10363000">SQL</a>, to name a few. These are lucky breaks, it is very hard to say beforehand where these will emerge. Object oriented people would like to see such everywhere, which just leads to problems of modeling.</p> <p>There was a keynote from Telefonica about infrastructure. We heard that the power and cooling cost more than the equipment, that data centers ought to be scaled down from the football stadium and 20 megawatt scale, that systems must be designed for partitioning, to name a few topics. This is all well accepted. The new question is whether storage should go into the network infrastructure. We have blogged that the network will be the database, and it is no surprise that a telco should have the same idea, just with slightly different emphasis and wording. For Telefonica, this is about efficiency of bulk delivery, for us this is more about virtualized query-able dataspaces. Both will be distributed but issues of separation of powers may keep the two roles of network with storage separate.</p> <p>In conclusion, the network being the database was much more visible and accepted this year than last. The <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x100f4cf0">linked data</a> <a href="http://dbpedia.org/resource/Giant_Global_Graph" id="link-id0x15a55db8">web</a> was in Tim B-L's keynote as it was in the opening speech by the Prince of Asturias.</p>
Orri Erling
oerling@openlinksw.com
2009-04-30T12:11:44-04:00
Short Recap of Virtuoso Basics (#3 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1550
2009-04-30T15:49:53Z
<p>(Third of five posts related to the <a href="http://www2009.org/" id="link-id0x1081fe40">WWW 2009</a> conference, held the week of April 20, 2009.) </p> <p>There are some points that came up in conversation at WWW 2009 that I will reiterate here. We find there is still some lack of clarity in the product image, so I will here condense it.</p> <p> <a href="http://virtuoso.openlinksw.com" id="link-id0xd0e85f0">Virtuoso</a> is a DBMS. We pitch it primarily to the <a href="http://dbpedia.org/resource/Data" id="link-id0x14a294d8">data</a> web space because this is where we see the emerging frontier. Virtuoso does both <a href="http://dbpedia.org/resource/SQL" id="link-id0x108042f8">SQL</a> and <a href="http://dbpedia.org/resource/SPARQL" id="link-id0x10889878">SPARQL</a> and can do both at large scale and high performance. The popular perception of <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id0x107d3b40">RDF</a> and Relational models as mutually exclusive and antagonistic poles is based on the poor scalability of early RDF implementations. What we do is to have all the RDF specifics, like IRIs and typed literals as native SQL types, and to have a cost based optimizer that knows about this all.</p> <p>If you want application-specific data structures as opposed to a schema-agnostic quad-store model (triple + graph-name), then Virtuoso can give you this too. <a href="http://docs.openlinksw.com/virtuoso/rdfsparqlintegrationmiddleware.html#rdfviews" id="link-id14ddc7c8">Rendering application specific data structures as RDF</a> applies equally to relational data in non-Virtuoso databases because Virtuoso SQL can <a href="http://docs.openlinksw.com/virtuoso/qsvdbsrv.html" id="link-id14aaea70">federate tables from heterogenous DBMS</a>.</p> <p>On top of this, there is a <a href="http://docs.openlinksw.com/virtuoso/qswebserver.html" id="link-id16fcde60">web server built in</a>, so that no extra server is needed for web services, web pages, and the like.</p> <p>Installation is simple, just one exe and one config file. There is a huge amount of code in <a href="http://docs.openlinksw.com/virtuoso/installation.html" id="link-id16767b40">installers</a> — application code and test suites and such — but none of this is needed when you deploy. Scale goes from a 25MB memory footprint on the desktop to hundreds of gigabytes of RAM and endless terabytes of disk on shared-nothing clusters.</p> <p>Clusters (coming in Release 6) and SQL federation are <a href="http://download.openlinksw.com/download/product_matrix.vsp?p=l_os&c=39&df=16" id="link-id16722550">commercial only</a>; the rest can be had <a href="http://sourceforge.net/project/showfiles.php?group_id=161622" id="link-id131080a8">under GPL</a>.</p> <p>To condense further:</p> <ul> <li>Scalable Delivery of <a href="http://dbpedia.org/resource/Linked_Data" id="link-id0x12211da8">Linked Data</a> </li> <li>SPARQL and SQL <ul> <li>Arbitrary RDF Data + Relational</li> <li>Also From 3rd Party <a href="http://dbpedia.org/resource/Relational_database_management_system" id="link-id0x168db0e0">RDBMS</a> </li> </ul> </li> <li>Easy Deployment </li> <li>Standard Interfaces <ul> <li> <a href="http://dbpedia.org/resource/Open_Database_Connectivity" id="link-id0x10473bf0">ODBC</a>, <a href="http://dbpedia.org/resource/Java_Database_Connectivity" id="link-id0x12187f58">JDBC</a>, OLE DB, <a href="http://dbpedia.org/resource/ADO.NET" id="link-id0x10354e48">ADO</a>.<a href="http://dbpedia.org/resource/.NET_Framework" id="link-id0x16eeadd0">NET</a>, XMLA</li> <li> <a href="http://jena.sourceforge.net/" id="link-id0x12e3fe08">Jena</a>, <a href="http://sourceforge.net/projects/sesame/" id="link-id0x15e62470">Sesame</a>, etc.</li> <li>All Web Protocols </li> </ul> </li> </ul>
Orri Erling
oerling@openlinksw.com
2009-04-30T12:11:43.000001-04:00
Search at WWW 2009 (#2 of 5)
http://www.openlinksw.com/weblog/oerling/?id=1548
2009-04-30T15:18:24Z
<p>(Second of five posts related to the <a href="http://www2009.org/" id="link-id124024c8">WWW 2009</a> conference, held the week of April 20, 2009.) </p> <p>There was a <a href="http://data.semanticweb.org/conference/www/2009/paper/109/html" id="link-id1207a3b0">workshop on semantic search</a> plus <a href="http://data.semanticweb.org/conference/www/2009/html" id="link-id1704ff48">a number of papers</a> and of course <a href="http://www2009.org/keynote.html" id="link-id11ec08d8">keynotes from Google and Yahoo</a>.</p> <p>A general topic was the use of and access to query logs. Are these the monopoly of GYM (Google, Yahoo, Microsoft) or should they be made more generally available? This is a privacy question. Use of query logs and click through of search results for improved ranking was mentioned many times throughout the conference.</p> <p>The <a href="http://data.semanticweb.org/conference/www/2009/paper/109/html" id="link-id120b7d38">semantic search workshop</a> was largely about benchmarks for keyword search in <a href="http://dbpedia.org/resource/Information" id="link-id171e2950">information</a> retrieval. For <a href="http://dbpedia.org/resource/Linked_Data" id="link-id11e1a9b0">linked data</a>, which is a database proposition, these benchmarks are not really applicable. For document search aided by semantics derived by NLP, these are of course applicable. But there is a divide in approach.</p> <p> <a href="http://g1o.net/foaf.rdf#me" id="link-id11d1c7b0">Giovanni Tummarello</a> <a href="http://data.semanticweb.org/conference/www/2009/paper/59/html" id="link-id169add28">presented</a> <a href="http://sig.ma/" id="link-id11af0128">Sig.ma</a>, a service using <a href="http://sindice.com/" id="link-id11a69fa0">Sindice</a>'s <a href="http://dbpedia.org/resource/Resource_Description_Framework" id="link-id11f3a088">RDF</a> index for collecting all RDF statements about entities matching some set of keywords. One could then choose which sources and which entities were the right ones. One could further store such a query and embed it on a page. The point was that the filtering done manually could be persisted and republished, so as to create dynamic content aggregated from selected live sources. Further speculating, one could use such user feedback for adjusting ranking, even though Sig.ma did not. We may adopt the idea of manually excluding sources into our browser too. Fresnel lenses are another thing to look at.</p> <p>There was <a href="http://www2009.eprints.org/242/" id="link-id11dc7c68">a paper by Josep M. Pujol and Pablo Rodriguez, of Telefonica Research</a>, about returning search to the people by means of Porqpine, a peer-to-peer search implementation based on sharing search results from search engines among peers and indexing them locally as they were retrieved. For users with similar interests, this can give a community based ranking model but has issues of privacy. Another point was that with local processing and personal scale <a href="http://dbpedia.org/resource/Data" id="link-id171a8948">data</a> volumes various kinds of brute force processing were feasible that would cost a lot for the web scale. Much can be done web scale but it must be done cleverly, not with a shell script and not so ad hoc.</p> <p>As a counterpoint to this, there was <a href="http://www2009.eprints.org/220/" id="link-id120bf9e0">a talk about Hadoop and Hive</a>, a map-reduce-based <a href="http://dbpedia.org/resource/SQL" id="link-idee5d700">SQL</a>-like framework. One could do an SQL <code>GROUP BY</code> on text files with record parsing at run time, all spread over a Hadoop cluster. The issue is, if you have a petabyte of data, you may wish to run more than one ad hoc query on it. This means that joining between partitions and complex processing becomes important. This cannot be done without indices and complex query optimization, and needs a DBMS. Stonebraker and company are fully justified in their <a href="http://database.cs.brown.edu/sigmod09/" id="link-id11be1088">critique of map reduce</a>. It looks like each generation must get dazzled by the oversimplified and then retrace the same discoveries of complexity as the previous one.</p> <p>Some of our future plans were confirmed by what we saw, for example as concerns:</p> <ul> <li>Interactively selecting sources for search, showing the graphs, then interactively refining</li> <li>More social networks, more network analysis, and more work on social recommendation</li> <li>Real time indexing of new pings, filling the store by forwarding queries to search engines, and harvesting micro-formats from results</li> <li>Using <a href="http://dbpedia.org/resource/Entity" id="link-id16440770">entity</a> extraction</li> </ul> <p>These are all items in the pipeline, easy to do on top of the existing platform. For the machine learning and NLP parts, we will partner with others, details will be worked out while we work on the items we implement by ourselves.</p>
Orri Erling
oerling@openlinksw.com
2009-04-30T12:51:48-04:00