** 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.160 2005/08/12 22:56:09 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".  pIdx is an index on pTab.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints.  Any of these columns may be missing from the ORDER BY
** clause and the match can still be a success.
**
** If the index is UNIQUE, then the ORDER BY clause is allowed to have
** additional terms past the end of the index and the match will still
** be a success.
**
** All terms of the ORDER BY that match against the index must be either
** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
** index do not need to satisfy this constraint.)  The *pbRev value is
** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
** the ORDER BY clause is all ASC.
*/
static int isSortingIndex(
................................................................................
      sortOrder = pTerm->sortOrder;
    }
    j++;
    pTerm++;
  }

  /* The index can be used for sorting if all terms of the ORDER BY clause
  ** or covered or if we ran out of index columns and the it is a UNIQUE
  ** index.
  */
  if( j>=nTerm || (i>=pIdx->nColumn && pIdx->onError!=OE_None) ){

    *pbRev = sortOrder==SQLITE_SO_DESC;
    return 1;
  }
  return 0;
}

/*
................................................................................

/*
** Prepare a crude estimate of the logorithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operatings with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
**
** We can assume N>=1.0;
*/
static double estLog(double N){
  double logN = 1.0;
  double x = 10.0;
  while( N>x ){
    logN = logN+1.0;
    x *= 10;
  }
  return logN;
}

/*
** Find the best index for accessing a particular table.  Return a pointer
................................................................................
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (flags & WHERE_COLUMN_IN)==0 &&
        isSortingIndex(pParse, pProbe, pSrc->pTab, iCur, pOrderBy, nEq, &rev) ){
        if( flags==0 ){
          flags = WHERE_COLUMN_RANGE;
        }
        flags |= WHERE_ORDERBY;
        if( rev ){
          flags |= WHERE_REVERSE;
        }

** 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.161 2005/08/13 16:13:05 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".  pIdx is an index on pTab.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints.  Any of these columns may be missing from the ORDER BY
** clause and the match can still be a success.
**




** All terms of the ORDER BY that match against the index must be either
** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
** index do not need to satisfy this constraint.)  The *pbRev value is
** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
** the ORDER BY clause is all ASC.
*/
static int isSortingIndex(
................................................................................
      sortOrder = pTerm->sortOrder;
    }
    j++;
    pTerm++;
  }

  /* The index can be used for sorting if all terms of the ORDER BY clause
  ** are covered.

  */

  if( j>=nTerm ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
    return 1;
  }
  return 0;
}

/*
................................................................................

/*
** Prepare a crude estimate of the logorithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operatings with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.


*/
static double estLog(double N){
  double logN = 1.0;
  double x = 10.0;
  while( N>x ){
    logN += 1.0;
    x *= 10;
  }
  return logN;
}

/*
** Find the best index for accessing a particular table.  Return a pointer
................................................................................
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (flags & WHERE_COLUMN_IN)==0 &&
           isSortingIndex(pParse,pProbe,pSrc->pTab,iCur,pOrderBy,nEq,&rev) ){
        if( flags==0 ){
          flags = WHERE_COLUMN_RANGE;
        }
        flags |= WHERE_ORDERBY;
        if( rev ){
          flags |= WHERE_REVERSE;
        }

#    May you find forgiveness for yourself and forgive others.
#    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 CREATE TABLE statement.
#
# $Id: sort.test,v 1.21 2005/08/13 12:59:16 drh Exp $

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

# Create a bunch of data to sort against
#
do_test sort-1.0 {
................................................................................
  }
} {3 2 1}
do_test sort-10.3 {
  execsql {
    SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;
  }
} {2 1}

















finish_test

#    May you find forgiveness for yourself and forgive others.
#    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 CREATE TABLE statement.
#
# $Id: sort.test,v 1.22 2005/08/13 16:13:06 drh Exp $

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

# Create a bunch of data to sort against
#
do_test sort-1.0 {
................................................................................
  }
} {3 2 1}
do_test sort-10.3 {
  execsql {
    SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;
  }
} {2 1}

# ticket #1358.  Just because one table in a join gives a unique
# result does not mean they all do.  We cannot disable sorting unless
# all tables in the join give unique results.
#
do_test sort-11.1 {
  execsql {
    create table t8(a unique, b, c);
    insert into t8 values(1,2,3);
    insert into t8 values(2,3,4);
    create table t9(x,y);
    insert into t9 values(2,4);
    insert into t9 values(2,3);
    select y from t8, t9 where a=1 order by a, y;
  }
} {3 4}

finish_test

#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.4 2005/07/29 19:43:59 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
................................................................................
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}


































finish_test

#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.5 2005/08/13 16:13:06 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
................................................................................
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}

# Unique queries (queries that are guaranteed to return only a single
# row of result) do not call the sorter.  But all tables must give
# a unique result.  If any one table in the join does not give a unique
# result then sorting is necessary.
#
do_test where2-7.1 {
  cksort {
    create table t8(a unique, b, c);
    insert into t8 values(1,2,3);
    insert into t8 values(2,3,4);
    create table t9(x,y);
    insert into t9 values(2,4);
    insert into t9 values(2,3);
    select y from t8, t9 where a=1 order by a, y;
  }
} {3 4 sort}
do_test where2-7.2 {
  cksort {
    select * from t8 where a=1 order by b, c
  }
} {1 2 3 nosort}
do_test where2-7.3 {
  cksort {
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 sort}
do_test where2-7.4 {
  cksort {
    create unique index i9y on t9(y);
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 nosort}

finish_test