Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Simple-graph – a graph database in SQLite

github.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Show HN: Simple-graph – a graph database in SQLite

#31

Post by hansvm »

abetlen wrote: post #25
rklaehn wrote: post #21

Interesting. SQLite is awesome. I did something similar recently, a block store for a rust implementation of ipfs, which models a directed acyclic graph of content-addressed nodes. https://github.com/actyx/ipfs-sqlite-block-store I found that performance is pretty decent if you do almost everything inside SQLite using WITH RECURSIVE. The documentation has some really great examples for WITH RECURSIVE. https://sqlite.…

The issue I found with WITH RECURSIVE queries is that they're incredibly inefficient for anything but trees. I've looked around and there doesn't seem to be any way to store a global list of visited nodes. This means that when performing a traversal of the graph the recursive query will follow all paths between two nodes.

I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query.

At a moderate overhead you could also definitely return all seen nodes and a flag to identify them as such as part of your intermediate data at each recursive step.

The postgres query optimizer struggles with recursive queries even when well suited to the problem though. Are they actually efficient in sqlite even for trees?

Re: Show HN: Simple-graph – a graph database in SQLite

#32

Post by claytongulick »

pstuart wrote: post #12
kevas wrote: post #7

Why not add that functionality directly to SQLite via stored procs* https://www.amazon.com/Hierarchies-Smarties-Kaufmann-Managem... * https://github.com/wolfch/sqlite-3.7.3.p1

A more recent effort: https://cgsql.dev/

I just read through the docs of this, what an amazing project.

I'm considering doing a js template string implementation for node.. cql`...` type thing with an internal compilation cache.

Re: Show HN: Simple-graph – a graph database in SQLite

#33

Post by westurner »

lolive wrote: post #17

I wonder if there are ways, in SQLite, to build indices for s,p,o/s,p/p,o/ and maybe more subtle ones... That would be uber nice, given the fact that most graph databases have their own indexing strategies, and you cannot craft your own.

rdflib-sqlalchemy is a SQLAlchemy rdflib graph store backend: https://github.com/RDFLib/rdflib-sqlalchemy

It also persists namespace mappings so that e.g. schema:Thing expands to http://schema.org/Thing

The table schema and indices are defined in rdflib_sqlalchemy/tables.py: https://github.com/RDFLib/rdflib-sqlalchemy/blob/develop/rdf...

You can execute SPARQL queries against SQL, but most native triplestores will have a better query plan and/or better performance.

Apache Rya, for example:

> indexes SPO, POS, and OSP.

Re: Show HN: Simple-graph – a graph database in SQLite

#34

Post by rklaehn »

hansvm wrote: post #31
abetlen wrote: post #25

Earlier quoted context omitted.

The issue I found with WITH RECURSIVE queries is that they're incredibly inefficient for anything but trees. I've looked around and there doesn't seem to be any way to store a global list of visited nodes. This means that when performing a traversal of the graph the recursive query will follow all paths between two nodes.

I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query. At a moderate overhead you could also definitely return all seen nodes and a flag to identify them as such as part of your intermediate data at each recursive step. The postgres query optimizer struggles with recursive queries even when well suited to the problem tho…

I would say they are reasonably efficient.

Of course many orders of magnitude slower than keeping it all in in memory maps and doing the traversal there, but fast enough to not be a limiting factor.

Traversing a medium depth DAG with a million nodes to find orphaned nodes takes less than a second on average hardware.

One thing to be aware of is that SQLite has lots of tuning options, and they are all set to very conservative values by default.

E.g. the default journal mode is FULL, which means that it will flush all the way to disk after each write. The default cache size is tiny.

With a bit of tuning you can get quite decent performance out of SQLite while still having full ACID guarantees, or very good performance for cases where you can compromise on the ACID stuff.

I have not yet found a situation where nosql databases like leveldb offer an orders of magnitude advantage over SQLite, and SQLite is so much more powerful and robust...

https://danluu.com/file-consistency/

Re: Show HN: Simple-graph – a graph database in SQLite

#35

Post by roland_nilsson »

Isn't the whole point of graph databases that they can traverse graph edges efficiently by following pointers to nodes, which relational databases can't do? Then it seems a bit strange to implement a graph database on top of a relational database like SQLite?

Re: Show HN: Simple-graph – a graph database in SQLite

#36

Post by lolive »

beaconstudios wrote: post #29
szarnyasg wrote: post #22

Earlier quoted context omitted.

There has been a lot of progress on creating standardized query languages for graphs. The two most notable ones are [2]: - SQL/PGQ, a property graph query extension to SQL is planned to be released next year as part of SQL:2021. - GQL, a standalone graph query language will follow later. While it is a lot of work to design these languages, both graph database vendors (e.g. Neo4j, TigerGraph) and traditional RDBMS com…

have SPARQL and Gremlin not seen adoption as standard graph traversal languages? They're the two names that spring to mind when I think "graph querying".

I second that. I have not followed the news about the Gremlin-to-SPARQL (or SPARQL-to-Cypher) bridge. But afaiu, making your graph system Gremlin-compatible is a first step in the right direction. (And yes, doing that on top of a SQL backend sounds not that natural).

Re: Show HN: Simple-graph – a graph database in SQLite

#37

Post by szarnyasg »

beaconstudios wrote: post #29
szarnyasg wrote: post #22

Earlier quoted context omitted.

There has been a lot of progress on creating standardized query languages for graphs. The two most notable ones are [2]: - SQL/PGQ, a property graph query extension to SQL is planned to be released next year as part of SQL:2021. - GQL, a standalone graph query language will follow later. While it is a lot of work to design these languages, both graph database vendors (e.g. Neo4j, TigerGraph) and traditional RDBMS com…

have SPARQL and Gremlin not seen adoption as standard graph traversal languages? They're the two names that spring to mind when I think "graph querying".

Both SPARQL and Gremlin have been adopted to some extent. SPARQL is a W3C standard and Gremlin is reasonably well-specified (it has good documentation and a reference implementation), so it's possible to implement a functionally correct SPARQL/Gremlin engine with a reasonable development effort.

Gremlin's main focus is defining traversal operations on property graphs. While it supports pattern matching [1], IMHO its syntax is not as clean as Cypher's. Gremlin queries are also difficult to optimize: while it is possible to define traversal rewrite rules, they are more involved than relational optimization rules. The fact that most open-source Gremlin implementations are focusing on distributed setups (e.g. a typical deployment of Titan/JanusGraph runs on top of Cassandra) has also implications on single-machine performance, which certainly did not help the adoption of Gremlin -- but this is not necessarily the problem of the query language. Overall, Gremlin is great for workloads where complex single-source traversal operations do the bulk of the work but it's less well-suited to global pattern matching queries such as the ones in the LDBC Social Network Benchmark's BI workload [2].

SPARQL focuses on the graph problems of the "semantic web" domain, which include not only pattern matching but semantic reasoning/inferencing. One can use it for pattern matching queries but with the following caveats:

- Its data model is based on triples so if one wants to return a node and its attributes (properties), one has to specify each of these attributes explicitly.

- On the execution side, returning these attributes might necessitate executing a number of self-join operations.

- Many SPARQL implementations also have performance limitations due to the extra complexity introduced by self-joins, lack of intra-query parallelism, etc.

The "RDF* and SRARQL* approach" is an initiative to amend the self-join problem by introducing nested triples in the data model. It's currently being worked on by a W3C community group [3]. SPARQL also has "property paths", which allows regular path queries, i.e. traversals where the node/edge labels confirm some regular expression (the "property" in "property paths" has nothing to do with "property graphs").

SQL/PGQ and GQL target the property graph data model and support an ASCII-art like syntax for pattern matching queries (inspired by Cypher). They also offer some graph traversal/shortest path operations (including shortest path and regular path queries). Additionally, GQL supports returning graphs so it's queries can be composed.

[1] https://en.wikipedia.org/wiki/Gremlin_(query_language)#Decla...

[2] https://ldbc.github.io/ldbc_snb_docs/workload-bi-reads.pdf

[3] https://blog.liu.se/olafhartig/2019/01/10/position-statement...

Re: Show HN: Simple-graph – a graph database in SQLite

#38

Post by mark_l_watson »

westurner wrote: post #33
lolive wrote: post #17

I wonder if there are ways, in SQLite, to build indices for s,p,o/s,p/p,o/ and maybe more subtle ones... That would be uber nice, given the fact that most graph databases have their own indexing strategies, and you cannot craft your own.

rdflib-sqlalchemy is a SQLAlchemy rdflib graph store backend: https://github.com/RDFLib/rdflib-sqlalchemy It also persists namespace mappings so that e.g. schema:Thing expands to http://schema.org/Thing The table schema and indices are defined in rdflib_sqlalchemy/tables.py: https://github.com/RDFLib/rdflib-sqlalchemy/blob/develop/rdf... You can execute SPARQL queries against SQL, but most native triplestores will ha…

Thanks for your comment. I use rdflib frequently but have never tried the SQLAlchemy back end. Now I will. That said, Jena or Fuseki, or the commercial RDF stores like GraphDB, Stardog, and Allegrograph are so much more efficient.

Re: Show HN: Simple-graph – a graph database in SQLite

#39

Post by hansvm »

rklaehn wrote: post #34
hansvm wrote: post #31

Earlier quoted context omitted.

I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query. At a moderate overhead you could also definitely return all seen nodes and a flag to identify them as such as part of your intermediate data at each recursive step. The postgres query optimizer struggles with recursive queries even when well suited to the problem tho…

I would say they are reasonably efficient. Of course many orders of magnitude slower than keeping it all in in memory maps and doing the traversal there, but fast enough to not be a limiting factor. Traversing a medium depth DAG with a million nodes to find orphaned nodes takes less than a second on average hardware. One thing to be aware of is that SQLite has lots of tuning options, and they are all set to very cons…

> Traversing a medium depth DAG with a million nodes to find orphaned nodes takes less than a second on average hardware.

Unless you have an abnormally high edge count that sounds super slow to me. Even accounting for metadata overhead and disk page slop you're only reading and processing tens of megabytes, and every algorithm in sight is linear. I'd be surprised if you couldn't get a 2-5x speedup by reading the whole table to RAM in your favorite compiled/jitted language and just traversing it there.

> I have not yet found a situation where nosql databases like leveldb offer an orders of magnitude advantage over SQLite, and SQLite is so much more powerful and robust...

I have no skin in that game, but would some of the nosql solutions not perform significantly better under heavily concurrent insertions and the other workloads they were designed for?

Re: Show HN: Simple-graph – a graph database in SQLite

#40

Post by abetlen »

hansvm wrote: post #31
abetlen wrote: post #25

Earlier quoted context omitted.

The issue I found with WITH RECURSIVE queries is that they're incredibly inefficient for anything but trees. I've looked around and there doesn't seem to be any way to store a global list of visited nodes. This means that when performing a traversal of the graph the recursive query will follow all paths between two nodes.

I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query. At a moderate overhead you could also definitely return all seen nodes and a flag to identify them as such as part of your intermediate data at each recursive step. The postgres query optimizer struggles with recursive queries even when well suited to the problem tho…

> I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query.

I'm not sure if this is possible in SQLite, as far as I know the WITH clause is limited to SELECT statements.

> Are they actually efficient in sqlite even for trees?

Recursive common table expressions work by adding returned rows to a queue and then performing the recursive select statement independently on each row in the queue until it's empty.

You can use WITH RECURSIVE to traverse a tree by adding the root node to the queue and recursively visiting adjacent rows until the queue is empty. This works correctly and quickly because trees have only a single path between nodes. If you try the same query on a DAG though it will return every path to a given node, you then have to perform a GROUP BY to find the shortest path outside of the recursive query. In the worst case, if you have a graph with many paths between nodes, this method is exponentially slower than a standard BFS.

Post reply on HN