/*

** 2001 September 15

**

** 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 contains C code routines that are called by the parser

** to handle SELECT statements in SQLite.

*/

#include "sqliteInt.h"

/*

** An instance of the following object is used to record information about

** how to process the DISTINCT keyword, to simplify passing that information

** into the selectInnerLoop() routine.

*/

typedef struct DistinctCtx DistinctCtx;

struct DistinctCtx {

u8 isTnct; /* 0: Not distinct. 1: DISTICT 2: DISTINCT and ORDER BY */

u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */

int tabTnct; /* Ephemeral table used for DISTINCT processing */

int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */

};

/*

** An instance of the following object is used to record information about

** the ORDER BY (or GROUP BY) clause of query is being coded.

**

** The aDefer[] array is used by the sorter-references optimization. For

** example, assuming there is no index that can be used for the ORDER BY,

** for the query:

**

** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10;

**

** it may be more efficient to add just the "a" values to the sorter, and

** retrieve the associated "bigblob" values directly from table t1 as the

** 10 smallest "a" values are extracted from the sorter.

**

** When the sorter-reference optimization is used, there is one entry in the

** aDefer[] array for each database table that may be read as values are

** extracted from the sorter.

*/

typedef struct SortCtx SortCtx;

struct SortCtx {

ExprList *pOrderBy; /* The ORDER BY (or GROUP BY clause) */

int nOBSat; /* Number of ORDER BY terms satisfied by indices */

int iECursor; /* Cursor number for the sorter */

int regReturn; /* Register holding block-output return address */

int labelBkOut; /* Start label for the block-output subroutine */

int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */

int labelDone; /* Jump here when done, ex: LIMIT reached */

int labelOBLopt; /* Jump here when sorter is full */

u8 sortFlags; /* Zero or more SORTFLAG_* bits */

#ifdef SQLITE_ENABLE_SORTER_REFERENCES

u8 nDefer; /* Number of valid entries in aDefer[] */

struct DeferredCsr {

Table *pTab; /* Table definition */

int iCsr; /* Cursor number for table */

int nKey; /* Number of PK columns for table pTab (>=1) */

} aDefer[4];

#endif

struct RowLoadInfo *pDeferredRowLoad; /* Deferred row loading info or NULL */

};

#define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */

/*

** Delete all the content of a Select structure. Deallocate the structure

** itself depending on the value of bFree

**

** If bFree==1, call sqlite3DbFree() on the p object.

** If bFree==0, Leave the first Select object unfreed

*/

static void clearSelect(sqlite3 *db, Select *p, int bFree){

while( p ){

Select *pPrior = p->pPrior;

sqlite3ExprListDelete(db, p->pEList);

sqlite3SrcListDelete(db, p->pSrc);

sqlite3ExprDelete(db, p->pWhere);

sqlite3ExprListDelete(db, p->pGroupBy);

sqlite3ExprDelete(db, p->pHaving);

sqlite3ExprListDelete(db, p->pOrderBy);

sqlite3ExprDelete(db, p->pLimit);

if( OK_IF_ALWAYS_TRUE(p->pWith) ) sqlite3WithDelete(db, p->pWith);

#ifndef SQLITE_OMIT_WINDOWFUNC

if( OK_IF_ALWAYS_TRUE(p->pWinDefn) ){

sqlite3WindowListDelete(db, p->pWinDefn);

}

while( p->pWin ){

assert( p->pWin->ppThis==&p->pWin );

sqlite3WindowUnlinkFromSelect(p->pWin);

}

#endif

if( bFree ) sqlite3DbFreeNN(db, p);

p = pPrior;

bFree = 1;

}

}

/*

** Initialize a SelectDest structure.

*/

void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){

pDest->eDest = (u8)eDest;

pDest->iSDParm = iParm;

pDest->iSDParm2 = 0;

pDest->zAffSdst = 0;

pDest->iSdst = 0;

pDest->nSdst = 0;

}

/*

** Allocate a new Select structure and return a pointer to that

** structure.

*/

Select *sqlite3SelectNew(

Parse *pParse, /* Parsing context */

ExprList *pEList, /* which columns to include in the result */

SrcList *pSrc, /* the FROM clause -- which tables to scan */

Expr *pWhere, /* the WHERE clause */

ExprList *pGroupBy, /* the GROUP BY clause */

Expr *pHaving, /* the HAVING clause */

ExprList *pOrderBy, /* the ORDER BY clause */

u32 selFlags, /* Flag parameters, such as SF_Distinct */

Expr *pLimit /* LIMIT value. NULL means not used */

){

Select *pNew, *pAllocated;

Select standin;

pAllocated = pNew = sqlite3DbMallocRawNN(pParse->db, sizeof(*pNew) );

if( pNew==0 ){

assert( pParse->db->mallocFailed );

pNew = &standin;

}

if( pEList==0 ){

pEList = sqlite3ExprListAppend(pParse, 0,

sqlite3Expr(pParse->db,TK_ASTERISK,0));

}

pNew->pEList = pEList;

pNew->op = TK_SELECT;

pNew->selFlags = selFlags;

pNew->iLimit = 0;

pNew->iOffset = 0;

pNew->selId = ++pParse->nSelect;

pNew->addrOpenEphm[0] = -1;

pNew->addrOpenEphm[1] = -1;

pNew->nSelectRow = 0;

if( pSrc==0 ) pSrc = sqlite3DbMallocZero(pParse->db, sizeof(*pSrc));

pNew->pSrc = pSrc;

pNew->pWhere = pWhere;

pNew->pGroupBy = pGroupBy;

pNew->pHaving = pHaving;

pNew->pOrderBy = pOrderBy;

pNew->pPrior = 0;

pNew->pNext = 0;

pNew->pLimit = pLimit;

pNew->pWith = 0;

#ifndef SQLITE_OMIT_WINDOWFUNC

pNew->pWin = 0;

pNew->pWinDefn = 0;

#endif

if( pParse->db->mallocFailed ) {

clearSelect(pParse->db, pNew, pNew!=&standin);

pAllocated = 0;

}else{

assert( pNew->pSrc!=0 || pParse->nErr>0 );

}

return pAllocated;

}

/*

** Delete the given Select structure and all of its substructures.

*/

void sqlite3SelectDelete(sqlite3 *db, Select *p){

if( OK_IF_ALWAYS_TRUE(p) ) clearSelect(db, p, 1);

}

/*

** Return a pointer to the right-most SELECT statement in a compound.

*/

static Select *findRightmost(Select *p){

while( p->pNext ) p = p->pNext;

return p;

}

/*

** Given 1 to 3 identifiers preceding the JOIN keyword, determine the

** type of join. Return an integer constant that expresses that type

** in terms of the following bit values:

**

** JT_INNER

** JT_CROSS

** JT_OUTER

** JT_NATURAL

** JT_LEFT

** JT_RIGHT

**

** A full outer join is the combination of JT_LEFT and JT_RIGHT.

**

** If an illegal or unsupported join type is seen, then still return

** a join type, but put an error in the pParse structure.

**

** These are the valid join types:

**

**

** pA pB pC Return Value

** ------- ----- ----- ------------

** CROSS - - JT_CROSS

** INNER - - JT_INNER

** LEFT - - JT_LEFT|JT_OUTER

** LEFT OUTER - JT_LEFT|JT_OUTER

** RIGHT - - JT_RIGHT|JT_OUTER

** RIGHT OUTER - JT_RIGHT|JT_OUTER

** FULL - - JT_LEFT|JT_RIGHT|JT_OUTER

** FULL OUTER - JT_LEFT|JT_RIGHT|JT_OUTER

** NATURAL INNER - JT_NATURAL|JT_INNER

** NATURAL LEFT - JT_NATURAL|JT_LEFT|JT_OUTER

** NATURAL LEFT OUTER JT_NATURAL|JT_LEFT|JT_OUTER

** NATURAL RIGHT - JT_NATURAL|JT_RIGHT|JT_OUTER

** NATURAL RIGHT OUTER JT_NATURAL|JT_RIGHT|JT_OUTER

** NATURAL FULL - JT_NATURAL|JT_LEFT|JT_RIGHT

** NATURAL FULL OUTER JT_NATRUAL|JT_LEFT|JT_RIGHT

**

** To preserve historical compatibly, SQLite also accepts a variety

** of other non-standard and in many cases non-sensical join types.

** This routine makes as much sense at it can from the nonsense join

** type and returns a result. Examples of accepted nonsense join types

** include but are not limited to:

**

** INNER CROSS JOIN -> same as JOIN

** NATURAL CROSS JOIN -> same as NATURAL JOIN

** OUTER LEFT JOIN -> same as LEFT JOIN

** LEFT NATURAL JOIN -> same as NATURAL LEFT JOIN

** LEFT RIGHT JOIN -> same as FULL JOIN

** RIGHT OUTER FULL JOIN -> same as FULL JOIN

** CROSS CROSS CROSS JOIN -> same as JOIN

**

** The only restrictions on the join type name are:

**

** * "INNER" cannot appear together with "OUTER", "LEFT", "RIGHT",

** or "FULL".

**

** * "CROSS" cannot appear together with "OUTER", "LEFT", "RIGHT,

** or "FULL".

**

** * If "OUTER" is present then there must also be one of

** "LEFT", "RIGHT", or "FULL"

*/

int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){

int jointype = 0;

Token *apAll[3];

Token *p;

/* 0123456789 123456789 123456789 123 */

static const char zKeyText[] = "naturaleftouterightfullinnercross";

static const struct {

u8 i; /* Beginning of keyword text in zKeyText[] */

u8 nChar; /* Length of the keyword in characters */

u8 code; /* Join type mask */

} aKeyword[] = {

/* (0) natural */ { 0, 7, JT_NATURAL },

/* (1) left */ { 6, 4, JT_LEFT|JT_OUTER },

/* (2) outer */ { 10, 5, JT_OUTER },

/* (3) right */ { 14, 5, JT_RIGHT|JT_OUTER },

/* (4) full */ { 19, 4, JT_LEFT|JT_RIGHT|JT_OUTER },

/* (5) inner */ { 23, 5, JT_INNER },

/* (6) cross */ { 28, 5, JT_INNER|JT_CROSS },

};

int i, j;

apAll[0] = pA;

apAll[1] = pB;

apAll[2] = pC;

for(i=0; i<3 && apAll[i]; i++){

p = apAll[i];

for(j=0; j<ArraySize(aKeyword); j++){

if( p->n==aKeyword[j].nChar

&& sqlite3StrNICmp((char*)p->z, &zKeyText[aKeyword[j].i], p->n)==0 ){

jointype |= aKeyword[j].code;

break;

}

}

testcase( j==0 || j==1 || j==2 || j==3 || j==4 || j==5 || j==6 );

if( j>=ArraySize(aKeyword) ){

jointype |= JT_ERROR;

break;

}

}

if(

(jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||

(jointype & JT_ERROR)!=0 ||

(jointype & (JT_OUTER|JT_LEFT|JT_RIGHT))==JT_OUTER

){

const char *zSp1 = " ";

const char *zSp2 = " ";

if( pB==0 ){ zSp1++; }

if( pC==0 ){ zSp2++; }

sqlite3ErrorMsg(pParse, "unknown join type: "

"%T%s%T%s%T", pA, zSp1, pB, zSp2, pC);

jointype = JT_INNER;

}

return jointype;

}

/*

** Return the index of a column in a table. Return -1 if the column

** is not contained in the table.

*/

int sqlite3ColumnIndex(Table *pTab, const char *zCol){

int i;

u8 h = sqlite3StrIHash(zCol);

Column *pCol;

for(pCol=pTab->aCol, i=0; i<pTab->nCol; pCol++, i++){

if( pCol->hName==h && sqlite3StrICmp(pCol->zCnName, zCol)==0 ) return i;

}

return -1;

}

/*

** Mark a subquery result column as having been used.

*/

void sqlite3SrcItemColumnUsed(SrcItem *pItem, int iCol){

assert( pItem!=0 );

assert( (int)pItem->fg.isNestedFrom == IsNestedFrom(pItem->pSelect) );

if( pItem->fg.isNestedFrom ){

ExprList *pResults;

assert( pItem->pSelect!=0 );

pResults = pItem->pSelect->pEList;

assert( pResults!=0 );

assert( iCol>=0 && iCol<pResults->nExpr );

pResults->a[iCol].fg.bUsed = 1;

}

}

/*

** Search the tables iStart..iEnd (inclusive) in pSrc, looking for a

** table that has a column named zCol. The search is left-to-right.

** The first match found is returned.

**

** When found, set *piTab and *piCol to the table index and column index

** of the matching column and return TRUE.

**

** If not found, return FALSE.

*/

static int tableAndColumnIndex(

SrcList *pSrc, /* Array of tables to search */

int iStart, /* First member of pSrc->a[] to check */

int iEnd, /* Last member of pSrc->a[] to check */

const char *zCol, /* Name of the column we are looking for */

int *piTab, /* Write index of pSrc->a[] here */

int *piCol, /* Write index of pSrc->a[*piTab].pTab->aCol[] here */

int bIgnoreHidden /* Ignore hidden columns */

){

int i; /* For looping over tables in pSrc */

int iCol; /* Index of column matching zCol */

assert( iEnd<pSrc->nSrc );

assert( iStart>=0 );

assert( (piTab==0)==(piCol==0) ); /* Both or neither are NULL */

for(i=iStart; i<=iEnd; i++){

iCol = sqlite3ColumnIndex(pSrc->a[i].pTab, zCol);

if( iCol>=0

&& (bIgnoreHidden==0 || IsHiddenColumn(&pSrc->a[i].pTab->aCol[iCol])==0)

){

if( piTab ){

sqlite3SrcItemColumnUsed(&pSrc->a[i], iCol);

*piTab = i;

*piCol = iCol;

}

return 1;

}

}

return 0;

}

/*

** Set the EP_OuterON property on all terms of the given expression.

** And set the Expr.w.iJoin to iTable for every term in the

** expression.

**

** The EP_OuterON property is used on terms of an expression to tell

** the OUTER JOIN processing logic that this term is part of the

** join restriction specified in the ON or USING clause and not a part

** of the more general WHERE clause. These terms are moved over to the

** WHERE clause during join processing but we need to remember that they

** originated in the ON or USING clause.

**

** The Expr.w.iJoin tells the WHERE clause processing that the

** expression depends on table w.iJoin even if that table is not

** explicitly mentioned in the expression. That information is needed

** for cases like this:

**

** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5

**

** The where clause needs to defer the handling of the t1.x=5

** term until after the t2 loop of the join. In that way, a

** NULL t2 row will be inserted whenever t1.x!=5. If we do not

** defer the handling of t1.x=5, it will be processed immediately

** after the t1 loop and rows with t1.x!=5 will never appear in

** the output, which is incorrect.

*/

void sqlite3SetJoinExpr(Expr *p, int iTable, u32 joinFlag){

assert( joinFlag==EP_OuterON || joinFlag==EP_InnerON );

while( p ){

ExprSetProperty(p, joinFlag);

assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );

ExprSetVVAProperty(p, EP_NoReduce);

p->w.iJoin = iTable;

if( p->op==TK_FUNCTION ){

assert( ExprUseXList(p) );

if( p->x.pList ){

int i;

for(i=0; i<p->x.pList->nExpr; i++){

sqlite3SetJoinExpr(p->x.pList->a[i].pExpr, iTable, joinFlag);

}

}

}

sqlite3SetJoinExpr(p->pLeft, iTable, joinFlag);

p = p->pRight;

}

}

/* Undo the work of sqlite3SetJoinExpr(). This is used when a LEFT JOIN

** is simplified into an ordinary JOIN, and when an ON expression is

** "pushed down" into the WHERE clause of a subquery.

**

** Convert every term that is marked with EP_OuterON and w.iJoin==iTable into

** an ordinary term that omits the EP_OuterON mark. Or if iTable<0, then

** just clear every EP_OuterON and EP_InnerON mark from the expression tree.

**

** If nullable is true, that means that Expr p might evaluate to NULL even

** if it is a reference to a NOT NULL column. This can happen, for example,

** if the table that p references is on the left side of a RIGHT JOIN.

** If nullable is true, then take care to not remove the EP_CanBeNull bit.

** See forum thread https://sqlite.org/forum/forumpost/b40696f50145d21c

*/

static void unsetJoinExpr(Expr *p, int iTable, int nullable){

while( p ){

if( iTable<0 || (ExprHasProperty(p, EP_OuterON) && p->w.iJoin==iTable) ){

ExprClearProperty(p, EP_OuterON|EP_InnerON);

if( iTable>=0 ) ExprSetProperty(p, EP_InnerON);

}

if( p->op==TK_COLUMN && p->iTable==iTable && !nullable ){

ExprClearProperty(p, EP_CanBeNull);

}

if( p->op==TK_FUNCTION ){

assert( ExprUseXList(p) );

if( p->x.pList ){

int i;

for(i=0; i<p->x.pList->nExpr; i++){

unsetJoinExpr(p->x.pList->a[i].pExpr, iTable, nullable);

}

}

}

unsetJoinExpr(p->pLeft, iTable, nullable);

p = p->pRight;

}

}

/*

** This routine processes the join information for a SELECT statement.

**

** * A NATURAL join is converted into a USING join. After that, we

** do not need to be concerned with NATURAL joins and we only have

** think about USING joins.

**

** * ON and USING clauses result in extra terms being added to the

** WHERE clause to enforce the specified constraints. The extra

** WHERE clause terms will be tagged with EP_OuterON or

** EP_InnerON so that we know that they originated in ON/USING.

**

** The terms of a FROM clause are contained in the Select.pSrc structure.

** The left most table is the first entry in Select.pSrc. The right-most

** table is the last entry. The join operator is held in the entry to

** the right. Thus entry 1 contains the join operator for the join between

** entries 0 and 1. Any ON or USING clauses associated with the join are

** also attached to the right entry.

**

** This routine returns the number of errors encountered.

*/

static int sqlite3ProcessJoin(Parse *pParse, Select *p){

SrcList *pSrc; /* All tables in the FROM clause */

int i, j; /* Loop counters */

SrcItem *pLeft; /* Left table being joined */

SrcItem *pRight; /* Right table being joined */

pSrc = p->pSrc;

pLeft = &pSrc->a[0];

pRight = &pLeft[1];

for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){

Table *pRightTab = pRight->pTab;

u32 joinType;

if( NEVER(pLeft->pTab==0 || pRightTab==0) ) continue;

joinType = (pRight->fg.jointype & JT_OUTER)!=0 ? EP_OuterON : EP_InnerON;

/* If this is a NATURAL join, synthesize an approprate USING clause

** to specify which columns should be joined.

*/

if( pRight->fg.jointype & JT_NATURAL ){

IdList *pUsing = 0;

if( pRight->fg.isUsing || pRight->u3.pOn ){

sqlite3ErrorMsg(pParse, "a NATURAL join may not have "

"an ON or USING clause", 0);

return 1;

}

for(j=0; j<pRightTab->nCol; j++){

char *zName; /* Name of column in the right table */

if( IsHiddenColumn(&pRightTab->aCol[j]) ) continue;

zName = pRightTab->aCol[j].zCnName;

if( tableAndColumnIndex(pSrc, 0, i, zName, 0, 0, 1) ){

pUsing = sqlite3IdListAppend(pParse, pUsing, 0);

if( pUsing ){

assert( pUsing->nId>0 );

assert( pUsing->a[pUsing->nId-1].zName==0 );

pUsing->a[pUsing->nId-1].zName = sqlite3DbStrDup(pParse->db, zName);

}

}

}

if( pUsing ){

pRight->fg.isUsing = 1;

pRight->fg.isSynthUsing = 1;

pRight->u3.pUsing = pUsing;

}

if( pParse->nErr ) return 1;

}

/* Create extra terms on the WHERE clause for each column named

** in the USING clause. Example: If the two tables to be joined are

** A and B and the USING clause names X, Y, and Z, then add this

** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z

** Report an error if any column mentioned in the USING clause is

** not contained in both tables to be joined.

*/

if( pRight->fg.isUsing ){

IdList *pList = pRight->u3.pUsing;

sqlite3 *db = pParse->db;

assert( pList!=0 );

for(j=0; j<pList->nId; j++){

char *zName; /* Name of the term in the USING clause */

int iLeft; /* Table on the left with matching column name */

int iLeftCol; /* Column number of matching column on the left */

int iRightCol; /* Column number of matching column on the right */

Expr *pE1; /* Reference to the column on the LEFT of the join */

Expr *pE2; /* Reference to the column on the RIGHT of the join */

Expr *pEq; /* Equality constraint. pE1 == pE2 */

zName = pList->a[j].zName;

iRightCol = sqlite3ColumnIndex(pRightTab, zName);

if( iRightCol<0

|| tableAndColumnIndex(pSrc, 0, i, zName, &iLeft, &iLeftCol,

pRight->fg.isSynthUsing)==0

){

sqlite3ErrorMsg(pParse, "cannot join using column %s - column "

"not present in both tables", zName);

return 1;

}

pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iLeftCol);

sqlite3SrcItemColumnUsed(&pSrc->a[iLeft], iLeftCol);

if( (pSrc->a[0].fg.jointype & JT_LTORJ)!=0 ){

/* This branch runs if the query contains one or more RIGHT or FULL

** JOINs. If only a single table on the left side of this join

** contains the zName column, then this branch is a no-op.

** But if there are two or more tables on the left side

** of the join, construct a coalesce() function that gathers all

** such tables. Raise an error if more than one of those references

** to zName is not also within a prior USING clause.

**

** We really ought to raise an error if there are two or more

** non-USING references to zName on the left of an INNER or LEFT

** JOIN. But older versions of SQLite do not do that, so we avoid

** adding a new error so as to not break legacy applications.

*/

ExprList *pFuncArgs = 0; /* Arguments to the coalesce() */

static const Token tkCoalesce = { "coalesce", 8 };

while( tableAndColumnIndex(pSrc, iLeft+1, i, zName, &iLeft, &iLeftCol,

pRight->fg.isSynthUsing)!=0 ){

if( pSrc->a[iLeft].fg.isUsing==0

|| sqlite3IdListIndex(pSrc->a[iLeft].u3.pUsing, zName)<0

){

sqlite3ErrorMsg(pParse, "ambiguous reference to %s in USING()",

zName);

break;

}

pFuncArgs = sqlite3ExprListAppend(pParse, pFuncArgs, pE1);

pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iLeftCol);

sqlite3SrcItemColumnUsed(&pSrc->a[iLeft], iLeftCol);

}

if( pFuncArgs ){

pFuncArgs = sqlite3ExprListAppend(pParse, pFuncArgs, pE1);

pE1 = sqlite3ExprFunction(pParse, pFuncArgs, &tkCoalesce, 0);

}

}

pE2 = sqlite3CreateColumnExpr(db, pSrc, i+1, iRightCol);

sqlite3SrcItemColumnUsed(pRight, iRightCol);

pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2);

assert( pE2!=0 || pEq==0 );

if( pEq ){

ExprSetProperty(pEq, joinType);

assert( !ExprHasProperty(pEq, EP_TokenOnly|EP_Reduced) );

ExprSetVVAProperty(pEq, EP_NoReduce);

pEq->w.iJoin = pE2->iTable;

}

p->pWhere = sqlite3ExprAnd(pParse, p->pWhere, pEq);

}

}

/* Add the ON clause to the end of the WHERE clause, connected by

** an AND operator.

*/

else if( pRight->u3.pOn ){

sqlite3SetJoinExpr(pRight->u3.pOn, pRight->iCursor, joinType);

p->pWhere = sqlite3ExprAnd(pParse, p->pWhere, pRight->u3.pOn);

pRight->u3.pOn = 0;

pRight->fg.isOn = 1;

}

}

return 0;

}

/*

** An instance of this object holds information (beyond pParse and pSelect)

** needed to load the next result row that is to be added to the sorter.

*/

typedef struct RowLoadInfo RowLoadInfo;

struct RowLoadInfo {

int regResult; /* Store results in array of registers here */

u8 ecelFlags; /* Flag argument to ExprCodeExprList() */

#ifdef SQLITE_ENABLE_SORTER_REFERENCES

ExprList *pExtra; /* Extra columns needed by sorter refs */

int regExtraResult; /* Where to load the extra columns */

#endif

};

/*

** This routine does the work of loading query data into an array of

** registers so that it can be added to the sorter.

*/

static void innerLoopLoadRow(

Parse *pParse, /* Statement under construction */

Select *pSelect, /* The query being coded */

RowLoadInfo *pInfo /* Info needed to complete the row load */

){

sqlite3ExprCodeExprList(pParse, pSelect->pEList, pInfo->regResult,

0, pInfo->ecelFlags);

#ifdef SQLITE_ENABLE_SORTER_REFERENCES

if( pInfo->pExtra ){

sqlite3ExprCodeExprList(pParse, pInfo->pExtra, pInfo->regExtraResult, 0, 0);

sqlite3ExprListDelete(pParse->db, pInfo->pExtra);

}

#endif

}

/*

** Code the OP_MakeRecord instruction that generates the entry to be

** added into the sorter.

**

** Return the register in which the result is stored.

*/

static int makeSorterRecord(

Parse *pParse,

SortCtx *pSort,

Select *pSelect,

int regBase,

int nBase

){

int nOBSat = pSort->nOBSat;

Vdbe *v = pParse->pVdbe;

int regOut = ++pParse->nMem;

if( pSort->pDeferredRowLoad ){

innerLoopLoadRow(pParse, pSelect, pSort->pDeferredRowLoad);

}

sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regOut);

return regOut;

}

/*

** Generate code that will push the record in registers regData

** through regData+nData-1 onto the sorter.

*/

static void pushOntoSorter(

Parse *pParse, /* Parser context */

SortCtx *pSort, /* Information about the ORDER BY clause */

Select *pSelect, /* The whole SELECT statement */

int regData, /* First register holding data to be sorted */

int regOrigData, /* First register holding data before packing */

int nData, /* Number of elements in the regData data array */

int nPrefixReg /* No. of reg prior to regData available for use */

){

Vdbe *v = pParse->pVdbe; /* Stmt under construction */

int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0);

int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */

int nBase = nExpr + bSeq + nData; /* Fields in sorter record */

int regBase; /* Regs for sorter record */

int regRecord = 0; /* Assembled sorter record */

int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */

int op; /* Opcode to add sorter record to sorter */

int iLimit; /* LIMIT counter */

int iSkip = 0; /* End of the sorter insert loop */

assert( bSeq==0 || bSeq==1 );

/* Three cases:

** (1) The data to be sorted has already been packed into a Record

** by a prior OP_MakeRecord. In this case nData==1 and regData

** will be completely unrelated to regOrigData.

** (2) All output columns are included in the sort record. In that

** case regData==regOrigData.

** (3) Some output columns are omitted from the sort record due to

** the SQLITE_ENABLE_SORTER_REFERENCE optimization, or due to the

** SQLITE_ECEL_OMITREF optimization, or due to the

** SortCtx.pDeferredRowLoad optimiation. In any of these cases

** regOrigData is 0 to prevent this routine from trying to copy

** values that might not yet exist.

*/

assert( nData==1 || regData==regOrigData || regOrigData==0 );

if( nPrefixReg ){

assert( nPrefixReg==nExpr+bSeq );

regBase = regData - nPrefixReg;

}else{

regBase = pParse->nMem + 1;

pParse->nMem += nBase;

}

assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );

iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;

pSort->labelDone = sqlite3VdbeMakeLabel(pParse);

sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,

SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));

if( bSeq ){

sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);

}

if( nPrefixReg==0 && nData>0 ){

sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);

}

if( nOBSat>0 ){

int regPrevKey; /* The first nOBSat columns of the previous row */

int addrFirst; /* Address of the OP_IfNot opcode */

int addrJmp; /* Address of the OP_Jump opcode */

VdbeOp *pOp; /* Opcode that opens the sorter */

int nKey; /* Number of sorting key columns, including OP_Sequence */

KeyInfo *pKI; /* Original KeyInfo on the sorter table */

regRecord = makeSorterRecord(pParse, pSort, pSelect, regBase, nBase);

regPrevKey = pParse->nMem+1;

pParse->nMem += pSort->nOBSat;

nKey = nExpr - pSort->nOBSat + bSeq;

if( bSeq ){

addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr);

}else{

addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);

}

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);

pOp = 0; /* Ensure pOp not used after sqltie3VdbeAddOp3() */

addrJmp = sqlite3VdbeCurrentAddr(v);

sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);

pSort->labelBkOut = sqlite3VdbeMakeLabel(pParse);

pSort->regReturn = ++pParse->nMem;

sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);

sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);

if( iLimit ){

sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);

VdbeCoverage(v);

}

sqlite3VdbeJumpHere(v, addrFirst);

sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);

sqlite3VdbeJumpHere(v, addrJmp);

}

if( iLimit ){

/* At this point the values for the new sorter entry are stored

** in an array of registers. They need to be composed into a record

** and inserted into the sorter if either (a) there are currently

** less than LIMIT+OFFSET items or (b) the new record is smaller than

** the largest record currently in the sorter. If (b) is true and there

** are already LIMIT+OFFSET items in the sorter, delete the largest

** entry before inserting the new one. This way there are never more

** than LIMIT+OFFSET items in the sorter.

**

** If the new record does not need to be inserted into the sorter,

** jump to the next iteration of the loop. If the pSort->labelOBLopt

** value is not zero, then it is a label of where to jump. Otherwise,

** just bypass the row insert logic. See the header comment on the

** sqlite3WhereOrderByLimitOptLabel() function for additional info.

*/

int iCsr = pSort->iECursor;

sqlite3VdbeAddOp2(v, OP_IfNotZero, iLimit, sqlite3VdbeCurrentAddr(v)+4);

VdbeCoverage(v);

sqlite3VdbeAddOp2(v, OP_Last, iCsr, 0);

iSkip = sqlite3VdbeAddOp4Int(v, OP_IdxLE,

iCsr, 0, regBase+nOBSat, nExpr-nOBSat);

VdbeCoverage(v);

sqlite3VdbeAddOp1(v, OP_Delete, iCsr);

}

if( regRecord==0 ){

regRecord = makeSorterRecord(pParse, pSort, pSelect, regBase, nBase);

}

if( pSort->sortFlags & SORTFLAG_UseSorter ){

op = OP_SorterInsert;

}else{

op = OP_IdxInsert;

}

sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,

regBase+nOBSat, nBase-nOBSat);

if( iSkip ){

sqlite3VdbeChangeP2(v, iSkip,

pSort->labelOBLopt ? pSort->labelOBLopt : sqlite3VdbeCurrentAddr(v));

}

}

/*

** Add code to implement the OFFSET

*/

static void codeOffset(

Vdbe *v, /* Generate code into this VM */

int iOffset, /* Register holding the offset counter */

int iContinue /* Jump here to skip the current record */

){

if( iOffset>0 ){

sqlite3VdbeAddOp3(v, OP_IfPos, iOffset, iContinue, 1); VdbeCoverage(v);

VdbeComment((v, "OFFSET"));

}

}

/*

** Add code that will check to make sure the array of registers starting at

** iMem form a distinct entry. This is used by both "SELECT DISTINCT ..." and

** distinct aggregates ("SELECT count(DISTINCT <expr>) ..."). Three strategies

** are available. Which is used depends on the value of parameter eTnctType,

** as follows:

**

** WHERE_DISTINCT_UNORDERED/WHERE_DISTINCT_NOOP:

** Build an ephemeral table that contains all entries seen before and

** skip entries which have been seen before.

**

** Parameter iTab is the cursor number of an ephemeral table that must

** be opened before the VM code generated by this routine is executed.

** The ephemeral cursor table is queried for a record identical to the

** record formed by the current array of registers. If one is found,

** jump to VM address addrRepeat. Otherwise, insert a new record into

** the ephemeral cursor and proceed.

**

** The returned value in this case is a copy of parameter iTab.

**

** WHERE_DISTINCT_ORDERED:

** In this case rows are being delivered sorted order. The ephermal

** table is not required. Instead, the current set of values

** is compared against previous row. If they match, the new row

** is not distinct and control jumps to VM address addrRepeat. Otherwise,

** the VM program proceeds with processing the new row.

**

** The returned value in this case is the register number of the first

** in an array of registers used to store the previous result row so that

** it can be compared to the next. The caller must ensure that this

** register is initialized to NULL. (The fixDistinctOpenEph() routine

** will take care of this initialization.)

**

** WHERE_DISTINCT_UNIQUE:

** In this case it has already been determined that the rows are distinct.

** No special action is required. The return value is zero.

**

** Parameter pEList is the list of expressions used to generated the

** contents of each row. It is used by this routine to determine (a)

** how many elements there are in the array of registers and (b) the

** collation sequences that should be used for the comparisons if

** eTnctType is WHERE_DISTINCT_ORDERED.

*/

static int codeDistinct(

Parse *pParse, /* Parsing and code generating context */

int eTnctType, /* WHERE_DISTINCT_* value */

int iTab, /* A sorting index used to test for distinctness */

int addrRepeat, /* Jump to here if not distinct */

ExprList *pEList, /* Expression for each element */

int regElem /* First element */

){

int iRet = 0;

int nResultCol = pEList->nExpr;

Vdbe *v = pParse->pVdbe;

switch( eTnctType ){

case WHERE_DISTINCT_ORDERED: {

int i;

int iJump; /* Jump destination */

int regPrev; /* Previous row content */

/* Allocate space for the previous row */

iRet = regPrev = pParse->nMem+1;

pParse->nMem += nResultCol;

iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;

for(i=0; i<nResultCol; i++){

CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr);

if( i<nResultCol-1 ){

sqlite3VdbeAddOp3(v, OP_Ne, regElem+i, iJump, regPrev+i);

VdbeCoverage(v);

}else{

sqlite3VdbeAddOp3(v, OP_Eq, regElem+i, addrRepeat, regPrev+i);

VdbeCoverage(v);

}

sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);

sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

}

assert( sqlite3VdbeCurrentAddr(v)==iJump || pParse->db->mallocFailed );

sqlite3VdbeAddOp3(v, OP_Copy, regElem, regPrev, nResultCol-1);

break;

}

case WHERE_DISTINCT_UNIQUE: {

/* nothing to do */

break;

}

default: {

int r1 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp4Int(v, OP_Found, iTab, addrRepeat, regElem, nResultCol);

VdbeCoverage(v);

sqlite3VdbeAddOp3(v, OP_MakeRecord, regElem, nResultCol, r1);

sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iTab, r1, regElem, nResultCol);

sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);

sqlite3ReleaseTempReg(pParse, r1);

iRet = iTab;

break;

}

}

return iRet;

}

/*

** This routine runs after codeDistinct(). It makes necessary

** adjustments to the OP_OpenEphemeral opcode that the codeDistinct()

** routine made use of. This processing must be done separately since

** sometimes codeDistinct is called before the OP_OpenEphemeral is actually

** laid down.

**

** WHERE_DISTINCT_NOOP:

** WHERE_DISTINCT_UNORDERED:

**

** No adjustments necessary. This function is a no-op.

**

** WHERE_DISTINCT_UNIQUE:

**

** The ephemeral table is not needed. So change the

** OP_OpenEphemeral opcode into an OP_Noop.

**

** WHERE_DISTINCT_ORDERED:

**

** The ephemeral table is not needed. But we do need register

** iVal to be initialized to NULL. So change the OP_OpenEphemeral

** into an OP_Null on the iVal register.

*/

static void fixDistinctOpenEph(

Parse *pParse, /* Parsing and code generating context */

int eTnctType, /* WHERE_DISTINCT_* value */

int iVal, /* Value returned by codeDistinct() */

int iOpenEphAddr /* Address of OP_OpenEphemeral instruction for iTab */

){

if( pParse->nErr==0

&& (eTnctType==WHERE_DISTINCT_UNIQUE || eTnctType==WHERE_DISTINCT_ORDERED)

){

Vdbe *v = pParse->pVdbe;

sqlite3VdbeChangeToNoop(v, iOpenEphAddr);

if( sqlite3VdbeGetOp(v, iOpenEphAddr+1)->opcode==OP_Explain ){

sqlite3VdbeChangeToNoop(v, iOpenEphAddr+1);

}

if( eTnctType==WHERE_DISTINCT_ORDERED ){

/* Change the OP_OpenEphemeral to an OP_Null that sets the MEM_Cleared

** bit on the first register of the previous value. This will cause the

** OP_Ne added in codeDistinct() to always fail on the first iteration of

** the loop even if the first row is all NULLs. */

VdbeOp *pOp = sqlite3VdbeGetOp(v, iOpenEphAddr);

pOp->opcode = OP_Null;

pOp->p1 = 1;

pOp->p2 = iVal;

}

}

}

#ifdef SQLITE_ENABLE_SORTER_REFERENCES

/*

** This function is called as part of inner-loop generation for a SELECT

** statement with an ORDER BY that is not optimized by an index. It

** determines the expressions, if any, that the sorter-reference

** optimization should be used for. The sorter-reference optimization

** is used for SELECT queries like:

**