MySQL Bugs: #21191: records_in_range error in MySQL Cluster

Bug #21191	records_in_range error in MySQL Cluster
Submitted:	20 Jul 2006 19:12	Modified:	10 May 2007 10:12
Reporter:	Mikael Ronström	Email Updates:
Status:	Won't fix	Impact on me:	None
Category:	MySQL Cluster: Cluster (NDB) storage engine	Severity:	S3 (Non-critical)
Version:	5.1.12-beta-debug	OS:	Linux (Fedora Core 5)
Assigned to:	Assigned Account	CPU Architecture:	Any

Description:
When running the DBT2 benchmark tests there are occasions when the queries on
the order_line table will be implemented as a full table scan on the table. Given that
an index scan will scan 11 records and a full table scan will scan around 100.000 records
per warehouse in the test, the wrong choice is very significant.

Given the nature of DBT2 it also affects all other transactions since the transaction will
retain locks for an extended period of time.

The wrong selection only happens sometimes:
It either happens at the end of an interval where district id is 1 or district id is 10.
For all other values of district id it always returns a proper result.

When returning a faulty number, records_in_range returned 566000 instead of 11 in a table of
1.5M records.

How to repeat:
Run DBT2 benchmark with a single thread, use enable-debug-query
Check for queries that take seconds to complete (DELIVERY_5, DELIVERY_6 and one more
in the ORDER_STATUS table).

Suggested fix:
One problem with the implementation is that it keeps 32 cached values. If a value is looked for in
an interval where no cached statistics exist it will calculate the estimate as 50% of the interval.
This can be seriously wrong if intervals are not well spread in the cache.

Solution can be in many ways,
One thing is to use a security check that if interval is bigger than 5% to always go down into NDB
and make a real check in the database to see what the records in range are.

On top of this one can probably use some statistics to ensure that we do not report intervals that are
much bigger than what we normally report. So if the estimated range is very big, select a smaller
range based on statistics of the table.

Shouldnt we always use ranges if there are any?

There are a number of cases where a range should not be used.
1) When there exists a better range to use
2) When we have implemented TUP Disk scan (or have we already, don't remember)
in that case a full table scan can be 20 times faster per record.

So this means that we should still deliver a reasonable result for records_in_range but
we should avoid a result that is very large (e.g. larger than 5% of the records) unless we
have safe statitics or a real measure of that

The current idea I have is the following:
Measure for all cached statistics the mean value of ranges + the standard deviation of
ranges. For intervals that contain uncertainty never deliver anything which is bigger than
either of 
1) 5% of records
2) 5 * standard deviation + mean value (99.9% confidence interval)

If we have three measurements a1 < a2 < a3 and we get a range from [a0, a21] where
a0 < a1 and  a2 < a21 < a3. In this case we'll use the interval [a1,a2] even if it is very
big since it is based on a measurement but for the intervals [a0,a1] and [a2,a21] we
use a much more cautios approach.

The cache replacement algorithm should also strive to delete one of close neighbours as much as
possible to ensure that the sampling points are not too close to each other.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/11827

ChangeSet@1.2308, 2006-09-13 12:27:48+02:00, pekka@orca.ndb.mysql.com +2 -0
  ndb - bug#21191: ndb index stats OFF by default

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/11829

ChangeSet@1.2309, 2006-09-13 12:46:26+02:00, pekka@orca.ndb.mysql.com +1 -0
  ndb - bug#21191: ndb-index-stat-enable: one more suspicious default

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/12920

ChangeSet@1.2310, 2006-10-01 16:05:53+02:00, pekka@orca.ndb.mysql.com +2 -0
  ndb - bug#21191: test pgm: testIndexStat

This bug is not scheduled to be fixed at this time.