21–30 of 44 posts
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.org/lang_with.html
Earlier quoted context omitted.
Neo4j has failed queries I have written, with "out of memory" errors. I have never, ever, ever gotten that from SQLite.
Performance issues are a very valid discussion. But to me, the availability of a graph-oriented query language on top of this graph variant of SQLite is, imho, the very first step to investigate. (RDF import/CSV import being next)
- 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 companies (e.g. Oracle [2], PostgreSQL/2ndQuadrant [3]) seem serious about them. And with a well-defined query language, it should be possible to build a SQL/PGQ engine in (or on top of) SQLite as well.
[1] https://www.linkedin.com/pulse/sql-now-gql-alastair-green/
[2] http://wiki.ldbcouncil.org/pages/viewpage.action?pageId=1062...
[3] https://www.linkedin.com/pulse/postgresql-oracle-graph-query...
Tangentially related to graph dbs, but if you're looking for more hierarchical support, SQLite does has a transitive closure extension[0] that might be of some assistance. I leveraged this back in 2014 to write our framework-agnostic result storage on AWS Device Farm. [0] - https://www.sqlite.org/cgi/src/artifact/636024302cde41b2bf0c... [1] - https://charlesleifer.com/blog/querying-tree-structures-in-s...
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.…
How does this perform compared to a “native” graph database like Neo4J?
It really depends on what you want to do with it. I would benchmark the tasks "traversal", "aggregation" and "shortest past" for a 10k to 10M node graph. Anything under 10k would be good enough with most techs and over 10M need to consider more tasks (writes, backup, the precise fields queried can become their particular problems at larger scale). The Github link implements "traversal "in Python instead of pure SQLit…
It is indeed quite common that relational databases outperform graph databases on certain graph processing problems such as subgraph queries (a.k.a. graph pattern matching). There are two key reasons for this: (1) most graph pattern matching operations can be formulated using relational operations such as natural joins, antijoins, and outer joins; and (2) relational databases have been around longer and have well-optimized operators.
A lot of the value that graph databases provide lies in their query languages which (for most systems) allow formulating path queries using a nice syntax (unlike SQL's WITH RECURSIVE which many people find difficult to read and write). Their property graph data model supports a schema-optional approach, which makes them better suited for storing semi-structured data. They also "provide efficient programmatic access to the graph, allowing one to write arbitrary algorithms against them if needed" [1].
With all these said, graph databases could be much faster on subgraph queries than relational databases and there are recent research results on the topic (worst-case optimal joins, A+ indexes, etc.). But these are not available in any production system yet.
How does this perform compared to a “native” graph database like Neo4J?
It depends on how the graph is stored in the database. In this project the nodes ids are TEXT so it will likely not scale very well. I know because I use a similar implementation with GUID as string in Sqlite in a project since a couple of years and while it works fine for the graph I have (<1 million nodes, few edges per nodes) it won’t perform too well past that.
https://github.com/schinckel/ulid-postgres/blob/master/ulid....
Earlier quoted context omitted.
Performance issues are a very valid discussion. But to me, the availability of a graph-oriented query language on top of this graph variant of SQLite is, imho, the very first step to investigate. (RDF import/CSV import being next)
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…
However, what's lacking from something like this is a detailed bill of the cost. I'd love to see some, any benchmark on a DB with > 10^6 edges to see how it goes. That's the other hand of the equation "just use sqlite and be happy" -- the expectation that performance will actually be reasonable.