5 ms·
Can I ask a simple question about efficiency? It seems to me that graph databases are far more efficient than relational ones for most tasks. That’s because a
by EGreg 8y ago
Can I ask a simple question about efficiency?
It seems to me that graph databases are far more efficient than relational ones for most tasks.
That’s because all lookups are O(1) instead of O(log N). That adds up. Also, copying a subgraph is far easier, and so is joining.
Think about it, when you shard you are essentially approaching graph databases because your hash or range by which you find your shard is basically the “pointer” half of the way there. And then you do a bunch of O(log N) lookups.
Also, data locality and caching would be better in graph databases. Especially when you have stuff distributed around the world, you aren’t going to want to do relational index lookups. You shard — in the limit you have a graph database. Why not just use one from the start?
So it seems to me that something like Neo4J and Cypher would have taken off and beat SQL. Why is it hardly heard of, and NoSQL is instead relegated to documents without schemas?
- rtpg 8y agoIn practice enterprise applications do a lot of relational operations. Graph DBs might be valuable for a lot of problems, and it does feel like something like Neo4J would make a lot of sense for stuff like social networks, but for business records stuff isn't really that spread out
- slifin 8y agoAlthough if you want versioning to the attribute level, you'd want something that spread out, see Datomic
- indigo945 8y agoA hash index is O(1) no matter what language it's called from. The reason most people don't use hash indices very often is that they do not allow you to do a lot of useful things that you often end up wanting to do, such as retrieving all values within a given range.
- EGreg 8y agoI still don’t think it’s O(1) in the limit. Why not just store pointers to the data, or one indirection if the data can be moved?
- barrkel 8y agoChasing pointers (on the same medium) is usually slower than the access patterns that databases usually use. First, a database can have hash indexes instead of btree indexes, so lookups can be O(1) too, but it turns out that btrees are often better because they can return range results efficiently, and finding the range in a btree is only logarithmic for the first lookup. If your index is clustered - if it covers the fields needed downstream in the plan - no further indirections are needed and locality is far better than a hash lookup. For example, a filter could be efficiently evaluated along with the index scan. And if your final results need to be sorted, major bonus if the index also covers this. Second, it's best to think of databases doing operations on batches of data at a time. Depending on your database planner, different queries will tend to result in more row-based lookups (MySQL generally does everything that isn't a derived table, uncorrelated subquery or a filesort in a nested loop fashion) but others build lookups for more efficiency (a derived table in MySQL, or a hash join in Postgres). The flexibility to mix and match hash lookups with scans and sequential access - which are usually a few orders of magnitude faster than iterated indirection - means it can outperform graph traversal that is constantly getting caches misses at every level of the hierarchy. The reason NoSQL and document databases suck from a relational standpoint is that they are bad at joins, and work better if you denormalize your joins and embed child structures in your rows and documents. Add decent indexes to NoSQL and they gradually turn back into relational databases - indexes are a denormalization of your data that is automatically handled by the database, but have nonlocality and write amplification consequences which can slow things down. In terms of distribution, a relational plan can be parallelized and distributed somewhat easily if your data is also replicated - sometimes join results need to be redundantly recalculated or shuffled / copied around - and most analytics databases use this approach, though usually with column stores rather than row stores, again because scanning sequential access is so much faster than indirection. Joins don't always distribute well, is the main catch.
- nostrademons 8y agoDepends a lot on the actual access patterns of your data. Many recent web & mobile apps have a lot of screens where you just want to grab one blob of heterogenous data and format it with the UI toolkit of choice. Or if they do display multiple results, it's O(10) rather than O(1000) or O(1M). Chasing pointers is fine for use-cases like this, because you do it once and you have all the information you're looking for. This is also behind the recent popularity of key/value stores and document databases. If all you need is a key/value lookup, well, just do a key/value lookup and don't pay the overhead of query parsing, query planning, predicate matching, joins, etc. When I was working on Google Search > 50% of features could get by with read-only datasets that supported only key/value lookup. You don't need a database for that, just binary search or hash indexes over a big file.
- ako 8y agoGraph databases are great for retrieving existing data with associated data. The power of SQL comes from the fact that you can easily create new information out of the data: create new sets, group by certain features, aggregates on certain features. It's a lot more powerful than just store and retrieve.
- bonesss 8y agoPeople forget that SQL isn't just Query (DQL), it's also definition (DDL), manipulation (DML), control (DCL), and transaction control (TCL), language [0]. Checkout that platform that a full-blown Oracle license can provide to your DBA... It's definitely more than just CRUD. - [0] https://www.oreilly.com/library/view/discovering-sql-a/9781118002674/ch002-sec022.html https://www.oreilly.com/library/view/discovering-sql-a/97811...
- asark 8y agoN4J's a lot slower at tons of common tasks. If you look into its underlying data model, it's clear why. It achieves the speed it does at certain graph-traversal operations by storing its data in such a way that it's highly specialized for those operations—one would expect this to come at a high cost for other operations, and sure enough, it does. It also doesn't bother with tons of consistency guarantees and such that you (may) get from, say, PostgreSQL. Yet is still slower for many purposes.