**
  **   1. The index is itself UNIQUE, and
  **
  **   2. All of the columns in the index are either part of the pDistinct
  **      list, or else the WHERE clause contains a term of the form "col=X",
  **      where X is a constant value. The collation sequences of the
  **      comparison and select-list expressions must match those of the index.



  */
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    if( pIdx->onError==OE_None ) continue;
    for(i=0; i<pIdx->nColumn; i++){
      int iCol = pIdx->aiColumn[i];
      if( 0==findTerm(pWC, iBase, iCol, ~(Bitmask)0, WO_EQ, pIdx) 
       && 0>findIndexCol(pParse, pDistinct, iBase, pIdx, i)
      ){
        break;

      }
    }
    if( i==pIdx->nColumn ){
      /* This index implies that the DISTINCT qualifier is redundant. */
      return 1;
    }
  }
................................................................................
  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }
  if( pIdx->onError!=OE_None && i==pIdx->nColumn
      && (wsFlags & WHERE_COLUMN_NULL)==0
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){




    /* All terms of this index match some prefix of the ORDER BY clause
    ** and the index is UNIQUE and no terms on the tail of the ORDER BY
    ** clause reference other tables in a join.  If this is all true then
    ** the order by clause is superfluous.  Not that if the matching
    ** condition is IS NULL then the result is not necessarily unique
    ** even on a UNIQUE index, so disallow those cases. */












    return 1;
  }
  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating

  **
  **   1. The index is itself UNIQUE, and
  **
  **   2. All of the columns in the index are either part of the pDistinct
  **      list, or else the WHERE clause contains a term of the form "col=X",
  **      where X is a constant value. The collation sequences of the
  **      comparison and select-list expressions must match those of the index.
  **
  **   3. All of those index columns for which the WHERE clause does not
  **      contain a "col=X" term are subject to a NOT NULL constraint.
  */
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    if( pIdx->onError==OE_None ) continue;
    for(i=0; i<pIdx->nColumn; i++){
      int iCol = pIdx->aiColumn[i];
      if( 0==findTerm(pWC, iBase, iCol, ~(Bitmask)0, WO_EQ, pIdx) ){
        int iIdxCol = findIndexCol(pParse, pDistinct, iBase, pIdx, i);
        if( iIdxCol<0 || pTab->aCol[pIdx->aiColumn[i]].notNull==0 ){
          break;
        }
      }
    }
    if( i==pIdx->nColumn ){
      /* This index implies that the DISTINCT qualifier is redundant. */
      return 1;
    }
  }
................................................................................
  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }
  if( pIdx->onError!=OE_None && i==pIdx->nColumn
      && (wsFlags & WHERE_COLUMN_NULL)==0
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) 
  ){
    Column *aCol = pIdx->pTable->aCol;
    int i;

    /* All terms of this index match some prefix of the ORDER BY clause,
    ** the index is UNIQUE, and no terms on the tail of the ORDER BY




    ** refer to other tables in a join. So, assuming that the index entries
    ** visited contain no NULL values, then this index delivers rows in
    ** the required order.
    **
    ** It is not possible for any of the first nEqCol index fields to be
    ** NULL (since the corresponding "=" operator in the WHERE clause would 
    ** not be true). So if all remaining index columns have NOT NULL 
    ** constaints attached to them, we can be confident that the visited
    ** index entries are free of NULLs.  */
    for(i=nEqCol; i<pIdx->nColumn; i++){
      if( aCol[pIdx->aiColumn[i]].notNull==0 ) break;
    }
    return (i==pIdx->nColumn);
  }
  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating

do_execsql_test 1.0 {
  CREATE TABLE t1(a, b, c, d);
  CREATE UNIQUE INDEX i1 ON t1(b, c);
  CREATE UNIQUE INDEX i2 ON t1(d COLLATE nocase);

  CREATE TABLE t2(x INTEGER PRIMARY KEY, y);

  CREATE TABLE t3(c1 PRIMARY KEY, c2);
  CREATE INDEX i3 ON t3(c2);




}
foreach {tn noop sql} {


  1   1   "SELECT DISTINCT b, c FROM t1"
  2   1   "SELECT DISTINCT c FROM t1 WHERE b = ?"

  3   1   "SELECT DISTINCT rowid FROM t1"
  4   1   "SELECT DISTINCT rowid, a FROM t1"
  5   1   "SELECT DISTINCT x FROM t2"
  6   1   "SELECT DISTINCT * FROM t2"
  7   1   "SELECT DISTINCT * FROM (SELECT * FROM t2)"


  8   1   "SELECT DISTINCT * FROM t1"

  8   0   "SELECT DISTINCT a, b FROM t1"

  9   0   "SELECT DISTINCT c FROM t1 WHERE b IN (1,2)"
  10  0   "SELECT DISTINCT c FROM t1"
  11  0   "SELECT DISTINCT b FROM t1"

  12  0   "SELECT DISTINCT a, d FROM t1"

  13  0   "SELECT DISTINCT a, b, c COLLATE nocase FROM t1"


  14  1   "SELECT DISTINCT a, d COLLATE nocase FROM t1"

  15  0   "SELECT DISTINCT a, d COLLATE binary FROM t1"

  16  1   "SELECT DISTINCT a, b, c COLLATE binary FROM t1"

  16  0   "SELECT DISTINCT t1.rowid FROM t1, t2"
  17  0   { /* Technically, it would be possible to detect that DISTINCT
            ** is a no-op in cases like the following. But SQLite does not
            ** do so. */
            SELECT DISTINCT t1.rowid FROM t1, t2 WHERE t1.rowid=t2.rowid }

................................................................................
  21  0   "SELECT DISTINCT c2 FROM t3"

  22  0   "SELECT DISTINCT * FROM (SELECT 1, 2, 3 UNION SELECT 4, 5, 6)"
  23  1   "SELECT DISTINCT rowid FROM (SELECT 1, 2, 3 UNION SELECT 4, 5, 6)"

  24  0   "SELECT DISTINCT rowid/2 FROM t1"
  25  1   "SELECT DISTINCT rowid/2, rowid FROM t1"
  26  1   "SELECT DISTINCT rowid/2, b FROM t1 WHERE c = ?"

} {
  if {$noop} {
    do_distinct_noop_test 1.$tn $sql
  } else {
    do_distinct_not_noop_test 1.$tn $sql
  }
}

do_execsql_test 1.0 {
  CREATE TABLE t1(a, b, c, d);
  CREATE UNIQUE INDEX i1 ON t1(b, c);
  CREATE UNIQUE INDEX i2 ON t1(d COLLATE nocase);

  CREATE TABLE t2(x INTEGER PRIMARY KEY, y);

  CREATE TABLE t3(c1 PRIMARY KEY NOT NULL, c2 NOT NULL);
  CREATE INDEX i3 ON t3(c2);

  CREATE TABLE t4(a, b NOT NULL, c NOT NULL, d NOT NULL);
  CREATE UNIQUE INDEX t4i1 ON t4(b, c);
  CREATE UNIQUE INDEX t4i2 ON t4(d COLLATE nocase);
}
foreach {tn noop sql} {

  1.1 0   "SELECT DISTINCT b, c FROM t1"
  1.2 1   "SELECT DISTINCT b, c FROM t4"
  2.1 0   "SELECT DISTINCT c FROM t1 WHERE b = ?"
  2.2 1   "SELECT DISTINCT c FROM t4 WHERE b = ?"
  3   1   "SELECT DISTINCT rowid FROM t1"
  4   1   "SELECT DISTINCT rowid, a FROM t1"
  5   1   "SELECT DISTINCT x FROM t2"
  6   1   "SELECT DISTINCT * FROM t2"
  7   1   "SELECT DISTINCT * FROM (SELECT * FROM t2)"

  8.1 0   "SELECT DISTINCT * FROM t1"
  8.2 1   "SELECT DISTINCT * FROM t4"

  8   0   "SELECT DISTINCT a, b FROM t1"

  9   0   "SELECT DISTINCT c FROM t1 WHERE b IN (1,2)"
  10  0   "SELECT DISTINCT c FROM t1"
  11  0   "SELECT DISTINCT b FROM t1"

  12.1 0   "SELECT DISTINCT a, d FROM t1"
  12.2 0   "SELECT DISTINCT a, d FROM t4"
  13.1 0   "SELECT DISTINCT a, b, c COLLATE nocase FROM t1"
  13.2 0   "SELECT DISTINCT a, b, c COLLATE nocase FROM t4"
  14.1 0   "SELECT DISTINCT a, d COLLATE nocase FROM t1"
  14.2 1   "SELECT DISTINCT a, d COLLATE nocase FROM t4"

  15   0   "SELECT DISTINCT a, d COLLATE binary FROM t1"
  16.1 0   "SELECT DISTINCT a, b, c COLLATE binary FROM t1"
  16.2 1   "SELECT DISTINCT a, b, c COLLATE binary FROM t4"

  16  0   "SELECT DISTINCT t1.rowid FROM t1, t2"
  17  0   { /* Technically, it would be possible to detect that DISTINCT
            ** is a no-op in cases like the following. But SQLite does not
            ** do so. */
            SELECT DISTINCT t1.rowid FROM t1, t2 WHERE t1.rowid=t2.rowid }

................................................................................
  21  0   "SELECT DISTINCT c2 FROM t3"

  22  0   "SELECT DISTINCT * FROM (SELECT 1, 2, 3 UNION SELECT 4, 5, 6)"
  23  1   "SELECT DISTINCT rowid FROM (SELECT 1, 2, 3 UNION SELECT 4, 5, 6)"

  24  0   "SELECT DISTINCT rowid/2 FROM t1"
  25  1   "SELECT DISTINCT rowid/2, rowid FROM t1"
  26.1  0   "SELECT DISTINCT rowid/2, b FROM t1 WHERE c = ?"
  26.2  1   "SELECT DISTINCT rowid/2, b FROM t4 WHERE c = ?"
} {
  if {$noop} {
    do_distinct_noop_test 1.$tn $sql
  } else {
    do_distinct_not_noop_test 1.$tn $sql
  }
}

# 2012 April 19
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# The tests in this file were used while developing the SQLite 4 code. 
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix tkt-2a5629202f

# This procedure executes the SQL.  Then it checks to see if the OP_Sort
# opcode was executed.  If an OP_Sort did occur, then "sort" is appended
# to the result.  If no OP_Sort happened, then "nosort" is appended.
#
# This procedure is used to check to make sure sorting is or is not
# occurring as expected.
#
proc cksort {sql} {
  set data [execsql $sql]
  if {[db status sort]} {set x sort} {set x nosort}
  lappend data $x
  return $data
}

do_execsql_test 1.1 {
  CREATE TABLE t8(b TEXT, c TEXT);
  INSERT INTO t8 VALUES('a',  'one');
  INSERT INTO t8 VALUES('b',  'two');
  INSERT INTO t8 VALUES(NULL, 'three');
  INSERT INTO t8 VALUES(NULL, 'four');
}

do_execsql_test 1.2 {
  SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
} {null/four null/three a/one b/two}

do_execsql_test 1.3 {
  CREATE UNIQUE INDEX i1 ON t8(b);
  SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
} {null/four null/three a/one b/two}

#-------------------------------------------------------------------------
#

do_execsql_test 2.1 {
  CREATE TABLE t2(a, b NOT NULL, c);
  CREATE UNIQUE INDEX t2ab ON t2(a, b);
  CREATE UNIQUE INDEX t2ba ON t2(b, a);
}

do_test 2.2 {
  cksort { SELECT * FROM t2 WHERE a = 10 ORDER BY a, b, c }
} {nosort}

do_test 2.3 {
  cksort { SELECT * FROM t2 WHERE b = 10 ORDER BY a, b, c }
} {sort}

do_test 2.4 {
  cksort { SELECT * FROM t2 WHERE a IS NULL ORDER BY a, b, c }
} {sort}

finish_test

# 2012 April 02
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# The tests in this file were used while developing the SQLite 4 code. 
#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix tkt-385a5b56b9

do_execsql_test 1.0 { 
  CREATE TABLE t1(x, y);
  INSERT INTO t1 VALUES(1, NULL);
  INSERT INTO t1 VALUES(2, NULL);
  INSERT INTO t1 VALUES(1, NULL);
}

do_execsql_test 1.1 { SELECT DISTINCT x, y FROM t1 } {1 {} 2 {}}
do_execsql_test 1.2 { CREATE UNIQUE INDEX i1 ON t1(x, y) }
do_execsql_test 1.3 { SELECT DISTINCT x, y FROM t1 } {1 {} 2 {}}


#-------------------------------------------------------------------------

do_execsql_test 2.0 {
  CREATE TABLE t2(x, y NOT NULL);
  CREATE UNIQUE INDEX t2x ON t2(x);
  CREATE UNIQUE INDEX t2y ON t2(y);
}

do_eqp_test 2.1 { SELECT DISTINCT x FROM t2 } {
  0 0 0 {SCAN TABLE t2 USING COVERING INDEX t2x (~1000000 rows)}
}

do_eqp_test 2.2 { SELECT DISTINCT y FROM t2 } {
  0 0 0 {SCAN TABLE t2 (~1000000 rows)}
}

do_eqp_test 2.3 { SELECT DISTINCT x, y FROM t2 WHERE y=10 } {
  0 0 0 {SEARCH TABLE t2 USING INDEX t2y (y=?) (~1 rows)}
}

do_eqp_test 2.4 { SELECT DISTINCT x, y FROM t2 WHERE x=10 } {
  0 0 0 {SEARCH TABLE t2 USING INDEX t2x (x=?) (~1 rows)}
}

finish_test

} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.4 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {

  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.6 {

  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {

} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.4 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.6 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {