From: phlip <phlip2005@...>
Date: 2008-07-14T20:25:43+09:00
Subject: Re: What is the complexity of find_by_name ?

Kretch Kretchmer wrote:

> I was wondering whether find_by_name has linear complexity O(n) with n
> being the number of records? Or is it log(n) or constant? I have some
> code which uses find_by_name heavily, and I was wondering if the long
> runtimes I'm seeing are a result of find_by_name being linear

Try: sudo gem install assert_efficient_sql

Then write a unit test like this:

   def test_find_by_name_is_efficient
     assert_efficient_sql :verbose do
       Table.find_all_by_name('foo')
     end
   end

It will print out the result of a MySQL EXPLAIN call. If the output contains an 
ALL call, or does not contain the name of a candidate index, then the SELECT is 
probably reading every record to find your hit.

If you can take the :verbose out, and the assertion passes, then its EXPLAIN 
won't contain certain indicators of inefficiencies, and might be more efficient.

If you leave that assertion online as you add features, then if it ever breaks 
your efficiency has regressed.

-- 
   Phlip