aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/select.c35
-rw-r--r--src/sqliteInt.h42
-rw-r--r--src/treeview.c5
-rw-r--r--src/where.c44
-rw-r--r--src/whereInt.h1
5 files changed, 79 insertions, 48 deletions
diff --git a/src/select.c b/src/select.c
index ff4d9d85c..bde278b43 100644
--- a/src/select.c
+++ b/src/select.c
@@ -105,7 +105,7 @@ Select *sqlite3SelectNew(
ExprList *pGroupBy, /* the GROUP BY clause */
Expr *pHaving, /* the HAVING clause */
ExprList *pOrderBy, /* the ORDER BY clause */
- u16 selFlags, /* Flag parameters, such as SF_Distinct */
+ u32 selFlags, /* Flag parameters, such as SF_Distinct */
Expr *pLimit, /* LIMIT value. NULL means not used */
Expr *pOffset /* OFFSET value. NULL means no offset */
){
@@ -1845,8 +1845,9 @@ static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){
VdbeComment((v, "LIMIT counter"));
if( n==0 ){
sqlite3VdbeGoto(v, iBreak);
- }else if( n>=0 && p->nSelectRow>(u64)n ){
- p->nSelectRow = n;
+ }else if( n>=0 && p->nSelectRow>sqlite3LogEst((u64)n) ){
+ p->nSelectRow = sqlite3LogEst((u64)n);
+ p->selFlags |= SF_FixedLimit;
}
}else{
sqlite3ExprCode(pParse, p->pLimit, iLimit);
@@ -2287,12 +2288,12 @@ static int multiSelect(
testcase( rc!=SQLITE_OK );
pDelete = p->pPrior;
p->pPrior = pPrior;
- p->nSelectRow += pPrior->nSelectRow;
+ p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
if( pPrior->pLimit
&& sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)
- && nLimit>0 && p->nSelectRow > (u64)nLimit
+ && nLimit>0 && p->nSelectRow > sqlite3LogEst((u64)nLimit)
){
- p->nSelectRow = nLimit;
+ p->nSelectRow = sqlite3LogEst((u64)nLimit);
}
if( addr ){
sqlite3VdbeJumpHere(v, addr);
@@ -2364,7 +2365,9 @@ static int multiSelect(
pDelete = p->pPrior;
p->pPrior = pPrior;
p->pOrderBy = 0;
- if( p->op==TK_UNION ) p->nSelectRow += pPrior->nSelectRow;
+ if( p->op==TK_UNION ){
+ p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
+ }
sqlite3ExprDelete(db, p->pLimit);
p->pLimit = pLimit;
p->pOffset = pOffset;
@@ -3001,7 +3004,7 @@ static int multiSelectOrderBy(
addrEofA_noB = sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, labelEnd);
VdbeCoverage(v);
sqlite3VdbeGoto(v, addrEofA);
- p->nSelectRow += pPrior->nSelectRow;
+ p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
}
/* Generate a subroutine to run when the results from select B
@@ -4987,7 +4990,7 @@ int sqlite3Select(
sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
sqlite3Select(pParse, pSub, &dest);
- pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
+ pItem->pTab->nRowLogEst = pSub->nSelectRow;
pItem->fg.viaCoroutine = 1;
pItem->regResult = dest.iSdst;
sqlite3VdbeEndCoroutine(v, pItem->regReturn);
@@ -5018,7 +5021,7 @@ int sqlite3Select(
sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
sqlite3Select(pParse, pSub, &dest);
- pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
+ pItem->pTab->nRowLogEst = pSub->nSelectRow;
if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
VdbeComment((v, "end %s", pItem->pTab->zName));
@@ -5101,7 +5104,7 @@ int sqlite3Select(
/* Set the limiter.
*/
iEnd = sqlite3VdbeMakeLabel(v);
- p->nSelectRow = LARGEST_INT64;
+ p->nSelectRow = 320; /* 4 billion rows */
computeLimitRegisters(pParse, p, iEnd);
if( p->iLimit==0 && sSort.addrSortIndex>=0 ){
sqlite3VdbeChangeOpcode(v, sSort.addrSortIndex, OP_SorterOpen);
@@ -5125,10 +5128,12 @@ int sqlite3Select(
if( !isAgg && pGroupBy==0 ){
/* No aggregate functions and no GROUP BY clause */
u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
+ assert( WHERE_USE_LIMIT==SF_FixedLimit );
+ wctrlFlags |= p->selFlags & SF_FixedLimit;
/* Begin the database scan. */
pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
- p->pEList, wctrlFlags, 0);
+ p->pEList, wctrlFlags, p->nSelectRow);
if( pWInfo==0 ) goto select_end;
if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
@@ -5188,9 +5193,11 @@ int sqlite3Select(
for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){
pItem->u.x.iAlias = 0;
}
- if( p->nSelectRow>100 ) p->nSelectRow = 100;
+ assert( 66==sqlite3LogEst(100) );
+ if( p->nSelectRow>66 ) p->nSelectRow = 66;
}else{
- p->nSelectRow = 1;
+ assert( 0==sqlite3LogEst(1) );
+ p->nSelectRow = 0;
}
/* If there is both a GROUP BY and an ORDER BY clause and they are
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 2ea5f5791..7924ed9dc 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2442,6 +2442,7 @@ struct SrcList {
#define WHERE_SORTBYGROUP 0x0800 /* Support sqlite3WhereIsSorted() */
#define WHERE_REOPEN_IDX 0x1000 /* Try to use OP_ReopenIdx */
#define WHERE_ONEPASS_MULTIROW 0x2000 /* ONEPASS is ok with multiple rows */
+#define WHERE_USE_LIMIT 0x4000 /* There is a constant LIMIT clause */
/* Allowed return values from sqlite3WhereIsDistinct()
*/
@@ -2520,13 +2521,13 @@ struct NameContext {
struct Select {
ExprList *pEList; /* The fields of the result */
u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
- u16 selFlags; /* Various SF_* values */
+ LogEst nSelectRow; /* Estimated number of result rows */
+ u32 selFlags; /* Various SF_* values */
int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */
#if SELECTTRACE_ENABLED
char zSelName[12]; /* Symbolic name of this SELECT use for debugging */
#endif
int addrOpenEphm[2]; /* OP_OpenEphem opcodes related to this select */
- u64 nSelectRow; /* Estimated number of result rows */
SrcList *pSrc; /* The FROM clause */
Expr *pWhere; /* The WHERE clause */
ExprList *pGroupBy; /* The GROUP BY clause */
@@ -2543,22 +2544,23 @@ struct Select {
** Allowed values for Select.selFlags. The "SF" prefix stands for
** "Select Flag".
*/
-#define SF_Distinct 0x0001 /* Output should be DISTINCT */
-#define SF_All 0x0002 /* Includes the ALL keyword */
-#define SF_Resolved 0x0004 /* Identifiers have been resolved */
-#define SF_Aggregate 0x0008 /* Contains aggregate functions */
-#define SF_UsesEphemeral 0x0010 /* Uses the OpenEphemeral opcode */
-#define SF_Expanded 0x0020 /* sqlite3SelectExpand() called on this */
-#define SF_HasTypeInfo 0x0040 /* FROM subqueries have Table metadata */
-#define SF_Compound 0x0080 /* Part of a compound query */
-#define SF_Values 0x0100 /* Synthesized from VALUES clause */
-#define SF_MultiValue 0x0200 /* Single VALUES term with multiple rows */
-#define SF_NestedFrom 0x0400 /* Part of a parenthesized FROM clause */
-#define SF_MaybeConvert 0x0800 /* Need convertCompoundSelectToSubquery() */
-#define SF_MinMaxAgg 0x1000 /* Aggregate containing min() or max() */
-#define SF_Recursive 0x2000 /* The recursive part of a recursive CTE */
-#define SF_Converted 0x4000 /* By convertCompoundSelectToSubquery() */
-#define SF_IncludeHidden 0x8000 /* Include hidden columns in output */
+#define SF_Distinct 0x00001 /* Output should be DISTINCT */
+#define SF_All 0x00002 /* Includes the ALL keyword */
+#define SF_Resolved 0x00004 /* Identifiers have been resolved */
+#define SF_Aggregate 0x00008 /* Contains aggregate functions */
+#define SF_UsesEphemeral 0x00010 /* Uses the OpenEphemeral opcode */
+#define SF_Expanded 0x00020 /* sqlite3SelectExpand() called on this */
+#define SF_HasTypeInfo 0x00040 /* FROM subqueries have Table metadata */
+#define SF_Compound 0x00080 /* Part of a compound query */
+#define SF_Values 0x00100 /* Synthesized from VALUES clause */
+#define SF_MultiValue 0x00200 /* Single VALUES term with multiple rows */
+#define SF_NestedFrom 0x00400 /* Part of a parenthesized FROM clause */
+#define SF_MaybeConvert 0x00800 /* Need convertCompoundSelectToSubquery() */
+#define SF_MinMaxAgg 0x01000 /* Aggregate containing min() or max() */
+#define SF_Recursive 0x02000 /* The recursive part of a recursive CTE */
+#define SF_FixedLimit 0x04000 /* nSelectRow set by a constant LIMIT */
+#define SF_Converted 0x08000 /* By convertCompoundSelectToSubquery() */
+#define SF_IncludeHidden 0x10000 /* Include hidden columns in output */
/*
@@ -3489,7 +3491,7 @@ Index *sqlite3CreateIndex(Parse*,Token*,Token*,SrcList*,ExprList*,int,Token*,
void sqlite3DropIndex(Parse*, SrcList*, int);
int sqlite3Select(Parse*, Select*, SelectDest*);
Select *sqlite3SelectNew(Parse*,ExprList*,SrcList*,Expr*,ExprList*,
- Expr*,ExprList*,u16,Expr*,Expr*);
+ Expr*,ExprList*,u32,Expr*,Expr*);
void sqlite3SelectDelete(sqlite3*, Select*);
Table *sqlite3SrcListLookup(Parse*, SrcList*);
int sqlite3IsReadOnly(Parse*, Table*, int);
@@ -3501,7 +3503,7 @@ void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
void sqlite3WhereEnd(WhereInfo*);
-u64 sqlite3WhereOutputRowCount(WhereInfo*);
+LogEst sqlite3WhereOutputRowCount(WhereInfo*);
int sqlite3WhereIsDistinct(WhereInfo*);
int sqlite3WhereIsOrdered(WhereInfo*);
int sqlite3WhereIsSorted(WhereInfo*);
diff --git a/src/treeview.c b/src/treeview.c
index 298580431..ff3b4be5a 100644
--- a/src/treeview.c
+++ b/src/treeview.c
@@ -132,9 +132,10 @@ void sqlite3TreeViewSelect(TreeView *pView, const Select *p, u8 moreToFollow){
sqlite3TreeViewPush(pView, 1);
}
do{
- sqlite3TreeViewLine(pView, "SELECT%s%s (0x%p) selFlags=0x%x",
+ sqlite3TreeViewLine(pView, "SELECT%s%s (0x%p) selFlags=0x%x nSelectRow=%d",
((p->selFlags & SF_Distinct) ? " DISTINCT" : ""),
- ((p->selFlags & SF_Aggregate) ? " agg_flag" : ""), p, p->selFlags
+ ((p->selFlags & SF_Aggregate) ? " agg_flag" : ""), p, p->selFlags,
+ (int)p->nSelectRow
);
if( cnt++ ) sqlite3TreeViewPop(pView);
if( p->pPrior ){
diff --git a/src/where.c b/src/where.c
index ca9e4a6f9..addd50674 100644
--- a/src/where.c
+++ b/src/where.c
@@ -31,8 +31,8 @@ static int whereLoopResize(sqlite3*, WhereLoop*, int);
/*
** Return the estimated number of output rows from a WHERE clause
*/
-u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
- return sqlite3LogEstToInt(pWInfo->nRowOut);
+LogEst sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
+ return pWInfo->nRowOut;
}
/*
@@ -3438,6 +3438,7 @@ static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
** order.
*/
static LogEst whereSortingCost(
+ WhereInfo *pWInfo,
LogEst nRow,
int nOrderBy,
int nSorted
@@ -3458,7 +3459,15 @@ static LogEst whereSortingCost(
LogEst rScale, rSortCost;
assert( nOrderBy>0 && 66==sqlite3LogEst(100) );
rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66;
- rSortCost = nRow + estLog(nRow) + rScale + 16;
+ rSortCost = nRow + rScale + 16;
+
+ /* Multiple by log(M) where M is the number of output rows.
+ ** Use the LIMIT for M if it is smaller */
+ if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 ){
+ LogEst m = sqlite3LogEst(pWInfo->iLimit);
+ if( m<nRow ) nRow = m;
+ }
+ rSortCost += estLog(nRow);
return rSortCost;
}
@@ -3592,7 +3601,7 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
if( isOrdered>=0 && isOrdered<nOrderBy ){
if( aSortCost[isOrdered]==0 ){
aSortCost[isOrdered] = whereSortingCost(
- nRowEst, nOrderBy, isOrdered
+ pWInfo, nRowEst, nOrderBy, isOrdered
);
}
rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]);
@@ -3991,7 +4000,8 @@ WhereInfo *sqlite3WhereBegin(
ExprList *pOrderBy, /* An ORDER BY (or GROUP BY) clause, or NULL */
ExprList *pResultSet, /* Result set of the query */
u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
- int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */
+ int iAuxArg /* If WHERE_ONETABLE_ONLY is set, index cursor number,
+ ** If WHERE_USE_LIMIT, then the limit amount */
){
int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
int nTabList; /* Number of elements in pTabList */
@@ -4012,6 +4022,10 @@ WhereInfo *sqlite3WhereBegin(
&& (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
));
+ /* Only one of WHERE_ONETABLE_ONLY or WHERE_USE_LIMIT */
+ assert( (wctrlFlags & WHERE_ONETABLE_ONLY)==0
+ || (wctrlFlags & WHERE_USE_LIMIT)==0 );
+
/* Variable initialization */
db = pParse->db;
memset(&sWLB, 0, sizeof(sWLB));
@@ -4065,6 +4079,7 @@ WhereInfo *sqlite3WhereBegin(
pWInfo->pResultSet = pResultSet;
pWInfo->iBreak = pWInfo->iContinue = sqlite3VdbeMakeLabel(v);
pWInfo->wctrlFlags = wctrlFlags;
+ pWInfo->iLimit = iAuxArg;
pWInfo->savedNQueryLoop = pParse->nQueryLoop;
assert( pWInfo->eOnePass==ONEPASS_OFF ); /* ONEPASS defaults to OFF */
pMaskSet = &pWInfo->sMaskSet;
@@ -4145,9 +4160,14 @@ WhereInfo *sqlite3WhereBegin(
}
/* Construct the WhereLoop objects */
- WHERETRACE(0xffff,("*** Optimizer Start *** (wctrlFlags: 0x%x)\n",
- wctrlFlags));
#if defined(WHERETRACE_ENABLED)
+ if( sqlite3WhereTrace & 0xffff ){
+ sqlite3DebugPrintf("*** Optimizer Start *** (wctrlFlags: 0x%x",wctrlFlags);
+ if( wctrlFlags & WHERE_USE_LIMIT ){
+ sqlite3DebugPrintf(", limit: %d", iAuxArg);
+ }
+ sqlite3DebugPrintf(")\n");
+ }
if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
int i;
for(i=0; i<sWLB.pWC->nTerm; i++){
@@ -4330,8 +4350,8 @@ WhereInfo *sqlite3WhereBegin(
Index *pIx = pLoop->u.btree.pIndex;
int iIndexCur;
int op = OP_OpenRead;
- /* iIdxCur is always set if to a positive value if ONEPASS is possible */
- assert( iIdxCur!=0 || (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 );
+ /* iAuxArg is always set if to a positive value if ONEPASS is possible */
+ assert( iAuxArg!=0 || (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 );
if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIx)
&& (wctrlFlags & WHERE_ONETABLE_ONLY)!=0
){
@@ -4341,7 +4361,7 @@ WhereInfo *sqlite3WhereBegin(
op = 0;
}else if( pWInfo->eOnePass!=ONEPASS_OFF ){
Index *pJ = pTabItem->pTab->pIndex;
- iIndexCur = iIdxCur;
+ iIndexCur = iAuxArg;
assert( wctrlFlags & WHERE_ONEPASS_DESIRED );
while( ALWAYS(pJ) && pJ!=pIx ){
iIndexCur++;
@@ -4349,8 +4369,8 @@ WhereInfo *sqlite3WhereBegin(
}
op = OP_OpenWrite;
pWInfo->aiCurOnePass[1] = iIndexCur;
- }else if( iIdxCur && (wctrlFlags & WHERE_ONETABLE_ONLY)!=0 ){
- iIndexCur = iIdxCur;
+ }else if( iAuxArg && (wctrlFlags & WHERE_ONETABLE_ONLY)!=0 ){
+ iIndexCur = iAuxArg;
if( wctrlFlags & WHERE_REOPEN_IDX ) op = OP_ReopenIdx;
}else{
iIndexCur = pParse->nTab++;
diff --git a/src/whereInt.h b/src/whereInt.h
index 1a189980e..eb6ca326f 100644
--- a/src/whereInt.h
+++ b/src/whereInt.h
@@ -412,6 +412,7 @@ struct WhereInfo {
WhereLoop *pLoops; /* List of all WhereLoop objects */
Bitmask revMask; /* Mask of ORDER BY terms that need reversing */
LogEst nRowOut; /* Estimated number of output rows */
+ LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */
u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */
i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */
u8 sorted; /* True if really sorted (not just grouped) */
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-21 15:51:11 +0000