<div dir="ltr">The reason I mention Postgres is because it takes only a couple of days to build a useful solution based on it. Most meta-data storage I've seen easily fits within 1 Terabyte of memory, which means for 99% of all use cases it tends to be enough.<div><br></div><div>A distributed solution is going to measured in weeks or months to build. If you want to go that route, I think LevelDB on individual nodes, riak_core for handling a hash ring and some of the ideas from facebook's TAO-paper for handling secondary key garbage collection could be a rather scalable solution. This could probably scale into the petabyte range if you add enough machines to the ring. But these are Google/Facebook data sizes.</div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Sep 26, 2017 at 12:25 AM Grzegorz Junka <<a href="mailto:list1@gjunka.com">list1@gjunka.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">
<br>
<div class="m_8426177124378221728moz-cite-prefix">On 25/09/2017 20:53, Jesper Louis
Andersen wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div dir="ltr">On Mon, Sep 25, 2017 at 9:16 PM Grzegorz Junka
<<a href="mailto:list1@gjunka.com" target="_blank">list1@gjunka.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF"><br>
</div>
<div text="#000000" bgcolor="#FFFFFF"> gb_tree would not
prevent from having to store the key twice (once as the
key for gb_tree and once as the value). Not sure why you
mention gb_tree here?</div>
<div text="#000000" bgcolor="#FFFFFF"><br>
</div>
</blockquote>
<div><br>
</div>
<div>The reason I mention this is because if we have:</div>
<div><br>
</div>
<div>Key = T, % for some arbitrary term T</div>
<div>Id = Horizon, % for some horizon value</div>
<div>Tree2 = gb_trees:enter(Key, Id, Tree1),</div>
<div>Tree3 = gb_trees:enter(Id, Key, Tree2),</div>
<div><br>
</div>
<div>then the `Key` is immutable and thus shared. It will in
practice be of pointer size (4-8 bytes). This only holds if
you are in a gb_trees setting because if we start going to
ETS for this, then we obviously might lose the sharing.
Perhaps it does work if you insert multiple entries at once.</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">That's the whole
point. How would you implement an RDF/triple database in
Erlang? :)<br>
<br>
</div>
</blockquote>
<div><br>
</div>
<div>The obvious candidate to beat is Postgres with an
appropriately designed table structure and indexes. If we
can't beat this, we are not even in game. It is also fairly
easy to write, so first, we should use that as a baseline
implementation.</div>
<div><br>
</div>
<div>If our RDF store is fairly small and can fit in memory,
I'd probably just store one ETS table doing a bidrectional
ID<->Key mapping as above. And then, depending on
query needs store those ID's as {{spo, Subject, Predicate},
Object} or such in ETS. This should allow fairly efficient
query, as most of the data resides in memory and lookup is
going to be fast. Some data waste is expected in these
solutions. It might be beneficial to just ignore the ID
mapping for a start and do it naively. This also establishes
a model which can be run in unison with other models via
QuickCheck so we can check for agreement with a simpler
model.</div>
<div><br>
</div>
<div>Going to billions of RDF triples will break the above
scheme. I'd probably do like the Cayley datastore in Go:
store data in eleveldb and steal the Cayley-format. In this
format you store everything in one leveldb database where
different parts of the storage are mapped by different
prefixes (IDs are <<"z", SHA1:160/integer>> for
instance. To run fast SPO, OSP, POS ... indexed hashes are
stored for these mappings as well. In addition a horizon and
history is tracked for each quad so we can answer a query in
the past faithfully if needed. Sharding/Batching might come
in handy here at a later point.</div>
<div><br>
</div>
<div>Leveled trees such as the one leveldb uses tend to be
quite efficient compared to B+-trees in many situations. It
might be in this case too. Because Cayley uses unique SHA1
hashes for data, we obtain that keys with the same subject
will be iterable because they will have the same prefix in
that part of the data store. We essentially pay with writes
up-front to make the lookups faster. Also note that leveldb
will naturally keep often used data in memory if tuned.</div>
<div><br>
</div>
<div>TL;DR: either data fits in memory or it doesn't :P</div>
<div><br>
</div>
</div>
</div>
</blockquote>
<br></div><div text="#000000" bgcolor="#FFFFFF">
Yeah, there dozens of possible solutions. Bear in mind that if you
implement RDF on top of Postgres then you need to implement SPARQL
on top of SQL. This is no longer an Erlang database. You can
implement Riak or Couch like database on top of Postgres. The
question is, why? The main reason for using Erlang is to be able
distribute the database across multiple cores and nodes. Postgres as
an SQL database scales very well but up to some point. After a
terabyte of data or so it starts breaking down. You can extend the
performance with some tricks but that's it.<br>
<br>
It's not as much about finding a solution that is good enough
(Postgres, ETS) but about designing an algorithm that allows to
store and query triples in a way that can scale into thousands of
nodes. Erlang is perfect for that because you can start with
implementing an algorithm that works with a few thousand of
processes on multiple CPU cores on one computer. If that works then
the same algorithm can transparently be extended to run those
processes across multiple nodes. And if that works, the algorithm
can probably run millions of processes on those nodes.<br>
<br>
You can compare this problem to a choice between a single big and
complex solution (Postgres/SQL or Cray/mainframe) and many small
distributed and cooperating nodes (Riak/NoSQL or a mesh of
interconnected PCs).<br>
<br>
RDF is by design a way of representing data that is most capable of
distributing across nodes (distributing table cells rather than
whole columns or tables). In such an environment the biggest
problem, in my opinion, is to efficiently handle the LIMIT and ORDER
query modifiers. Imagine having to sort a billion of RDF triples
across a thousand of nodes just to return 10 triples with the least
values/objects.<br>
<br>
GrzegorzJ<br>
<br>
<br>
</div>
</blockquote></div>