List:Internals« Previous MessageNext Message »
From:Zardosht Kasheff Date:July 22 2009 1:40pm
Subject:Re: help with index_merge and clustering keys
View as plain text  
Hello Sergey,

Thanks a lot for the recommended fix. This is the fix that seems to be
working for me, and I figured I would post it on this forum to see if
anyone might find issues with it:

===================================================================
--- opt_range.cc        (revision 13471)
+++ opt_range.cc        (working copy)
@@ -4505,6 +4505,7 @@
   ROR_SCAN_INFO *cpk_scan= NULL;
   uint cpk_no;
   bool cpk_scan_used= FALSE;
+  bool supports_clustered_keys = param->table->file->supports_clustered_keys();


   if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
                                                      sizeof(ROR_SCAN_INFO*)*
@@ -4516,8 +4517,20 @@
   for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
   {
     ROR_SCAN_INFO *scan;
+    uint keyno= param->real_keynr[idx];
+
     if (!tree->ror_scans_map.is_set(idx))
+    {
       continue;
+    }
+    /*
+      Ignore clustering keys.
+    */
+    if (keyno != cpk_no && param->table->key_info[keyno].flags &
HA_CLUSTERING
&& supports_clustered_keys)
+    {
+      tree->n_ror_scans--;
+      continue;
+    }
     if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))


I had to put the clustering key check in a separate if-clause, because
tree->n_ror_scans needs to be decremented (for the same reasons it is
decremented when keyno == cpk_no). That is the only difference.

This fix seems to be working for me. If anyone on the internals list
has any comments on this fix, I would greatly appreciate it.
Otherwise, thanks a lot for the help in solving this problem.

-Zardosht

On Wed, Jul 15, 2009 at 6:20 AM, Sergey Petrunya<psergey@stripped> wrote:
> On Sun, Jul 12, 2009 at 01:01:14PM -0400, Zardosht Kasheff wrote:
>> ah, yes, I made the mistake of making my example have equality checks
>> instead of ranges.
>>
>> So instead of "= 1", suppose each of the range checks are "> 1" (or >
>> 100000, some value where the optimizer needs records_in_range to
>> determine the cost estimate of using a key).
>>
>> So for the simple example Rich mentioned, "select * from foo where a >
>> 1 and b > 1"
>> The more complex example, "select * from foo where a > 1 and b > 1
>> and c > 1 and d > 1"
>>
>> What happens here?
> Ok, here it goes:
>
> The whole process is in opt_range.cc, SQL_SELECT::test_quick_select() function.
> get_mm_tree() call analyzes the WHERE condition and constructs possible
> range/index_merge accesses.
>
> Then get_key_scans_params() is called, which uses records_in_range() calls to
> get #records estimates and costs for range accesses (i.e. accesses using
> individual indexes), and picks the best range access (this is fairly easy as
> the number of options is limited by the number of available indexes).
>
> Then it starts looking for best ROR[*]-intersection. This is more complicated
> as N ranges over different indexes give  2^N-N possible ways to intersect it.
> This is done in two steps
>
> * get_best_ror_intersect() searches for best ROR-intersection
>
> Then get_best_ror_intersect() is called which tries to construct a
> ROR-intersection.  The idea is that we available range scans by their
> desirability:
>
>  ranges[]= {range_scan(key1), range_scan(key2), range_scan(key3) }
>
> and then consider doing intersect on
>  ranges[0], ranges[1]
>  ranges[0], ranges[1], ranges[2]
>  ranges[0], ranges[1], ranges[2], ranges[3]
>  ... and so forth
>
> and pick the best intersection.
>
> After that, get_best_covering_ror_intersect() is called which uses a similar
> approach but only considers covering intersections (i.e. those where one won't
> have to call rnd_pos() to retrieve the full table record).
>
> This algorithm works, albeit not fully, it is known to make poor choices in
> certain situations.
>
> Hope this clarifies things a bit.
>
> [*] ROR=Rowid Ordered Retrieval. At the moment we only support intersection of
> ordered streams, more exactly rowid-ordered. index scans are expected produce
> records in rowid order when:
> * it is a scan on clustered primary key
> * it is a scan on "keyXpart1=const AND .. keyXpartN=const", where N is the last
>  [visible] part.
>
> BR
>  Sergey
> --
> Sergey Petrunia, Software Developer
> Monty Program AB, http://askmonty.org
> Blog: http://s.petrunia.net/blog
>
Thread
help with index_merge and clustering keysZardosht Kasheff23 Jun
  • Re: help with index_merge and clustering keysZardosht Kasheff9 Jul
    • Re: help with index_merge and clustering keysSergey Petrunya10 Jul
      • Re: help with index_merge and clustering keysZardosht Kasheff10 Jul
        • RE: help with index_merge and clustering keysRick James10 Jul
          • RE: help with index_merge and clustering keysMichael Widenius16 Jul
            • Re: help with index_merge and clustering keysZardosht Kasheff16 Jul
            • RE: help with index_merge and clustering keysRick James16 Jul
              • RE: help with index_merge and clustering keysMichael Widenius19 Jul
        • Re: help with index_merge and clustering keysSergey Petrunya12 Jul
          • Re: help with index_merge and clustering keysZardosht Kasheff12 Jul
            • Re: help with index_merge and clustering keysSergey Petrunya15 Jul
              • RE: help with index_merge and clustering keysRick James15 Jul
              • Re: help with index_merge and clustering keysZardosht Kasheff24 Jul
      • Re: help with index_merge and clustering keysMichael Widenius16 Jul
Re: help with index_merge and clustering keysZardosht Kasheff10 Jul
Re: help with index_merge and clustering keysZardosht Kasheff16 Jul
  • RE: help with index_merge and clustering keysRick James16 Jul
    • Re: help with index_merge and clustering keysZardosht Kasheff16 Jul