4 ms·

Spoken like someone who has never implemented a large graph in a relational database. One of the main things you do with a graph is traversal, not just recalli

by wheels 18y ago

Spoken like someone who has never implemented a large graph in a relational database. One of the main things you do with a graph is traversal, not just recalling edges. Doing graph traversal in an RDBMS is beyond painful. Every edge you traverse typically comprises of one query. Sending that rate of queries to an RDBMS isn't anywhere close to efficient. As for key-value stuff, that can be done pretty easily in an RDBMS, but is often more natural in databases geared specifically towards that. If you'd prefer not to use those sorts of systems, by all means, don't. Relational databases break down at the point that the sort of queries that you're interested in running don't map flexibly to a relational model. You can insist this isn't the case with handwaving and saying the guy that wrote the DB doesn't know anything about databases, but Google, Amazon, eBay and LinkedIn (just to name the few that come to mind off the top of my head) disagree.

davidmathers 18y ago
"Doing graph traversal in an RDBMS is beyond painful. Every edge you traverse typically comprises of one query." You mean MySQL doesn't do transitive closure? Sounds like a product problem, not a relational database problem.
- jrockway 18y ago
  I think he means graphs with cycles.
  - davidmathers 18y ago
    My graph-fu is weak. If it's not too much time could you give me an example of something that can't be done with a transitive closure statement?
Retric 18y ago
Creating a Key Value DB from scratch is simpler than creating a RDBMS from scratch. So, when no existing RDBMS meets your needs creating a Key Value DB and dealing with it's limitations is a reasonable solution. See Big Table and others. As to graph traversal you can do more with SQL than you might think. Granted I just came up with it on the fly but you get the idea. Let's say you're DB represents a 3d Maze and you want to find the shortest path from A to B. Well create a temporary table with a copy of that data and a new weight field, run an update command on all nodes if it links a node that has a weight, or the sum of those weights is less than it's current weight. Keep running that update until you find a solution. Total SQL commands is equal to distance not number of nodes on the graph. PS: There are many types of graph traversal and this is far from an ideal solution, but clearly 1 command per node is not needed. Also many Databases let you run custom code when existing queries don't meet your needs.
- wheels 18y ago
  Nah, not really practical in a database with millions of nodes and millions or billions of edges (which both the Directed Edge DB and neo4j support). The query would finish, but not in in the amount of time that you'd need for a lot of graph applications.
  - Retric 18y ago
    For up to million nodes this would probably take less than 1 second if it's kept in memory. Anyway, if you want to query this 50 times a second on a huge DB write custom code, or use Directed Edge DB etc. My point was you can still do it on all SQL databases in a reasonable amount of time using basic SQL. SQL trades speed for flexibility and it's incredibly flexible. Computers are insanely fast and they have incredible amounts of storage. Problems that used to take expensive custom HW tend to migrate to the generic solution which why SQL is still the default after all these years. If anything I suspect most problems that take clusters today will quickly migrate to a single machine solution. Google might have a 50,000 node cluster, but web search is probably being consolidated to fewer machines over time. Google keeps adding other services like gmail that use their cluster, but the searchable internet is just not growing that fast over the next 20 years. Edit: A graph of every human relationship in the world is still finite. Rendering a complex 3D model can take limitless amount of computational resources but most data centric problems don't really grow. Early on they take huge amount of resources say 1960's era Mainframes but eventual that class of problems fit on your iPhone.
    - rw 18y ago
      > "but the searchable internet is just not growing that fast over the next 20 years." Please defend that statement.
      - Retric 18y ago
        To "keep up" with computing power, the searchable internet would need to grow at more than 50% per year which it's not. Now we could argue that Google is going to add some AI that does image search though actual sound / images / movies etc, but IMO it's all still going to be text in 20 years. So, it's a question of how much text is going to be on the internet over the next 20 years. Facebook is already popular enough that there are not enough people in the world for it to grow 50% / year much longer, so it comes down to what % of all human interactions are going to take place online. Granted things change, but I don't see the average person in south Africa is going to start tweeting 10 hours a day within 20 years. We could argue that more companies are going to place their information online but many already do that and it's not growing at 50% / year. It all comes down to the limits of exponential growth, computers are not going to hit hard limits within 20 years and few things can keep up with that level of growth.
justinsb 18y ago
It's about using the right tool for the job. It seems most of the companies you mentioned have decided that relational databases are actually the right tool. You mentioned... Google: Proprietary stack for document-orientated systems (search, GMail), use MySQL to run AdWords (their revenue business). http://xooglers.blogspot.com/2005/12/lets-get-real-database.html http://xooglers.blogspot.com/2005/12/lets-get-real-database.... Amazon: Major Oracle customer. Functionality is managed by modular teams, each of which has their own architectural choices, so difficult to generalize. Certainly in the early days was entirely Oracle (and look, it's a story about Oracle failing!) http://glinden.blogspot.com/2006/03/early-amazon-oracle-down.html http://glinden.blogspot.com/2006/03/early-amazon-oracle-down... Want you to use SimpleDB, but difficult to find Amazon groups actually eating the dog-'food'. eBay: Oracle. http://www.addsimplicity.com/downloads/eBaySDForum2006-11-29.pdf http://www.addsimplicity.com/downloads/eBaySDForum2006-11-29... LinkedIn: Oracle & MySQL. Custom caching layer on top to get round the 'graph' problems you talked about. http://hurvitz.org/blog/2008/06/linkedin-architecture http://hurvitz.org/blog/2008/06/linkedin-architecture OK, what about some others: Facebook: MySQL. Memcached for caching. Custom data stores for images and for inbox search (so non-relational for document storage again) http://glinden.blogspot.com/2008/05/scaling-facebooks-databases.html http://glinden.blogspot.com/2008/05/scaling-facebooks-databa... Wikipedia: MySQL. They're document storage, so it is possible to get document storage to work on MySQL. http://venublog.com/2008/04/16/notes-from-scaling-mysql-up-or-out/ http://venublog.com/2008/04/16/notes-from-scaling-mysql-up-o... Maybe it's just not sexy to stand up at a conference and say 'We architected this system to run on a relational database, in the normal proven way, and it runs wonderfully in production. We scaled it using partitioning, in the normal way. We're generating real money with the system.' You only hear a biased sample, which is why you think the companies you named are good examples of people that use non-relational databases.
- wheels 18y ago
  We seem to be oscillating between "key value stores are the way!" and "relational databases are the way!" Both have their places. If my notes were read as seeming to advocate the end of relational databases, please excuse me because that was certainly not my intent. Of course all of those companies use relational databases. Often they're the best tools for the job and in an IT landscape as large as their respective setups, of course they're the right tool for several jobs. But they've also got problem domains where they've decided RDBMSes are not the best tools for the job, which was my point to begin with. This thread started off with the assertion, basically, that if you weren't using a RDBMS to store everything, you probably didn't know anything about databases and I feel like we've (including the original poster) been slowly narrowing in on something closer to reality. As for the examples on the non-RDBMS side, BigTable, SimpleDB, Voldemort (+) and, well, the guy that I met with last week that wrote eBay Germany's search system and told me they had their own non-RDBMS storage system. + http://blog.linkedin.com/2009/03/20/project-voldemort-scaling-simple-storage-at-linkedin/ http://blog.linkedin.com/2009/03/20/project-voldemort-scalin...

by wheels 18y ago

davidmathers 18y ago

"Doing graph traversal in an RDBMS is beyond painful. Every edge you traverse typically comprises of one query." You mean MySQL doesn't do transitive closure? Sounds like a product problem, not a relational database problem.

jrockway 18y ago
I think he means graphs with cycles.
- davidmathers 18y ago
  My graph-fu is weak. If it's not too much time could you give me an example of something that can't be done with a transitive closure statement?

Retric 18y ago

Creating a Key Value DB from scratch is simpler than creating a RDBMS from scratch. So, when no existing RDBMS meets your needs creating a Key Value DB and dealing with it's limitations is a reasonable solution. See Big Table and others. As to graph traversal you can do more with SQL than you might think. Granted I just came up with it on the fly but you get the idea. Let's say you're DB represents a 3d Maze and you want to find the shortest path from A to B. Well create a temporary table with a copy of that data and a new weight field, run an update command on all nodes if it links a node that has a weight, or the sum of those weights is less than it's current weight. Keep running that update until you find a solution. Total SQL commands is equal to distance not number of nodes on the graph. PS: There are many types of graph traversal and this is far from an ideal solution, but clearly 1 command per node is not needed. Also many Databases let you run custom code when existing queries don't meet your needs.

wheels 18y ago
Nah, not really practical in a database with millions of nodes and millions or billions of edges (which both the Directed Edge DB and neo4j support). The query would finish, but not in in the amount of time that you'd need for a lot of graph applications.
- Retric 18y ago
  For up to million nodes this would probably take less than 1 second if it's kept in memory. Anyway, if you want to query this 50 times a second on a huge DB write custom code, or use Directed Edge DB etc. My point was you can still do it on all SQL databases in a reasonable amount of time using basic SQL. SQL trades speed for flexibility and it's incredibly flexible. Computers are insanely fast and they have incredible amounts of storage. Problems that used to take expensive custom HW tend to migrate to the generic solution which why SQL is still the default after all these years. If anything I suspect most problems that take clusters today will quickly migrate to a single machine solution. Google might have a 50,000 node cluster, but web search is probably being consolidated to fewer machines over time. Google keeps adding other services like gmail that use their cluster, but the searchable internet is just not growing that fast over the next 20 years. Edit: A graph of every human relationship in the world is still finite. Rendering a complex 3D model can take limitless amount of computational resources but most data centric problems don't really grow. Early on they take huge amount of resources say 1960's era Mainframes but eventual that class of problems fit on your iPhone.
  - rw 18y ago
    > "but the searchable internet is just not growing that fast over the next 20 years." Please defend that statement.
    - Retric 18y ago
      To "keep up" with computing power, the searchable internet would need to grow at more than 50% per year which it's not. Now we could argue that Google is going to add some AI that does image search though actual sound / images / movies etc, but IMO it's all still going to be text in 20 years. So, it's a question of how much text is going to be on the internet over the next 20 years. Facebook is already popular enough that there are not enough people in the world for it to grow 50% / year much longer, so it comes down to what % of all human interactions are going to take place online. Granted things change, but I don't see the average person in south Africa is going to start tweeting 10 hours a day within 20 years. We could argue that more companies are going to place their information online but many already do that and it's not growing at 50% / year. It all comes down to the limits of exponential growth, computers are not going to hit hard limits within 20 years and few things can keep up with that level of growth.

justinsb 18y ago

It's about using the right tool for the job. It seems most of the companies you mentioned have decided that relational databases are actually the right tool. You mentioned... Google: Proprietary stack for document-orientated systems (search, GMail), use MySQL to run AdWords (their revenue business). http://xooglers.blogspot.com/2005/12/lets-get-real-database.html http://xooglers.blogspot.com/2005/12/lets-get-real-database.... Amazon: Major Oracle customer. Functionality is managed by modular teams, each of which has their own architectural choices, so difficult to generalize. Certainly in the early days was entirely Oracle (and look, it's a story about Oracle failing!) http://glinden.blogspot.com/2006/03/early-amazon-oracle-down.html http://glinden.blogspot.com/2006/03/early-amazon-oracle-down... Want you to use SimpleDB, but difficult to find Amazon groups actually eating the dog-'food'. eBay: Oracle. http://www.addsimplicity.com/downloads/eBaySDForum2006-11-29.pdf http://www.addsimplicity.com/downloads/eBaySDForum2006-11-29... LinkedIn: Oracle & MySQL. Custom caching layer on top to get round the 'graph' problems you talked about. http://hurvitz.org/blog/2008/06/linkedin-architecture http://hurvitz.org/blog/2008/06/linkedin-architecture OK, what about some others: Facebook: MySQL. Memcached for caching. Custom data stores for images and for inbox search (so non-relational for document storage again) http://glinden.blogspot.com/2008/05/scaling-facebooks-databases.html http://glinden.blogspot.com/2008/05/scaling-facebooks-databa... Wikipedia: MySQL. They're document storage, so it is possible to get document storage to work on MySQL. http://venublog.com/2008/04/16/notes-from-scaling-mysql-up-or-out/ http://venublog.com/2008/04/16/notes-from-scaling-mysql-up-o... Maybe it's just not sexy to stand up at a conference and say 'We architected this system to run on a relational database, in the normal proven way, and it runs wonderfully in production. We scaled it using partitioning, in the normal way. We're generating real money with the system.' You only hear a biased sample, which is why you think the companies you named are good examples of people that use non-relational databases.

wheels 18y ago
We seem to be oscillating between "key value stores are the way!" and "relational databases are the way!" Both have their places. If my notes were read as seeming to advocate the end of relational databases, please excuse me because that was certainly not my intent. Of course all of those companies use relational databases. Often they're the best tools for the job and in an IT landscape as large as their respective setups, of course they're the right tool for several jobs. But they've also got problem domains where they've decided RDBMSes are not the best tools for the job, which was my point to begin with. This thread started off with the assertion, basically, that if you weren't using a RDBMS to store everything, you probably didn't know anything about databases and I feel like we've (including the original poster) been slowly narrowing in on something closer to reality. As for the examples on the non-RDBMS side, BigTable, SimpleDB, Voldemort (+) and, well, the guy that I met with last week that wrote eBay Germany's search system and told me they had their own non-RDBMS storage system. + http://blog.linkedin.com/2009/03/20/project-voldemort-scaling-simple-storage-at-linkedin/ http://blog.linkedin.com/2009/03/20/project-voldemort-scalin...