Actually your cost is O(n) for the graph in the worst case, and the mysql index is worst case to O(log(n)) (as you implicitly point out), so really what we are

Actually your cost is O(n) for the graph in the worst case, and the mysql index is worst case to O(log(n)) (as you implicitly point out), so really what we are talking about here is speed in practice. I've found that in practice graph databases generally need more (in gigabytes / terabytes) fast random access (SSD / RAM), or very intelligent / lucky data storage strategies. Furthermore, adding data to a already large node can sometimes cause problems since the database will take steps to avoid fragmentation. This is also a problem in some kinds of manipulations in a traditional relational database, but generally you farm more information into its own table in though, which makes this problem less likely. Also, I find sharding harder on graph databases of sufficient complexity, although there are cases where it can be easier too. But if we're talking actual performance operations, generally relational databases preform as well or better than graph databases for a traditional SaaS or social network app, which relies more heavily on aggregate querying, something that is easier to make more performant for the types of scales and expected timelines that most of these apps operate on. As for your slides that you linked, joins are considered harmful for certain types of querying at certain scales, but you can usually work around these problems by either "doing the join in code", creating Entity–Attribute–Value models (EAV) for certain cases, or if you really want you can just use the MEMORY storage engine (and get that o(1) average case lookup time). Or at that point you can use multiple datastores if you need to. Anyway, I don't really know what my point is. I've used graph DBs before, and they were alright, but I find the cost of giving up SQL to be pretty high, and I actually enjoy some of the constraints that exist on the DB level for something like MySQL or Postgres. Plus, when you're ready to scale there are a bunch of people that can quickly get you 2x or 3x speed improvements without knowing much about the structure of your data. If you ever want someone to analyze your data to figure out your growth rate, or what have you, it is easier. It is easier for marketing to get weekly Excel exports of the data. Right tool, right job, yadda yadda.