4 ms·

The issue is that if you can avoid joins long term, then you really either don't have enough data, enough complexity, or very rarely managed to have a data set

The issue is that if you can avoid joins long term, then you really either don't have enough data, enough complexity, or very rarely managed to have a data set that doesn't need joins. If it is option 1 or 2, you just didn't need joins YET. When the time comes that 1 and 2 no longer apply it will be VERY hard to add them. Sure you can use both types of databases where it makes the most sense but at that point you might as well just use the "NoSql" functionality in the relational db. PSQL does a JSON doc store VERY well and even allows deep joins when time comes. I personally never saw much benefit to the graph databases. Sure the are great for a few data structures but most of the speed differences came them from being in memory more than anything else. Pretty much everything is fast with a good data structure design and everything in memory.

EGreg 9y ago
Actually major graph databases store data on disk as well. That's not the reason they are faster. The reason is that all the pointers point directly to the data. Consider how you'd get the "top 10 books, and their related authors, and their related biographies". 1. A graph database would literally just look at an index of books, and then grab the book records. A relational database would do the same with an index, so far so good. 2. Now comes the difference. For each book, the graph database would just load the list of pointers to related authors and load those. And for each author, it would load the list of pointers to related biographies, which have pointers to related pictures etc. And in O(jk) where j is the number of books to return, and k the maximum number of things to get per book, it's done. 3. Now consider the same step for a relational database. After getting the books, it has to load the authors, and search it for each author. This takes O(k log N) where N is the total number of entries, and grows (albeit slower and slower) with increasing amounts of data. Then once every author record is loaded, it has to enumerate all their ids into a giant list and do it again. The list can be stored incrementally and the searches can be parallelized but at the end of the day ALL JOINS have an extra O(log N) factor, which is what slows down the database, usually by a factor of 10 for data that's in the millions or billions of rows. 4) The design of a graph database naturally encourages using indexes. In relational databases you have to remember to add them. And even after you do, the relational database takes log N longer to do all the joins. And joins are done very often in social networks, fetching related stuff, and other things in a normalized schema. You can do all the relational algebra stuff while walking a graph, too. In fact any relational database can be turned into a graph database by just adding a variable-length list of "pointers to related data" to each record which would point to the actual location of the rows in the related table's index. And then manage all relations between rows not as joins but as entries in these lists. And finally, implement support for a graph database language alongside SQL. However, I have not seen any such extensions to InnoDB or Postgres etc. which turn them into graph databases.
- mohaine 9y ago
  I understand that they do persist to disk and store data differently but the ones I've seen used in practice are in memory during runtime. It as been a few years but so maybe this has changed. Any examples? Graph databases also are only fast when doing graph transversal lookups. They all have index just like RDB. Sure you got from parent->child->grandchild quickly but how to do you find the parent in the first place? An index normally.
  - EGreg 9y ago
    But the parent is one lookup and the children are 1000. Thats why.
    - mohaine 9y ago
      This is only if the 1000 children are already in memory. Otherwise it is still 1000 lookups, by index. This is why the Graph Dbs on the market tend to be in memory. I'm not saying Graph DBs don't have their place. They do, but they are the wrong answer for MOST datasets.
      - EGreg 9y ago
        NO. Each lookup thereafter is NOT by index. That's where the savings come from. The pointers already contain the exact block where to load the info from.
thehardsphere 9y ago
I have noob questions about what you've written here. I apologize for asking them here but you seem like you think clearly and know what your are talking about. If you are in case 3, then is that when NoSQL allegedly starts paying off? If so, is the payoff in actual performance or just not having to write SQL? I know you said that you could just use the NoSQL features of the relational DB. If you really truely know for certain that you will never need to join your data, then isn't using an entire relational DB software package a lot more overhead?
- mohaine 9y ago
  I case 3 you get get some real speedups, but you usually have to design the db layout for the use case. Step one is "How am I going to lookup this data" then design the data structures for that use case. Often(but not always) in these cases the NoSql db is just a lookup db with the system of record being a somewhere else and data is transformed into multiple data sets for lookup. IMHO, most of the NoSQL hype was developers not wanting to learn sql/ddl along with a lot of resume padding. It is also important to note that NoSQL no longer means "No SQL" but really is now "Not Relational and/or ACID" (https://en.wikipedia.org/wiki/ACID https://en.wikipedia.org/wiki/ACID). The only thing worse than SQL is everything else created to replace it. Many "NoSQL" products use a limited SQL like syntax as their only query format. As for relational DB overhead, there is no reason for it be more then NoSQL(see sqlite) unless you are willing to give up part of ACID. Special cases like this are another use case for NoSQL but you probably want ACID unless you have data/throughput to make it nonviable. Otherwise you have it just ignore issues (normally what happens) or code for them in your app.

EGreg 9y ago

Actually major graph databases store data on disk as well. That's not the reason they are faster. The reason is that all the pointers point directly to the data. Consider how you'd get the "top 10 books, and their related authors, and their related biographies". 1. A graph database would literally just look at an index of books, and then grab the book records. A relational database would do the same with an index, so far so good. 2. Now comes the difference. For each book, the graph database would just load the list of pointers to related authors and load those. And for each author, it would load the list of pointers to related biographies, which have pointers to related pictures etc. And in O(jk) where j is the number of books to return, and k the maximum number of things to get per book, it's done. 3. Now consider the same step for a relational database. After getting the books, it has to load the authors, and search it for each author. This takes O(k log N) where N is the total number of entries, and grows (albeit slower and slower) with increasing amounts of data. Then once every author record is loaded, it has to enumerate all their ids into a giant list and do it again. The list can be stored incrementally and the searches can be parallelized but at the end of the day ALL JOINS have an extra O(log N) factor, which is what slows down the database, usually by a factor of 10 for data that's in the millions or billions of rows. 4) The design of a graph database naturally encourages using indexes. In relational databases you have to remember to add them. And even after you do, the relational database takes log N longer to do all the joins. And joins are done very often in social networks, fetching related stuff, and other things in a normalized schema. You can do all the relational algebra stuff while walking a graph, too. In fact any relational database can be turned into a graph database by just adding a variable-length list of "pointers to related data" to each record which would point to the actual location of the rows in the related table's index. And then manage all relations between rows not as joins but as entries in these lists. And finally, implement support for a graph database language alongside SQL. However, I have not seen any such extensions to InnoDB or Postgres etc. which turn them into graph databases.

mohaine 9y ago
I understand that they do persist to disk and store data differently but the ones I've seen used in practice are in memory during runtime. It as been a few years but so maybe this has changed. Any examples? Graph databases also are only fast when doing graph transversal lookups. They all have index just like RDB. Sure you got from parent->child->grandchild quickly but how to do you find the parent in the first place? An index normally.
- EGreg 9y ago
  But the parent is one lookup and the children are 1000. Thats why.
  - mohaine 9y ago
    This is only if the 1000 children are already in memory. Otherwise it is still 1000 lookups, by index. This is why the Graph Dbs on the market tend to be in memory. I'm not saying Graph DBs don't have their place. They do, but they are the wrong answer for MOST datasets.
    - EGreg 9y ago
      NO. Each lookup thereafter is NOT by index. That's where the savings come from. The pointers already contain the exact block where to load the info from.

thehardsphere 9y ago

I have noob questions about what you've written here. I apologize for asking them here but you seem like you think clearly and know what your are talking about. If you are in case 3, then is that when NoSQL allegedly starts paying off? If so, is the payoff in actual performance or just not having to write SQL? I know you said that you could just use the NoSQL features of the relational DB. If you really truely know for certain that you will never need to join your data, then isn't using an entire relational DB software package a lot more overhead?

mohaine 9y ago
I case 3 you get get some real speedups, but you usually have to design the db layout for the use case. Step one is "How am I going to lookup this data" then design the data structures for that use case. Often(but not always) in these cases the NoSql db is just a lookup db with the system of record being a somewhere else and data is transformed into multiple data sets for lookup. IMHO, most of the NoSQL hype was developers not wanting to learn sql/ddl along with a lot of resume padding. It is also important to note that NoSQL no longer means "No SQL" but really is now "Not Relational and/or ACID" (https://en.wikipedia.org/wiki/ACID https://en.wikipedia.org/wiki/ACID). The only thing worse than SQL is everything else created to replace it. Many "NoSQL" products use a limited SQL like syntax as their only query format. As for relational DB overhead, there is no reason for it be more then NoSQL(see sqlite) unless you are willing to give up part of ACID. Special cases like this are another use case for NoSQL but you probably want ACID unless you have data/throughput to make it nonviable. Otherwise you have it just ignore issues (normally what happens) or code for them in your app.