4 ms·

You can reasonably model graphs in a column-oriented database, but traditional SQL models tend to be horrible performance-wise, because most graph algorithms ne

by wheels 5y ago

You can reasonably model graphs in a column-oriented database, but traditional SQL models tend to be horrible performance-wise, because most graph algorithms need fast traversal of edges, and doing a lot of recursive lookups in SQL is impractically slow. It's not that you can't model it, it's just that performance is terrible. For a graph database to be efficient, you need a high degree of locality for edge information (ideally a vector you can simply read out). (Note: I've actually written a graph database from scratch, for exactly these reasons.)

ahevia 5y ago
Do you have examples of Graph DBs that could embedded in a static site as easily as SQLite?
oever 5y ago
Modelling transitive edges can be done in Sqlite with recursive common table expressions. The performance for that is probably less than for graphs databases, but Sqlite has many other advantages over graph databases.
- wheels 5y ago
  Uhm, that's basically what I said? Aside from the "other advantages" -- which, yeah, sure. Socket sets have other advantages than hammers, but they're not very good at pounding in nails. You can do it, but it'll suck at it. Also, in this case, "probably less" is "multiple orders of magnitude slower".
  - oever 5y ago
    The locality that you want for performance is available as row values in sqlite. Sqlite seems to have the parts needed to build a graph db.
    - deleted 5y ago
      [deleted]
    - WJW 5y ago
      Why do you keep making the same argument again? Yes, SQLite has the parts needed to build a (very poor) graph db. But it will never be as performant as something dedicated, because the data structures used in SQLite have terrible characteristics for the algorithms used in graph operations. I like SQLite a lot, but it targets a niche and graph operations is simply not that niche.
      - oever 5y ago
        Using Sqlite for semantic web is the topic of the post. And while Sqlite is not suited for billions of triples, it can be adequate for the small graphs. The advantage is that Sqlite is widely deployed.
    - wheels 5y ago
      You're not understanding what I mean by locality in this context. I mean that the on-disk structure should approximate an array of indexes, e.g.: const unsigned *edge_indexes = (const unsigned *) mmaped_structure_on_disk[disk_offsets[index]]; That's not the same as just being able to access those via an API; locality in this case means that you shouldn't need extra seeks for every single value, nor have to make a bunch of round trips through SQL. That is the primary difference between traditional relational databases and column-oriented databases. Normal relational databases have row-based locality; column-oriented databases have column-based locality.
      - oever 5y ago
        Sqlite does indeed not have an array type for columns. The overhead of (de)serializing binary values or json values would have to be offset against the advantage of cache coherence. Or one could implement a virtual table that stores arrays in integers.
      - fauigerzigerk 5y ago
        If your typical query visits all adjacent edges of a few nodes then the locality you're talking about is great. If your queries typically aggregate over a few types of edges across many nodes then this locality is the worst case. So the question is, do we actually want to run graph algorithms or is the data graph structured for other reasons? You're implying that choosing a graph representation means we want to perform graph analyses. I disagree with that if we're still talking about the semantic web. RDF is a general purpose knowledge representation model. The triple structure lends itself well to combining data from different sources with little coordination. It happens to form a graph, but running graph algorithms is just one of many special purpose problems.
        wheels 5y ago
        Yes, you're mostly correct. (The one caveat being that if you know your access patterns in advance, you can choose if you store the edge type along with the edge, or if you store separate edge types in separate columns.) I'm not even arguing against storing RDF in SQLite. There are times that would make sense, and times that it wouldn't. I'm primarily replying to: > What is a graph database? A miserable little pile of joins. > Though to be serious: what do you expect a graph database to provide that sqlite cannot / does not do efficiently? That seemed like a general questions of, "What are graph databases for, and why would someone use them?" And I'm trying to answer that question.
simonw 5y ago
SQLite may be uniquely well suited to building graph databases out if all of the relational engines, thanks to this: https://www.sqlite.org/np1queryprob.html https://www.sqlite.org/np1queryprob.html
- wheels 5y ago
  s/uniquely well suited/somewhat less bad/ Fixed that for you. ;-) Actually a few RDMBSes (Oracle, Postgres, MS SQL) have graph extensions. I've never used any of them, but I assume they work around some of the basic unsuitability of traditional tables for storing graphs.

by wheels 5y ago

ahevia 5y ago

Do you have examples of Graph DBs that could embedded in a static site as easily as SQLite?

oever 5y ago

Modelling transitive edges can be done in Sqlite with recursive common table expressions. The performance for that is probably less than for graphs databases, but Sqlite has many other advantages over graph databases.

wheels 5y ago
Uhm, that's basically what I said? Aside from the "other advantages" -- which, yeah, sure. Socket sets have other advantages than hammers, but they're not very good at pounding in nails. You can do it, but it'll suck at it. Also, in this case, "probably less" is "multiple orders of magnitude slower".
- oever 5y ago
  The locality that you want for performance is available as row values in sqlite. Sqlite seems to have the parts needed to build a graph db.
  - deleted 5y ago
    [deleted]
  - WJW 5y ago
    Why do you keep making the same argument again? Yes, SQLite has the parts needed to build a (very poor) graph db. But it will never be as performant as something dedicated, because the data structures used in SQLite have terrible characteristics for the algorithms used in graph operations. I like SQLite a lot, but it targets a niche and graph operations is simply not that niche.
    - oever 5y ago
      Using Sqlite for semantic web is the topic of the post. And while Sqlite is not suited for billions of triples, it can be adequate for the small graphs. The advantage is that Sqlite is widely deployed.
  - wheels 5y ago
    You're not understanding what I mean by locality in this context. I mean that the on-disk structure should approximate an array of indexes, e.g.: const unsigned *edge_indexes = (const unsigned *) mmaped_structure_on_disk[disk_offsets[index]]; That's not the same as just being able to access those via an API; locality in this case means that you shouldn't need extra seeks for every single value, nor have to make a bunch of round trips through SQL. That is the primary difference between traditional relational databases and column-oriented databases. Normal relational databases have row-based locality; column-oriented databases have column-based locality.
    - oever 5y ago
      Sqlite does indeed not have an array type for columns. The overhead of (de)serializing binary values or json values would have to be offset against the advantage of cache coherence. Or one could implement a virtual table that stores arrays in integers.
    - fauigerzigerk 5y ago
      If your typical query visits all adjacent edges of a few nodes then the locality you're talking about is great. If your queries typically aggregate over a few types of edges across many nodes then this locality is the worst case. So the question is, do we actually want to run graph algorithms or is the data graph structured for other reasons? You're implying that choosing a graph representation means we want to perform graph analyses. I disagree with that if we're still talking about the semantic web. RDF is a general purpose knowledge representation model. The triple structure lends itself well to combining data from different sources with little coordination. It happens to form a graph, but running graph algorithms is just one of many special purpose problems.
      - wheels 5y ago
        Yes, you're mostly correct. (The one caveat being that if you know your access patterns in advance, you can choose if you store the edge type along with the edge, or if you store separate edge types in separate columns.) I'm not even arguing against storing RDF in SQLite. There are times that would make sense, and times that it wouldn't. I'm primarily replying to: > What is a graph database? A miserable little pile of joins. > Though to be serious: what do you expect a graph database to provide that sqlite cannot / does not do efficiently? That seemed like a general questions of, "What are graph databases for, and why would someone use them?" And I'm trying to answer that question.

simonw 5y ago

SQLite may be uniquely well suited to building graph databases out if all of the relational engines, thanks to this: https://www.sqlite.org/np1queryprob.html https://www.sqlite.org/np1queryprob.html

wheels 5y ago
s/uniquely well suited/somewhat less bad/ Fixed that for you. ;-) Actually a few RDMBSes (Oracle, Postgres, MS SQL) have graph extensions. I've never used any of them, but I assume they work around some of the basic unsuitability of traditional tables for storing graphs.