svn commit - mysqldoc@docsrva: r3599 - trunk/internals

[jon]

Author: jstephens
Date: 2006-10-11 08:29:28 +0200 (Wed, 11 Oct 2006)
New Revision: 3599

Log:

Adding Sergey P's new NULLs filtering writeup.



Modified:
   trunk/internals/optimizer.xml


Modified: trunk/internals/optimizer.xml
===================================================================
--- trunk/internals/optimizer.xml	2006-10-11 06:18:16 UTC (rev 3598)
+++ trunk/internals/optimizer.xml	2006-10-11 06:29:28 UTC (rev 3599)
Changed blocks: 1, Lines Added: 132, Lines Deleted: 0; 4746 bytes

@@ -1738,7 +1738,139 @@
       In this section, we discuss other, more specialized optimizations
       performed in the MySQL server.
     </para>
+    
+    <section id="optimizer-nulls-filtering">
 
+  <title><literal>NULL</literal>s Filtering for <literal>ref</literal> and
+    <literal>eq_ref</literal> Access</title>
+
+  <para>
+    This section discusses the <literal>NULL</literal>s filtering
+    optimization used for <literal>ref</literal> and
+    <literal>eq_ref</literal> joins.
+  </para>
+
+  <section id="optimizer-early-nulls-filtering">
+
+    <title>Early <literal>NULL</literal>s Filtering</title>
+
+    <para>
+      Suppose we have a join order such as this one:
+    </para>
+
+<programlisting>
+...,  tblX, ..., tblY, ...
+</programlisting>
+
+    <para>
+      Suppose further that table <literal>tblY</literal> is accessed via
+      <literal>ref</literal> or <literal>eq_ref</literal> access on
+    </para>
+
+<programlisting>    
+tblY.<replaceable>key_column</replaceable> = tblX.<replaceable>column</replaceable>
+</programlisting>
+
+    <para>
+      or, in the case of <literal>ref</literal> access using multiple
+      key parts, via
+    </para>
+
+<programlisting>    
+... AND tblY.key_part<replaceable>N</replaceable> = tblX.<replaceable>column</replaceable> AND ...
+</programlisting>
+
+    <para>
+      where <literal>tblX.<replaceable>column</replaceable></literal>
+      can be <literal>NULL</literal>. Here the early
+      <literal>NULL</literal>s filtering for <literal>ref</literal> (or
+      <literal>eq_ref</literal>) access is applied. We make the
+      following inference:
+    </para>
+
+<programlisting>    
+(tblY.key_part<replaceable>N</replaceable> = tblX.<replaceable>column</replaceable>)  =&gt;  (tblX.<replaceable>column</replaceable> IS NOT NULL)
+</programlisting>
+
+    <para>
+      The original equality can be checked only after we've read the
+      current rows of both tables <literal>tblX</literal> and
+      <literal>tblY</literal>. The <literal>IS NOT NULL</literal>
+      predicate can be checked after we've read the current row of table
+      <literal>tblX</literal>. If there are any tables in the join order
+      between <literal>tblX</literal> and <literal>tblY</literal>, the
+      added <literal>IS NOT NULL</literal> check will allow us to skip
+      accessing those tables.
+    </para>
+
+    <para>
+      This feature is implemented in these places in the server code:
+    </para>
+
+    <itemizedlist>
+
+      <listitem>
+        <para>
+          The <literal>ref</literal> analyzer (contained in such
+          functions as <literal>update_ref_and_keys()</literal>) detects
+          and marks equalities like that shown above by setting
+          <literal>KEY_FIELD::null_rejecting=TRUE</literal>.
+        </para>
+      </listitem>
+
+      <listitem>
+        <para>
+          After the join order has been choosen,
+          <literal>add_not_null_conds()</literal> adds appropriate
+          <literal>IS NOT NULL</literal> predicates to the conditions of
+          the appropriate tables.
+        </para>
+      </listitem>
+
+    </itemizedlist>
+
+    <para>
+      It is possible to add <literal>IS NOT NULL</literal> predicates
+      for all equalities that could be used for <literal>ref</literal>
+      access (and not for those that are actually used). However, this
+      is currently not done.
+    </para>
+
+  </section>
+
+  <section id="optimizer-late-nulls-filtering">
+
+    <title>Late <literal>NULL</literal>s Filtering</title>
+
+    <para>
+      Suppose we have a query plan with table <literal>tblX</literal>
+      being accessed via the <literal>ref</literal> access method:
+    </para>
+
+<programlisting>    
+tblX.key_part1 = expr1 AND tblX.key_part2 = expr2 AND ...
+</programlisting>
+
+    <para>
+      Before performing an index lookup, we determine whether any of the
+      <literal>expr<replaceable>i</replaceable></literal> values is
+      <literal>NULL</literal>. If it is, we don't perform the lookup,
+      but rather immediately return that the matching tuple is not
+      found.
+    </para>
+
+    <para>
+      This optimization reuses the <literal>null_rejecting</literal>
+      attribute produced by the early <literal>NULL</literal>s filtering
+      code (see <xref linkend="optimizer-early-nulls-filtering"/>). The
+      check itself is located in the function
+      <literal>join_read_always_key()</literal>.
+    </para>
+
+  </section>
+
+</section>
+
     <section id="optimizer-partitioning-related">
 
       <title>Partitioning-Related Optimizations</title>