SQLite

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.209 2006/06/06 11:45:55 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

    double lowestCost;          /* Cost of the pBest */
    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */

    lowestCost = SQLITE_BIG_DBL;
    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      int doNotReorder;  /* True if this table should not be reordered */

      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0
                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);

      if( once && doNotReorder ) break;

      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      cost = bestIndex(pParse, &wc, pTabItem, notReady,
                       (i==0 && ppOrderBy) ? *ppOrderBy : 0,
                       &pIdx, &flags, &nEq);
      if( cost<lowestCost ){
        once = 1;
        lowestCost = cost;
        pBest = pIdx;
        bestFlags = flags;
        bestNEq = nEq;
        bestJ = j;
      }
      if( doNotReorder ) break;
    }
    TRACE(("*** Optimizer choose table %d for loop %d\n", bestJ,
           pLevel-pWInfo->a));
    if( (bestFlags & WHERE_ORDERBY)!=0 ){
      *ppOrderBy = 0;
    }
    andFlags &= bestFlags;

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the join reordering optimization
# in cases that include a LEFT JOIN.
#
# $Id: where3.test,v 1.2 2006/06/06 11:45:55 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# The following is from ticket #1652.
#
# A comma join then a left outer join:  A,B left join C.

    INSERT INTO t3 VALUES(999,'nine');
    CREATE INDEX t3i1 ON t3(x);
    
    SELECT * FROM t1, t2 LEFT JOIN t3 ON q=x WHERE p=2 AND a=q;
  }
} {222 two 2 222 {} {}}

# Ticket #1830
#
# This is similar to the above but with the LEFT JOIN on the
# other side.
#
do_test where3-1.2 {
  execsql {
    CREATE TABLE parent1(parent1key, child1key, Child2key, child3key);
    CREATE TABLE child1 ( child1key NVARCHAR, value NVARCHAR );
    CREATE UNIQUE INDEX PKIDXChild1 ON child1 ( child1key );
    CREATE TABLE child2 ( child2key NVARCHAR, value NVARCHAR );

    INSERT INTO parent1(parent1key,child1key,child2key)
       VALUES ( 1, 'C1.1', 'C2.1' );
    INSERT INTO child1 ( child1key, value ) VALUES ( 'C1.1', 'Value for C1.1' );
    INSERT INTO child2 ( child2key, value ) VALUES ( 'C2.1', 'Value for C2.1' );

    INSERT INTO parent1 ( parent1key, child1key, child2key )
       VALUES ( 2, 'C1.2', 'C2.2' );
    INSERT INTO child2 ( child2key, value ) VALUES ( 'C2.2', 'Value for C2.2' );

    INSERT INTO parent1 ( parent1key, child1key, child2key )
       VALUES ( 3, 'C1.3', 'C2.3' );
    INSERT INTO child1 ( child1key, value ) VALUES ( 'C1.3', 'Value for C1.3' );
    INSERT INTO child2 ( child2key, value ) VALUES ( 'C2.3', 'Value for C2.3' );

    SELECT parent1.parent1key, child1.value, child2.value
    FROM parent1
    LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key
    INNER JOIN child2 ON child2.child2key = parent1.child2key;
  }
} {1 {Value for C1.1} {Value for C2.1} 2 {} {Value for C2.2} 3 {Value for C1.3} {Value for C2.3}}

finish_test