MySQL Bugs: #48111: Slow endgame for the RQG mysqltest simplification algorithm

Bug #48111	Slow endgame for the RQG mysqltest simplification algorithm
Submitted:	16 Oct 2009 11:19	Modified:	4 Apr 2010 12:33
Reporter:	Philip Stoev	Email Updates:
Status:	Closed	Impact on me:	None
Category:	Tools: Random Query Generator	Severity:	S3 (Non-critical)
Version:	2	OS:	Any
Assigned to:	Bernt Marius Johnsen	CPU Architecture:	Any

Description:
The endgame, that is, the final stages of the GenTest::Simplify::Mysqltest algorithm is sub-optimal, actually approaching quadratic runtime.

The algorithm is good at quickly chopping out big chunks of the test case at once, however detoriates badly when it is about removing individual lines from a larger test case.

How to repeat:
The attached mysqltest case causes a crash on 5.1 Try to simplify it.

Note that while all code blocks appear to be required, there are many individual lines within each code block that can be removed.

Suggested fix:
Possible fixes within the current algorithm:
* Make the number of initial splits configurable, so that a person can set the number of splits to a high value, causing the algorithm to immediately start working on individual lines, rather than bisect the test case progressively.

* Have the algorithm continue if a simplification was found. Currently, the algorithm will restart its search from the top of the test case, causing it to rework previously visited test lines repeatedly.

Possible solution with a new algorithm:
* create a separate algorithm that will linearily proceed to simplify the test case one line at a time starting from the top without trying to be clever about things. For test cases less than 1000 lines, this dumb algorithm will deliver a minimal test case within a bounded ammount of time.

bug48111.test

Attachment: bug48111.test (application/octet-stream, text), 24.26 KiB.

The algorithm was fixed to use less back-tracking so now performance seems acceptable. A new bug will be opened if a new bottleneck is discovered