Graph Databases Intrigue Me • Hacker News Board

Re: Graph Databases Intrigue Me

#11

Post by colanderman » Sat, Feb 26, 2011, 2:53 PM UTC

aristidb wrote: post #10

colanderman wrote: post #8

I'm having trouble understanding how exactly graph databases differ from relational databases, especially seeing as how graphs are isomorphic to relations. All the examples on this page look equivalent to how I'd model them in SQL: http://wiki.neo4j.org/content/Domain_Modeling_Gallery The best I gather is that graph databases are schemaless (big whoop, more room for error), and that their implementations tend to perf…

If you have stored a tree with adjacence (parent-child) relations, how would you retrieve all nested children? Or would you propose a different storage mechanism that keeps the property that reparenting entire subtrees is cheap? (All this in your RDBMS of choice.)

You mean all descendants of a node / transitive closure?

WITH RECURSIVE r AS (SELECT parent, child FROM tree UNION SELECT r.parent, tree.child FROM tree, r WHERE tree.parent = r.child) SELECT parent, child FROM r;

transforms this: (A,B), (B,C), (B,D)

into this: (A,B), (A,C), (A,D), (B,C), (B,D)

Re: Graph Databases Intrigue Me

#12

Post by aristidb » Sat, Feb 26, 2011, 2:59 PM UTC

colanderman wrote: post #11

aristidb wrote: post #10

Earlier quoted context omitted.

If you have stored a tree with adjacence (parent-child) relations, how would you retrieve all nested children? Or would you propose a different storage mechanism that keeps the property that reparenting entire subtrees is cheap? (All this in your RDBMS of choice.)

You mean all descendants of a node / transitive closure? WITH RECURSIVE r AS (SELECT parent, child FROM tree UNION SELECT r.parent, tree.child FROM tree, r WHERE tree.parent = r.child) SELECT parent, child FROM r; transforms this: (A,B), (B,C), (B,D) into this: (A,B), (A,C), (A,D), (B,C), (B,D)

Nice! I did not know about this feature. How efficient is it, and which databases support it? :-)

Re: Graph Databases Intrigue Me

#13

Post by colanderman » Sat, Feb 26, 2011, 3:13 PM UTC

aristidb wrote: post #12

colanderman wrote: post #11

Earlier quoted context omitted.

You mean all descendants of a node / transitive closure? WITH RECURSIVE r AS (SELECT parent, child FROM tree UNION SELECT r.parent, tree.child FROM tree, r WHERE tree.parent = r.child) SELECT parent, child FROM r; transforms this: (A,B), (B,C), (B,D) into this: (A,B), (A,C), (A,D), (B,C), (B,D)

Nice! I did not know about this feature. How efficient is it, and which databases support it? :-)

It is SQL standard. I use PostgreSQL, and I'm pretty sure Oracle supports it. MySQL doesn't seem to.

Performance wise it's not magical; it quite literally repeatedly scans the database, broadening the search tree until there is no fringe. On a table I have with nearly exactly that structure of about 300 rows and limited nesting depth, the transitive closure takes 4 ms on a crappy VPS.

Of course I'm sure graph databases are somehow caching the results or performing some other optimization; you can achieve the same effect in RDBMSes with materialized views (which just cache the results of this query & keep it updated). Oracle natively supports materialized views; you can hack it easily in PostgreSQL and MySQL (though it should really be built in).

Re: Graph Databases Intrigue Me

#14

Post by yummyfajitas » Sat, Feb 26, 2011, 3:38 PM UTC

colanderman wrote: post #8

I'm having trouble understanding how exactly graph databases differ from relational databases, especially seeing as how graphs are isomorphic to relations. All the examples on this page look equivalent to how I'd model them in SQL: http://wiki.neo4j.org/content/Domain_Modeling_Gallery The best I gather is that graph databases are schemaless (big whoop, more room for error), and that their implementations tend to perf…

Suppose you have a graph with edge weights.

Query: find all the nodes a distance With SQL92 or earlier, this will require an unbounded number of queries. Proof: A SQL92 query can only traverse a finite number of edges, since it has only a finite number of joins (say K). Consider the graph 1->2->3->...->N with edge weights 1/N. This will require N/K queries to traverse. N is arbitrary.

It's probably doable in SQL99 and various vendor specific extensions (I think it's Turing Complete), but it is unlikely to be fast.

So, as is the normal situation, you can do whatever you want in SQL. But the performance is likely to suck.

(That said, I agree with you that many people are using NoSQL because it's the hip new thing, when they should just use SQL. "Schemaless flexibility" is BS - SQL is very flexible if you use an ORM + migration tool. The only flexibility you lose is the flexibility to screw up the data in application logic.)

Re: Graph Databases Intrigue Me

#15

Post by yummyfajitas » Sat, Feb 26, 2011, 3:48 PM UTC

colanderman wrote: post #13

aristidb wrote: post #12

Earlier quoted context omitted.

Nice! I did not know about this feature. How efficient is it, and which databases support it? :-)

It is SQL standard. I use PostgreSQL, and I'm pretty sure Oracle supports it. MySQL doesn't seem to. Performance wise it's not magical; it quite literally repeatedly scans the database, broadening the search tree until there is no fringe. On a table I have with nearly exactly that structure of about 300 rows and limited nesting depth, the transitive closure takes 4 ms on a crappy VPS. Of course I'm sure graph databas…

In a connected graph, you don't want to cache this [1]. It will take up O(N^2) space. If you have 100k nodes, that would require 10^10 cached edges.

Further, insertion time becomes worst case O(N^2). Consider a graph with two connected components (each having O(N/2) nodes). Once you add an edge that connects them, updating the view will require O(N^2/4) operations - you need to connect every node in the first component to every node in the second.

A graph database is more specialized than SQL, so they can perform a very simple optimization. You don't scan the database, you just follow links. Links are typically stored with the node, so it's O(1) time.

[1] In a connected graph, there is a constant time algorithm - return True. But that won't work if you also want edge distance.

Re: Graph Databases Intrigue Me

#16

Post by colanderman » Sat, Feb 26, 2011, 3:52 PM UTC

yummyfajitas wrote: post #14

colanderman wrote: post #8

I'm having trouble understanding how exactly graph databases differ from relational databases, especially seeing as how graphs are isomorphic to relations. All the examples on this page look equivalent to how I'd model them in SQL: http://wiki.neo4j.org/content/Domain_Modeling_Gallery The best I gather is that graph databases are schemaless (big whoop, more room for error), and that their implementations tend to perf…

Suppose you have a graph with edge weights. Query: find all the nodes a distance With SQL92 or earlier, this will require an unbounded number of queries. Proof: A SQL92 query can only traverse a finite number of edges, since it has only a finite number of joins (say K). Consider the graph 1->2->3->...->N with edge weights 1/N. This will require N/K queries to traverse. N is arbitrary. It's probably doable in SQL99 an…

Trivial with SQL-standard recursive queries:

WITH RECURSIVE r AS (SELECT parent, child, distance FROM graph UNION ALL SELECT r.parent, graph.child, r.distance + graph.distance AS distance FROM graph, r WHERE graph.parent = r.child) SELECT parent, child FROM r WHERE distance Testing your graph with N=1000 on a teeny VPS. 477,897 rows returned in 6.1s.

If we move the WHERE clause inside the sub-SELECT (which unfortunately makes the query slightly more awkward to use), selecting lower distances reduces the compute time. For example, a bound of 0.5 returns 196,238 rows in 2.5s.

What sort of performance gains does a graph database give for this same query?

Re: Graph Databases Intrigue Me

#17

Post by yummyfajitas » Sat, Feb 26, 2011, 4:28 PM UTC

colanderman wrote: post #16

yummyfajitas wrote: post #14

Earlier quoted context omitted.

Suppose you have a graph with edge weights. Query: find all the nodes a distance With SQL92 or earlier, this will require an unbounded number of queries. Proof: A SQL92 query can only traverse a finite number of edges, since it has only a finite number of joins (say K). Consider the graph 1->2->3->...->N with edge weights 1/N. This will require N/K queries to traverse. N is arbitrary. It's probably doable in SQL99 an…

Trivial with SQL-standard recursive queries: WITH RECURSIVE r AS (SELECT parent, child, distance FROM graph UNION ALL SELECT r.parent, graph.child, r.distance + graph.distance AS distance FROM graph, r WHERE graph.parent = r.child) SELECT parent, child FROM r WHERE distance Testing your graph with N=1000 on a teeny VPS. 477,897 rows returned in 6.1s. If we move the WHERE clause inside the sub-SELECT (which unfortunat…

As I said, you can probably do it with SQL99 query, them being turing complete and all.

I don't know how your database is implementing things under the hood, so I don't know. I'll just list the major advantages of a graph database:

1) Edges stored with nodes. You can almost certainly read an edge and all it's neighbors with a single disk seek. This is unlikely to be the case for a SQL system.

2) Compute time is always O( portion of graph traversed), not O(graph size), and is always under the control of the user. In SQL, this will vary quite a bit with implementation.

3) You can specify various heuristics for the traversal - depth first, breadth first, etc. This is important if the specific nature of your data will affect the speed of the query.

Re: Graph Databases Intrigue Me

#18

Post by colanderman » Sat, Feb 26, 2011, 5:17 PM UTC

yummyfajitas wrote: post #17

colanderman wrote: post #16

Earlier quoted context omitted.

Trivial with SQL-standard recursive queries: WITH RECURSIVE r AS (SELECT parent, child, distance FROM graph UNION ALL SELECT r.parent, graph.child, r.distance + graph.distance AS distance FROM graph, r WHERE graph.parent = r.child) SELECT parent, child FROM r WHERE distance Testing your graph with N=1000 on a teeny VPS. 477,897 rows returned in 6.1s. If we move the WHERE clause inside the sub-SELECT (which unfortunat…

As I said, you can probably do it with SQL99 query, them being turing complete and all. I don't know how your database is implementing things under the hood, so I don't know. I'll just list the major advantages of a graph database: 1) Edges stored with nodes. You can almost certainly read an edge and all it's neighbors with a single disk seek. This is unlikely to be the case for a SQL system. 2) Compute time is alway…

Ah thank you, this answers my original question. In response:

1) I contest that this is "unlikely" for SQL -- MySQL (unless I'm misremembering) orders data on disk by its primary key, which would be an equivalent optimization. (PostgreSQL does not do this to my knowledge.)

2) In my two queries above, I demonstrate both O(graph) and O(traversed) (in that order). At least in PostgreSQL, this is very much under control of the user as well, since WITH queries are evaluated in a specific order.

3) There is no way to specify such things in SQL. However most SQLs are designed with the idea that the query planner is smarter than you (it almost always is, at least in PostgreSQL), so you shouldn't be trying to specify execution plans anyway.

Overall, I see no reason for graph databases & SQL to be separate. It seems that if graph DBs really only address performance issues as you claim, that one is throwing out the baby with the bathwater by creating a new kind of database rather than simply adding specialized optimizations to e.g. PostgreSQL.

Re: Graph Databases Intrigue Me

#19

Post by colanderman » Sat, Feb 26, 2011, 5:25 PM UTC

yummyfajitas wrote: post #15

colanderman wrote: post #13

Earlier quoted context omitted.

It is SQL standard. I use PostgreSQL, and I'm pretty sure Oracle supports it. MySQL doesn't seem to. Performance wise it's not magical; it quite literally repeatedly scans the database, broadening the search tree until there is no fringe. On a table I have with nearly exactly that structure of about 300 rows and limited nesting depth, the transitive closure takes 4 ms on a crappy VPS. Of course I'm sure graph databas…

In a connected graph, you don't want to cache this [1]. It will take up O(N^2) space. If you have 100k nodes, that would require 10^10 cached edges. Further, insertion time becomes worst case O(N^2). Consider a graph with two connected components (each having O(N/2) nodes). Once you add an edge that connects them, updating the view will require O(N^2/4) operations - you need to connect every node in the first compone…

You're right about caching. I wasn't sure if graph databases took the typical NoSQL approach of massive non-normalized tables to avoid computational overhead.

SQL doesn't scan either -- tables are indexed via either a hash (O(1)) or a tree (O(log edges)). While I do realize the speed advantage of a specialized structure, I feel this could be better implemented as a specialized index/storage mechanism in SQL than as an entirely new database system.

Re: Graph Databases Intrigue Me

#20

Post by olihb » Sat, Feb 26, 2011, 5:57 PM UTC

I'm curious about the performance and scalability of those database. Right now at work we have a MSSQL server with 32 CPU, SSDs and 128GB RAM and I was wondering if a graph database would be better.

Our dataset is very peculiar, we have about 20M nodes and 500M edges in one of our smallest database. We also need fulltext search and complex joins between tables.

I'm wondering if graph databases are mature enough or if they are not quite ready yet for production work. We're a small shop and software development is not our core competency.