No More Joins - SilverStripe and OrientDB | Hacker News Reader

No More Joins - SilverStripe and OrientDB

silverstripe.org

24 pointsreactor50 comments

The title of the post is throwing people off, because it's actually the opposite. Graph databases like OrientDB and Neo4j "Pre-Join" everything. Using nodes connected by relationships, every single "record" in your database knows what is connected to it without having to do a table or index scan/lookup. It's all pre-joined, so you avoid the pain of having to JOIN dynamically when you run your queries.

After years of MS SQL Server, switching to a graph database (I use Neo4j but it's the same concept) requires a mental mode change, but once you get past the "graph epiphany" you'll never want to go back.

This.

Graph DBs don't do away with JOINs...

they just do the JOIN on INSERT.

Two questions about that.

1) Wouldn't that have roughly the same performance impact on insert/update/etc. as building indexes? Possibly even more, as building an index (without foreign key constraints) only affects one table, whereas this would imply updating all tables with which this table has relationships?

2) Doesn't this require you to know all of the relationships your data has at insert/update, rather than at select?

1) No. It stores the id/address of the 'row' you are linking too, so there is no performance impact on insert/update/etc.

2) Yes, very much so.

EDIT: For a bit more clarity on how/why you'd use it.

Graph DBs are very good for something like a social network. You would store each person as an object/document and then you could have a simple array of ids for all that person's friends.

Then when you retrieve the person from the database, the database can automatically retrieve all of the friends very quickly as there is no need to do further searching - it already knows where all the friends are stored as their id/address is already in the document.

In a relational DB, you would have a table of friend->friend and would need to do a one-many join across that table.

Okay. I'm not sure I understand why that form of linking would be significantly faster than JOINs when you are properly indexing everything (or significantly faster on INSERT/UPDATE, for that matter).

To the second, it sounds like if you're willing to give up a substantial amount of the flexibility that SQL gives you, you can achieve performance gains. Isn't that true of any RDBMS, though? If you go through and denormalize heavily, you can make similar tradeoffs (maybe not the exact same ones, so there could be cases where a graph DB would be better, but it's hardly the blanket "joins are bad" that seems to be implied by the original post).

Yes, it is true that the major performance gains are for a (commonly used) subset of what is possible in SQL. But you need to keep in mind that you don't have to de-normalize or adopt some sort of design pattern in OrientDB for some use cases you would in SQL, instead you can just model your data.

It's faster, but it's not remarkably faster, no. The main place it becomes faster is deep joins - if you want the friend of the friend of the friend. If using joins that looks like LEFT OUTER JOIN bla a1 LEFT OUTER JOIN bla a2 LEFT OUTER JOIN bla a3 etc. If you've got much experience with SQL you should realize the performance impact of that. So graph dbs are best suited to highly networked problems.

Denormalize is something different, you're misunderstanding something I've said. With a graph DB, you still only have 1 copy of each person - you are just storing the 'joins' or ids/addresses of the 'rows' you want to join with ahead of time.

I certainly did not say that joins are bad, I was just answering your questions as to how a graph db differs and why it would perform better in certain specific circumstances. If you're in those circumstances then a graph DB is very useful.

Another nice part of a graph db is if you have a large collection of different objects in your programming language that all interact with each other. Those interactions can be stored directly in-line and allow for an ORM layer to be more efficient when retrieving the whole collection.

> The main place it becomes faster is deep joins - if you want the friend of the friend of the friend. If using joins that looks like LEFT OUTER JOIN bla a1 LEFT OUTER JOIN bla a2 LEFT OUTER JOIN bla a3 etc.

If you want all friends out to some specified distance n where n > 1, recursive CTEs are a much more sane solution that anything involving n levels of OUTER JOINs.

And if you just want specifically friends-of-friends-of-friends by joins, you want three levels of INNER JOINS.

> With a graph DB, you still only have 1 copy of each person - you are just storing the 'joins' or ids/addresses of the 'rows' you want to join with ahead of time.

More accurately, graph DBs store addresses (not ids/addresses) while RDBMS store ids (Foreign Keys) of the records you want to join with ahead of time. This means that to get from one record to a related record takes an additional level of indirection in an RDBMS compared to a graph database, but that doing so from many similar structured records to their equivalent linked records is more efficient in an RDBMS.

> Another nice part of a graph db is if you have a large collection of different objects in your programming language that all interact with each other. Those interactions can be stored directly in-line and allow for an ORM layer to be more efficient when retrieving the whole collection.

With a Graph DB instead of an RDBMS, you obviously wouldn't haven a ORM (Object-Relational Mapping) layer in any case.

At more than one level out

Recursive CTEs are not what one would traditionally call 'relational' and many relational databases certainly don't have them.

Some distributed graph databases do store ids and not addresses - there is no actual requirement that they be addresses, only that they be efficient to retrieve. So not actually more accurate.

People still call object-db mappers 'ORMs' even when dealing with document databases such as Google's bigtable or MongoDB. It's just an acronym at this point. [1][2]

[1] - http://mongomapper.com/

[2] - https://code.google.com/p/mongo-java-orm/

EDIT: By 'id' I'm referring to some unique hash or key that can be used to locate a document. By 'address' I'm referring to an actual on-disk location that can be directly loaded. Maybe my definitions clash with yours, I don't think this stuff is formally defined.

> Recursive CTEs are not what one would traditionally call 'relational'

I'm not a big fan of tradition for its own sake.

> and many relational databases certainly don't have them.

The only major SQL-based RDBMSs I can think of off the top my head that don't support recursive CTEs in their current version are SQLite and MySQL -- Postgres, Firebird, DB2, Oracle, and MS SQL Server all do.

There isn't much you can't do with a modern RDBMS. If you want to denormalize relationships, you can do that. If the queries are too repetitive or hard to write, you can use views or stored procedures. One thing that I find peculiar about RDBMSs is that foreign key relationships are tracked for integrity, but they are not used to make joins easier by automatically inferring the kind of join implied by a foreign key field. But that isn't a limitation on power.

> One thing that I find peculiar about RDBMSs is that foreign key relationships are tracked for integrity, but they are not used to make joins easier by automatically inferring the kind of join implied by a foreign key field.

Huh? Could you expand on this?

A foreign key is frequently just an integer. You can create a foreign key constraint that checks that the integer exists in a field in another table, but that information isn't used by the database for anything other than checking that constraint (that I know of). In a select query, if you want to resolve that relationship in a join, you have to restate it as if the database knows nothing about it. To make the join use the foreign key information, you'd have to invent some new syntactic sugar, so that's a potential valid criticism.

> In a select query, if you want to resolve that relationship in a join, you have to restate it as if the database knows nothing about it.

Okay, I see what you are saying. So, what you'd like is something like NATURAL JOIN that instead of using matching column names to infer join conditions it would use declared FK relations. That would be convenient -- but possible complicated by the possibility of multiple different FKs from one table to another (though the syntax could involve specifying the FK rather than the target table, which would solve that.)

e.g., if you had

  CREATE TABLE emp (
    emp_id INTEGER PRIMARY KEY,
    manager_id INTEGER FOREIGN KEY REFERENCES emp JOIN AS manager,
    hr_rep_id INTEGER FOREIGN KEY REFERENCES emp JOIN AS hr_rep,
    name VARCHAR(50),
    ...
  );

You could do something like:

  SELECT emp.name AS "Employee", manager.name AS "Manager"
  FROM emp
  NAMED JOIN emp.manager;

That's pretty much it.

If you want to do it with a minimum of new syntax, you could defer naming the join until the select, as you normally would:

  CREATE TABLE emp (
    emp_id INTEGER PRIMARY KEY,
    manager_id INTEGER FOREIGN KEY REFERENCES emp,
    hr_rep_id INTEGER FOREIGN KEY REFERENCES emp,
    name VARCHAR(50),
    ...
  );

  SELECT emp.name AS "Employee", manager.name AS "Manager"
  FROM emp
  NAMED JOIN emp.manager_id AS manager;

I hadn't given any thought to the syntax, but that looks pretty nice and tidy.

Edit: NAMED JOIN isn't really appropriate anymore with that change in syntax. Something like DECLARED JOIN might be better.

Yeah, I originally had thought to do it more like that, but I figured that the big win from having language-level support for something like this was the ability to have clear semantic definitions in the declared relations and concise queries, so I thought naming in the Foreign Key was the best way.

But I can see it either way.

I'd leave it to experts to design the best syntax, because they could foresee all the possible ramifications of different choices. I think we've clearly articulated the ends and some potential means.

You might have to give the join a name in the query in either case, because what if you want to go two levels deep, e.g. join in your boss's boss? Both can't be manager.

All I'm interested in is making the queries more concise. Otherwise, I like the loose coupling between related entities in the relational model. I would have been hesitant to add join information to the table declaration if it wasn't already there. But since it's already there as a constraint, you might as well get all the mileage you can out of it.

1) I think you want to compare apples to apples. Linking up validated primary key relationships should be faster in OrientDB. I am not sure how you handle other types of relaitonships.

2) exactly. The tradeoff is that SQL lets you easily do ad-hoc analysis (which isn't an important use case for a lot of applications). But also in SQL you do have to know about foreign key relationships at insert/update time to validate those.

That's true for keys, but that really only covers a subset of what JOINs can do -- if I want to use things like dates, times, quantities of things... and frankly, if I want to do something other than JOIN on equal values, say join on greater or less than or between, then that's an entirely different thing altogether.

I've spent over a decade living in relational databases . . . currently senior db architect. I like the joins. I work and think in sets of data and not objects.

But, I do spend a good deal of time transforming this data for application consumption, so I suppose this kind of database would cut down that time.

With the possible downside of making it very difficult to use the data in another application. So there's that.

Sets are the most elemental way to abstract data. Not all data are graphs, but all data are sets. A graph is a set of vertices and a set of edges. So there's no loss of generality in using sets.

"OrientDB does away with the concept of a join table, one of the most significant bottle necks in relational databases."

I'm having a hard time not reading this as "joins are too hard for me to understand, so I love the idea of a no-join database"

Agreed. It seems at best that they're simply reformalizing RDBMSs in a different way, and at worst they're losing something (depending on how inheritance and linkSets work). Not all joins are analogous to single inheritance, and multiple inheritance is intrinsically complex in pretty much the same way JOINs can be, so where's the win?

I must disagree. Conceptually, JOINs are pretty simple. In fact, so simple that it admits a straightforward mathematical description.

To understand the difference between JOINS and direct links in a Graph Database look at: http://www.slideshare.net/lvca/why-relationships-are-cool-bu...

Slide 18 is titled "The JOIN is the evil!"

I will probably stop laughing at that, but I can't guarantee when.

A sales presentation is not going to convince me.

I am interested in static guarantees of data integrity. I do not want to be worried whether I am inserting the wrong kind of data to a database, or whether by deleting some data, I am putting the database into an inconsistent state. For this particular need, I have found nothing better than relational databases in practice.

There is still room for improvement, e.g. http://math.mit.edu/~dspivak/informatics/talks/CTDBIntroduct... , but that category-theory-based model is a refactoring and extension of the relational model, not a rejection of it.

I don't get the supposed benefits of direct links over joins. Index lookups are O(log n) or close to O(1) for B-tree and hash indexes, respectively. You can model any kind of graph in a relational database.

O(log n) is ok with small data, let's say up to thousands. But when you've millions or billions of record also the O(log n) takes time. It's about size. Until yesterday we managed small database in comparison to the today's BigData-Base. That's why a Graph Database makes sense today, much more than yesterday.

You're not disagreeing with anything I wrote. I said multiple inheritance is intrinsically complex in ways JOINs can be. JOINs can be used to do all kinds of wild and whacky things, they can also (easily) lead to horribly slow queries. They may be conceptually simple, but so is Universal Algebra.

We are disagreeing.

Multiple inheritance does not admit an elegant (per Dijkstra: simple yet effective) mathematical description. Since it is a programming construct, however, there must be some description of it, which we also know must be ugly - we have ruled out it being elegant.

JOINs are not intrinsically complex in the way multiple inheritance is. And they need not have bad performance either: it is just that relational databases have not caught up yet with the advances in category and type theory, and suffer from that accordingly. Saying schema-backed databases are intrinsically bad because SQL databases suck is just like saying static typing is bad because it sucks in Java and C++.

And, yes, Universal Algebra is one big source of inspiration of mine, precisely because it leads to simple descriptions of large classes of structures.

Ok, i'm arguing that trading conceptually more complex multiple inheritance for conceptually simple JOINs isn't a win because multiple inheritance won't protect you from stuff blowing up. You"re just against multiple inheritance because it's a conceptual mess (I agree) without allowing for the argument that it might work better in practice (which I have anticipated and dismissed).

Monopoly is concpetually more complex and less cleanly defined than Go, but not easier to play. I am saying that multiple inheritance is not Monopoly, but Go with extra, badly written rules.

This is a pretty minor disagreement. You ignore a possibility, I mention it in passing and dismiss it.

(Perhaps you're hung up on my stating that JOINs can be complex — conceptually complex is not the same as complex, just as universal algebra might breezily describe a realm of mathematics that has devoured the attention of geniuses for centuries.)

what's a "join table" even? This speaks to a lack of understanding of how relational databases should best be used.

I believe they're referring to tables that have just two columns, both of which are foreign keys to other tables. They're used to create many-to-many relationships.

I usually call them staple tables.

No it doesn't. It is a common term for tables that are just foreign keys to other tables, generally for expressing many to many relationships.

ok - that does indeed make some sense.

I'm not so sure that it has anything to do with complexity of understanding. Joins make scaling RDMSs horizontally much more difficult, if not impossible in certain situations.

I also notice that the only performance comparison against a relational database is where it says "A single server does the work of about 125 servers running MySQL". I was under the impression that MySQL is especially bad at joins, so I'd be more convinced by benchmarks involving Postgres or SQL Server.

Aside from whether or not this method of linking data increases performance, there is a huge cost in relational databases to the complexity created by many-to-many relationships. Even if the performance were the same, the dispersion of data makes it a nightmare to pull together a hierarchical object out of many different database tables, and then to deduplicate the data that is cross-joined (ie in the case of a user with multiple shipping addresses...join user on address => you get the same user record for every instance of address, which then has to be consolidated in code). Then do that times 5-10 other tables and you have yourself a very messy query that is very slow.

These problems can be solved with KV stores, but at the cost of human readable databases. Likewise, with ORMs, you sacrifice performance and direct understanding of how the database is being queried.

There are many advantages to a document-graph model like orientdb for these reasons.

>in the case of a user with multiple shipping addresses...join user on address => you get the same user record for every instance of address, which then has to be consolidated in code

One solution is to use two queries: one to get the user with the user's key, then a second to get the addresses that match that user key.

If you want to get all the user fields and all the addresses in one query, you can do a join with a group by on user and aggregate the addresses. In Postgres, you can aggregate into an array with array_agg(). More recent versions have json_agg() to aggregate into json.

Under no circumstances should you have to deduplicate data in code. That's what the database is for.

These queries can get tricky to write, but I view them as enjoyable puzzles, like writing regular expressions. The payoff for writing the right query is that it's faster than fetching too many records and deduplicating in client code, and the SQL is short and declarative.

"OrientDB does away with the concept of a join table, one of the most significant bottle necks in relational databases."

join table? Does he mean that you are able to join tables in queries? This is awesome! It might be a bottleneck but its also on of RDBMS best features. I also would revisit the bottleneck claim with todays SSDs and fast CPUs.

"...support for inheritance in OrientDB is useful ... to avoid joining tables to mimic class inheritance."

I have never used joins to "mimic class inheritance" and dont understand why you would ever want to do such a thing. Can someone enlighten me?

I think they are talking about a junction table.

I also think they're talking about a class table inheritance pattern, where you have a base table that stores the data for the base/abstract class, then more tables to store the data for classes that extend the base class. You could use junction tables to model that relationship.

http://en.wikipedia.org/wiki/Junction_table

OrientDB has some great explanations on their github wiki. Here is their thoughts on why references are better than joins: https://github.com/orientechnologies/orientdb/wiki/Tutorial:...

And this page gives an overview of relationships in general with OrientDB: https://github.com/orientechnologies/orientdb/wiki/Concepts#...

Personally I have found the relational model limiting for performance in certain use cases and limiting in terms of mental overhead in others. I have used MongoDB a lot, however only having embedding to model relationships is also very limiting.

The promise of OrientDB is a documunt store with support for embedding (and class inheritance), but also being able to use references rather than joins.

What embedding and references have in common is that you have to do more up front work to define your relationships. You can think of it as freezing the possible queries available in a relational model to the subset that you actually use. I think this is a great default for most applications.

However, it is not what an analyst wants for doing ad-hoc queries, which SQL databases are great at. And even application creators often later decide that they want to do some ad-hoc analysis of data sitting in the database. This is where polyglot persistence should shine and you can have multiple databases that index the data in different ways.

"As many relational databases such as MySQL do not have native support for inheritance this concept is approximated by joining normalised tables which together have all the attributes necessary to build a subclass object."

This suggests to me that their problem is not JOIN but a dogged insistence on a particular style of object-relational mapping. If you're having to do complex joins to retrieve a single persisted object you're probably coupling your objects and the database too closely.

That said, a customizable CMS is a natural fit for both document databases and graph databases. All of the ones I've seen built on relational DBs have extremely generic schemas that allow users to build their own quasi-schemas on the fly, at which point you've sacrificed pretty much every benefit the relational model brings.

Good timing. I was waiting until a big player bought into OrientDB. SilverStripe may not be as big as Drupal, Joomla or WP but they have a large user base.

Since the storage model is plain Javascript objects - what's the situation concerning offline sync on mobiles (as in, run a lightweight db server on the device and let it replicate with the db in the cloud)?

I think we've read this story before. It turns out it is a tragedy.

Reply on news.ycombinator.com