[PATCH] Alternative to eager loading

Ooops, should read "Eager loading is sometimes inefficient"

I'm interested to see where each performs better than the other and whether we could simply preload instead of eager load accordingly.

Perhaps testing for one-to-one joins like has_one and belongs_to?

I've had a plugin that I've been using privately to do this for quite some time now - aside from not having the time to support users, one of the issues that's held me back from releasing it is the performance implications. To explain:

First of all, if you are doing a *monster* list of :includes, hydrating your associations like this goes a long way to reducing memory consumption - there's a lot less 'discarded' data. The discarded data doesn't tax mysql too much, but it does tax the ruby vm.

In general, hydrating with multiple queries is at least as fast as eager loads with :include but it just depends on the structure of your data. When your toplevel objects are 'large' and you eager :include a has_many, it's probably about 3-4 times faster to hydrate.

As your :include list grows, so too does the benefit of hydrating.

But there is a major gotcha with hydration - while it performs your queries much faster, it increases the load on your database server significantly.

To me it's a trade-off: would you rather see 10,000 find()s completed in 10 seconds with a 5% system load for mysql or 10,000 find()s completed in 3 seconds with a 30% system load for mysql.

Every DBA I've spoken to has been *very* concerned about the increased load - even if it was for a shorter time. Above all, DBAs want to be able to tune the strategy for a given set of queries.

So to answer bitsweat - I've always treated this as a strategy you choose on a per-find() basis. Sometimes it's worth it, sometimes it's not. I've never believed it should be automatically applied.

This seems counterintuitive to me (although of course if that's what you see then that's the way it is. I don't have any DBAs to pester me though :-)) Sure part of the stuff that makes :include slow with several :has_manys is what the ruby code does with the data afterwards, but the database doesn't get away completely free either

Surely making the database server give you back 200 rows instead of 10000 can only be a good thing for it. I would have also thought 3 really simple queries (since the associations turn into select * from foos where bar_id IN (1,2,3)) would be kinder to the db (as well as faster) than 1 really uber joined query

I've got an example where a question object has 2 has_many associations, each with 50 objects. Doing an :include on both of those and on a has_one takes around 1.3 seconds (wall clock time), and 0.1s spent in the database (according to the rails log). Doing the :preload thing results in wall clock time of .025s, with around 0.01s spent in the database. I plain don't understand how that could ever be worse (or do other uses show different patterns?)

Frederick,

you have to measure more than just wall-clock time at the ruby end. You need to watch the system load of your mysql process over a sustained period of time using hydration as a strategy.

What I found is that there is a non-linear relation between 'results obtained' and mysql system load when you compare :include and hydration. If you consider wall-clock-time * mysql-system-load to be how 'hard' mysql is working for a given set of results, hydration makes mysql work 'harder'.

I presented this to one of the mysql core developers back at RailsConf 2006 and the impression I got from him was that from a pure-database standpoint, he wasn't a fan of the hydration strategy (for reasons above). However, he did concede that ActiveRecord's treatment of the database as a 'bucket' (aggressively loading all columns, for example) meant that maybe it was an acceptable strategy.

I think what worries DBAs can be best summed up with another benchmark that compares the effects of one query vs many queries (in the extreme):

I had a benchmark (lasting about 5 minutes) where I set up an enormous mysql query cache and repeatedly hit the same object graph (top level of 100 objects, with 2 has_many relations) using N+1 queries.

With a near-perfect hit rate for the query cache I've found that N+1 is as much as 17 times *faster* at the ruby end than running the benchmark with :include.

Unfortunately, the system load for mysql during N+1 benchmark spiked to nearly 100% cpu. DBAs really hate that :-)

If you just consider the wall-clock at the ruby-end you might be ignoring the way you're beating up your mysql server.

Trevor

I ran a benchmark which was essentially this:

500.times do

Question.find an_id_with_many_objects_in_its_has_manys, :preload => ... Quesiton.find :all, :order => 'questions.id desc', :preload => ..., :limit => 50

end

where the :preload/:included associations were 2 has_manys and one has_one, and a has_many :through on one of the has_many

:preload version:

55 secs total, 10.2 secs spent inside mysql (according to ps), average mysql load around 18% (

:include version 36 minutes, 76 secs spent inside mysql mysql load around 3-4%. So total amount of load put on mysql is more than sextuple. It's also worse on the wallclock * mysql cpu percentage front.

Sure the mysql cpu usage is higher, but that's only because we're running the queries as fast as we can: in the real world if I were to replace :includes with :preloads I'd have the same numbers of queries over the same amount of time in both cases: my users aren't going to start clicking the buttons in their browser any faster. Put it another way: if I were to override find to be

def find_with_sleep

sleep 1 find_without_sleep

end

Then the mysql load goes down to the same level as with :include (except that ruby processes aren't chewing all my cpu time), but I haven't actually done anything that increases/decreases the amount of load put on the server (for a constant amount of work.

The only way I can see this impacting real world mysql server load is if all you day is run benchmarks continuously

Frederick,

well, the difference between our benchmark results at the very least indicates that performance of the various strategies may be data/environment specific, and there is no hard and fast rule (at least that I can determine) for all situations.

I have to say though... The results you're seeing are odd - it's almost as though you only have one 'client' ruby process hitting the database... or maybe you're even using a single machine for both ruby and the db...

Either way, all I'm saying is that in my experience there are trade-offs and as such, this behavior should be opt-in for a given find() rather than automatic for *all* find()s.

Trevor

I have been using just the one machine for now. It needs be optional anyway, given that :include does allow you to specify conditions on the extra tables and this doesn't

I think I can extract a concise summary from my lengthy ramble. If during a lengthy benchmark mysql use is low it just means that it;s not the bottleneck (since as we know rails' unpacking of the rows returned chews up resources). The fact that changing things means that a benchmark now taxes mysql fully just means that the bottleneck is no longer ruby but the database (and it's normal that during a benchmark like this the bottleneck be maxed out - in my tests the ruby processes were using 100% cpu during the 'mysql friendly' version).

In any cases, it'll be good to have both the options.

extra test, stylistic changes

I've added a few tests. As requested, I've done a few simple benchmarks:

	user	system	total	real
:include belongs_to	0.170000	0.010000	0.180000	( 0.194349)
:preload belongs_to	0.120000	0.010000	0.130000	( 0.144132)
:include has_many	0.220000	0.010000	0.230000	( 0.255290)
:preload has_many	0.140000	0.010000	0.150000	( 0.185786)
:include multiple has_many	7.470000	0.200000	7.670000	( 8.122567)
:include multiple has_many	0.290000	0.010000	0.300000	( 0.391572)
:include nested has_many	0.510000	0.020000	0.530000	( 0.577883)
:preload nested has_many	0.290000	0.010000	0.300000	( 0.402208)
:include single_record small has_many	0.020000	0.000000	0.020000	( 0.030637)
:preload single_record small has_many	0.010000	0.000000	0.010000	( 0.018658)
:include single_record medium has_many	0.020000	0.000000	0.020000	( 0.021437)
:preload single_record medium has_many	0.010000	0.000000	0.010000	( 0.020416)
:include has_one	0.070000	0.010000	0.080000	( 0.091121)
:preload has_one	0.060000	0.000000	0.060000	( 0.090098)

To my untrained eye this says that :include is basically ok until its bad, then it's really bad. I think a little more care would be required to read more into this.

Code to generate the benchmarks:

Benchmark.bm(15) do |x|
  x.report(":include belongs_to") { 10.times {Question.find( :all, :limit => 50, :include => :customer, :order => 'questions.id desc') }}
  x.report(":preload belongs_to") { 10.times {Question.find( :all, :limit => 50, :preload => :customer, :order => 'questions.id desc') }}

  x.report(":include has_many") { 10.times {Question.find( :all, :limit => 50, :include => :incoming_messages, :order => 'questions.id desc') }}
  x.report(":preload has_many") { 10.times {Question.find( :all, :limit => 50, :preload => :incoming_messages, :order => 'questions.id desc') }}

  x.report(":include multiple has_many") {10.times {Question.find :all, :limit => 50, :include => [:incoming_messages, :outgoing_messages], :order => 'questions.id desc'}}
  x.report(":include multiple has_many") {10.times {Question.find :all, :limit => 50, :preload => [:incoming_messages, :outgoing_messages], :order => 'questions.id desc'}}

  x.report(":include nested has_many") { 10.times {Customer.find :all, :limit => 50, :include => {:questions => :incoming_messages}, :order => 'customers.id desc' }}
  x.report(":preload nested has_many") { 10.times {Customer.find :all, :limit => 50, :preload => {:questions => :incoming_messages}, :order => 'customers.id desc' }}
  
  #8 questions
  x.report(":include single_record small has_many") {10.times {Customer.find 123456, :include => :questions}}
  x.report(":preload single_record small has_many") {10.times {Customer.find 123456, :preload => :questions}}

  #50 questions
  x.report(":include single_record medium has_many") {10.times {Customer.find 123480, :include => :questions}}
  x.report(":preload single_record medium has_many") {10.times {Customer.find 123480, :preload => :questions}}

  x.report(":include has_one") {10.times {Question.find :all, :limit => 50, :include => :question_time_record, :order => 'questions.id desc'}}
  x.report(":preload has_one") {10.times {Question.find :all, :limit => 50, :preload => :question_time_record, :order => 'questions.id desc'}}
end

had previously omitted tests in the diff (d'oh)

added tests for conditions

Allow preconfigured preload (ie class Post; has_many :comments, :preload => :author)

Add support for polymorphic associations

I've never used polymorphic associations much, so I could easily have got things wrong (i've written tests of course, but then those could be wrong too :-))

Extra tests & no excessive singularisation

restored previously zapped tests

Replace :include with :preload when possible

:include is now effectively :preload. The patch defers to the old include if the condition or order reference the :included table (this only works if the tables are explicitly_name (ie. "foos.bar =42")

With this patch I can no longer :include associations which have :conditions that require interpolate_sql. The interpolation is there just so it would be possible to :include those columns so I can just remove the interpolation (which I'm using to specify the aliased_table_name for ambiguous column references) now.

Perhaps as it would be good to default associations which use sql interpolation to not use preloading but just normal eager loading?

Replying to tarmo:

Perhaps as it would be good to default associations which use sql interpolation to not use preloading but just normal eager loading?

That's entirely possible. It would make the 'should I use normal eager loading' code a little bit more complicated but I think it is doable (or do you mean do no :preload if any of the associations uses sql interpolation). If you can exhibit a test case for this I might also have a go at seeing if I can bludgeon preload into working in this case.

In general, might this be a case of having our cake and eating it? ie given {{{ Post.find :all, :include =>[:comments, :some_other_associations], :conditions => ['comments.unmoderated = ?', true]}}} then we normal-eager-load comments, but we :preload :some_other_associations. I can see this getting tricky to work out in more complicated cases (eg nested associations), so it might be better to leave that for another day.

Refactored Fred's patch

Hey guys, I'm really expectant about this feature. Is there any chance you could implement an "afterload" feature? I think this will help in cases where you cannot preload, but still want to load many rows without Rails doing hundreds of queries for each item.

For example:

# user.rb
has_many :blogs

# blog.rb
belongs_to :user
has_many :posts

# post.rb
belongs_to :blog
has_many :comments

# comment.rb
belongs_to :post

# users_controller.rb
def all_coments
@user = User.find params[:id]
@posts = @user.blogs.find(:all, :preload => [:post])
Post.afterload(@posts, [:comments])
# each post in @posts has comments preloaded

An alternate approach would be to do nested preloads:

@posts = @user.blogs.find(:all, :preload => {:post => [:comments]})

Replying to davidomundo:

An alternate approach would be to do nested preloads: {{{ @posts = @user.blogs.find(:all, :preload => {:post => [:comments]}) }}}

Isn't that exactly what :preload (not really called that anymore, it's :include in the latest patch) already does?

Yup, that's definitely what it already does. tarmo, could you show an example using interpolate_sql (it's not something i've ever really needed before)? I think I can just add that in same as :include does but I'd far rather start with a failing test.

Replying to fcheung:

tarmo, could you show an example using interpolate_sql (it's not something i've ever really needed before)? I think I can just add that in same as :include does but I'd far rather start with a failing test.

An ugly example would be:

  has_many :upcoming_performances_on_sale, :class_name => 'Performance',
    :conditions => ['#{"#{aliased_table_name}." rescue ""}state = ?', 'on_sale']

The point of the interpolation part is to make the association eager loadable while also working with normal access (when the aliasing is not needed). The aliasing itself is expected though as it's a self-referential association and thus can not be eager loaded without aliasing. :preload theoretically reduces the need for such workarounds but in cases where it falls back to regular eager loading it is still needed.

So you're saying that

Blog.find(:all, :preload => {:post => [:comments]})

Would first load all blogs, then load all posts for each blog, and then load all comments for each post? If so, I'm pleasantly surprised and impressed.

Replying to davidomundo:

So you're saying that {{{ Blog.find(:all, :preload => {:post => [:comments]}) }}} Would first load all blogs, then load all posts for each blog, and then load all comments for each post? If so, I'm pleasantly surprised and impressed.

That's exactly the way it works. And also the reason why preload is a great improvement on the old eager loading behavior.

Yup, that was the whole point :-)

Oh, nice!

I was under the impression that :preload was preferred over :include because :include returns a huge cartesian product with redundant info whereas preload returns only one row per needed item.

I guess this is another plus!

That's exactly it. The way it avoids the cartesian product is by doing it in steps.

Now how long until we get this in Core? :)

The patch seems to not apply anymore (due to the :joins changes from #10012), anyone planning to fix it?

I'll have a look at it today or tomorrow

I've got a patch attached to #10061 which will change how :joins works again (to be more consistent with the intent of :joins).

Once I rework the tests that were orginally submitted with #10012 I'm told it will be applied.

updated to apply to latest edge

interpolate sql

I've updated this against the latest edge and also added some stuff for interpolated conditions. I'm not a big user of that myself, so while it doesn't just blow up in the most trivial of cases it could still be iffy.

Now that #10061 has been fixed by [8109] lifofifo's patch applies again and tests pass (although the patch supposedly lacks the sql interpolation changes).

Updated against latest edge, still with interpolation.

Hey Fred,

If you have your benchmarking script handy, it'd be great if you could post the benchmarking report against the latest edge.

Well my data has changed quite a bit (and I've changed machine), so this isn't comparable to the previous benchmarks, but:

Without patch:

	user	system	total	real
:include belongs_to	0.610000	0.040000	0.650000	( 0.685515)
:include has_many	0.760000	0.060000	0.820000	( 0.891274)
:include multiple has_many	3.720000	0.230000	3.950000	( 4.329490)
:include nested has_many	2.780000	0.130000	2.910000	( 3.200279)
:include single_record small has_many	0.010000	0.010000	0.020000	( 0.025702)
:include single_record medium has_many	0.010000	0.000000	0.010000	( 0.046113)
:include has_one	0.620000	0.030000	0.650000	( 0.694406)

With patch

:include belongs_to	0.310000	0.040000	0.350000	( 0.391471)
:include has_many	0.550000	0.040000	0.590000	( 0.728103)
:include multiple has_many	0.930000	0.090000	1.020000	( 1.283857)
:include nested has_many	2.200000	0.160000	2.360000	( 2.834314)
:include single_record small has_many	0.010000	0.000000	0.010000	( 0.013746)
:include single_record medium has_many	0.010000	0.000000	0.010000	( 0.012381)
:include has_one	0.430000	0.040000	0.470000	( 0.574127)

In particular, my data no longer includes a good example of 2 has manys with large number of rows, that really killed old-style :include.

As an alternative example of the case where the current implemenation suffers:

Benchmark.bm(15) do |x|
x.report(":include multiple has_many") {10.times {Question.find :all, :limit => 100 :include => [:incoming_messages, :outgoing_messages, :log_entries], :order => 'questions.id desc'}}
end

We're loading 3 has_manys old style:

	user	system	total	real
:include multiple has_many	4.400000	0.240000	4.640000	( 5.220345)

new style

	user	system	total	real
:include multiple has_many	0.550000	0.050000	0.600000	( 0.741723)

So there's still a decent gain on 'normal' cases, and a huge win on the case the current code really doesn't like.

beef up some tests & pass more association options through

rebased on latest edge

failing test with symbol arg to :order option

fix for test-order.patch

failing test for polymorphic association preloading on STI subclass

fix for test-sti

tried latest patch on top of trunk r8641. Found couple of bugs. Tests and fixes are applied.

(In [8672]) Introduce preload query strategy for eager :includes. Closes #9640.

Fixed a bug with preloading belongs_to associations that doesn't use 'id' as the primary_key.

Fixed a bug with preloading belongs_to associations that doesn't use 'id' as the primary_key.

There is a small bug with eager loading belongs_to associations that does not use the standard 'id' primary_key. I've attached a patch that adds a test to check for it, and a fix for the bug.

Oops, my bad :-) That certainly looks sane to me (and thanks Aleksey for your fixes!)

fixes nested includes for preloading

This broke nested includes for me, i.e. :include => { :model1 => :model2 }. There was a problem when the association was NULL and also when it was retrieving the nested association, it wasn't sanitizing the SQL conditions for the parent model, rather than the associated child.

I've submitted a patch that fixes it for me. (Hopefully it's done correctly, it's my first patch.)

[8672] completely broke eager loading for me, because the naive regexes in include_eager_conditions? and include_eager_order? fail to match quoted table and column names such as those generated by the :conditions => { :bar => 'baz' } finder syntax, i.e.

Foo.find :all, :conditions => { :bar => 'baz' }

generates

SELECT * FROM "foos" WHERE ("foos"."bar" = 'baz')

which scan(/([\.\w]+)\.\w+/) totally misses, so preloading always happens even though there may be conditions or orders which depend upon a join. You've only got away with it because all of the test cases use :conditions => "bar = 'baz'" instead of the hash syntax and so any table and column names are always unquoted. Would a regex like /([\.\w]+)["']?\.["']?\w+/ be enough, or could we use a more robust way to analyse the table references?

blweiner, your patch is missing test/models/picture.rb and test/models/avatar.rb

tom, looks good. Needs a unit test.

(In [8762]) Fixed preloading belongs_to associations which reference a custom foreign key. References #9640.

I don't see where vanilla AR eager loading results in a cartesian product of tables being loaded. The cartesian product of two or more tables is the set of all combinations of the rows from each of these tables. By contrast, :include generates left outer joins, which only load a subset of the cartesian product.

The effect of a left outer join is that columns from the base table are repeated for each joined row. If this has the effect that duplicate objects are allocated over and over for what is essentially the same value, that's far from optimal, of course. However, this behavior should be improved somewhere way down in the database adapter.

At this time I'm not very enthusiastic about the approach taken by the patch. I can think of a few important questions:

• How is loading of associated objects affected by concurrent DB updates (atomicity)?
• How does the patch compare to vanilla eager loading when there are lots of concurrent accesses to the DB?
• What's the performance impact on DBMS other than MySQL?

There's definitely a difference regarding atomicity. I don't think this is an issue though (and you can always stik it in a transaction if it is), given that you're normally trying to speed up something along the lines of

for post in @posts
  #do something with post.comments
end

Which isn't atomic at all.

Regarding the cartesian product, maybe that's the wrong word, substitute 'hell of a lot of rows' if you like. But as far as concrete examples go, i've got a Question object which has many :incoming_messages, :outgoing_messages. one particular instance of it has 145 outgoing, 160 incoming.

If I load that instance, with those associations, the sql you get is (minus all the table aliasing) is

SELECT  ... FROM `questions` 
LEFT OUTER JOIN `incoming_messages` 
ON incoming_messages.question_id = questions.id 
LEFT OUTER JOIN `outgoing_messages` ON outgoing_messages.question_id = questions.id WHERE (`questions`.`id` = 2389495)

If I run that query on its own, the resultset has 23200 rows (=145 * 160) which sounds rather cartesiany to me.

I've little expertise with other databases so I'll leave that up to someone more qualified

"Hell of a lot of rows" is definitely a fitting description (to get the cartesian product, leave out all join conditions). In Rails this causes performance pain and suffering due to the inordinate number of short-lived objects that are allocated.

The easiest solution would be to just not :include multiple has_many associations on the same object. Including nested has_many associations is an entirely different case, however, as it does not suffer from the same explosion of rows.

With regards to multiple has_manys that is certainly the issue (and gettin 23000 rows back for 300 rows of actual information feels inefficient, independantly of rails). Not including multiple has_manys does avoid this, but that's not always a very appealing solution.

Poor chuyeow ;-)

I'm encountering an error when using nested preloading and one of the eager loaded records does not have any further associations. In the example below, Roles are a tree so I am preloading up to 4 levels deep. The problem is if a particular Role only has ancestors that go 2 levels deep then role.parent returns Nil and the preloading code still attempts to preload it. I have provided a patch to fix this issue.

Here is my example query:

user = User.find(:first,
  :conditions => {
    :account_id => account_id,
    :login      => login
  },
  :include => {
    :roles => [:permissions, :permission_assignments, {
      :parent => [:permissions, :permission_assignments, {
        :parent => [:permissions, :permission_assignments, {
          :parent => [:permissions, :permission_assignments]
        }]
      }]
    }]
  }
)

The error it produces:

NoMethodError in SessionsController#create
undefined method `preload_associations' for NilClass:Class

Stack Trace:
vendor/rails/activerecord/lib/active_record/association_preload.rb:25:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:25:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:25:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:19:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `each'
vendor/rails/activerecord/lib/active_record/association_preload.rb:16:in `preload_associations'
vendor/rails/activerecord/lib/active_record/base.rb:1247:in `find_every'
vendor/rails/activerecord/lib/active_record/base.rb:1236:in `find_initial'
vendor/rails/activerecord/lib/active_record/base.rb:1530:in `send'
vendor/rails/activerecord/lib/active_record/base.rb:1530:in `find_by_account_id_and_login'
vendor/rails/activesupport/lib/active_support/deprecation.rb:44:in `silence'
vendor/rails/activerecord/lib/active_record/base.rb:1530:in `find_by_account_id_and_login'
vendor/rails/activerecord/lib/active_record/base.rb:1518:in `send'
vendor/rails/activerecord/lib/active_record/base.rb:1518:in `method_missing'
app/models/user.rb:161:in `authenticate'
app/controllers/sessions_controller.rb:7:in `create'

This ticket has more than 20 patches attached to it, it's becoming impossible to figure out what is going on :/

Can you please open new tickets for the issues which remain open, and assign them directly to me (nzkoz).

Please open any remaining issues in new tickets and assign them directly to me.