# What is the complexity of find\_by\_name? **URL:** \ **Category:** Ruby\ **Created:** [July 14, 2008, 6:50am UTC](https://www.ruby-forum.com/t/what-is-the-complexity-of-find-by-name/142980 "2008-07-14T06:50:01Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![kretch](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/db5fbb/32.png) [@kretch](https://www.ruby-forum.com/u/kretch)\ **Post date:** [July 14, 2008, 6:50am UTC](https://www.ruby-forum.com/t/what-is-the-complexity-of-find-by-name/142980/1 "2008-07-14T06:50:01Z")
Hi All 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 Thanks Kretch ---
**Author:** ![kretch](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/db5fbb/32.png) [@kretch](https://www.ruby-forum.com/u/kretch)\ **Post date:** [July 14, 2008, 7:30am UTC](https://www.ruby-forum.com/t/what-is-the-complexity-of-find-by-name/142980/2 "2008-07-14T07:30:31Z")
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 Assuming you’re talking about Rails and ActiveRecord (this is a _Ruby_ group here; there are better places to ask Rails questions)… find\_by\_name turns into an SQL “select \* from where name = ‘value’”. If you have query caching enabled (the default), this call might be averted and be turned into a hash lookup… but assuming that isn’t the case, the costs come down to several factors: Any call to SQL has a large almost-constant overhead, simply due to the context-switch involved. A remote procedure call (whether transported using shared memory, pipes or sockets) involves upward of 100,000 instructions, and from Ruby, possibly much more - especially if several layers of database adapters are involved. This will almost completely flush the processor’s caches, and possibly much of the L2 cache as well. All the code executed, and all the data touched, will have to be loaded from RAM, and that’s a significant time cost. A rule of thumb would be 2-15 milliseconds per database call… an age in the CPU’s time-scale. The limit here is the speed of main memory and the FSB interface of your CPU chip. Next, SQL must parse and optimize the query, since Rails doesn’t make any use of the stored procedures that most DBMS provide to speed bypass this step. The optimization process will _hopefully_ find that you’ve placed an index over the “name” field. If not, the entire table must be loaded until the matching entry is found. In either case, quite a lot of code is required to parse and optimize your query and that will normally complete the cache flushing mentioned above. Then, to execute the search requires a log(N) search through disk pages, where N is the number of disk pages in the index - divide the size of an index page (say 8K) by the average size of a key (plus say 16 bytes), and you know how many pages are involved. Each physical disk access will take perhaps 5 milliseconds, but even a large index will only search 2-4 pages. However, the disk pages will normally exist in the DBMS’s buffer cache, at least all the internal nodes of the indices should be, so you may only have one real disk access. In these days of web apps having databases of 20MB running on servers having 1GB, the need to hit the disk is minimized. DBMS technology is optimized around the DB being more than 10x the available RAM, but typical Rails apps never go close to that. Having found the correct index entry, the data page will normally need to be loaded as well - again Rails doesn’t know anything about clustering the data with the most-used index (and even if it did, that’d be the surrogate key “id” field). Finally the results will be passed back to your program and turned from a row into an ActiveRecord object. That requires your CPU to reload most of the instructions (and some data) that make up the Ruby interpreter and program, hitting main memory again. Bottom line: though there is a log(N) component - and perhaps even an O(N) component if you forgot to add indexes - in most Rails apps you are hit heavily on fixed per-call costs. I hope this message gives you some insight into why Rails database performance is often poor, especially compared to more “enterprisey” toolkits that streamline some of the above operations by making proper use of the DBMS’ features. Clifford H., Data Constellation. ---
**Author:** ![kretch](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/db5fbb/32.png) [@kretch](https://www.ruby-forum.com/u/kretch)\ **Post date:** [July 14, 2008, 1:31pm UTC](https://www.ruby-forum.com/t/what-is-the-complexity-of-find-by-name/142980/3 "2008-07-14T13:31:26Z")
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.