Tuesday, August 4, 2009

In Defense of MRR

A few days before OSCon Henrik Ingo, our newly hired COO, forwarded me a post of Mark Callaghan with the following plaint on the state of certain latest optimizations that had been introduced into the MySQL Server, namely, Multi-Range Read (MRR), Index Condition Pushdown (ICP) and Batched Key Access (BKA).

> I have seen descriptions for each of these features that describes
> them in isolation. Is there one page where they are described
> together? And if there isn't can I convince Sergey and Igor to write a
> new blog post?

Further in the post, Mark points to the slew of bugs allegedly in the implementation of ICP for the InnoDb engine that forced managers at Sun/Oracle to ask Sergey Petrunia, the author of the code, to turn the feature off , though for this engine only. The patch was submitted and the next alpha release of the Azalea version will appear with this optimization disabled. At the same time Sergey was asked to disable the implementation of the MRR interface for InnoDB too.
Why? Because at Sun they were not sure who the culprit was. They had a choir of unhappy customers (reported bugs #36981, #34591, #35080, #37415, #34590, #37208, #40992, #42580, #43617), some of whom blamed ICP, some – MRR, and some - both. Taking into account a subdued grumble of some undisputed authorities who first planned to port the BKA code into their product and then put the project on hold due to a mere fact that the MRR code was said to be “utterly crappy”, what would you do if you were responsible for making decisions? Right. Condemn both suspects to minimize the consequences of a mistake. None of them is worth a single tear of our customers. What? Are they are not even of the same kind? This makes them even more guilty. This makes them an organized gang. You are still not sure they are desperate criminals? Open the bug reports, read them. Do they make you cry too? Are you convinced at last?

Anyway, the verdict runs as follows:

[25 Jun 4:00] Paul DuBois Noted in 5.4.4 changelog.
The Multi-Range Read access method does not work reliably for InnoDB
and has been disabled for InnoDB tables.

End of the story. Justice reigns. The villains deserve capital punishment, but we are civilized people and we believe that properly applied corrective measures have a good chance of improving any scoundrel. As for now a full isolation of the convicts would be not only in the interest of good folks, but in the interest of the poor creatures as well.
At last all of us can exhale with a relief and rejoice the life where there are no bugs just because everything that could attract them has been mortified.

I used to know MRR for InndDb when he was a just a child. There was nothing wrong in how he was raising up. He was brought up together with his siblings, first with MRR for MyISAM, MRR for NDB Cluster, later with MRR for Falcon. That's true that they have different biological mothers, but all these children were conceived by the same father. Moreover the implementations of the MRR interface for MyISAM and for InnoDB were based on the same code and were engine independent. If there had been any genetic defect in the code it would have manifested itself for MyISAM as well.
The implementation of the MRR interface for MyISAM/InnoDb employs other handler functions such as index_read and rnd_pos. Either there are some subtleties or side effects in the implementations of these functions for InnoDB, or the accusations are false.

So I decided to spend some of my time to investigate the case on my own. First I looked through the bug reports.
The reports for bugs #36981, #34591, #35080, #37415 say that with the settings:

set optimizer_use_mrr='disable';
set engine_condition_pushdown=off;

no crashes are observed for the reported cases.

The report for bug #34590 is certain that the setting

set engine_condition_pushdown=off;

is enough to prevent crashing.

The analysis made by Paul DuBois for bug #40992 leads to the conclusion that only settings for engine_condition_pushdown matter when trying to cause a crash. It's worth noting that the test case for this bug resembles pretty much the one reported by Shane Bester for bug #36981.
The reports for bugs #37208, #42580, #43617 complain about wrong results when engine_condition_pushdown is 'on'. Once more the report for #42580 says that the problem appears when both optimizer_use_mrr and engine_condition_pushdown are set to default values.

After I had read all these reports, it became clear for me that there were no direct evidences of MRR's bad behavior, at least from the cases that were submitted.
To check that the MRR code had nothing to do the reported problems, I built the server from the latest mysql-azalea tree, reverted the patch from bug #45029, and ran the test cases with engine_condition_pushdown set to 'off'. All the test cases passed through without crashes and with correct results. (Of course I could run only those test cases that I was able to extract from bug database easily. These were the test cases for bugs: #36981, #34590, #42580, #43617.)

I continued my investigation. First I debugged the test case for bug #42580 that returned a wrong result and looked quite simple. After several attempts to force my way through the InnoDB native code finally I came to the offending lines in innobase/row/row0sel.c:

*(prebuilt->fetch_cache[prebuilt->n_fetch_cached] + offs) ^=
(*(remainder_buf + offs) & templ->mysql_null_bit_mask);

It was Sergey's code and the intention was to mask in the null bit of an index field in the internal InnoDB row cache. It could be properly done with the code like this:

null_byte= prebuilt->fetch_cache[prebuilt->n_fetch_cached]+offs;
(*null_byte)&= ~templ->mysql_null_bit_mask;
(*null_byte)|= (*(remainder_buf + offs) &
templ->mysql_null_bit_mask);

I applied the fix and all the wrong results (bugs #37208, #42580, #43617) went away.
The crashes remained though. Several hours of additional debugging for the test case of bug #36981 brought me to a really bad memory overwrite in the build_template function from innobase/handler/ha_innodb.cc. By a pure chance the overwrite did not cause a problem for my test case. The crash was caused by usage of wrong template structures for reading row fields from mysql buffers. The crash happened in the code that had been added by Sergey in the row_search_for_mysql function to evaluate conditions pushed down to indexes. This problem can not be easily fixed since with ICP we may need two arrays of prebuilt template structures when executing the SELECT FOR UPDATE queries or multi-UPDATE/DELETE queries: one for the fields of the scanning index, another for the fields of the clustering index.
As a temporary solution I could suggest to block usage of ICP for such queries. It can be done with the following code:

if (file->active_index == file->pushed_idx_cond_keyno &&
file->active_index != MAX_KEY &&
index == prebuilt->index)
do_idx_cond_push= need_second_pass= TRUE;

This code prevents crashes for all reported test cases.

Only two days of investigations (I literally spent only a week-end for it, and, I would have spent much less time if I were familiar a little bit with the InnoDB code) convinced me that MRR for InnoDB is absolutely innocent, while ICP for InnoDB, though being guilty of serious misdeeds, should not undergo any severe punishment, as it's quite naturally to expect some faults from such a young feature and we don't have to employ any penitentiary institutions to correct these deviations.
A different attitude to this misdemeanor would make me doubt that we are really supportive for young talents: we turn them down should they manifest some erratic behavior .

I want to be clear here. Stating that MRR is innocent, I don't want to say that the MRR code is absolutely clean. It's a relatively new code, so most probably it still contains serious bugs. Sergey has recently pointed me to the problem of unlocked gaps for InnoDB. A similar problem should exist for Index Merge. If it's resolved there, why can't the same solution be applied for MMR? If it's not resolved there, should we disable Index Merge for InnoDB as well?

And what about you? How do you find MRR/ICP? Guilty, or NOT guilty? Should the case be appealed?

On a side note, I would like to add that MRR and ICP for InnoDB are really smart optimizations. MRR for InnoDB allows us to accumulate primary keys for multiple lookups in a buffer before fetching data in a sequential manner. The more keys you accumulate, the less disk sweeps you need to fetch the data. ICP allows us to reject a row as soon as the condition over the index fields is not satisfied.
MRR and ICP can interplay, or can be used independently. They both can be very helpful for BKA . Moreover, in fact, it does not make too much sense to use BKA for InnoDB/MyISAM without MRR.
The three features put together can give you a boost of performance for join queries that involve many rows. Yet, this will be the subject of a separate blog.

71 comments:

  1. I am pretty sure there is a backport of BKA in the v4 Google patch. That enables remarkable performance gains.

    I also hope to experiment with prefetching in InnoDB when BKA is used. Even without prefetching, IO-bound index nested loops join should be faster.

    ReplyDelete
  2. Not guilty. Hopefully should win on appeal.

    ReplyDelete
  3. 以簡單的行為愉悅他人的心靈,勝過千人低頭禱告。........................................

    ReplyDelete
  4. 思想與理論,貴呼先於行動,但行動較思想或理論更高貴..............................

    ReplyDelete
  5. 人類最大的悲劇不是死亡,而是沒有掌握有意義的人生........................................

    ReplyDelete
  6. 能猜得出女人真實年齡的男人也許耳聰目明,但肯定毫無大腦。哈哈!......................................................

    ReplyDelete
  7. Poverty is stranger to industry..................................................................                           

    ReplyDelete
  8. 向著星球長驅直進的人,反比踟躕在峽路上的人,更容易達到目的。............................................................

    ReplyDelete
  9. 愛,拆開來是心和受兩個字。用心去接受對方的一切,用心去愛對方的所有。......................................................................

    ReplyDelete
  10. 一個人的價值,應該看他貢獻了什麼,而不是他取得了什麼....................................................

    ReplyDelete
  11. Joy often comes after sorrow, like morning after night.. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

    ReplyDelete
  12. 愛,拆開來是心和受兩個字。用心去接受對方的一切,用心去愛對方的所有。......................................................................

    ReplyDelete
  13. Replies
    1. World's Best Current Affairs Website which you Get Any thing you want, Most Popular Pictures, Loll Pictures, Funny Pictures, Funny Videos, Current Affairs Videos, Entertainment News and Videos, Entertainment Pictures, Hot Girls Affairs and all hot Current Affairs in the World
      HotCurrentAffairs.com

      Delete
  14. Glorious Live design philosophy is based on versatility and glamour with a clear focus on creating outfits to make each woman feel beautiful in whatever she wears. We also provide custom made design as per your requirement.
    GloriousLive.Net

    ReplyDelete
  15. We are the one who have development team behind Pakistan's largest media websites and who made wesbites which are busiest and most famous in Pakistan and very high ranking in Alexa and SEO point of view.
    Reserver Your Website Now...

    ReplyDelete
  16. Entertainment for Fun... Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and Much More Fun Only on 1 Current Affairs Network
    hotcurrentaffairs.com

    ReplyDelete
  17. http://igors-notes.blogspot.com/2009/08/in-defense-of-mrr.html

    ReplyDelete
  18. Internet Users have very big Good News, Now you can earn with Just Share an add or picture on Facebook, Facebook is the Most popular Website in the World and you can make unlimited income with Just Facebook Posting Program.
    Genuines Works of Data Entry, Facebook Posting, Copy Pasting, Add Posting, Clicking, Web Surfing, Website Visiting, Article Sharing, Data Sharing, Google Business Plan and Much More Business Plans.
    www.jobzcorner.com

    ReplyDelete
  19. Entertainment for Fun... Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and Much More Fun Only on 1 Current Affairs Network
    hotcurrentaffairs.com

    ReplyDelete
  20. Want to Learn Forex Trading and earn with Forex Business...?? The best Forex Trading Learning Website where you can get any thing about Forex, Trading updates, forex trading latest news, forex brokers directory, forex brokers list, Dollars news affairs, Stock Markets, stock market news, stock market analysis, technology news, international forex markets, international forex business news and all updates about Forex Trading
    ForexAffairs.Com

    ReplyDelete
  21. Latest cars and vehicles, Latest Mazda Models, Racing Cars, International Sport Cars, Concept Cars, PS-Pod, Strange Vehicles, Nissan, Royce Corniche, Ford Concept Cars, Strange Vehicles, Mercedes and More Sport Cars and Vehicles with Pictures and Info
    WorldLatestVehicles.com

    ReplyDelete
  22. Classified Sites, Pakistani Classified Sites, USA Classifieds, Indian Classifieds, Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and Much More Fun Only on 1 Current Affairs Network
    hotcurrentaffairs.com

    ReplyDelete
  23. Online Jobs of Data Entry, Copy Pasting, Add Posting, Clicking, Web Surfing, Website Visiting, Article Sharing, Data Sharing, Google Business Plans, Investment Plans, Genuine earnings from home.
    www.jobzcorner.com

    ReplyDelete
  24. Online Business with hourly profit, Just Invest and Rest
    AllTimeProfit.com

    ReplyDelete
  25. Online Corner is the best Platform to earn money online from internet, Just Join Now and start earnings
    OnlineCornerz.com

    ReplyDelete
  26. Get your website on google top 10 Results, Best Search Engine Optimization Company in Pakistan
    Contact Now
    Skype : Jobz.Corner
    www.jobzcorner.com

    ReplyDelete
  27. Business at home...??? want to join the best business without any work, just invest and rest
    www.earningsclub.com

    ReplyDelete
  28. Get Facebook Likes on your fb page, likes on your facebook pictures, followers on your facebook id, shares of your facebook posts, every thing is available here, visit for more details
    www.jobzcorner.com

    ReplyDelete
  29. Online Jobs, Just Post a Comment on any blog site and earn $0.06 per Link, Just Like this post, Visit and Click on Link Relation
    JobzCorner.com

    ReplyDelete
  30. Find Best online home based jobs, data entry, copy pasting, facebook and clicking jobs
    JobzCorner.com

    ReplyDelete
  31. Play Games and Earn Money online from home, best add clicking website in the world
    PaidVerts.com

    ReplyDelete
  32. Earning is only for you, just spend 1 hour daily and earn upto $35 Daily with just clicking job, Join Now
    adsclickearning.com

    ReplyDelete
  33. Instant Payment without any Risk, Just Invest and Rest of your home, Just Invest as low as $5 and Get Instant Profit, Join Fast
    HotProfitOnline.com

    ReplyDelete
  34. for best Online Jobs without any rejection, no time limit required, no investment requires, just spend few minutes and earn upto $35 daily
    www.adsclickearning.com

    ReplyDelete
  35. Find best business in the world where you can invest only $5 and get profit upto 7% daily for 60 Days, most popular website in ranking, Join now
    www.hotprofitonline.com

    ReplyDelete
  36. Find best business in the world where you can invest only $10 and get 3000% Profit, most popular website in ranking, Join now
    www.investorganization.com

    ReplyDelete
  37. Hot Forex Investments where you can earn profit without any work, just invest on forex and get profit daily upto 12%, Join Now
    HotFxInvest.com

    ReplyDelete