Present and Future Scalability

Measurable Targets for Scalable Reasoning

This analysis is based on published results of several of the most scalable engines: ORACLE, AllegroGraph, DAML DB, Openlink Virtuoso, and BigOWLIM. The targets are defined with respect to two of the currently most popular performance measuring sticks: the LUBM repository benchmark (and its UOBM modification) and the OWL version of UNIPROT - the richest database of protein-related information.

An interesting aspect of this paper is its description of some of the difficulties in comparing data loading and querying across triple stores. For example, at load time this can include forward chaining (inferencing) and what the complexity of the data model is (whether named graphs and other metadata is used). Query evaluation can vary due to backward chaining, result set size and the types of queries.

While some triple stores can now load up to 40,000 triples a second (BigOWLIM) the average seems to be around 10,000 triples a second for a billion triples. The target in the next few years is 20-100 billion triples at 100,000 triples second. The rate of 100,000 triples per second is the upper range but I would imagine that to load the data in a reasonable time this is what people have to aim towards. Otherwise, 100 billion triples is going to take 100 days.

Lucene for the Semantic Web

Hbase

Google's [WWW] Bigtable, a distributed storage system for structured data, is a very effective mechanism for storing very large amounts of data in a distributed environment.

Just as Bigtable leverages the distributed data storage provided by the [WWW] Google File System, Hbase will provide Bigtable-like capabilities on top of Hadoop.

Data is organized into tables, rows and columns, but a query language like SQL is not supported. Instead, an Iterator-like interface is available for scanning through a row range (and of course there is an ability to retrieve a column value for a specific key).

Any particular column may have multiple values for the same row key. A secondary key can be provided to select a particular value or an Iterator can be set up to scan through the key-value pairs for that column given a specific row key.

From the Hbase/HbaseArchitecture page:

HBase uses a data model very similar to that of Bigtable. Users store data rows in labelled tables. A data row has a sortable key and an arbitrary number of columns. The table is stored sparsely, so that rows in the same table can have crazily-varying columns, if the user likes.

A column name has the form ":" where and can be any string you like. A single table enforces its set of s (called "column groups"). You can only adjust this set of groups by performing administrative operations on the table. However, you can use new strings at any write without preannouncing it. HBase stores column groups physically close on disk. So the items in a given column group should have roughly the same write/read behavior.

Writes are row-locked only. You cannot lock multiple rows at once. All row-writes are atomic by default.

All updates to the database have an associated timestamp. The HBase will store a configurable number of versions of a given cell. Clients can get data by asking for the "most recent value as of a certain time". Or, clients can fetch all available versions at once.

The example tables given are very similar to untyped relations. This has only just become part of the nightly build.

Via, Data Parallel.

Why have millions of triples? When you can have billions.

Big news, literally, with BigOWLIM. "BigOWLIM is a high-performance semantic repository, implemented in Java and packaged as a Storage and Inference Layer (SAIL) for the Sesame RDF database. BigOWLIM uses the TRREE engine to perform RDFS, OWL DLP, and OWL Horst reasoning, based on forward-chaining of entailment rules. The most expressive language supported is a combination of limited OWL Lite and unconstrained RDFS. BigOWLIM can manage billions of explicit statements on server hardware. A principle limitation of BigOWLIM is the relatively slow delete operation. The upload, reasoning, and the query evaluation proceed fast even against huge ontologies and datasets."

"BigOWLIM successfully passed the threshold of 1 billion (10^9) statements of OWL/RDF – it loaded an 8000-university dataset of the LUBM benchmark and answered the evaluation queries correctly. Evaluation setup and statistics:

BigOWLIM successfully passed the threshold of 1 billion (10^9) statements of OWL/RDF –
it loaded an 8000-university dataset of the LUBM benchmark and answered the evaluation queries correctly. Evaluation setup and statistics:

• Hardware: 2 x Opteron 270, 16GB of RAM, RAID 10; assembly cost < 5000 EURO
  
• OS: Suse 10.0 Linux, x86_64, Kernel 2.6.13-15-smp; 64-bit JDK 1.5 -Xmx12000m
  
• Loading, inference, and storage took 69 hours and 51 min
  
• LUBM(8000,0) contains 1.06 billions of explicit statements
  
  
  
  • The "inferred closure" contains about 786M statements
    
  • BigOWLIM had to manage over 1.85 billions of statements in total
    
  • These figures indicate that, if used as a plain-RDF repository, BigOWLIM can easily handle around 2 billion statements on the same hardware setup
    
  
  
• 92GB RDF/XML files; 95 GB binary storage files
  
• Average Speed: 4 538 statements/sec."

While not available for download, a scaled down version, OWLIM is.

Hot on the heals of recent postings, Scalability of the Semantic Web and performance, triplestores, and going round in circles...

RETE Rebuked

A recent blog I started reading after criticizing SPARQL. This time its criticizing an entry Paul made about the scalability of the RETE algorithm: "I am a bit confused by the statement that RETE does not scale. This is contrary to a mountain of papers by researchers and developers around the world. From the paragraph, a couple of things come to mind. "(loading indexes) does not need to be done often" tells me the author doesn't understand the purpose and goal of RETE. RETE was designed to solve machine learning problems where data changes rapidly and reasoning is a continuous process. What the author wants is something closer to BitMap indexes used in OLAP products."

A lot of the points raised, like RETE being for changing data, are mentioned in a previous post under Meeting. Drools was chosen as a starting to point to see what kind of system needed to be developed in Kowari.

Also mentioned, bitmap indexing: "Given Tucana is indexing everything, they might as well adapt Bitmap indexing and get better than linear performance. The problem described by the blog is a well understood problem in the OLAP world."

An previous entry, "Relational theory, RETE and Derby" points to some interesting articles about bitmap indexes (available in Oracle 9) and high scalability requirements: "In a large financial institution like a mutual fund company, they may have 1-20 million customers. If each customer has an average of 20-30 positions (aka specific holding of an equity) that means the potential dataset for firm wide compliance rule could involve 20million+ rows. Doing this within 2-5 seconds is rather hard, so it requires using lots of different techniques. In the extreme cases, a company might have 20 million accounts, which means the potential dataset is 600 million rows."

From the OTN article: "B-tree indexes are usually used when columns are unique or near unique; bitmap indexes should be used, or at least considered, in all other cases. While you would not generally use a b-tree index when retrieving 40 percent of the rows of a table, a bitmap index is often still faster than doing a full table scan. This is seemingly in violation of the 80/20 rule, which is to generally use an index when retrieving 20 percent or less of the rows and do a full table scan when retrieving more. Bitmap indexes are smaller and work differently from the 80/20 rule. You can effectively use bitmap indexes even when retrieving large percentages (20 to 80 percent) of a table. Bitmaps can also be used to retrieve conditions based on nulls (since nulls are also indexed) and for "not equal" conditions."

It would appear that this would be suitable for predicate indexation but not generally as both subjects and objects are near unique.

Comparing YARS and Kowari

Cold, Mastering OWL, Scalability, Indexing "There are two differences in their implementation to our own. The first is that they used B-trees rather than the AVL trees that Kowari uses. That is not a significant difference, and I blogged about this several times before. The main advantage of the AVL tree is that they are cheaper to write to the structure than B-trees are, though a little slower to read. They also pointed out that they wanted to use an existing library for the index, and while B-tree libraries are common, we never found a completely working AVL tree library (deletions were always buggy).

The second difference is a set of special statements which count the number of triples in parts of each of the indexes. This is certainly novel, but not an approach I would use. I believe that counting is still very efficient in Kowari (O(log(n)), and the space overhead they incurred would seem prohibitive. More importantly, writing is always the slowest operation, and their system would incur a large writing penalty for using this scheme."

Crisis

In the same week Tucana goes under we get probably the busiest week on the Kowari mailing list and 45 downloads for Pre-release 2. Considering three quarters of these is the 50MB version, there's either a lot of good bandwidth out there or great patience.

Before the holidays there was great progress being made. We have been attempting to make the "10,000 triple/second challenge" and had succeeded (at least the first 1 million triples, it degraded to a few thousand a second after 200 million). This is on the same 1.6 Mhz Opteron system that we use for all our tests.

Andrae was working on a large refactoring of the transaction operations so that any JRDF, Jena, or iTQL (or anything new) could be put within a transaction or use an existing one. They were already in a transaction but they couldn't tell whether they already had the write phase for example. From what I can remember Simon was working on the problems associated with using file and HTTP protocols in the FROM (external resolvers). David M was working on speeding up deleting triples as well as loading speed. Paul had been working on SOFA and OWL. Robert had started looking at JDO, EJB and mapping relational databases to RDF.

Our commercial focus had been on speed and scalablilty. With Tucana gone some of this focus is probably going to change. It takes a lot of time, effort and resources to keep everything changing and to continue to perform at a commercial level. Between 1.0 and 1.1 there practically isn't a portion of code that wasn't modified - more often than not it was completely changed. This kind of development, on multiple fronts, is something that probably can't occur in the future.

So the future is probably smaller, simpler, with an eye on standards compliance. I hope some things like multiple writes, phase holding, pluggable datatypes, inferencing Hotspot, SPARQL support etc. will be developed but I doubt many of these things will see the light of day now. I'm not discounting them entirely, but there are many things that had to occur in parallel that need a team of developers. A lot of the new features depended on the multiple writers feature. Multiple writers is not an easy feature to describe but suffice to say it's more like Lucene than a normal relational database.

So I think that means improving RDF, RDFS and OWL support. We made some good improvements in Pre-Release 2 with better datatype support. David M added the functionality to allow literal and URI prefix matching - someone just has to add it into the query layer. Combining this with matching nodes based on type (literal, URI or bnode) and trans/walk queries and they're a very powerful combination of features. In the background there's also been a focus on languages (I know we were talking about 3066bis support). Paul and I were looking at inference models (seems to have similarities with pseudo models and datalog vs tableau). Paul's Masters will probably push some of this into reality.

So all in all there does seem to be some good opportunities in the future. I know that Tucana had customers who were paying lots of money for TKS and I know that Kowari did help in the risk assessment. So my intentions, at least in the short term, is to see that good support occurs, bugs get fixed and the like. Although there isn't anyone left to do TKS releases.

I don't really understand why this happened (or what's going on) but to quote Marge Simpson: "One person can make a difference. But most of the time they probably shouldn't."

Just Ask for Help

Came across Yet Another RDF Store: Perfect Index Structures for Storing Semantic Web Data With Contexts "We tried to install Kowari, but failed to get a running version. In one of our installations, inserting a 1 MB N-triples file via the Jena interface resulted in 30 minutes processing time before the process threw an exception because of a full disk (there were 200MB disk space available before starting the Kowari server). On another installation, we got a core dump of the JVM when running Kowari. Therefore we concentrated in our efforts on Sesame 1.1RC2 and Redland 0.9.18."

This is the first record of anyone having a problem with Kowari in this respect and without any idea of what version of Kowari or Java or the OS or anything else I went and downloaded their example code. Using Kowari 1.0.5 (they mentioned Sesame 1.1RC2 which was released after 1.0.5) with the given code you get an exception as NTriples is not supported as a parameter. NTriples is a subset of N3. So this code doesn't work. However, if the code is modified so that the last lines become:

  model.read(new FileReader(file), file.toURI().toString(), "N3");
  model.close();
  database.close();

And run the code you get:

...
 INFO [main] (AbstractDatabaseSession.java:699) - Loading 
file:/.../University1_0.nt into rmi://.../server1#camera
 INFO [main] (AbstractDatabaseSession.java:770) - Loaded 7304 
statements
...

If people have any problems running Kowari, before they write it up as a paper maybe they should ask someone how to get it running first. Although, this isn't the first time.