SQLite

  sqlite3 *db = pParse->db;
  int i;

  nExpr = pList->nExpr;
  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1);
  if( pInfo ){
    assert( sqlite3KeyInfoIsWriteable(pInfo) );
    for(i=iStart, pItem=pList->a; i<nExpr; i++, pItem++){
    for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
      CollSeq *pColl;
      pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
      if( !pColl ) pColl = db->pDfltColl;
      pInfo->aColl[i] = pColl;
      pInfo->aSortOrder[i] = pItem->sortOrder;
      pInfo->aColl[i-iStart] = pColl;
      pInfo->aSortOrder[i-iStart] = pItem->sortOrder;
    }
  }
  return pInfo;
}

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*

    explainTempTable(pParse, "DISTINCT");
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( sSort.pOrderBy ){
    explainTempTable(pParse, "ORDER BY");
    explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
    generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
  }

  /* Jump here to skip this query
  */
  sqlite3VdbeResolveLabel(v, iEnd);

        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly 4*N*log(N).
            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).
            ** If some but not all of the columns are in sorted order, then
            ** scale down the log(N) term. */
            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
            LogEst rSortCost = 20 + nRowEst +
            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;
                                estLog(nRowEst)*(nOrderBy-isOrdered)/nOrderBy;
            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,
               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
                sqlite3LogEstAdd(rCost,rSortCost)));
            rCost = sqlite3LogEstAdd(rCost, rSortCost);
          }
        }else{

  INSERT INTO t1 VALUES('a', 'b', 'c');
  INSERT INTO t1 VALUES('A', 'B', 'C');
}

foreach {tn sql temptables res} {
  1   "a, b FROM t1"                                       {}      {A B a b}
  2   "b, a FROM t1"                                       {}      {B A b a}
  3   "a, b, c FROM t1"                                    {hash}  {a b c A B C}
  3   "a, b, c FROM t1"                                    {hash}  {A B C a b c}
  4   "a, b, c FROM t1 ORDER BY a, b, c"                   {btree} {A B C a b c}
  5   "b FROM t1 WHERE a = 'a'"                            {}      {b}
  6   "b FROM t1 ORDER BY +b COLLATE binary"          {btree hash} {B b}
  7   "a FROM t1"                                          {}      {A a}
  8   "b COLLATE nocase FROM t1"                           {}      {b}
  9   "b COLLATE nocase FROM t1 ORDER BY b COLLATE nocase" {}      {b}
} {

  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.7 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE +a=0;
} {/B-TREE/}

# In some cases, it is faster to do repeated index lookups than it is to
# sort.  But in other cases, it is faster to sort than to do repeated index
# lookups.
#
do_execsql_test 2.1 {
do_execsql_test 2.1a {
  CREATE TABLE t2(a,b,c);
  CREATE INDEX t2bc ON t2(b,c);
  ANALYZE;
  INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9');
  INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5');
  ANALYZE sqlite_master;

  EXPLAIN QUERY PLAN
  SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}
do_execsql_test 2.1b {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}
} {/B-TREE/}


do_execsql_test 2.2 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
} {/B-TREE/}
do_execsql_test 2.3 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;

do_eqp_test whereG-1.5 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {/.*track.*composer.*album.*/}
} {/.*track.*(composer.*album|album.*composer).*/}
do_execsql_test whereG-1.6 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND composer.cid=track.cid
     AND album.aid=track.aid;
} {{Mass in B Minor, BWV 232}}

do_eqp_test whereG-1.7 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {/.*track.*composer.*album.*/}
} {/.*track.*(composer.*album|album.*composer).*/}
do_execsql_test whereG-1.8 {
  SELECT DISTINCT aname
    FROM album, composer, track
   WHERE cname LIKE '%bach%'
     AND unlikely(composer.cid=track.cid)
     AND unlikely(album.aid=track.aid);
} {{Mass in B Minor, BWV 232}}