From: Zardosht Kasheff
Date: July 22 2009 1:40pm
Subject: Re: help with index_merge and clustering keys
List-Archive: http://lists.mysql.com/internals/37220
Message-Id: <2f9663ba0907220640s41327d0cx53151e086c9e2c3f@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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:

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


   if (!(tree->ror_scans=3D (ROR_SCAN_INFO**)alloc_root(param->mem_root,
                                                      sizeof(ROR_SCAN_INFO*=
)*
@@ -4516,8 +4517,20 @@
   for (idx=3D 0, cur_ror_scan=3D tree->ror_scans; idx < param->keys; idx++=
)
   {
     ROR_SCAN_INFO *scan;
+    uint keyno=3D param->real_keynr[idx];
+
     if (!tree->ror_scans_map.is_set(idx))
+    {
       continue;
+    }
+    /*
+      Ignore clustering keys.
+    */
+    if (keyno !=3D cpk_no && param->table->key_info[keyno].flags & HA_CLUS=
TERING
&& supports_clustered_keys)
+    {
+      tree->n_ror_scans--;
+      continue;
+    }
     if (!(scan=3D 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 =3D=3D 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> wrot=
e:
> 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 "=3D 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() fun=
ction.
> 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() call=
s 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 complic=
ated
> as N ranges over different indexes give =A02^N-N possible ways to interse=
ct 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. =A0The idea is that we available range scans by their
> desirability:
>
> =A0ranges[]=3D {range_scan(key1), range_scan(key2), range_scan(key3) }
>
> and then consider doing intersect on
> =A0ranges[0], ranges[1]
> =A0ranges[0], ranges[1], ranges[2]
> =A0ranges[0], ranges[1], ranges[2], ranges[3]
> =A0... and so forth
>
> and pick the best intersection.
>
> After that, get_best_covering_ror_intersect() is called which uses a simi=
lar
> 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=3DRowid Ordered Retrieval. At the moment we only support intersec=
tion of
> ordered streams, more exactly rowid-ordered. index scans are expected pro=
duce
> records in rowid order when:
> * it is a scan on clustered primary key
> * it is a scan on "keyXpart1=3Dconst AND .. keyXpartN=3Dconst", where N i=
s the last
> =A0[visible] part.
>
> BR
> =A0Sergey
> --
> Sergey Petrunia, Software Developer
> Monty Program AB, http://askmonty.org
> Blog: http://s.petrunia.net/blog
>