We actually did the experiment I mentioned a couple of posts back, about storing RDF triples column-wise.
The test loads 4.8 million triples of LUBM data and reads the whole set on one index and then checks if it finds the same row on another index.
Reading GSPO and checking OGPS takes 27 seconds.
Doing the same with column wise bitmap indices on S, G, P and O takes 86 seconds.
The latter checks the existence of the row by AND'ing 4 bitmap indices and the former checks its existence by a single lookup in a multi-part index whose last part is a bitmap.
The result is approximately what one would expect.
The bitmap AND could be optimized a bit, dropping the time to maybe 70 seconds.
Now speaking of compression, it is true that column storage will work better.
For example the G and P columns will compress to pretty much nothing.
On a row layout they compress too but not to nothing since even if a value is not unique you have to store the place where the value is if you want to read rows in constant time per row.
What is nice with the 4 bitmaps is that no combination of search conditions is penalized.
But the trick of using bitmaps for self-join is lost:
You can't evaluate {?s a Person . ?s name "Mary"} by and'ing the S bitmaps for persons and for subjects named "Mary".
The 4 bitmap indices are remarkably compact, though. 8840 pages all together.
We could probably get the G, S, P, O columns in 3000 pages or so, using very little
compression.
The OGPS index is
5169 pages and the GSPO index is 21243 pages.
None of the figures have any compression, except what a bitmap naturally produces.
Now we have figured out a modified row layout which will about double working set with the same memory and keep things in rows.
We will try that.
The GSPO index will be about
10000 pages and OGPS will be about 4500.
We do not expect much impact on search or insert times.
We looked at using gzip for database pages.
They go to between 1/4 to 1/3 page.
But this does not improve working set and having variable length pages generates all kinds of special cases you don’tt want.
So we will improve working set first and deal with somewhat compressed data in the execution engine.
After that, maybe gzip will cut the size to 1/2 or so but
that will be good for disk only.
And it does not so much matter how much you transfer but how many seeks you do.
Still, column-wise storage will likely win for size.
So if the working set is much larger than memory this may have an edge.
To keep all bases covered we will eventually add this as an option.
Semantic Web |Database |Databases |Virtuoso |SPARQL|RDF