From 781def29c7e5fec282f4b69d94a4508b93e4891f Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 22 Jan 2014 13:35:53 +0000 Subject: [PATCH] Add new SelectDest codes, SRT_Queue and SRT_DistQueue in anticipation of adding ORDER BY support on recursive queries. Factor out the recursive query code generator into a separate procedure. FossilOrigin-Name: 3eb5f9f8d6ac1ee145cb4119087c516f66fe1456 --- manifest | 16 ++-- manifest.uuid | 2 +- src/select.c | 245 +++++++++++++++++++++++++++++++----------------- src/sqliteInt.h | 26 +++-- 4 files changed, 184 insertions(+), 105 deletions(-) diff --git a/manifest b/manifest index bd186f12e4..1f03409943 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sa\stypo\sin\sa\scomment.\sNo\schanges\sto\scode\sor\stests. -D 2014-01-22T10:22:25.214 +C Add\snew\sSelectDest\scodes,\sSRT_Queue\sand\sSRT_DistQueue\sin\santicipation\sof\sadding\nORDER\sBY\ssupport\son\srecursive\squeries.\s\sFactor\sout\sthe\srecursive\squery\ncode\sgenerator\sinto\sa\sseparate\sprocedure. +D 2014-01-22T13:35:53.476 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 2ef13430cd359f7b361bb863504e227b25cc7f81 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -219,12 +219,12 @@ F src/printf.c 85d07756e45d7496d19439dcae3e6e9e0090f269 F src/random.c d10c1f85b6709ca97278428fd5db5bbb9c74eece F src/resolve.c 7eda9097b29fcf3d2b42fdc17d1de672134e09b6 F src/rowset.c 64655f1a627c9c212d9ab497899e7424a34222e0 -F src/select.c c2021c75911362ac2fa4d9390741c889101bca65 +F src/select.c 11c02c82a6f3cb8a491452fc7474a568a48c64ef F src/shell.c 24722d24d4ea8ca93db35e44db7308de786767ca F src/sqlite.h.in eed7f7d66a60daaa7b4a597dcd9bad87aad9611b F src/sqlite3.rc 11094cc6a157a028b301a9f06b3d03089ea37c3e F src/sqlite3ext.h 886f5a34de171002ad46fae8c36a7d8051c190fc -F src/sqliteInt.h 73074ee596a978bc4431746c417527d03a3bb510 +F src/sqliteInt.h 16c73326604e5603c3c10c97ac1e63473590d4ff F src/sqliteLimit.h 164b0e6749d31e0daa1a4589a169d31c0dec7b3d F src/status.c 7ac05a5c7017d0b9f0b4bcd701228b784f987158 F src/table.c 2cd62736f845d82200acfa1287e33feb3c15d62e @@ -1152,7 +1152,7 @@ F tool/vdbe-compress.tcl 0cf56e9263a152b84da86e75a5c0cdcdb7a47891 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh d1a6de74685f360ab718efda6265994b99bbea01 F tool/win/sqlite.vsix 030f3eeaf2cb811a3692ab9c14d021a75ce41fff -P 5e6c4a55f6df30da9dbaa8170f3223613cc86f65 -R d64224deb212538f78a2f080c518a12f -U dan -Z 6bf281c516c82d71cce682fb71803759 +P cceacc0e79c4e54682daddf2056c6bb8e88d9484 +R 3e53ba84b5d9e416a6e5f351b0fd4313 +U drh +Z aa06559c4dc503939fd80ca5aa152df9 diff --git a/manifest.uuid b/manifest.uuid index bcd373500c..2b7addbf9a 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -cceacc0e79c4e54682daddf2056c6bb8e88d9484 \ No newline at end of file +3eb5f9f8d6ac1ee145cb4119087c516f66fe1456 \ No newline at end of file diff --git a/src/select.c b/src/select.c index a6eee2735d..0152db8b25 100644 --- a/src/select.c +++ b/src/select.c @@ -581,8 +581,10 @@ static void selectInnerLoop( pDest->iSdst = pParse->nMem+1; pDest->nSdst = nResultCol; pParse->nMem += nResultCol; + if( eDest==SRT_Queue ) pParse->nMem++; }else{ assert( pDest->nSdst==nResultCol ); + assert( eDest!=SRT_Queue ); } regResult = pDest->iSdst; if( srcTab>=0 ){ @@ -662,10 +664,30 @@ static void selectInnerLoop( ** table iParm. */ #ifndef SQLITE_OMIT_COMPOUND_SELECT +#ifndef SQLITE_OMIT_CTE + case SRT_Queue: { + sqlite3VdbeAddOp2(v, OP_Sequence, iParm, regResult+nResultCol); + nResultCol++; + /* Fall through into SRT_Union */ + } + case SRT_DistQueue: +#endif /* SQLITE_OMIT_CTE */ case SRT_Union: { int r1; r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); +#ifndef SQLITE_OMIT_CTE + if( eDest==SRT_DistQueue ){ + /* If the destination is DistQueue, then cursor (iParm+1) is open + ** on a second ephemeral index that holds all values every previously + ** added to the queue. Only add this new value if it has never before + ** been added */ + int addr = sqlite3VdbeCurrentAddr(v) + 3; + sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0); + sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1); + assert( pOrderBy==0 ); + } +#endif /* SQLITE_OMIT_CTE */ sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); sqlite3ReleaseTempReg(pParse, r1); break; @@ -679,7 +701,7 @@ static void selectInnerLoop( sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol); break; } -#endif +#endif /* SQLITE_OMIT_COMPOUND_SELECT */ /* Store the result as data using a unique key. */ @@ -1676,7 +1698,139 @@ static CollSeq *multiSelectCollSeq(Parse *pParse, Select *p, int iCol){ } #endif /* SQLITE_OMIT_COMPOUND_SELECT */ -/* Forward reference */ +#ifndef SQLITE_OMIT_CTE +/* +** This routine generates VDBE code to compute the content of a WITH RECURSIVE +** query of the form: +** +** AS ( UNION [ALL] ) +** \___________/ \_______________/ +** p->pPrior p +** +** +** There is exactly one reference to the recursive-table in the FROM clause +** of recursive-query, marked with the SrcList->a[].isRecursive flag. +** +** The setup-query runs once to generate an initial set of rows that go +** into a Queue table. Rows are extracted from the Queue table one by +** one. Each row extracted from iQueue is output to pDest. Then the single +** extracted row (now the iCurrent table) becomes the content of the +** recursive-table and recursive-query is run. The output of the recursive-query +** is added back into the Queue table. Then another row is extracted from Queue +** and the iteration continues until the Queue table is empty. +** +** If the compound query operator is UNION then no duplicate rows are ever +** inserted into the Queue table. The iDistinct table keeps a copy of all rows +** that have ever been inserted into Queue and causes duplicates to be +** discarded. If the operator is UNION ALL, then duplicates are allowed. +** +** If the query has an ORDER BY, then entries in the Queue table are kept in +** ORDER BY order and the first entry is extracted for each cycle. Without +** an ORDER BY, the Queue table is just a FIFO. +** +** If a LIMIT clause is provided, then the iteration stops after LIMIT rows +** have been output to pDest. A LIMIT of zero means to output no rows and a +** negative LIMIT means to output all rows. If there is also an OFFSET clause +** with a positive value, then the first OFFSET outputs are discarded rather +** than being sent to pDest. The LIMIT count does not begin until after OFFSET +** rows have been skipped. +*/ +static void generateWithRecursiveQuery( + Parse *pParse, /* Parsing context */ + Select *p, /* The recursive SELECT to be coded */ + SelectDest *pDest /* What to do with query results */ +){ + SrcList *pSrc = p->pSrc; /* The FROM clause of the recursive query */ + int nCol = p->pEList->nExpr; /* Number of columns in the recursive table */ + Vdbe *v = pParse->pVdbe; /* The prepared statement under construction */ + Select *pSetup = p->pPrior; /* The setup query */ + int addrTop; /* Top of the loop */ + int addrCont, addrBreak; /* CONTINUE and BREAK addresses */ + int iCurrent; /* The Current table */ + int regCurrent; /* Register holding Current table */ + int iQueue; /* The Queue table */ + int iDistinct = 0; /* To ensure unique results if UNION */ + int eDest = SRT_Table; /* How to write to Queue */ + SelectDest destQueue; /* SelectDest targetting the Queue table */ + int i; /* Loop counter */ + int rc; /* Result code */ + + /* Obtain authorization to do a recursive query */ + if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return; + addrBreak = sqlite3VdbeMakeLabel(v); + addrCont = sqlite3VdbeMakeLabel(v); + + + /* Check that there is no ORDER BY or LIMIT clause. Neither of these + ** are currently supported on recursive queries. + */ + assert( p->pOffset==0 || p->pLimit ); + if( p->pOrderBy || p->pLimit ){ + sqlite3ErrorMsg(pParse, "%s in a recursive query", + p->pOrderBy ? "ORDER BY" : "LIMIT" + ); + return; + } + + /* Locate the cursor number of the Current table */ + for(i=0; ALWAYS(inSrc); i++){ + if( pSrc->a[i].isRecursive ){ + iCurrent = pSrc->a[i].iCursor; + break; + } + } + + /* Allocate cursors for Queue and Distinct. The cursor number for + ** the Distinct table must be exactly one greater than Queue in order + ** for the SRT_DistTable destination to work. */ + iQueue = pParse->nTab++; + if( p->op==TK_UNION ){ + assert( SRT_Table+1==SRT_DistTable ); + assert( SRT_Queue+1==SRT_DistQueue ); + eDest++; + iDistinct = pParse->nTab++; + } + sqlite3SelectDestInit(&destQueue, eDest, iQueue); + + /* Allocate cursors for Current, Queue, and Distinct. */ + regCurrent = ++pParse->nMem; + sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol); + sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); + if( iDistinct ){ + p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); + p->selFlags |= SF_UsesEphemeral; + } + + /* Store the results of the setup-query in Queue. */ + rc = sqlite3Select(pParse, pSetup, &destQueue); + if( rc ) return; + + /* Find the next row in the Queue and output that row */ + addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); + selectInnerLoop(pParse, p, p->pEList, iQueue, + 0, 0, pDest, addrCont, addrBreak); + sqlite3VdbeResolveLabel(v, addrCont); + + /* Transfer the next row in Queue over to Current */ + sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ + sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); + sqlite3VdbeAddOp1(v, OP_Delete, iQueue); + + /* Execute the recursive SELECT taking the single row in Current as + ** the value for the recursive-table. Store the results in the Queue. + */ + p->pPrior = 0; + sqlite3Select(pParse, p, &destQueue); + assert( p->pPrior==0 ); + p->pPrior = pSetup; + + /* Keep running the loop until the Queue is empty */ + sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); + sqlite3VdbeResolveLabel(v, addrBreak); +} +#endif + +/* Forward references */ static int multiSelectOrderBy( Parse *pParse, /* Parsing context */ Select *p, /* The right-most of SELECTs to be coded */ @@ -1784,92 +1938,7 @@ static int multiSelect( #ifndef SQLITE_OMIT_CTE if( p->selFlags & SF_Recursive ){ - SrcList *pSrc = p->pSrc; /* The FROM clause of the recursive query */ - int nCol = p->pEList->nExpr; /* Number of columns in the CTE */ - int addrTop; /* Top of the loop */ - int addrCont, addrBreak; /* CONTINUE and BREAK addresses */ - int iCurrent; /* The Current table */ - int regCurrent; /* Register holding Current table */ - int iQueue; /* The Queue table */ - int iDistinct; /* To ensure unique results if UNION */ - int eDest; /* How to write to Queue */ - SelectDest destQueue; /* SelectDest targetting the Queue table */ - int i; /* Loop counter */ - - /* Check that there is no ORDER BY or LIMIT clause. Neither of these - ** are currently supported on recursive queries. - */ - assert( p->pOffset==0 || p->pLimit ); - if( p->pOrderBy || p->pLimit ){ - sqlite3ErrorMsg(pParse, "%s in a recursive query", - p->pOrderBy ? "ORDER BY" : "LIMIT" - ); - goto multi_select_end; - } - - if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ){ - goto multi_select_end; - } - addrBreak = sqlite3VdbeMakeLabel(v); - addrCont = sqlite3VdbeMakeLabel(v); - - /* Locate the cursor number of the Current table */ - for(i=0; ALWAYS(inSrc); i++){ - if( pSrc->a[i].isRecursive ){ - iCurrent = pSrc->a[i].iCursor; - break; - } - } - - /* Allocate cursors for Queue and Distinct. The cursor number for - ** the Distinct table must be exactly one greater than Queue in order - ** for the SRT_DistTable destination to work. */ - iQueue = pParse->nTab++; - if( p->op==TK_UNION ){ - eDest = SRT_DistTable; - iDistinct = pParse->nTab++; - }else{ - eDest = SRT_Table; - iDistinct = 0; - } - sqlite3SelectDestInit(&destQueue, eDest, iQueue); - - /* Allocate cursors for Current, Queue, and iDistinct. */ - regCurrent = ++pParse->nMem; - sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol); - sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); - if( iDistinct ){ - p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); - p->selFlags |= SF_UsesEphemeral; - } - - /* Store the results of the initial SELECT in Queue. */ - rc = sqlite3Select(pParse, pPrior, &destQueue); - if( rc ) goto multi_select_end; - - /* Find the next row in the Queue and output that row */ - addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); - selectInnerLoop(pParse, p, p->pEList, iQueue, - 0, 0, &dest, addrCont, addrBreak); - sqlite3VdbeResolveLabel(v, addrCont); - - /* Transfer the next row in Queue over to Current */ - sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ - sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); - sqlite3VdbeAddOp1(v, OP_Delete, iQueue); - - /* Execute the recursive SELECT taking the single row in Current as - ** the value for the CTE. Store the results in the Queue. - */ - p->pPrior = 0; - rc = sqlite3Select(pParse, p, &destQueue); - assert( p->pPrior==0 ); - p->pPrior = pPrior; - if( rc ) goto multi_select_end; - - /* Keep running the loop until the Queue is empty */ - sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); - sqlite3VdbeResolveLabel(v, addrBreak); + generateWithRecursiveQuery(pParse, p, &dest); }else #endif diff --git a/src/sqliteInt.h b/src/sqliteInt.h index f2c08ad296..ac48291d80 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -2199,10 +2199,6 @@ struct Select { ** Apply the affinity pDest->affSdst before storing ** results. Used to implement "IN (SELECT ...)". ** -** SRT_Table Store results in temporary table pDest->iSDParm. -** This is like SRT_EphemTab except that the table -** is assumed to already be open. -** ** SRT_EphemTab Create an temporary table pDest->iSDParm and store ** the result there. The cursor is left open after ** returning. This is like SRT_Table except that @@ -2215,10 +2211,22 @@ struct Select { ** and the result row is stored in pDest->nDest registers ** starting with pDest->iSdst. ** +** SRT_Table Store results in temporary table pDest->iSDParm. +** This is like SRT_EphemTab except that the table +** is assumed to already be open. +** ** SRT_DistTable Store results in a temporary table pDest->iSDParm. ** But also use temporary table pDest->iSDParm+1 as ** a record of all prior results and ignore any duplicate ** rows. Name means: "Distinct Table". +** +** SRT_Queue Store results in priority queue pDest->iSDParm (really +** an index). Append a sequence number so that all entries +** are distinct. +** +** SRT_DistQueue Store results in priority queue pDest->iSDParm only if +** the same record has never been stored before. The +** index at pDest->iSDParm+1 hold all prior stores. */ #define SRT_Union 1 /* Store result as keys in an index */ #define SRT_Except 2 /* Remove result from a UNION index */ @@ -2231,10 +2239,12 @@ struct Select { #define SRT_Output 5 /* Output each row of result */ #define SRT_Mem 6 /* Store result in a memory cell */ #define SRT_Set 7 /* Store results as keys in an index */ -#define SRT_Table 8 /* Store result as data with an automatic rowid */ -#define SRT_EphemTab 9 /* Create transient tab and store like SRT_Table */ -#define SRT_Coroutine 10 /* Generate a single row of result */ -#define SRT_DistTable 11 /* Like SRT_TABLE, but unique results only */ +#define SRT_EphemTab 8 /* Create transient tab and store like SRT_Table */ +#define SRT_Coroutine 9 /* Generate a single row of result */ +#define SRT_Table 10 /* Store result as data with an automatic rowid */ +#define SRT_DistTable 11 /* Like SRT_Table, but unique results only */ +#define SRT_Queue 12 /* Store result in an queue */ +#define SRT_DistQueue 13 /* Like SRT_Queue, but unique results only */ /* ** An instance of this object describes where to put of the results of -- 2.47.2