Bug #41582 Falcon index access returns no result for indexes with numeric datatype
Submitted: 18 Dec 2008 7:47 Modified: 15 May 2009 14:16
Reporter: Allan Packer Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Falcon storage engine Severity:S2 (Serious)
Version:6.0.9 OS:Any (Solaris Nevada, OS X 10.5.6)
Assigned to: Lars-Erik Bjørk CPU Architecture:Any
Tags: datatype, F_ENCODING, INDEX, numeric

[18 Dec 2008 7:47] Allan Packer
Description:
When a numeric datatype is used as a Falcon index, a subsequent index access fails to return any data.

Note that this seems related to Bug#40607 (Falcon unsigned indexes broken), except that the datatype used in this case was not unsigned, it was "numeric".

For example:

The customer table has a key originally declared as numeric(11):
Field=c_id, Type=decimal(11,0), Null=NO, Key=PRI, Default=NULL

The following SQL illustrates the problem:

mysql> select * from customer limit 3;
+------------+----------------+---------+----------+----------+----------+--------+--------+------------+------------+----------+----------+-----------+---------+----------+----------+-----------+---------+----------+----------+-----------+---------+---------------------+-----------------------+ 
| c_id      | c_tax_id       | c_st_id | c_l_name | c_f_name | c_m_name | c_gndr | c_tier | c_dob      | c_ad_id    | c_ctry_1 | c_area_1 | c_local_1 | c_ext_1 | c_ctry_2 | c_area_2 | c_local_2 | c_ext_2 | c_ctry_3 | c_area_3 | c_local_3 | c_ext_3 | c_email_1           | c_email_2             |
+------------+----------------+---------+----------+----------+----------+--------+--------+------------+------------+----------+----------+-----------+---------+----------+----------+-----------+---------+----------+----------+-----------+---------+---------------------+-----------------------+ 
| 4300000001 | 078GO5457DB627 | ACTV    | Fowle    | Joshua   | W        | M      |      2 | 1968-01-07 | 4300002505 | 011      | 240      | 2619077   |         | 011      | 510      | 0783203   |         | 011      | 805      | 6289414   |         | JFowle@msn.com      | JFowle@netzero.com    |
| 4300000002 | 803MO6290MK444 | ACTV    | Swigert  | Willie   | N        | M      |      2 | 1976-04-17 | 4300002506 | 011      | 604      | 7677511   |         | 011      | 336      | 3500450   |         | 011      | 814      | 2071392   |         | WSwigert@msn.com    | WSwigert@netzero.com  |
| 4300000003 | 329GW9315LX866 | ACTV    | Labree   | Amos     | G        | M      |      3 | 1958-03-13 | 4300002507 | 011      | 905      | 7559403   | 737     | 011      | 956      | 3095007   | 613     | 011      | 204      | 0469550   |         | ALabree@hotmail.com | ALabree@earthlink.com |
+------------+----------------+---------+----------+----------+----------+--------+--------+------------+------------+----------+----------+-----------+---------+----------+----------+-----------+---------+----------+----------+-----------+---------+---------------------+-----------------------+
3 rows in set (0.00 sec)
mysql> select * from customer where c_id = 4300000001;
Empty set (0.03 sec)
mysql> 

How to repeat:
A test system can be made available.

Suggested fix:
A successful workaround is to declare c_id as bigint instead of numeric(11) and rebuild the index.  The query then returns the correct result.
[18 Dec 2008 9:12] Sveta Smirnova
Thank you for the report.

I can not repeat described behavior with test table. Please provide output of SHOW CREATE TABLE customer
[18 Dec 2008 10:15] Lars-Erik Bjørk
I can reproduce this with a very simple test case:

mysql> create table customer(customer_id numeric(11), key(customer_id)) engine=falcon;
Query OK, 0 rows affected (0.06 sec)

mysql> insert into customer values (4300000001),(4300000000),(4299999999),(4299999998),(4300000002);
Query OK, 5 rows affected (0.00 sec)
Records: 5  Duplicates: 0  Warnings: 0

mysql> select * from customer;
+-------------+
| customer_id |
+-------------+
|  4300000001 | 
|  4300000000 | 
|  4299999999 | 
|  4299999998 | 
|  4300000002 | 
+-------------+
5 rows in set (0.00 sec)

mysql> select * from customer where customer_id = 4300000001;
Empty set (0.00 sec)

The same thing happens if customer_id is of type decimal(11,0)
[18 Dec 2008 12:05] John Embretsen
This is the kind of bugs the test falcon_index_datatypes in the falcon test suite is supposed to catch. It includes a test for the DECIMAL type (which is what NUMERIC is implemented as), with precision (10,2) but it does not fail. It looks like this:

--echo #-------- Test: DECIMAL --------#

ALTER TABLE t1 ADD INDEX index_decimal (a_decimal);
SHOW INDEXES FROM t1;
INSERT INTO t1 SET a_decimal = 112.04;
UPDATE t1 SET a_decimal = 112.05 where a_decimal = 112.04;
SELECT * FROM t1 ORDER BY a_decimal;
SELECT * FROM t1 WHERE a_decimal > 1 LIMIT 1;
ALTER TABLE t1 DROP INDEX index_decimal;
SHOW INDEXES FROM t1;
SELECT * FROM t1;

---

Seems like it has something to do with the size of the numbers, since Lars-Erik's repro does not show the issue if the table contains three-digit values instead of 10-digit values:

mysql> select * from t2;
+-------------+
| customer_id |
+-------------+
|         431 |
|         430 |
|         429 |
|         428 |
|         432 |
+-------------+
5 rows in set (0.00 sec)

mysql> select * from t2 where customer_id = 431;
+-------------+
| customer_id |
+-------------+
|         431 |
+-------------+
1 row in set (0.00 sec)
[18 Dec 2008 13:50] Lars-Erik Bjørk
This is what seems to be happening, starting with a quote from the reference manual:

"Values for DECIMAL columns in MySQL 5.1 are stored using a binary format that packs nine decimal digits into four bytes. The storage requirements for the integer and fractional parts of each value are determined separately. Each multiple of nine digits requires four bytes, and any digits left over require some fraction of four bytes. For example, a DECIMAL(18,9) column has nine digits on either side of the decimal point, so the integer part and the fractional part each require four bytes. A DECIMAL(20,10) column has ten digits on either side of the decimal point. Each part requires four bytes for nine of the digits, and one byte for the remaining digit."

In StorageDatabase:getSegmentValue, Falcon does not take into account that the value is given as groups of four bytes (with possible extra bytes). Falcon treats the entire key as the value. Therefore, Falcon will search for the wrong value when a search key is given with more than nine digits on either side of the '.' (I have however only tested for number where the scale is 0).

An example of this is the following set of queries, and values fetched from gdb:

1. Creating the table
----------------
mysql> create table c2(cid decimal(12,0), key(cid)) engine=falcon;
Query OK, 0 rows affected (0.07 sec)

2. Inserting some values
-------------------
mysql> insert into c2 values(4300000001),(4300000000),(4299999999),(4299999998),(4300000002);
Query OK, 5 rows affected (0.00 sec)
Records: 5  Duplicates: 0  Warnings: 0

3. Searching:
----------
I am searching for non-existing values here, but that is OK. We only want to look at how Falcon treats the key.

a) Searching for a value with precision 9:

mysql> select * from c2 where cid = 999999999;
Empty set (3 min 6.13 sec)

The value is represented using 4 bytes. The value part of the key, as read from gdb (in StorageDatabase::getSegmentValue()), is
00111011 10011010 11001001 11111111

This is correctly interpreted by Falcon as 999999999

b) Searching for a value with precision 10:

mysql> select * from c2 where cid = 1000000000;

gdb shows this as:
00000001 00000000 00000000 00000000 00000000

Here, the value is coded as a single byte representing the first digit, and a group of four bytes representing the last 9 digits.
Falcon, however, interprets this as a 5 byte value, and gets 4294967296 instead of 1000000000

----

It seems like Falcon is missing some vital logic for interpreting keys for the decimal type correctly.
[18 Dec 2008 14:50] Lars-Erik Bjørk
When digging a little deeper, it *seems* like this can be fixed quite easily. Falcon has special handling of decimals with a precision >= 19, which is the boundary for the sign bit of an int64. However this boundary needs to be > 9 instead. (Maybe we can even treat all keys as if they *may* have higher precision than 9. This would give easier code, but would cost us a couple of stack frames... )
[23 Dec 2008 17:08] Ann Harrison
Let me see if I can  explain why Lars' suggestion of changing
the size check could cause problems.

First, decimal and numeric are exactly the same type in both
Falcon and MySQL, so I'm going to call that type decimal and
avoid saying decimal or numeric about a hundred times.

Falcon has internal types and uses them, not MySQL types.  Type
translation is done at the storage interface layer - ha_falcon.cpp.
The area of greatest difference is in the handling of values
declared as decimal.

In MySQL, those values are stored  using a binary format that
packs nine decimal digits into four bytes, where any leftover
digits require some fraction of four bytes.  There are separate
chunks for the integer and fraction part.  Thus a column
declared as decimal [10,5] with a value of 12345.06789 would
be stored as a sign indicator plus a four byte chunk that
contains the value 12345 and a second four byte chunk that
contains the value 6789.  A column declared as decimal[10,0]
with a value of 1234506789 is stored as a sign plus a single
byte containing a 1 and a four byte hunk thats a binary
234506789.

Falcon stores columns declared as decimal[x,y] as integers of
a large enough size to hold x decimal digits.  The y value is
stored in the column definition.  Decimal[x,y] is stored as a
sixteen bit integer if x is less than 5; as 32 bit integer if
x is less than 10; 64 bit integer if x is less than 19;
otherwise it's a BigInt.  So decimal [10,5] with a value of
12345.06789 is stored as a 64 bit integer containing 1234506789.
A decimal[10,0] is also stored as a 64 bit integer containing
1234506789, as is a bigint with a value of 1234506789.  When
comparing numbers from different columns, Falcon checks the
column declaration for a scale then multiplies as necessary
to get both numbers to the same scale.

When storing data, StorageInterface::encodeRecord looks
into the server record definition to find the actual type of
the field, and does necessary conversions.

When passing in a key, the server tells falcon that the key
is binary - meaning that its declaration was one of decimal,
numeric, tinyint, smallint, mediumint int, or bigint.  From
Falcon's internal metadata we find the precision and scale.
But Falcon's internal metadata doesn't let us distinguish
between a decimal[9,0] and a int, or between decimal[18,0]
and bigint.

The place where we're getting into trouble is the mapping of decimal[x,y] with a y value of zero and a x value < 20.

What the server says is that the value is "binary" meaning
its a number and not floating point, that it's length is
x digits and its scale is y.

If y > 0, then we know that the declaration was decimal
because integers don't have scale factors.

If x > 19, the declaration had to be decimal because the
largest integer type holds only 19 decimal digits (unsigned).

But a "binary" key that has a length of 10 and a scale of
0 could be a bigint, stored as an eight byte quantity or
it could be a decimal[10,0] and stored as a sign plus a byte
plus four bytes.

So, changing the test in StorageDatabase to

     else if (field->precision <= 9 && field->scale == 0)

will cause us to handle decimal[10] correctly, but will
break the handling of bigint keys.

Jim is suggesting that this structure in StorageTableShare

struct StorageSegment {
    short            type;
    short            nullPosition;
    int            offset;
    int            length;
    unsigned char        nullBit;
    char            isUnsigned;
    void            *mysql_charset;
    };

be augmented with another field that specifies whether
the "binary" type is decimal or integer.  There's a temptation
to make it a boolean, but I would resist that because we're
going to need to distinguish between varbinary and varchar
sooner or later - leave room for that.  This structure is
purely in memory and recreated when Falcon restarts, so
changing it is not a problem

Then StorageInterface::getKeyDesc populates that field,
and StorageDatabase uses it rather than guessing based on
length and scale.
[21 Jan 2009 9:47] Lars-Erik Bjørk
Was reviewed by Jim
[17 Apr 2009 9:31] Lars-Erik Bjørk
Pushed into 6.0.11
[15 May 2009 14:16] MC Brown
An entry has been added to the 6.0.11 changelog: 

Indexes on Falcon tables using numeric columns could return incorrect information.