Get to know your ORM and take control of joins.

http://use-the-index-luke.com/l/sql/join/nested-loops-join-n1-problem

by fatalmind • 14 years ago

40 23 14 years ago

lucian19002• 14 years ago

Not all ORMs give you the ability to do any joins, and even fewer give you subqueries and proper group by.

Relational libraries like SQLAlchemy (Python) and Korma (Clojure) are much better at letting you use your relational database conveniently.

BadassFractal• 14 years ago

How would you compare Korma to say.. ActiveRecord?

lucian19002• 14 years ago

I've never used active record, but from what I've read it's an ORM. Both SQLAlchemy and Korma expose relational concepts directly.

SQLAlchemy also has an optional ORM built on top of the relational abstraction.

jiggy20112• 14 years ago

I have noticed some unexpected behaviour in the past with joins vs N+1 selects.

I was using an ORM (hibernate) for a webapp connected to mysql. When I turned on the query log I found a lot of N+1 Select stuff going on.

I made the joins explicit, expecting a performance gain. When I tested the performance again, using apache benchmark and also a query profiler I discovered that there was absolutely 0 performance difference between the 2 solutions. These were with some reasonable sized datasets, ~20k entries across 2 tables.

I guess this is because of some sort of optimisation done at the mysql level.

I guess that my experiment did not take into account running the same set of queries more "spaced out" in time with other different queries (to account for caching etc).

Perhaps though it is possible that ORM designers are aware of these kind of optimisations so don't really worry about these queries as much as might be expected?

nl• 14 years ago

When I tested the performance again, using apache benchmark and also a query profiler I discovered that there was absolutely 0 performance difference between the 2 solutions.

Benchmarks are hard.

What were you testing exactly? The behaviour you are seeing is surprising, but if the database server is on the same physical server as the app server and you are testing for response time without loading the server I could see how it could happen.

Did you have indexes setup to support the joins?

Did you have sufficient RAM for the join to be done in memory?

Was the database server hitting IO limits?

fatalmind• 14 years ago

Besides your points, we must also consider that MySQL does neither support hash joins nor sort/merge join. MySQL it just not very good at joining.

Nevertheless, a MySQL join should never be slower than the N+1 select approach.

jiggy20112• 14 years ago

The test was done with DB and HTTP servers on the same box. I tested both the HTTP response times from another box and also the time for the SQL queries to return inside the same box. Indexes were setup for the joins and there would have been enough RAM to store the dataset.

I did not really bare IO in mind doing the test because if IO was the bottleneck then I would have optimised enough.

Certainly a bad test from anything approaching a scientific view but I had expected to see a performance difference even in this scenario (especially when testing the turnaround between the Java app and Mysql).

I think my faulty logic at the time was that N+1 selects would be slow because of the overhead of parsing multiple queries. What led to to that conclusion was that I had previously optimised an old PHP app that was using mysql_query() to use joins rather than millions of selects and more or less got 10x performance back.

_ea1k• 14 years ago

I do find it surprising that the results were identical. Having said that, my experience is that over low-latency connections N+1 selects are not as bad as they are often represented to be. I've occasionally chosen to accept an N+1 for a 5 row list of search results vs. "optimizing" to a JOIN for exactly this reason. Depending on the query plan, search limits, sort parameters, etc, the performance differences can be fairly non-intuitive.

I don't think this explains your case, though, where N=20k. I'm not sure what could have been going on there.

mdasen• 14 years ago

I have one possibility of what might be going on.

When you have multiple joins that aren't one-to-one mappings you get all of the different combinations in the result set.

Let's say that you have 5 people, each with 5 addresses and 5 phone numbers. The result set wouldn't have 55 rows (5 people + 25 phones + 25 addresses), but 125 rows (a row for each combination). The difference gets larger as the numbers get larger (for 100 addresses and phones per person, it's 1,005 vs. 50,000). Your ORM also needs to figure out that semi-mess and when you get to large numbers of rows, that's a lot of rows to process.

  John | Address 1 | Phone 1
  John | Address 1 | Phone 2
  John | Address 1 | Phone 3
  John | Address 1 | Phone 4
  John | Address 1 | Phone 5
  John | Address 2 | Phone 1. . .

So, you're potentially pulling back a ton of excess data. Phone 1 will appear 5 times in the result set and then the ORM has to de-duplicate that. Likewise, Address 1 shows up 5 fimes in the result set and John shows up 5 times in the result set and the ORM needs to deal with it. Likewise, it's a lot of excess data over the wire and a lot of excess data to even process into a hash.

Now, Hibernate has a way around this. It's been a while, but it's something along the lines of setting it to fetch related entities in batches (EDIT: doing slight Googling, but not checking it in code, it's the @BatchSize annotation and @Fetch annotation that you'll want to look into). In that case, Hibernate basically does a "SELECT * FROM people" and then a "SELECT * FROM addresses WHERE person_id IN (list_of_people_ids_from_last_query)" and a "SELECT * FROM phones WHERE person_id IN(list)". That way, Hibernate gets 5 people records plus 25 address records plus 25 phone records (55 rows in total) and there aren't any duplicates that need to be weeded out, etc. It's three queries which is more than 1, but a lot fewer than the looped queries without the cartesian product.

This is the behavior that Rails' Model.includes(:relation) and Django's Model.objects.prefetch_related('related_set') use. There was a discussion (possibly years ago) on the django-developers list about why select_related('related_set') didn't work on reverse foreign keys and this is the reason why.

ecopoesis• 14 years ago

Or better yet, ditch your ORM and learn SQL.

ORMs are an antipattern. They save you a little time and effort up front, but when you inevitably need to do something that's not basic CRUD you end up wasting an immense amount of time fighting your tools.

Don't fight your tools, just write SQL.

chimi• 14 years ago

People ask me, "Which language should I learn first?" I always say, SQL. If you know SQL you can do more than a lot of programmers who don't know SQL and SQL makes for better programs too. Win-Win.

ufo• 14 years ago

Come on, although SQL is declarative and relational, it is still very low level, has terrible support for abstraction and has all sorts of incompatibilities depending of the database implementation you use. I can't believe we are already in the 21st century and good relational libraries are not yet the standard solution.

einhverfr• 14 years ago

Yeah I was writing a blog on long SQL queries and why a 200 line SQL query is a breeze to maintain compared to a 200 line Perl or C function. And not to mention your 200 line SQL query does a lot more than you can do in 200 lines in any other language.

What I concluded was that we debug most languages line by line, like moving through a linked list. SQL is much more efficient. A query, if it is well structures (no inline views or UNIONs) is a small set of sections, each of which is broken down further. So instead of reading through a query line by line, we figure out which section to look at, which relations are involved and debug that way. It's like searching a btree instead.

typicalrunt• 14 years ago

There must be a way to upvote this comment more than once... :)

I always get strange looks from my fellow programmers when I suggest that we just ditch the ORM and use straight SQL. With some complex queries, like generating reports, I had a much easier time using iBATIS many years ago than hacking through ActiveRecord's oddities. AR is good for simple select/insert/update, but once you get into UNIONs and nested subqueries, you're fighting AR more than you should be.

generalk• 14 years ago

ORMs -- in my case ruby's ActiveRecord -- solve nearly every use-case I have. Find a record by its primary key; get a record and all of the associated records from another table; update a record with a bunch of data? Why should I write any of that SQL? It's a waste of time.

Is ActiveRecord running n+1 queries every time you call a method? You're doing it wrong. Ignorance of how an ORM works is not an indictment against ORMs.

Is ActiveRecord generating really bad SQL for the fifty-table report you want to generate? Fine, ditch it. Run your own custom-written SQL, or a stored procedure, or whatever. Just because an ORM can't write all the SQL you'll ever need does not mean that they're useless.

mattmanser2• 14 years ago

They're a very effective tool.

I have hand coded and maintained a lot of SQL. And you know what's not fun? Adding or removing a column and going through all the selects, updates, inserts and manually changing them all and still getting bit by the 'Table X has no corresponding column of type Y' for a piece of the system used once in a blue moon.

And every time you want to add a new class creating the table, creating all the boilerplate select, insert, update statements that are exactly the same as the thousands of times I've done this before.

All that pointless busy worked done away with in a second. In a couple of keystrokes.

You, in my opinion, do not know what you're missing.

That's what an ORM is for. It's not a 'little time'. It's only a 'little time' if you don't actually do serious business coding where there are often 100s of tables to effectively solve a problem domain.

An ORM will dissipate that entirely. And when you want to drop down to hand coded SQL, you can! Best of both worlds!

The only problem with ORMs is when novices don't understand what they're requesting the DB to do.

And guess what, SQL has exactly the same problem!

crazygringo• 14 years ago

I honestly have no idea what you're talking about.

"Adding or removing a column and going through all the selects, updates, inserts..."

If you're adding a column, you're adding functionality to the program, so of course you're going to have to add the column everywhere it's used! And if removing, then likewise. Because you have code depending on the new/old column that needs to be changed.

There's nothing boilerplate about any of this. Every column has unique functionality and integrates into my code in its own unique way, and needs to be treated as such.

In fact, going through all the code manually makes sure you discover the once-in-a-blue-moon cases where you need to change the behavior.

Using an ORM isn't going to help any of this at all.

Or, if your new column is exactly the same as 80 other columns in the table, which are all used in the same way, then you probably shouldn't be using columns at all, but rather rows in an id-attribute-value format, which solves your whole problem of boilerplate code.

andybak• 14 years ago

You assume that the only people who want to use an ORM as those who don't know SQL.

evilbit2• 14 years ago

Precisely!

I've been using ORM pattern throughout my career, and have even designed/built one 10 years ago because what was available at the time wasn't gonna cut it functionality- and performance-wise for the system we were building (a real-time bond trading system). Nowadays most mainstream ORMs do the job rather adequately.

Having said that, I have a fair share of gripes against most of them, but I still find that people who bitch the most about ORMs are those who understand it (and the problem it tries to solve) the least.

evilbit2• 14 years ago

If you think you can avoid knowing SQL by using ORM, you don't understand what ORM is and what problem it tries to solve.

Namely, what you can't avoid, if building an object-oriented system, is that you ultimately need to map those DB values to your live objects. Whether you end up using an off-the-shelf ORM or you hand-code the SQL yourself is less relevant.

Odds are if you eschew an ORM in favor of hand-coded SQL layer, you'll end up writing one anyways - only you're likely to do a shittier job of it than people who understand the problem area far more intimately (e.g. Hibernate committers).

RHSeeger• 14 years ago

I tend to find ORMs fantastically useful when working with code for front end web sites (ie, just reading data in simple ways) and raw SQL more useful when working on back end/business logic code. Specifically, if I'm going to need to do complex joins, inserts, updates, etc I'll use raw SQL... if I'm going to just read data I'll use an ORM.

I'll admit, though, that I'm a big fan of having a separate table that has the "front end view" (read: denormalized) of the data for the ORM to read from, especially in cases where the raw data tables are fairly complex.

dguaraglia• 14 years ago

I've been using various ORMs for the last 6 years (Django ORM, SQLAlchemy and EntitySpaces are the ones at the top of my head) and only in very rare occasions I've had to write my own SQL code to cover a case the ORM wouldn't cover.

A big issue nobody is addressing here is that using "pure SQL" requires you to use crappy data structures (say, a dictionary, "associative array" or, most likely, a simple array in languages like C/C++) to access and push the data. So, instead of having something simple like:

    user = User.objects.get(username='ecopoesis')
    ...
    # 100 lines of business logic that uses the 'user' object.
    # Methods like 'set_password' that calculates a hash of a
    # password and stores it in the object make my life much easier
    # by keeping the logic close to the data.
    ...
    user.save()

I first have to go through a bunch of boilerplate to read the data, put it in some easy-to-use container where I can keep my logic tied to the data, and then construct an SQL statement by concatenating strings.

Get to know your ORM and take control of joins.

Related Stories