[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
Re: [rdf4j-dev] Contributing a write-once/read-many triple store to RDF4j
|
- From: jerven Bolleman <jerven.bolleman@sib.swiss>
- Date: Sun, 6 Nov 2022 13:58:40 +0100
- Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=sib.swiss; dmarc=pass action=none header.from=sib.swiss; dkim=pass header.d=sib.swiss; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=f3YKQROVVj8OmPsVJtCg9RanTmIAlwQ5ch8liv647hU=; b=jWJ2RYA8any40ysy8Iih/rPttjTRelceP6JF0fObL045kfrej31/ATfuxD/1zo5A0HDZX6t0cTMkHTXQP/JqFMi7tCkEyZmI+BRyZuRZVRleaJCey/VKGlPh2RzkDHVabBhjLvMwu2qOmDLFmzyYCJB/LfHrvgaOdBNSSwpgiCh4mGKRkE/LbmFI4lJ8gzTAZx9Kmzk78niPjdt8GZpD4w5I6nqliutMVD575jYmGQKKsWLsovlDJpczZVYw21l2WlhynHYX9yMgClhib2UXn4PkVhoscpRQ9D2UPH3NnWc9mETMkam6+POtG+aJVJgHmsRocBi1S7gElcvgXkvvJA==
- Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=HAHllVinE8sU6ZEVPsOiGK1njwfZD84GPd/sI0C5JtO0KucG6wS7DpWZ7CUSJ0xfs3Vp9DLfGsStBsJP5Zl73FkDrAjXH5iGfiy1JHpoz/vZwrummaCwvjOuFBgCtxcOOhNitv9RxyBwZm6JoLzlef9AgUTzDUSfmuLnEizRDayyylQneYHZRtV14oAEFYkUA+NJQFrsY2scLS/x3PHK3SZZBIWmVxmYHV/STZclgnobZQMdwZroPwHccLO69t9LppNyIKhaQgx5N53Gx43zr+awojxOVBguBLqLK94XePYHc+W8eo+w3mdgp17lOtB8wPjvm1GThj/19QwAjdSGWw==
- Delivered-to: rdf4j-dev@xxxxxxxxxxx
- List-archive: <https://www.eclipse.org/mailman/private/rdf4j-dev/>
- List-help: <mailto:rdf4j-dev-request@eclipse.org?subject=help>
- List-subscribe: <https://www.eclipse.org/mailman/listinfo/rdf4j-dev>, <mailto:rdf4j-dev-request@eclipse.org?subject=subscribe>
- List-unsubscribe: <https://www.eclipse.org/mailman/options/rdf4j-dev>, <mailto:rdf4j-dev-request@eclipse.org?subject=unsubscribe>
- User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.4.0
Hi All,
Some more experimental details. So for the UniProtKB 2022_04 dataset
there are 17,435,087,503 quads where the predicate is rdf:type.
On disk this consumes 6,411,506,834 bytes. Leading to just under 3 bits
per quad of this kind disk usage.
So it shows inverting an index and bitset compression can really pay off
'SELECT (COUNT(*?) AS ?c) WHERE {?s a ?o }' took 92 minutes to run :(
Time is mostly spend on CPU intensive tasks.
25% of time goes to maintaining iterator in subject order (which is not
needed here but I coded it that way).
16% Is in testing if the ArrayBindingSet isEmpty or not :(
16% Is actual addSolution in the GroupIterator
14% Is spend in HashMap.get in the hot loop of buildEntries
9% Is iterating over the low level datastructures.
1 query pegs a single core to 100%.
So we can speed this up some more even though this is best case query
right now for the backing store.
Hope it is interesting :)
Regards,
Jerven
PS. The blocker off having a 100 billion+ triple store running on a my 5
year old laptop is:
https://github.com/RoaringBitmap/RoaringBitmap/issues/590
On 31/10/2022 15:09, jerven Bolleman wrote:
Dear RDF4j dev-community,
I have been distracted by writing a write-once/read-many quad store :)
This store is designed with some of the challenges of UniProt in mind.
It is based around two concepts sort all the things, and don't mix value
types. This quad store is aimed to be good for datasets with up to about
4000 distinct predicates and graphs in a few 100s range, billions of
distinct values and trillions of triples. That change relatively rarely
and when they do can be generated/reloaded from scratch.
# Some technical snippets.
## Sorted lists for values
The store has dictionaries for values like the vast majority of quad
stores. Difference is one dictionary for each distinct datatype plus one
for iris. A nuance of these dictionaries are that they are based around
sorted lists compressed and memory mapped and all keys are therefore
just index position values. These keys are valid for comparison
operators e.g. key 1 value "a" key 2 value "b" and key comparison
(Long.compare) would match SPARQL value comparison.
## Partioned triple tables, with graph filters
The quad table however is highly partitioned. e.g. one table per
* if the subject is bnode or iri
* the unique predicate
* if the object is bnode or iri or specific datatype.
e.g.
_:1 :pred_0 <http://example.org/iri> .
<http://example.org/iri> :pred_0 3 .
<http://example.org/iri> :pred_0 "lala" .
Will be stored in 3 distinct tables. Allowing us to a completely avoid
storing the predicates and the type of subject or object. For now stored
in separate files e.g.
./pred_0/bnode/iris
./pred_0/iri/datatype_xsd_int
./pred_0/iri/datatype_xsd_string
Which graphs a triple is in is encoded in bitset (roaring for
compression) and there might be multiple graph bitsets per table.
All graphs must be identified by an IRI.
## Inverted indexes using bitsets
Many values can be stored complet
ely inline in such a representation
and we also do inversion of the table. e.g. very valuable for when there
is a small set of distinct objects. e.g. for a with boolean values
We do
true -> [:iri1, :iri2, :iri4]
false -> [:iri1, :iri4, :iri8]
instead of
:iri1 true
:iri1 false
:iri2 true
:iri4 true
:iri4 false
:iri7 false
As all iri's string values are addressable by a 63 bit long value
(positive only). We an turn this into two bitsets. Which give very large
compression ratios and speed afterwards. Reduction to 2% of the input
data for quite a large number of datasets is possible. (2/3rds of the
predicate value combinations in UniProtKB are compressible this way)
## Join optimization candidates
Considering all triples are stored in subject, object order (or that
order is cheap to generate) we can also do a MergeJoin per default for
all patterns where a "subject variable" is joined on. BitSet joins might
in some cases also be possible.
## Open work
There is still a lot of work to be done to make it as fast as possible
and validate that it really works as it is supposed too.
* Strings using less than nine UTF-8 characters are also inline value
candidates but this is not wired up yet.
* FSST compression for the IRI dictionary instead of LZ4.
* Cleanup experiments
* Document more :(
* Reduce temporary file size requirements during compression stage (7TB
for UniProtKB)
## Early results
Early results are encouraging. With for UniProtKB release we need 610 GB
of diskspace. 197 GB for the "quads" the other 413GB for the values.
e.g. roughly 16 bit per triple! This is better than the raw rdf/xml
compressed with xz --best :)
Loading time (for UniProtKB 2022_04) is currently 59 hours on a 128 core
machine (first generation EPYC). With 24 hours in preparsing the rdf/xml
and merge sorting the triples. Another 10 hours in sorting all IRIs, and
25 for converting all values in the triple tables down into their long
identifiers.
In principle the first and last step are highly parallelize and the last
step might be much faster when moving from lz4 to fsst[1] compression
for IRIs and long strings.
I have an in principle agreement that I am allowed to contribute this to
RDF4j. But would like to poll if there is a desire for this and what
kind of paper work do I need to supply.
Considering it is a larger than normal contribution for me. I won't make
the code available until I am clear that the paperwork will be fine/or
that making it fine requires it to be open somewhere already.
Regards,
Jerven
[1] https://github.com/cwida/fsst/
--
*Jerven Tjalling Bolleman*
Principal Software Developer
*SIB | Swiss Institute of Bioinformatics*
1, rue Michel Servet - CH 1211 Geneva 4 - Switzerland
t +41 22 379 58 85
Jerven.Bolleman@sib.swiss - www.sib.swiss