List:Falcon Storage Engine« Previous MessageNext Message »
From:Kevin Lewis Date:February 20 2009 10:06pm
Subject:Patch for Bug#23692
View as plain text  

I code reviewed and approved the patch for Bug#23692.  But it got me 
thinking about our limit searches...

So I tweaked my LIMIT SQL from yesterday to see how we do here and sure 
enough, it shows another problem with the our current RUN version of 
multisegmented keys.  The RUN length is always padded with 0x00, not the 
pad character.  So the last query below gets the wrong answer.  If we 
padded each RUN with the pad character, it might be correct more often. 
  But it would still not be correct when the actual length is a multiple 
of RUN since there would be no padding.

The first limit query sorted just by f1 also fails.  Your current 
solution in this bug addresses non-limit searches, where the server can 
resort the answer.  It allows us to find the right answer even if the 
index is sorted incorrectly.  But if the server depends on our search 
order, we do not have a solution, because our storage order is incorrect.

I consider this a LIMIT problem and it should be a new bug, so that we 
can push this patch for Bug#23692.  Whereas 23692 is concerned with 
finding the correct values, the new bug would be concerned with the 
order they display using a limit query.  Can you open that bug?

I think the only solution is to add the dreaded pad character to the end 
of every char and varchar string created by makeKey, just in case that 
string also exists with an appended character < the pad character. I 
wish there was another solution.

Note that the second limit query sorted by f2 succeeds because we have 
no index on f2 and the server must re-sort.

Here is the test.
drop table t1;
create table t1 (f1 CHAR(5), f2 VARCHAR(5), f3 char(20),
                  key(f1), key(f2), key(f1,f2,f3)) engine=falcon;
insert into t1 values ('B', 'B', 'B');
insert into t1 values ('A', 'A', 'A');
insert into t1 values (0x00000240, 0x00000240, 'oh-oh-two-A');
insert into t1 values (0x00000202, 0x00000202, 'oh-oh-two-two');
insert into t1 values (0x000002, 0x000002, 'oh-oh-two-space');
insert into t1 values (0x0041, 0x0041, 'oh-B');
insert into t1 values (0x0002, 0x0002, 'oh-two');
insert into t1 values (0x0001, 0x0001, 'oh-one');
insert into t1 values (0x00, 0x00, 'oh-space');
insert into t1 values ('', '', 'none');
insert into t1 values (null, null, 'null');
select f1, hex(f1), f2, hex(f2), f3 from t1;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f1;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f1 limit 9;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f2;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f2 limit 9;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f1,f2,f3 ;
select f1, hex(f1), f2, hex(f2), f3 from t1 order by f1,f2,f3 limit 9 ;

Kevin Lewis
Falcon Team Lead

Bug Database wrote:
>  Updated by:           Kevin Lewis
>  Reported by:          Peter Gulutzan
>  Category:             Server: Falcon
>  Severity:             S3 (Non-critical)
> -Status:               Patch pending
> +Status:               Patch approved
>  Changeset:  
>  Version:              5.1.13-falcon-alpha-pb-debug
>  OS:                   Linux
>  OS Details:           SUSE 10.0 / 64-bit
>  Target Version:       6.0
>  Defect Class:         D2 (Serious)
>  Assigned To:          Lars-Erik Bjørk
>  Priority:             P4 (Low)
>  Workaround Viability: W1 (None)
>  Impact:               I4 (Minimal)
>  Verifier:             Hakan Kuecuekyilmaz
> +Reviewer:             Kevin Lewis [done]
>  Lead:                 Kevin Lewis
>  Internal Tags:        CHECKED
>  Triage:               Triaged
> [20 Feb 22:14] Kevin Lewis <klewis@stripped>
> Looks like a good soluition and the code looks good.
> ------------------------------------------------------------------------
> [20 Feb 13:12] Bugs System
> 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:
> 3030 lars-erik.bjork@stripped	2009-02-20
>       This is a patch for bug#23692 (Falcon: searches fail if data is
> 0x00)
>       The solution is to append a pad key to the upper 
>       bound search key, if its last character is equal
>       to or greater than the pad character. This is done
>       In order to make it position after all values with 
>       trailing characters lower than the pad character.
>       For fields with a collation registered
>       [if (field->collation)], there is no efficient way
>       of checking if the last character is equal or greater
>       than the pad character, without iterating through the
>       entire key from the beginning.
>       I have discussed this with Alexander Barkov who suggests
>       to always pad the upper bound search key in these cases,
>       and to pad it to the length of the key, instead of 
>       appending just a single character. This way I can use the
>       existing cs->coll->strnxfrm function.
>       In the other cases, I have checked on the last byte and
>       appended 0x20 if the byte was >= 0x20.
>       I have also added one more parameter to the makeKey methods
>       to say that this is a highKey.
> ------------------------------------------------------------------------
> [12 Oct 2008 15:48] *PRIVATE* Omer BarNir <omer.barnir@stripped>
> triage: setting tag to CHECKED
> ------------------------------------------------------------------------
> [26 Sep 2008 19:00] John H. Embretsen <john.embretsen@stripped>
> Test result file associated with the attached falcon_bug_23692.test.
> Attachment: falcon_bug_23692.result (application/octet-stream), 1543 bytes.
> ------------------------------------------------------------------------
> [26 Sep 2008 18:59] John H. Embretsen <john.embretsen@stripped>
> Test case for this bug. Moved from falcon_team suite. Will fail until
> bug is fixed.
> Attachment: falcon_bug_23692.test (application/octet-stream), 1423 bytes.
> ------------------------------------------------------------------------
> [27 Jun 2008 0:01] Kevin Lewis <klewis@stripped>
> Another character-set related bug.
> ------------------------------------------------------------------------
> Earlier comments can be viewed at
> Edit this bug report at
Patch for Bug#23692Kevin Lewis20 Feb
  • Re: Patch for Bug#23692Lars-Erik Bjørk22 Feb