SQLite

Check-in [07babb0f89]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Experimental implementation of NULLS FIRST/LAST. This branch still has problems - the most significant of which is that ORDER BY clauses with a non-default NULLS FIRST/LAST qualifier can never use an index.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nulls-last
Files: files | file ages | folders
SHA3-256: 07babb0f897fc8c9cb5b30481899c32fdd743f3f3ca508d8d957826252107dd5
User & Date: dan 2019-08-12 16:36:38.041
Context
2019-08-16
21:07
Add support for using indexes for some ORDER BY clauses that use non-default NULL handling. Still some problems on this branch. (check-in: 81069d7196 user: dan tags: nulls-last)
2019-08-12
16:36
Experimental implementation of NULLS FIRST/LAST. This branch still has problems - the most significant of which is that ORDER BY clauses with a non-default NULLS FIRST/LAST qualifier can never use an index. (check-in: 07babb0f89 user: dan tags: nulls-last)
16:25
For the ".testctrl prng_seed" command in the CLI, if the argument is "random" then select a random integer seed and print the seed value on stdout. (check-in: 636ca4472c user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/build.c.
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
      Expr *pCExpr = sqlite3ExprSkipCollate(pList->a[0].pExpr);
      sqlite3RenameTokenRemap(pParse, &pTab->iPKey, pCExpr);
    }
    pTab->iPKey = iCol;
    pTab->keyConf = (u8)onError;
    assert( autoInc==0 || autoInc==1 );
    pTab->tabFlags |= autoInc*TF_Autoincrement;
    if( pList ) pParse->iPkSortOrder = pList->a[0].sortOrder;
  }else if( autoInc ){
#ifndef SQLITE_OMIT_AUTOINCREMENT
    sqlite3ErrorMsg(pParse, "AUTOINCREMENT is only allowed on an "
       "INTEGER PRIMARY KEY");
#endif
  }else{
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, onError, 0,







|







1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
      Expr *pCExpr = sqlite3ExprSkipCollate(pList->a[0].pExpr);
      sqlite3RenameTokenRemap(pParse, &pTab->iPKey, pCExpr);
    }
    pTab->iPKey = iCol;
    pTab->keyConf = (u8)onError;
    assert( autoInc==0 || autoInc==1 );
    pTab->tabFlags |= autoInc*TF_Autoincrement;
    if( pList ) pParse->iPkSortOrder = pList->a[0].sortFlags;
  }else if( autoInc ){
#ifndef SQLITE_OMIT_AUTOINCREMENT
    sqlite3ErrorMsg(pParse, "AUTOINCREMENT is only allowed on an "
       "INTEGER PRIMARY KEY");
#endif
  }else{
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, onError, 0,
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
    sqlite3TokenInit(&ipkToken, pTab->aCol[pTab->iPKey].zName);
    pList = sqlite3ExprListAppend(pParse, 0, 
                  sqlite3ExprAlloc(db, TK_ID, &ipkToken, 0));
    if( pList==0 ) return;
    if( IN_RENAME_OBJECT ){
      sqlite3RenameTokenRemap(pParse, pList->a[0].pExpr, &pTab->iPKey);
    }
    pList->a[0].sortOrder = pParse->iPkSortOrder;
    assert( pParse->pNewTable==pTab );
    pTab->iPKey = -1;
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, pTab->keyConf, 0, 0, 0, 0,
                       SQLITE_IDXTYPE_PRIMARYKEY);
    if( db->mallocFailed || pParse->nErr ) return;
    pPk = sqlite3PrimaryKeyIndex(pTab);
    assert( pPk->nKeyCol==1 );







|







1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
    sqlite3TokenInit(&ipkToken, pTab->aCol[pTab->iPKey].zName);
    pList = sqlite3ExprListAppend(pParse, 0, 
                  sqlite3ExprAlloc(db, TK_ID, &ipkToken, 0));
    if( pList==0 ) return;
    if( IN_RENAME_OBJECT ){
      sqlite3RenameTokenRemap(pParse, pList->a[0].pExpr, &pTab->iPKey);
    }
    pList->a[0].sortFlags = pParse->iPkSortOrder;
    assert( pParse->pNewTable==pTab );
    pTab->iPKey = -1;
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, pTab->keyConf, 0, 0, 0, 0,
                       SQLITE_IDXTYPE_PRIMARYKEY);
    if( db->mallocFailed || pParse->nErr ) return;
    pPk = sqlite3PrimaryKeyIndex(pTab);
    assert( pPk->nKeyCol==1 );
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
    Column *pCol = &pTab->aCol[pTab->nCol-1];
    pCol->colFlags |= COLFLAG_UNIQUE;
    sqlite3TokenInit(&prevCol, pCol->zName);
    pList = sqlite3ExprListAppend(pParse, 0,
              sqlite3ExprAlloc(db, TK_ID, &prevCol, 0));
    if( pList==0 ) goto exit_create_index;
    assert( pList->nExpr==1 );
    sqlite3ExprListSetSortOrder(pList, sortOrder);
  }else{
    sqlite3ExprListCheckLength(pParse, pList, "index");
    if( pParse->nErr ) goto exit_create_index;
  }

  /* Figure out how many bytes of space are required to store explicitly
  ** specified collation sequence names.







|







3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
    Column *pCol = &pTab->aCol[pTab->nCol-1];
    pCol->colFlags |= COLFLAG_UNIQUE;
    sqlite3TokenInit(&prevCol, pCol->zName);
    pList = sqlite3ExprListAppend(pParse, 0,
              sqlite3ExprAlloc(db, TK_ID, &prevCol, 0));
    if( pList==0 ) goto exit_create_index;
    assert( pList->nExpr==1 );
    sqlite3ExprListSetSortOrder(pList, sortOrder, 0);
  }else{
    sqlite3ExprListCheckLength(pParse, pList, "index");
    if( pParse->nErr ) goto exit_create_index;
  }

  /* Figure out how many bytes of space are required to store explicitly
  ** specified collation sequence names.
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
      zColl = pTab->aCol[j].zColl;
    }
    if( !zColl ) zColl = sqlite3StrBINARY;
    if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){
      goto exit_create_index;
    }
    pIndex->azColl[i] = zColl;
    requestedSortOrder = pListItem->sortOrder & sortOrderMask;
    pIndex->aSortOrder[i] = (u8)requestedSortOrder;
  }

  /* Append the table key to the end of the index.  For WITHOUT ROWID
  ** tables (when pPk!=0) this will be the declared PRIMARY KEY.  For
  ** normal tables (when pPk==0) this will be the rowid.
  */







|







3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
      zColl = pTab->aCol[j].zColl;
    }
    if( !zColl ) zColl = sqlite3StrBINARY;
    if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){
      goto exit_create_index;
    }
    pIndex->azColl[i] = zColl;
    requestedSortOrder = pListItem->sortFlags & sortOrderMask;
    pIndex->aSortOrder[i] = (u8)requestedSortOrder;
  }

  /* Append the table key to the end of the index.  For WITHOUT ROWID
  ** tables (when pPk!=0) this will be the declared PRIMARY KEY.  For
  ** normal tables (when pPk==0) this will be the rowid.
  */
4700
4701
4702
4703
4704
4705
4706
4707

4708
4709
4710
4711
4712
4713
4714
  }
  if( pKey ){
    assert( sqlite3KeyInfoIsWriteable(pKey) );
    for(i=0; i<nCol; i++){
      const char *zColl = pIdx->azColl[i];
      pKey->aColl[i] = zColl==sqlite3StrBINARY ? 0 :
                        sqlite3LocateCollSeq(pParse, zColl);
      pKey->aSortOrder[i] = pIdx->aSortOrder[i];

    }
    if( pParse->nErr ){
      assert( pParse->rc==SQLITE_ERROR_MISSING_COLLSEQ );
      if( pIdx->bNoQuery==0 ){
        /* Deactivate the index because it contains an unknown collating
        ** sequence.  The only way to reactive the index is to reload the
        ** schema.  Adding the missing collating sequence later does not







|
>







4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
  }
  if( pKey ){
    assert( sqlite3KeyInfoIsWriteable(pKey) );
    for(i=0; i<nCol; i++){
      const char *zColl = pIdx->azColl[i];
      pKey->aColl[i] = zColl==sqlite3StrBINARY ? 0 :
                        sqlite3LocateCollSeq(pParse, zColl);
      pKey->aSortFlags[i] = pIdx->aSortOrder[i];
      assert( 0==(pKey->aSortFlags[i] & KEYINFO_ORDER_BIGNULL) );
    }
    if( pParse->nErr ){
      assert( pParse->rc==SQLITE_ERROR_MISSING_COLLSEQ );
      if( pIdx->bNoQuery==0 ){
        /* Deactivate the index because it contains an unknown collating
        ** sequence.  The only way to reactive the index is to reload the
        ** schema.  Adding the missing collating sequence later does not
Changes to src/expr.c.
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
        assert( pNewExpr->iColumn==pItem[-1].pExpr->iColumn+1 );
        assert( pPriorSelectCol==pItem[-1].pExpr->pLeft );
        pNewExpr->pLeft = pPriorSelectCol;
      }
    }
    pItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
    pItem->zSpan = sqlite3DbStrDup(db, pOldItem->zSpan);
    pItem->sortOrder = pOldItem->sortOrder;
    pItem->done = 0;
    pItem->bSpanIsTab = pOldItem->bSpanIsTab;
    pItem->bSorterRef = pOldItem->bSorterRef;
    pItem->u = pOldItem->u;
  }
  return pNew;
}







|







1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
        assert( pNewExpr->iColumn==pItem[-1].pExpr->iColumn+1 );
        assert( pPriorSelectCol==pItem[-1].pExpr->pLeft );
        pNewExpr->pLeft = pPriorSelectCol;
      }
    }
    pItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
    pItem->zSpan = sqlite3DbStrDup(db, pOldItem->zSpan);
    pItem->sortFlags = pOldItem->sortFlags;
    pItem->done = 0;
    pItem->bSpanIsTab = pOldItem->bSpanIsTab;
    pItem->bSorterRef = pOldItem->bSorterRef;
    pItem->u = pOldItem->u;
  }
  return pNew;
}
1653
1654
1655
1656
1657
1658
1659
1660
1661


1662
1663
1664
1665
1666





1667

1668



1669
1670
1671
1672
1673
1674
1675
  sqlite3IdListDelete(db, pColumns);
  return pList;
}

/*
** Set the sort order for the last element on the given ExprList.
*/
void sqlite3ExprListSetSortOrder(ExprList *p, int iSortOrder){
  if( p==0 ) return;


  assert( SQLITE_SO_UNDEFINED<0 && SQLITE_SO_ASC>=0 && SQLITE_SO_DESC>0 );
  assert( p->nExpr>0 );
  if( iSortOrder<0 ){
    assert( p->a[p->nExpr-1].sortOrder==SQLITE_SO_ASC );
    return;





  }

  p->a[p->nExpr-1].sortOrder = (u8)iSortOrder;



}

/*
** Set the ExprList.a[].zName element of the most recently added item
** on the expression list.
**
** pList might be NULL following an OOM error.  But pName should never be







|

>
>
|
|
|
|
<
>
>
>
>
>
|
>
|
>
>
>







1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667

1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
  sqlite3IdListDelete(db, pColumns);
  return pList;
}

/*
** Set the sort order for the last element on the given ExprList.
*/
void sqlite3ExprListSetSortOrder(ExprList *p, int iSortOrder, int eNulls){
  if( p==0 ) return;
  assert( p->nExpr>0 );

  assert( SQLITE_SO_UNDEFINED<0 && SQLITE_SO_ASC==0 && SQLITE_SO_DESC>0 );
  assert( iSortOrder==SQLITE_SO_UNDEFINED 
       || iSortOrder==SQLITE_SO_ASC 
       || iSortOrder==SQLITE_SO_DESC 

  );
  assert( eNulls==SQLITE_SO_UNDEFINED 
       || eNulls==SQLITE_SO_ASC 
       || eNulls==SQLITE_SO_DESC 
  );

  if( iSortOrder==SQLITE_SO_UNDEFINED ) iSortOrder = SQLITE_SO_ASC;
  p->a[p->nExpr-1].sortFlags = (u8)iSortOrder;
  if( eNulls!=SQLITE_SO_UNDEFINED && iSortOrder!=eNulls ){
    p->a[p->nExpr-1].sortFlags |= KEYINFO_ORDER_BIGNULL;
  }
}

/*
** Set the ExprList.a[].zName element of the most recently added item
** on the expression list.
**
** pList might be NULL following an OOM error.  But pName should never be
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
  int i;
  if( pA==0 && pB==0 ) return 0;
  if( pA==0 || pB==0 ) return 1;
  if( pA->nExpr!=pB->nExpr ) return 1;
  for(i=0; i<pA->nExpr; i++){
    Expr *pExprA = pA->a[i].pExpr;
    Expr *pExprB = pB->a[i].pExpr;
    if( pA->a[i].sortOrder!=pB->a[i].sortOrder ) return 1;
    if( sqlite3ExprCompare(0, pExprA, pExprB, iTab) ) return 1;
  }
  return 0;
}

/*
** Like sqlite3ExprCompare() except COLLATE operators at the top-level







|







4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
  int i;
  if( pA==0 && pB==0 ) return 0;
  if( pA==0 || pB==0 ) return 1;
  if( pA->nExpr!=pB->nExpr ) return 1;
  for(i=0; i<pA->nExpr; i++){
    Expr *pExprA = pA->a[i].pExpr;
    Expr *pExprB = pB->a[i].pExpr;
    if( pA->a[i].sortFlags!=pB->a[i].sortFlags ) return 1;
    if( sqlite3ExprCompare(0, pExprA, pExprB, iTab) ) return 1;
  }
  return 0;
}

/*
** Like sqlite3ExprCompare() except COLLATE operators at the top-level
Changes to src/parse.y.
207
208
209
210
211
212
213

214
215
216
217
218
219
220
%fallback ID
  ABORT ACTION AFTER ANALYZE ASC ATTACH BEFORE BEGIN BY CASCADE CAST COLUMNKW
  CONFLICT DATABASE DEFERRED DESC DETACH DO
  EACH END EXCLUSIVE EXPLAIN FAIL FOR
  IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH NO PLAN
  QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW ROWS
  ROLLBACK SAVEPOINT TEMP TRIGGER VACUUM VIEW VIRTUAL WITH WITHOUT

%ifdef SQLITE_OMIT_COMPOUND_SELECT
  EXCEPT INTERSECT UNION
%endif SQLITE_OMIT_COMPOUND_SELECT
%ifndef SQLITE_OMIT_WINDOWFUNC
  CURRENT FOLLOWING PARTITION PRECEDING RANGE UNBOUNDED
  EXCLUDE GROUPS OTHERS TIES
%endif SQLITE_OMIT_WINDOWFUNC







>







207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
%fallback ID
  ABORT ACTION AFTER ANALYZE ASC ATTACH BEFORE BEGIN BY CASCADE CAST COLUMNKW
  CONFLICT DATABASE DEFERRED DESC DETACH DO
  EACH END EXCLUSIVE EXPLAIN FAIL FOR
  IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH NO PLAN
  QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW ROWS
  ROLLBACK SAVEPOINT TEMP TRIGGER VACUUM VIEW VIRTUAL WITH WITHOUT
  NULLS FIRST LAST
%ifdef SQLITE_OMIT_COMPOUND_SELECT
  EXCEPT INTERSECT UNION
%endif SQLITE_OMIT_COMPOUND_SELECT
%ifndef SQLITE_OMIT_WINDOWFUNC
  CURRENT FOLLOWING PARTITION PRECEDING RANGE UNBOUNDED
  EXCLUDE GROUPS OTHERS TIES
%endif SQLITE_OMIT_WINDOWFUNC
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798





799
800
801
802
803
804
805
// sort order.
//
%type sortlist {ExprList*}
%destructor sortlist {sqlite3ExprListDelete(pParse->db, $$);}

orderby_opt(A) ::= .                          {A = 0;}
orderby_opt(A) ::= ORDER BY sortlist(X).      {A = X;}
sortlist(A) ::= sortlist(A) COMMA expr(Y) sortorder(Z). {
  A = sqlite3ExprListAppend(pParse,A,Y);
  sqlite3ExprListSetSortOrder(A,Z);
}
sortlist(A) ::= expr(Y) sortorder(Z). {
  A = sqlite3ExprListAppend(pParse,0,Y); /*A-overwrites-Y*/
  sqlite3ExprListSetSortOrder(A,Z);
}

%type sortorder {int}

sortorder(A) ::= ASC.           {A = SQLITE_SO_ASC;}
sortorder(A) ::= DESC.          {A = SQLITE_SO_DESC;}
sortorder(A) ::= .              {A = SQLITE_SO_UNDEFINED;}






%type groupby_opt {ExprList*}
%destructor groupby_opt {sqlite3ExprListDelete(pParse->db, $$);}
groupby_opt(A) ::= .                      {A = 0;}
groupby_opt(A) ::= GROUP BY nexprlist(X). {A = X;}

%type having_opt {Expr*}
%destructor having_opt {sqlite3ExprDelete(pParse->db, $$);}







|

|

|

|








>
>
>
>
>







778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
// sort order.
//
%type sortlist {ExprList*}
%destructor sortlist {sqlite3ExprListDelete(pParse->db, $$);}

orderby_opt(A) ::= .                          {A = 0;}
orderby_opt(A) ::= ORDER BY sortlist(X).      {A = X;}
sortlist(A) ::= sortlist(A) COMMA expr(Y) sortorder(Z) nulls(X). {
  A = sqlite3ExprListAppend(pParse,A,Y);
  sqlite3ExprListSetSortOrder(A,Z,X);
}
sortlist(A) ::= expr(Y) sortorder(Z) nulls(X). {
  A = sqlite3ExprListAppend(pParse,0,Y); /*A-overwrites-Y*/
  sqlite3ExprListSetSortOrder(A,Z,X);
}

%type sortorder {int}

sortorder(A) ::= ASC.           {A = SQLITE_SO_ASC;}
sortorder(A) ::= DESC.          {A = SQLITE_SO_DESC;}
sortorder(A) ::= .              {A = SQLITE_SO_UNDEFINED;}

%type nulls {int}
nulls(A) ::= NULLS FIRST.       {A = SQLITE_SO_ASC;}
nulls(A) ::= NULLS LAST.        {A = SQLITE_SO_DESC;}
nulls(A) ::= .                  {A = SQLITE_SO_UNDEFINED;}

%type groupby_opt {ExprList*}
%destructor groupby_opt {sqlite3ExprListDelete(pParse->db, $$);}
groupby_opt(A) ::= .                      {A = 0;}
groupby_opt(A) ::= GROUP BY nexprlist(X). {A = X;}

%type having_opt {Expr*}
%destructor having_opt {sqlite3ExprDelete(pParse->db, $$);}
Changes to src/select.c.
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
    }
    VdbeCoverage(v);
    sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);
    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
    if( pParse->db->mallocFailed ) return;
    pOp->p2 = nKey + nData;
    pKI = pOp->p4.pKeyInfo;
    memset(pKI->aSortOrder, 0, pKI->nKeyField); /* Makes OP_Jump testable */
    sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
    testcase( pKI->nAllField > pKI->nKeyField+2 );
    pOp->p4.pKeyInfo = sqlite3KeyInfoFromExprList(pParse,pSort->pOrderBy,nOBSat,
                                           pKI->nAllField-pKI->nKeyField-1);
    addrJmp = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
    pSort->labelBkOut = sqlite3VdbeMakeLabel(pParse);







|







660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
    }
    VdbeCoverage(v);
    sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);
    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
    if( pParse->db->mallocFailed ) return;
    pOp->p2 = nKey + nData;
    pKI = pOp->p4.pKeyInfo;
    memset(pKI->aSortFlags, 0, pKI->nKeyField); /* Makes OP_Jump testable */
    sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
    testcase( pKI->nAllField > pKI->nKeyField+2 );
    pOp->p4.pKeyInfo = sqlite3KeyInfoFromExprList(pParse,pSort->pOrderBy,nOBSat,
                                           pKI->nAllField-pKI->nKeyField-1);
    addrJmp = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
    pSort->labelBkOut = sqlite3VdbeMakeLabel(pParse);
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
** Allocate a KeyInfo object sufficient for an index of N key columns and
** X extra columns.
*/
KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *db, int N, int X){
  int nExtra = (N+X)*(sizeof(CollSeq*)+1) - sizeof(CollSeq*);
  KeyInfo *p = sqlite3DbMallocRawNN(db, sizeof(KeyInfo) + nExtra);
  if( p ){
    p->aSortOrder = (u8*)&p->aColl[N+X];
    p->nKeyField = (u16)N;
    p->nAllField = (u16)(N+X);
    p->enc = ENC(db);
    p->db = db;
    p->nRef = 1;
    memset(&p[1], 0, nExtra);
  }else{







|







1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
** Allocate a KeyInfo object sufficient for an index of N key columns and
** X extra columns.
*/
KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *db, int N, int X){
  int nExtra = (N+X)*(sizeof(CollSeq*)+1) - sizeof(CollSeq*);
  KeyInfo *p = sqlite3DbMallocRawNN(db, sizeof(KeyInfo) + nExtra);
  if( p ){
    p->aSortFlags = (u8*)&p->aColl[N+X];
    p->nKeyField = (u16)N;
    p->nAllField = (u16)(N+X);
    p->enc = ENC(db);
    p->db = db;
    p->nRef = 1;
    memset(&p[1], 0, nExtra);
  }else{
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362

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

/*
** Name of the connection operator, used for error messages.







|







1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362

  nExpr = pList->nExpr;
  pInfo = sqlite3KeyInfoAlloc(db, nExpr-iStart, nExtra+1);
  if( pInfo ){
    assert( sqlite3KeyInfoIsWriteable(pInfo) );
    for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
      pInfo->aColl[i-iStart] = sqlite3ExprNNCollSeq(pParse, pItem->pExpr);
      pInfo->aSortFlags[i-iStart] = pItem->sortFlags;
    }
  }
  return pInfo;
}

/*
** Name of the connection operator, used for error messages.
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
        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;
}

#ifndef SQLITE_OMIT_CTE







|







2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
        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->aSortFlags[i] = pOrderBy->a[i].sortFlags;
    }
  }

  return pRet;
}

#ifndef SQLITE_OMIT_CTE
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
    pParse->nMem += nExpr+1;
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
    pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);
    if( pKeyDup ){
      assert( sqlite3KeyInfoIsWriteable(pKeyDup) );
      for(i=0; i<nExpr; i++){
        pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);
        pKeyDup->aSortOrder[i] = 0;
      }
    }
  }
 
  /* Separate the left and the right query from one another
  */
  p->pPrior = 0;







|







3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
    pParse->nMem += nExpr+1;
    sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
    pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);
    if( pKeyDup ){
      assert( sqlite3KeyInfoIsWriteable(pKeyDup) );
      for(i=0; i<nExpr; i++){
        pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);
        pKeyDup->aSortFlags[i] = 0;
      }
    }
  }
 
  /* Separate the left and the right query from one another
  */
  p->pPrior = 0;
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
    eRet = WHERE_ORDERBY_MAX;
    sortOrder = SQLITE_SO_DESC;
  }else{
    return eRet;
  }
  *ppMinMax = pOrderBy = sqlite3ExprListDup(db, pEList, 0);
  assert( pOrderBy!=0 || db->mallocFailed );
  if( pOrderBy ) pOrderBy->a[0].sortOrder = sortOrder;
  return eRet;
}

/*
** The select statement passed as the first argument is an aggregate query.
** The second argument is the associated aggregate-info object. This 
** function tests if the SELECT is of the form:







|







4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
    eRet = WHERE_ORDERBY_MAX;
    sortOrder = SQLITE_SO_DESC;
  }else{
    return eRet;
  }
  *ppMinMax = pOrderBy = sqlite3ExprListDup(db, pEList, 0);
  assert( pOrderBy!=0 || db->mallocFailed );
  if( pOrderBy ) pOrderBy->a[0].sortFlags = sortOrder;
  return eRet;
}

/*
** The select statement passed as the first argument is an aggregate query.
** The second argument is the associated aggregate-info object. This 
** function tests if the SELECT is of the form:
Changes to src/sqliteInt.h.
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139



2140
2141
2142
2143
2144
2145
2146
*/
struct KeyInfo {
  u32 nRef;           /* Number of references to this KeyInfo object */
  u8 enc;             /* Text encoding - one of the SQLITE_UTF* values */
  u16 nKeyField;      /* Number of key columns in the index */
  u16 nAllField;      /* Total columns, including key plus others */
  sqlite3 *db;        /* The database connection */
  u8 *aSortOrder;     /* Sort order for each column. */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};




/*
** This object holds a record which has been parsed out into individual
** fields, for the purposes of doing a comparison.
**
** A record is an object that contains one or more fields of data.
** Records are used to store the content of a table row and to store







|


>
>
>







2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
*/
struct KeyInfo {
  u32 nRef;           /* Number of references to this KeyInfo object */
  u8 enc;             /* Text encoding - one of the SQLITE_UTF* values */
  u16 nKeyField;      /* Number of key columns in the index */
  u16 nAllField;      /* Total columns, including key plus others */
  sqlite3 *db;        /* The database connection */
  u8 *aSortFlags;     /* Sort order for each column. */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

#define KEYINFO_ORDER_DESC    0x01
#define KEYINFO_ORDER_BIGNULL 0x02

/*
** This object holds a record which has been parsed out into individual
** fields, for the purposes of doing a comparison.
**
** A record is an object that contains one or more fields of data.
** Records are used to store the content of a table row and to store
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
*/
struct ExprList {
  int nExpr;             /* Number of expressions on the list */
  struct ExprList_item { /* For each expression in the list */
    Expr *pExpr;            /* The parse tree for this expression */
    char *zName;            /* Token associated with this expression */
    char *zSpan;            /* Original text of the expression */
    u8 sortOrder;           /* 1 for DESC or 0 for ASC */
    unsigned done :1;       /* A flag to indicate when processing is finished */
    unsigned bSpanIsTab :1; /* zSpan holds DB.TABLE.COLUMN */
    unsigned reusable :1;   /* Constant expression is reusable */
    unsigned bSorterRef :1; /* Defer evaluation until after sorting */
    union {
      struct {
        u16 iOrderByCol;      /* For ORDER BY, column number in result set */







|







2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
*/
struct ExprList {
  int nExpr;             /* Number of expressions on the list */
  struct ExprList_item { /* For each expression in the list */
    Expr *pExpr;            /* The parse tree for this expression */
    char *zName;            /* Token associated with this expression */
    char *zSpan;            /* Original text of the expression */
    u8 sortFlags;           /* 1 for DESC or 0 for ASC */
    unsigned done :1;       /* A flag to indicate when processing is finished */
    unsigned bSpanIsTab :1; /* zSpan holds DB.TABLE.COLUMN */
    unsigned reusable :1;   /* Constant expression is reusable */
    unsigned bSorterRef :1; /* Defer evaluation until after sorting */
    union {
      struct {
        u16 iOrderByCol;      /* For ORDER BY, column number in result set */
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
Expr *sqlite3ExprSimplifiedAndOr(Expr*);
Expr *sqlite3ExprFunction(Parse*,ExprList*, Token*, int);
void sqlite3ExprAssignVarNumber(Parse*, Expr*, u32);
void sqlite3ExprDelete(sqlite3*, Expr*);
void sqlite3ExprUnmapAndDelete(Parse*, Expr*);
ExprList *sqlite3ExprListAppend(Parse*,ExprList*,Expr*);
ExprList *sqlite3ExprListAppendVector(Parse*,ExprList*,IdList*,Expr*);
void sqlite3ExprListSetSortOrder(ExprList*,int);
void sqlite3ExprListSetName(Parse*,ExprList*,Token*,int);
void sqlite3ExprListSetSpan(Parse*,ExprList*,const char*,const char*);
void sqlite3ExprListDelete(sqlite3*, ExprList*);
u32 sqlite3ExprListFlags(const ExprList*);
int sqlite3IndexHasDuplicateRootPage(Index*);
int sqlite3Init(sqlite3*, char**);
int sqlite3InitCallback(void*, int, char**, char**);







|







3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
Expr *sqlite3ExprSimplifiedAndOr(Expr*);
Expr *sqlite3ExprFunction(Parse*,ExprList*, Token*, int);
void sqlite3ExprAssignVarNumber(Parse*, Expr*, u32);
void sqlite3ExprDelete(sqlite3*, Expr*);
void sqlite3ExprUnmapAndDelete(Parse*, Expr*);
ExprList *sqlite3ExprListAppend(Parse*,ExprList*,Expr*);
ExprList *sqlite3ExprListAppendVector(Parse*,ExprList*,IdList*,Expr*);
void sqlite3ExprListSetSortOrder(ExprList*,int,int);
void sqlite3ExprListSetName(Parse*,ExprList*,Token*,int);
void sqlite3ExprListSetSpan(Parse*,ExprList*,const char*,const char*);
void sqlite3ExprListDelete(sqlite3*, ExprList*);
u32 sqlite3ExprListFlags(const ExprList*);
int sqlite3IndexHasDuplicateRootPage(Index*);
int sqlite3Init(sqlite3*, char**);
int sqlite3InitCallback(void*, int, char**, char**);
Changes to src/vdbe.c.
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232





2233
2234
2235
2236
2237
2238
2239
    idx = aPermute ? aPermute[i] : i;
    assert( memIsValid(&aMem[p1+idx]) );
    assert( memIsValid(&aMem[p2+idx]) );
    REGISTER_TRACE(p1+idx, &aMem[p1+idx]);
    REGISTER_TRACE(p2+idx, &aMem[p2+idx]);
    assert( i<pKeyInfo->nKeyField );
    pColl = pKeyInfo->aColl[i];
    bRev = pKeyInfo->aSortOrder[i];
    iCompare = sqlite3MemCompare(&aMem[p1+idx], &aMem[p2+idx], pColl);
    if( iCompare ){





      if( bRev ) iCompare = -iCompare;
      break;
    }
  }
  break;
}








|


>
>
>
>
>







2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
    idx = aPermute ? aPermute[i] : i;
    assert( memIsValid(&aMem[p1+idx]) );
    assert( memIsValid(&aMem[p2+idx]) );
    REGISTER_TRACE(p1+idx, &aMem[p1+idx]);
    REGISTER_TRACE(p2+idx, &aMem[p2+idx]);
    assert( i<pKeyInfo->nKeyField );
    pColl = pKeyInfo->aColl[i];
    bRev = (pKeyInfo->aSortFlags[i] & KEYINFO_ORDER_DESC);
    iCompare = sqlite3MemCompare(&aMem[p1+idx], &aMem[p2+idx], pColl);
    if( iCompare ){
      if( (pKeyInfo->aSortFlags[i] & KEYINFO_ORDER_BIGNULL) 
       && ((aMem[p1+idx].flags & MEM_Null) || (aMem[p2+idx].flags & MEM_Null))
      ){
        iCompare = -iCompare;
      }
      if( bRev ) iCompare = -iCompare;
      break;
    }
  }
  break;
}

Changes to src/vdbeaux.c.
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503


1504
1505
1506
1507
1508
1509
1510
  StrAccum x;
  assert( nTemp>=20 );
  sqlite3StrAccumInit(&x, 0, zTemp, nTemp, 0);
  switch( pOp->p4type ){
    case P4_KEYINFO: {
      int j;
      KeyInfo *pKeyInfo = pOp->p4.pKeyInfo;
      assert( pKeyInfo->aSortOrder!=0 );
      sqlite3_str_appendf(&x, "k(%d", pKeyInfo->nKeyField);
      for(j=0; j<pKeyInfo->nKeyField; j++){
        CollSeq *pColl = pKeyInfo->aColl[j];
        const char *zColl = pColl ? pColl->zName : "";
        if( strcmp(zColl, "BINARY")==0 ) zColl = "B";
        sqlite3_str_appendf(&x, ",%s%s", 
               pKeyInfo->aSortOrder[j] ? "-" : "", zColl);


      }
      sqlite3_str_append(&x, ")", 1);
      break;
    }
#ifdef SQLITE_ENABLE_CURSOR_HINTS
    case P4_EXPR: {
      displayP4Expr(&x, pOp->p4.pExpr);







|





|
|
>
>







1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
  StrAccum x;
  assert( nTemp>=20 );
  sqlite3StrAccumInit(&x, 0, zTemp, nTemp, 0);
  switch( pOp->p4type ){
    case P4_KEYINFO: {
      int j;
      KeyInfo *pKeyInfo = pOp->p4.pKeyInfo;
      assert( pKeyInfo->aSortFlags!=0 );
      sqlite3_str_appendf(&x, "k(%d", pKeyInfo->nKeyField);
      for(j=0; j<pKeyInfo->nKeyField; j++){
        CollSeq *pColl = pKeyInfo->aColl[j];
        const char *zColl = pColl ? pColl->zName : "";
        if( strcmp(zColl, "BINARY")==0 ) zColl = "B";
        sqlite3_str_appendf(&x, ",%s%s%s", 
               (pKeyInfo->aSortFlags[j] & KEYINFO_ORDER_DESC) ? "-" : "", 
               (pKeyInfo->aSortFlags[j] & KEYINFO_ORDER_BIGNULL)? "N." : "", 
               zColl);
      }
      sqlite3_str_append(&x, ")", 1);
      break;
    }
#ifdef SQLITE_ENABLE_CURSOR_HINTS
    case P4_EXPR: {
      displayP4Expr(&x, pOp->p4.pExpr);
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
){
  UnpackedRecord *p;              /* Unpacked record to return */
  int nByte;                      /* Number of bytes required for *p */
  nByte = ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem)*(pKeyInfo->nKeyField+1);
  p = (UnpackedRecord *)sqlite3DbMallocRaw(pKeyInfo->db, nByte);
  if( !p ) return 0;
  p->aMem = (Mem*)&((char*)p)[ROUND8(sizeof(UnpackedRecord))];
  assert( pKeyInfo->aSortOrder!=0 );
  p->pKeyInfo = pKeyInfo;
  p->nField = pKeyInfo->nKeyField + 1;
  return p;
}

/*
** Given the nKey-byte encoding of a record in pKey[], populate the 







|







3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
){
  UnpackedRecord *p;              /* Unpacked record to return */
  int nByte;                      /* Number of bytes required for *p */
  nByte = ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem)*(pKeyInfo->nKeyField+1);
  p = (UnpackedRecord *)sqlite3DbMallocRaw(pKeyInfo->db, nByte);
  if( !p ) return 0;
  p->aMem = (Mem*)&((char*)p)[ROUND8(sizeof(UnpackedRecord))];
  assert( pKeyInfo->aSortFlags!=0 );
  p->pKeyInfo = pKeyInfo;
  p->nField = pKeyInfo->nKeyField + 1;
  return p;
}

/*
** Given the nKey-byte encoding of a record in pKey[], populate the 
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
  */
  /*  mem1.u.i = 0;  // not needed, here to silence compiler warning */
  
  idx1 = getVarint32(aKey1, szHdr1);
  if( szHdr1>98307 ) return SQLITE_CORRUPT;
  d1 = szHdr1;
  assert( pKeyInfo->nAllField>=pPKey2->nField || CORRUPT_DB );
  assert( pKeyInfo->aSortOrder!=0 );
  assert( pKeyInfo->nKeyField>0 );
  assert( idx1<=szHdr1 || CORRUPT_DB );
  do{
    u32 serial_type1;

    /* Read the serial types for the next element in each key. */
    idx1 += getVarint32( aKey1+idx1, serial_type1 );







|







3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
  */
  /*  mem1.u.i = 0;  // not needed, here to silence compiler warning */
  
  idx1 = getVarint32(aKey1, szHdr1);
  if( szHdr1>98307 ) return SQLITE_CORRUPT;
  d1 = szHdr1;
  assert( pKeyInfo->nAllField>=pPKey2->nField || CORRUPT_DB );
  assert( pKeyInfo->aSortFlags!=0 );
  assert( pKeyInfo->nKeyField>0 );
  assert( idx1<=szHdr1 || CORRUPT_DB );
  do{
    u32 serial_type1;

    /* Read the serial types for the next element in each key. */
    idx1 += getVarint32( aKey1+idx1, serial_type1 );
3939
3940
3941
3942
3943
3944
3945





3946
3947
3948
3949
3950
3951
3952
3953

    /* Do the comparison
    */
    rc = sqlite3MemCompare(&mem1, &pPKey2->aMem[i],
                           pKeyInfo->nAllField>i ? pKeyInfo->aColl[i] : 0);
    if( rc!=0 ){
      assert( mem1.szMalloc==0 );  /* See comment below */





      if( pKeyInfo->aSortOrder[i] ){
        rc = -rc;  /* Invert the result for DESC sort order. */
      }
      goto debugCompareEnd;
    }
    i++;
  }while( idx1<szHdr1 && i<pPKey2->nField );








>
>
>
>
>
|







3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960

    /* Do the comparison
    */
    rc = sqlite3MemCompare(&mem1, &pPKey2->aMem[i],
                           pKeyInfo->nAllField>i ? pKeyInfo->aColl[i] : 0);
    if( rc!=0 ){
      assert( mem1.szMalloc==0 );  /* See comment below */
      if( (pKeyInfo->aSortFlags[i] & KEYINFO_ORDER_BIGNULL)
       && ((mem1.flags & MEM_Null) || (pPKey2->aMem[i].flags & MEM_Null)) 
      ){
        rc = -rc;
      }
      if( pKeyInfo->aSortFlags[i] & KEYINFO_ORDER_DESC ){
        rc = -rc;  /* Invert the result for DESC sort order. */
      }
      goto debugCompareEnd;
    }
    i++;
  }while( idx1<szHdr1 && i<pPKey2->nField );

4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
    pPKey2->errCode = (u8)SQLITE_CORRUPT_BKPT;
    return 0;  /* Corruption */
  }

  VVA_ONLY( mem1.szMalloc = 0; ) /* Only needed by assert() statements */
  assert( pPKey2->pKeyInfo->nAllField>=pPKey2->nField 
       || CORRUPT_DB );
  assert( pPKey2->pKeyInfo->aSortOrder!=0 );
  assert( pPKey2->pKeyInfo->nKeyField>0 );
  assert( idx1<=szHdr1 || CORRUPT_DB );
  do{
    u32 serial_type;

    /* RHS is an integer */
    if( pRhs->flags & (MEM_Int|MEM_IntReal) ){







|







4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
    pPKey2->errCode = (u8)SQLITE_CORRUPT_BKPT;
    return 0;  /* Corruption */
  }

  VVA_ONLY( mem1.szMalloc = 0; ) /* Only needed by assert() statements */
  assert( pPKey2->pKeyInfo->nAllField>=pPKey2->nField 
       || CORRUPT_DB );
  assert( pPKey2->pKeyInfo->aSortFlags!=0 );
  assert( pPKey2->pKeyInfo->nKeyField>0 );
  assert( idx1<=szHdr1 || CORRUPT_DB );
  do{
    u32 serial_type;

    /* RHS is an integer */
    if( pRhs->flags & (MEM_Int|MEM_IntReal) ){
4438
4439
4440
4441
4442
4443
4444
4445





4446

4447
4448
4449
4450
4451
4452
4453
    /* RHS is null */
    else{
      serial_type = aKey1[idx1];
      rc = (serial_type!=0);
    }

    if( rc!=0 ){
      if( pPKey2->pKeyInfo->aSortOrder[i] ){





        rc = -rc;

      }
      assert( vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, rc) );
      assert( mem1.szMalloc==0 );  /* See comment below */
      return rc;
    }

    i++;







|
>
>
>
>
>
|
>







4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
    /* RHS is null */
    else{
      serial_type = aKey1[idx1];
      rc = (serial_type!=0);
    }

    if( rc!=0 ){
      int sortFlags = pPKey2->pKeyInfo->aSortFlags[i];
      if( sortFlags ){
        if( (sortFlags & KEYINFO_ORDER_BIGNULL)==0
         || ((sortFlags & KEYINFO_ORDER_DESC)
           !=(serial_type==0 || (pRhs->flags&MEM_Null)))
        ){
          rc = -rc;
        }
      }
      assert( vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, rc) );
      assert( mem1.szMalloc==0 );  /* See comment below */
      return rc;
    }

    i++;
4656
4657
4658
4659
4660
4661
4662
4663



4664
4665
4666
4667
4668
4669
4670
  ** is an integer.
  **
  ** The easiest way to enforce this limit is to consider only records with
  ** 13 fields or less. If the first field is an integer, the maximum legal
  ** header size is (12*5 + 1 + 1) bytes.  */
  if( p->pKeyInfo->nAllField<=13 ){
    int flags = p->aMem[0].flags;
    if( p->pKeyInfo->aSortOrder[0] ){



      p->r1 = 1;
      p->r2 = -1;
    }else{
      p->r1 = -1;
      p->r2 = 1;
    }
    if( (flags & MEM_Int) ){







|
>
>
>







4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
  ** is an integer.
  **
  ** The easiest way to enforce this limit is to consider only records with
  ** 13 fields or less. If the first field is an integer, the maximum legal
  ** header size is (12*5 + 1 + 1) bytes.  */
  if( p->pKeyInfo->nAllField<=13 ){
    int flags = p->aMem[0].flags;
    if( p->pKeyInfo->aSortFlags[0] ){
      if( p->pKeyInfo->aSortFlags[0] & KEYINFO_ORDER_BIGNULL ){
        return sqlite3VdbeRecordCompare;
      }
      p->r1 = 1;
      p->r2 = -1;
    }else{
      p->r1 = -1;
      p->r2 = 1;
    }
    if( (flags & MEM_Int) ){
Changes to src/vdbesort.c.
825
826
827
828
829
830
831

832
833
834
835
836
837
838
839
  if( res==0 ){
    if( pTask->pSorter->pKeyInfo->nKeyField>1 ){
      res = vdbeSorterCompareTail(
          pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2
      );
    }
  }else{

    if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){
      res = res * -1;
    }
  }

  return res;
}








>
|







825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
  if( res==0 ){
    if( pTask->pSorter->pKeyInfo->nKeyField>1 ){
      res = vdbeSorterCompareTail(
          pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2
      );
    }
  }else{
    assert( !(pTask->pSorter->pKeyInfo->aSortFlags[0]&KEYINFO_ORDER_BIGNULL) );
    if( pTask->pSorter->pKeyInfo->aSortFlags[0] ){
      res = res * -1;
    }
  }

  return res;
}

893
894
895
896
897
898
899
900

901
902
903
904
905
906
907

  if( res==0 ){
    if( pTask->pSorter->pKeyInfo->nKeyField>1 ){
      res = vdbeSorterCompareTail(
          pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2
      );
    }
  }else if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){

    res = res * -1;
  }

  return res;
}

/*







|
>







894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909

  if( res==0 ){
    if( pTask->pSorter->pKeyInfo->nKeyField>1 ){
      res = vdbeSorterCompareTail(
          pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2
      );
    }
  }else if( pTask->pSorter->pKeyInfo->aSortFlags[0] ){
    assert( !(pTask->pSorter->pKeyInfo->aSortFlags[0]&KEYINFO_ORDER_BIGNULL) );
    res = res * -1;
  }

  return res;
}

/*
1008
1009
1010
1011
1012
1013
1014

1015
1016
1017
1018
1019
1020
1021
        pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz);
        if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM_BKPT;
      }
    }

    if( pKeyInfo->nAllField<13 
     && (pKeyInfo->aColl[0]==0 || pKeyInfo->aColl[0]==db->pDfltColl)

    ){
      pSorter->typeMask = SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT;
    }
  }

  return rc;
}







>







1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
        pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz);
        if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM_BKPT;
      }
    }

    if( pKeyInfo->nAllField<13 
     && (pKeyInfo->aColl[0]==0 || pKeyInfo->aColl[0]==db->pDfltColl)
     && (pKeyInfo->aSortFlags[0] & KEYINFO_ORDER_BIGNULL)==0
    ){
      pSorter->typeMask = SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT;
    }
  }

  return rc;
}
Changes to src/where.c.
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
    }

    j++;
  }
  for(i=0; i<nOrderBy; i++){
    Expr *pExpr = pOrderBy->a[i].pExpr;
    pIdxOrderBy[i].iColumn = pExpr->iColumn;
    pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
  }

  *pmNoOmit = mNoOmit;
  return pIdxInfo;
}

/*







|







1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
    }

    j++;
  }
  for(i=0; i<nOrderBy; i++){
    Expr *pExpr = pOrderBy->a[i].pExpr;
    pIdxOrderBy[i].iColumn = pExpr->iColumn;
    pIdxOrderBy[i].desc = pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC;
  }

  *pmNoOmit = mNoOmit;
  return pIdxInfo;
}

/*
3832
3833
3834
3835
3836
3837
3838

3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851

3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
            if( pOBExpr->iColumn!=iColumn ) continue;
          }else{
            Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr;
            if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){
              continue;
            }
          }

          if( iColumn!=XN_ROWID ){
            pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
          }
          if( wctrlFlags & WHERE_DISTINCTBY ){
            pLoop->u.btree.nDistinctCol = j+1;
          }
          isMatch = 1;
          break;
        }
        if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){
          /* Make sure the sort order is compatible in an ORDER BY clause.
          ** Sort order is irrelevant for a GROUP BY clause. */

          if( revSet ){
            if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) isMatch = 0;
          }else{
            rev = revIdx ^ pOrderBy->a[i].sortOrder;
            if( rev ) *pRevMask |= MASKBIT(iLoop);
            revSet = 1;
          }
        }
        if( isMatch ){
          if( iColumn==XN_ROWID ){
            testcase( distinctColumns==0 );







>













>

|

|







3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
            if( pOBExpr->iColumn!=iColumn ) continue;
          }else{
            Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr;
            if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){
              continue;
            }
          }
          if( pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL ) continue;
          if( iColumn!=XN_ROWID ){
            pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
          }
          if( wctrlFlags & WHERE_DISTINCTBY ){
            pLoop->u.btree.nDistinctCol = j+1;
          }
          isMatch = 1;
          break;
        }
        if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){
          /* Make sure the sort order is compatible in an ORDER BY clause.
          ** Sort order is irrelevant for a GROUP BY clause. */
          assert( (pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL)==0 );
          if( revSet ){
            if( (rev ^ revIdx)!=pOrderBy->a[i].sortFlags ) isMatch = 0;
          }else{
            rev = revIdx ^ pOrderBy->a[i].sortFlags;
            if( rev ) *pRevMask |= MASKBIT(iLoop);
            revSet = 1;
          }
        }
        if( isMatch ){
          if( iColumn==XN_ROWID ){
            testcase( distinctColumns==0 );
Changes to src/window.c.
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
    for(i=0; i<pAppend->nExpr; i++){
      Expr *pDup = sqlite3ExprDup(pParse->db, pAppend->a[i].pExpr, 0);
      if( bIntToNull && pDup && pDup->op==TK_INTEGER ){
        pDup->op = TK_NULL;
        pDup->flags &= ~(EP_IntValue|EP_IsTrue|EP_IsFalse);
      }
      pList = sqlite3ExprListAppend(pParse, pList, pDup);
      if( pList ) pList->a[nInit+i].sortOrder = pAppend->a[i].sortOrder;
    }
  }
  return pList;
}

/*
** If the SELECT statement passed as the second argument does not invoke







|







884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
    for(i=0; i<pAppend->nExpr; i++){
      Expr *pDup = sqlite3ExprDup(pParse->db, pAppend->a[i].pExpr, 0);
      if( bIntToNull && pDup && pDup->op==TK_INTEGER ){
        pDup->op = TK_NULL;
        pDup->flags &= ~(EP_IntValue|EP_IsTrue|EP_IsFalse);
      }
      pList = sqlite3ExprListAppend(pParse, pList, pDup);
      if( pList ) pList->a[nInit+i].sortFlags = pAppend->a[i].sortFlags;
    }
  }
  return pList;
}

/*
** If the SELECT statement passed as the second argument does not invoke
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
      */
      ExprList *pList = pWin->pOwner->x.pList;
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
      pWin->csrApp = pParse->nTab++;
      pWin->regApp = pParse->nMem+1;
      pParse->nMem += 3;
      if( pKeyInfo && pWin->pFunc->zName[1]=='i' ){
        assert( pKeyInfo->aSortOrder[0]==0 );
        pKeyInfo->aSortOrder[0] = 1;
      }
      sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2);
      sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
    }
    else if( p->zName==nth_valueName || p->zName==first_valueName ){
      /* Allocate two registers at pWin->regApp. These will be used to







|
|







1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
      */
      ExprList *pList = pWin->pOwner->x.pList;
      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
      pWin->csrApp = pParse->nTab++;
      pWin->regApp = pParse->nMem+1;
      pParse->nMem += 3;
      if( pKeyInfo && pWin->pFunc->zName[1]=='i' ){
        assert( pKeyInfo->aSortFlags[0]==0 );
        pKeyInfo->aSortFlags[0] = KEYINFO_ORDER_DESC;
      }
      sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2);
      sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
    }
    else if( p->zName==nth_valueName || p->zName==first_valueName ){
      /* Allocate two registers at pWin->regApp. These will be used to
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
  int arith = OP_Add;
  int addrGe;

  int regString = ++pParse->nMem;

  assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
  assert( p->pMWin->pOrderBy && p->pMWin->pOrderBy->nExpr==1 );
  if( p->pMWin->pOrderBy->a[0].sortOrder ){
    switch( op ){
      case OP_Ge: op = OP_Le; break;
      case OP_Gt: op = OP_Lt; break;
      default: assert( op==OP_Le ); op = OP_Ge; break;
    }
    arith = OP_Subtract;
  }







|







1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
  int arith = OP_Add;
  int addrGe;

  int regString = ++pParse->nMem;

  assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
  assert( p->pMWin->pOrderBy && p->pMWin->pOrderBy->nExpr==1 );
  if( p->pMWin->pOrderBy->a[0].sortFlags & KEYINFO_ORDER_DESC ){
    switch( op ){
      case OP_Ge: op = OP_Le; break;
      case OP_Gt: op = OP_Lt; break;
      default: assert( op==OP_Le ); op = OP_Ge; break;
    }
    arith = OP_Subtract;
  }
Added test/nulls1.test.










































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 2019 August 10
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#

####################################################
# DO NOT EDIT! THIS FILE IS AUTOMATICALLY GENERATED!
####################################################

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

do_execsql_test 1.0 {
  DROP TABLE IF EXISTS t3;
  CREATE TABLE t3(a INTEGER);
  INSERT INTO t3 VALUES(NULL), (10), (30), (20), (NULL);
} {}

for {set a 0} {$a < 2} {incr a} {
  foreach {tn limit} {
    1 ""
    2 "LIMIT 10"
  } {
    do_execsql_test 1.$a.$tn.1 "
      SELECT a FROM t3 ORDER BY a nULLS FIRST $limit
    " {{}   {}   10   20   30}
    
    do_execsql_test 1.$a.$tn.2 "
      SELECT a FROM t3 ORDER BY a nULLS LAST $limit
    " {10   20   30   {}   {}}
    
    do_execsql_test 1.$a.$tn.3 "
      SELECT a FROM t3 ORDER BY a DESC nULLS FIRST $limit
    " {{}   {}   30   20   10}
    
    do_execsql_test 1.$a.$tn.4 "
      SELECT a FROM t3 ORDER BY a DESC nULLS LAST $limit
    " {30   20   10   {}   {}}
  }

  catchsql { CREATE INDEX i1 ON t3(a) }
}

finish_test
Changes to tool/mkkeywordhash.c.
206
207
208
209
210
211
212

213
214
215
216
217
218
219
  { "EXCEPT",           "TK_EXCEPT",       COMPOUND               },
  { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
  { "EXCLUDE",          "TK_EXCLUDE",      WINDOWFUNC             },
  { "EXISTS",           "TK_EXISTS",       ALWAYS                 },
  { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
  { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
  { "FILTER",           "TK_FILTER",       WINDOWFUNC             },

  { "FOLLOWING",        "TK_FOLLOWING",    WINDOWFUNC             },
  { "FOR",              "TK_FOR",          TRIGGER                },
  { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
  { "FROM",             "TK_FROM",         ALWAYS                 },
  { "FULL",             "TK_JOIN_KW",      ALWAYS                 },
  { "GLOB",             "TK_LIKE_KW",      ALWAYS                 },
  { "GROUP",            "TK_GROUP",        ALWAYS                 },







>







206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
  { "EXCEPT",           "TK_EXCEPT",       COMPOUND               },
  { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
  { "EXCLUDE",          "TK_EXCLUDE",      WINDOWFUNC             },
  { "EXISTS",           "TK_EXISTS",       ALWAYS                 },
  { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
  { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
  { "FILTER",           "TK_FILTER",       WINDOWFUNC             },
  { "FIRST",            "TK_FIRST",        ALWAYS                 },
  { "FOLLOWING",        "TK_FOLLOWING",    WINDOWFUNC             },
  { "FOR",              "TK_FOR",          TRIGGER                },
  { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
  { "FROM",             "TK_FROM",         ALWAYS                 },
  { "FULL",             "TK_JOIN_KW",      ALWAYS                 },
  { "GLOB",             "TK_LIKE_KW",      ALWAYS                 },
  { "GROUP",            "TK_GROUP",        ALWAYS                 },
231
232
233
234
235
236
237

238
239
240
241
242
243
244
245
246
247

248
249
250
251
252
253
254
  { "INSTEAD",          "TK_INSTEAD",      TRIGGER                },
  { "INTERSECT",        "TK_INTERSECT",    COMPOUND               },
  { "INTO",             "TK_INTO",         ALWAYS                 },
  { "IS",               "TK_IS",           ALWAYS                 },
  { "ISNULL",           "TK_ISNULL",       ALWAYS                 },
  { "JOIN",             "TK_JOIN",         ALWAYS                 },
  { "KEY",              "TK_KEY",          ALWAYS                 },

  { "LEFT",             "TK_JOIN_KW",      ALWAYS                 },
  { "LIKE",             "TK_LIKE_KW",      ALWAYS                 },
  { "LIMIT",            "TK_LIMIT",        ALWAYS                 },
  { "MATCH",            "TK_MATCH",        ALWAYS                 },
  { "NATURAL",          "TK_JOIN_KW",      ALWAYS                 },
  { "NO",               "TK_NO",           FKEY|WINDOWFUNC        },
  { "NOT",              "TK_NOT",          ALWAYS                 },
  { "NOTHING",          "TK_NOTHING",      UPSERT                 },
  { "NOTNULL",          "TK_NOTNULL",      ALWAYS                 },
  { "NULL",             "TK_NULL",         ALWAYS                 },

  { "OF",               "TK_OF",           ALWAYS                 },
  { "OFFSET",           "TK_OFFSET",       ALWAYS                 },
  { "ON",               "TK_ON",           ALWAYS                 },
  { "OR",               "TK_OR",           ALWAYS                 },
  { "ORDER",            "TK_ORDER",        ALWAYS                 },
  { "OTHERS",           "TK_OTHERS",       WINDOWFUNC             },
  { "OUTER",            "TK_JOIN_KW",      ALWAYS                 },







>










>







232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
  { "INSTEAD",          "TK_INSTEAD",      TRIGGER                },
  { "INTERSECT",        "TK_INTERSECT",    COMPOUND               },
  { "INTO",             "TK_INTO",         ALWAYS                 },
  { "IS",               "TK_IS",           ALWAYS                 },
  { "ISNULL",           "TK_ISNULL",       ALWAYS                 },
  { "JOIN",             "TK_JOIN",         ALWAYS                 },
  { "KEY",              "TK_KEY",          ALWAYS                 },
  { "LAST",             "TK_LAST",         ALWAYS                 },
  { "LEFT",             "TK_JOIN_KW",      ALWAYS                 },
  { "LIKE",             "TK_LIKE_KW",      ALWAYS                 },
  { "LIMIT",            "TK_LIMIT",        ALWAYS                 },
  { "MATCH",            "TK_MATCH",        ALWAYS                 },
  { "NATURAL",          "TK_JOIN_KW",      ALWAYS                 },
  { "NO",               "TK_NO",           FKEY|WINDOWFUNC        },
  { "NOT",              "TK_NOT",          ALWAYS                 },
  { "NOTHING",          "TK_NOTHING",      UPSERT                 },
  { "NOTNULL",          "TK_NOTNULL",      ALWAYS                 },
  { "NULL",             "TK_NULL",         ALWAYS                 },
  { "NULLS",            "TK_NULLS",        ALWAYS                 },
  { "OF",               "TK_OF",           ALWAYS                 },
  { "OFFSET",           "TK_OFFSET",       ALWAYS                 },
  { "ON",               "TK_ON",           ALWAYS                 },
  { "OR",               "TK_OR",           ALWAYS                 },
  { "ORDER",            "TK_ORDER",        ALWAYS                 },
  { "OTHERS",           "TK_OTHERS",       WINDOWFUNC             },
  { "OUTER",            "TK_JOIN_KW",      ALWAYS                 },