SQLite

  }else{
    pRet = 0;
  }
  assert( iCol>=0 );
  if( pRet==0 && iCol<p->pEList->nExpr ){
    pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
  }
  return pRet;
}

/*
** The select statement passed as the second parameter is a compound SELECT
** with an ORDER BY clause. This function allocates and returns a KeyInfo
** structure suitable for implementing the ORDER BY.
**
** Space to hold the KeyInfo structure is obtained from malloc. The calling
** function is responsible for ensuring that this structure is eventually
** freed.
*/
static KeyInfo *multiSelectOrderByKeyInfo(Parse *pParse, Select *p, int nExtra){
  ExprList *pOrderBy = p->pOrderBy;
  int nOrderBy = p->pOrderBy->nExpr;
  sqlite3 *db = pParse->db;
  KeyInfo *pRet = sqlite3KeyInfoAlloc(db, nOrderBy+nExtra, 1);
  if( pRet ){
    int i;
    for(i=0; i<nOrderBy; i++){
      struct ExprList_item *pItem = &pOrderBy->a[i];
      Expr *pTerm = pItem->pExpr;
      CollSeq *pColl;

      if( pTerm->flags & EP_Collate ){
        pColl = sqlite3ExprCollSeq(pParse, pTerm);
      }else{
        pColl = multiSelectCollSeq(pParse, p, pItem->u.x.iOrderByCol-1);
        if( pColl==0 ) pColl = db->pDfltColl;
        pOrderBy->a[i].pExpr =
          sqlite3ExprAddCollateString(pParse, pTerm, pColl->zName);
      }
      assert( sqlite3KeyInfoIsWriteable(pRet) );
      pRet->aColl[i] = pColl;
      pRet->aSortOrder[i] = pOrderBy->a[i].sortOrder;
    }
  }

  return pRet;
}
#endif /* SQLITE_OMIT_COMPOUND_SELECT */

#ifndef SQLITE_OMIT_CTE
/*
** This routine generates VDBE code to compute the content of a WITH RECURSIVE

  computeLimitRegisters(pParse, p, addrBreak);
  pLimit = p->pLimit;
  pOffset = p->pOffset;
  regLimit = p->iLimit;
  regOffset = p->iOffset;
  p->pLimit = p->pOffset = 0;
  p->iLimit = p->iOffset = 0;
  pOrderBy = p->pOrderBy;

  /* Locate the cursor number of the Current table */
  for(i=0; ALWAYS(i<pSrc->nSrc); i++){
    if( pSrc->a[i].isRecursive ){
      iCurrent = pSrc->a[i].iCursor;
      break;
    }
  }





  /* Allocate cursors numbers for Queue and Distinct.  The cursor number for
  ** the Distinct table must be exactly one greater than Queue in order
  ** for the SRT_DistTable and SRT_DistQueue destinations to work. */
  iQueue = pParse->nTab++;
  if( p->op==TK_UNION ){
    eDest = pOrderBy ? SRT_DistQueue : SRT_DistTable;
    iDistinct = pParse->nTab++;
  }else{
    eDest = pOrderBy ? SRT_Queue : SRT_Table;
  }
  sqlite3SelectDestInit(&destQueue, eDest, iQueue);

  /* Allocate cursors for Current, Queue, and Distinct. */
  regCurrent = ++pParse->nMem;
  sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);
  if( pOrderBy ){
    KeyInfo *pKeyInfo = multiSelectOrderByKeyInfo(pParse, p, 1);
    sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0,
                      (char*)pKeyInfo, P4_KEYINFO);
    destQueue.pOrderBy = pOrderBy;
  }else{
    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol);
  }
  VdbeComment((v, "Queue table"));
  if( iDistinct ){
    p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0);
    p->selFlags |= SF_UsesEphemeral;
  }

  /* Detach the ORDER BY clause from the compound SELECT */
  p->pOrderBy = 0;

  /* Store the results of the setup-query in Queue. */
  rc = sqlite3Select(pParse, pSetup, &destQueue);
  if( rc ) goto end_of_recursive_query;

  /* Find the next row in the Queue and output that row */
  addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak);

  if( aPermute ){
    struct ExprList_item *pItem;
    for(i=0, pItem=pOrderBy->a; i<nOrderBy; i++, pItem++){
      assert( pItem->u.x.iOrderByCol>0
          && pItem->u.x.iOrderByCol<=p->pEList->nExpr );
      aPermute[i] = pItem->u.x.iOrderByCol - 1;
    }

    pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);
















  }else{
    pKeyMerge = 0;
  }

  /* Reattach the ORDER BY clause to the query.
  */
  p->pOrderBy = pOrderBy;

} [list {*}{
  /g /g/h
  /a /a/d /a/d/f 
          /a/d/e 
     /a/b /a/b/c
}]


# Test name resolution in ORDER BY clauses.
#
do_catchsql_test 10.7.1 {
  WITH t(a) AS (
    SELECT 1 AS b UNION ALL SELECT a+1 AS c FROM t WHERE a<5 ORDER BY a
  ) 
  SELECT * FROM t
} {1 {1st ORDER BY term does not match any column in the result set}}
do_execsql_test 10.7.2 {
  WITH t(a) AS (
    SELECT 1 AS b UNION ALL SELECT a+1 AS c FROM t WHERE a<5 ORDER BY b
  ) 
  SELECT * FROM t
} {1 2 3 4 5}
do_execsql_test 10.7.3 {
  WITH t(a) AS (
    SELECT 1 AS b UNION ALL SELECT a+1 AS c FROM t WHERE a<5 ORDER BY c
  ) 
  SELECT * FROM t
} {1 2 3 4 5}

# Test COLLATE clauses attached to ORDER BY.
#
insert_into_tree {
  /a/b
  /a/C
  /a/d
  /B/e
  /B/F
  /B/g
  /c/h
  /c/I
  /c/j
}

do_execsql_test 10.8.1 {
  WITH flat(fid, depth, p) AS (
    SELECT id, 1, '/' || payload FROM tree WHERE parentid IS NULL
    UNION ALL
    SELECT id, depth+1, p||'/'||payload FROM flat, tree WHERE parentid=fid
    ORDER BY 2, 3 COLLATE nocase
  )
  SELECT p FROM flat;
} {
  /a /B /c
  /a/b /a/C /a/d /B/e /B/F /B/g /c/h /c/I /c/j
}
do_execsql_test 10.8.2 {
  WITH flat(fid, depth, p) AS (
      SELECT id, 1, ('/' || payload) COLLATE nocase 
      FROM tree WHERE parentid IS NULL
    UNION ALL
      SELECT id, depth+1, (p||'/'||payload)
      FROM flat, tree WHERE parentid=fid
    ORDER BY 2, 3
  )
  SELECT p FROM flat;
} {
  /a /B /c
  /a/b /a/C /a/d /B/e /B/F /B/g /c/h /c/I /c/j
}

do_execsql_test 10.8.3 {
  WITH flat(fid, depth, p) AS (
      SELECT id, 1, ('/' || payload)
      FROM tree WHERE parentid IS NULL
    UNION ALL
      SELECT id, depth+1, (p||'/'||payload) COLLATE nocase 
      FROM flat, tree WHERE parentid=fid
    ORDER BY 2, 3
  )
  SELECT p FROM flat;
} {
  /a /B /c
  /a/b /a/C /a/d /B/e /B/F /B/g /c/h /c/I /c/j
}

do_execsql_test 10.8.4.1 {
  CREATE TABLE tst(a,b);
  INSERT INTO tst VALUES('a', 'A');
  INSERT INTO tst VALUES('b', 'B');
  INSERT INTO tst VALUES('c', 'C');
  SELECT a COLLATE nocase FROM tst UNION ALL SELECT b FROM tst ORDER BY 1;
} {a A b B c C}
do_execsql_test 10.8.4.2 {
  SELECT a FROM tst UNION ALL SELECT b COLLATE nocase FROM tst ORDER BY 1;
} {A B C a b c}
do_execsql_test 10.8.4.3 {
  SELECT a||'' FROM tst UNION ALL SELECT b COLLATE nocase FROM tst ORDER BY 1;
} {a A b B c C}

# Test cases to illustrate on the ORDER BY clause on a recursive query can be
# used to control depth-first versus breath-first search in a tree.
#
do_execsql_test 11.1 {
  CREATE TABLE org(
    name TEXT PRIMARY KEY,