Initial implementation of the unlikely() SQL function used as a hint to

the query planner.

FossilOrigin-Name: 036fc37a034093a4c6fc190633bd41c2b7230d77

5 files changed, 102 insertions, 18 deletions

diff --git a/src/expr.c b/src/expr.c
index 6587ee1f7..ece029384 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -89,8 +89,16 @@ Expr *sqlite3ExprAddCollateString(Parse *pParse, Expr *pExpr, const char *zC){
 ** an expression.
 */
 Expr *sqlite3ExprSkipCollate(Expr *pExpr){
-  while( pExpr && (pExpr->op==TK_COLLATE || pExpr->op==TK_AS) ){
-    pExpr = pExpr->pLeft;
+  while( pExpr ){
+    if( pExpr->op==TK_COLLATE || pExpr->op==TK_AS ){
+      pExpr = pExpr->pLeft;
+    }else if( ExprHasAnyProperty(pExpr, EP_Hint) ){
+      assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
+      assert( pExpr->x.pList->nExpr>0 );
+      pExpr = pExpr->x.pList->a[0].pExpr;
+    }else{
+      break;
+    }
   }
   return pExpr;
 }
@@ -2649,6 +2657,14 @@ int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){
         break;
       }
 
+      /* The UNLIKELY() function is a no-op.  The result is the value
+      ** of the first argument.
+      */
+      if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
+        assert( nFarg>=1 );
+        sqlite3ExprCode(pParse, pFarg->a[0].pExpr, target);
+        break;
+      }
 
       if( pFarg ){
         r1 = sqlite3GetTempRange(pParse, nFarg);
diff --git a/src/func.c b/src/func.c
index 64e33640b..26cbfbfb0 100644
--- a/src/func.c
+++ b/src/func.c
@@ -418,14 +418,14 @@ static void lowerFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 }
 
 /*
-** The COALESCE() and IFNULL() functions are implemented as VDBE code so
-** that unused argument values do not have to be computed.  However, we
-** still need some kind of function implementation for this routines in
-** the function table.  That function implementation will never be called
-** so it doesn't matter what the implementation is.  We might as well use
-** the "version()" function as a substitute.
+** Some functions like COALESCE() and IFNULL() and UNLIKELY() are implemented
+** as VDBE code so that unused argument values do not have to be computed.
+** However, we still need some kind of function implementation for this
+** routines in the function table.  The noopFunc macro provides this.
+** noopFunc will never be called so it doesn't matter what the implementation
+** is.  We might as well use the "version()" function as a substitute.
 */
-#define ifnullFunc versionFunc   /* Substitute function - never called */
+#define noopFunc versionFunc   /* Substitute function - never called */
 
 /*
 ** Implementation of random().  Return a random integer.  
@@ -1659,9 +1659,11 @@ void sqlite3RegisterGlobalFunctions(void){
     FUNCTION(lower,              1, 0, 0, lowerFunc        ),
     FUNCTION(coalesce,           1, 0, 0, 0                ),
     FUNCTION(coalesce,           0, 0, 0, 0                ),
-    FUNCTION2(coalesce,         -1, 0, 0, ifnullFunc,  SQLITE_FUNC_COALESCE),
+    FUNCTION2(coalesce,         -1, 0, 0, noopFunc,  SQLITE_FUNC_COALESCE),
     FUNCTION(hex,                1, 0, 0, hexFunc          ),
-    FUNCTION2(ifnull,            2, 0, 0, ifnullFunc,  SQLITE_FUNC_COALESCE),
+    FUNCTION2(ifnull,            2, 0, 0, noopFunc,  SQLITE_FUNC_COALESCE),
+    FUNCTION2(unlikely,          1, 0, 0, noopFunc,  SQLITE_FUNC_UNLIKELY),
+    FUNCTION2(unlikely,          2, 0, 0, noopFunc,  SQLITE_FUNC_UNLIKELY),
     FUNCTION(random,             0, 0, 0, randomFunc       ),
     FUNCTION(randomblob,         1, 0, 0, randomBlob       ),
     FUNCTION(nullif,             2, 0, 1, nullifFunc       ),
diff --git a/src/resolve.c b/src/resolve.c
index 43a3870e2..cb86a83ee 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -570,6 +570,18 @@ static void notValidCheckConstraint(
 # define notValidCheckConstraint(P,N,M)
 #endif
 
+/*
+** Expression p should encode a floating point value between 1.0 and 0.0.
+** Return 1024 times this value.  Or return -1 if p is not a floating point
+** value between 1.0 and 0.0.
+*/
+static int exprProbability(Expr *p){
+  double r = -1.0;
+  if( p->op!=TK_FLOAT ) return -1;
+  sqlite3AtoF(p->u.zToken, &r, sqlite3Strlen30(p->u.zToken), SQLITE_UTF8);
+  if( r<0.0 || r>1.0 ) return -1;
+  return (int)(r*1000.0);
+}
 
 /*
 ** This routine is callback for sqlite3WalkExpr().
@@ -683,6 +695,19 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){
         }
       }else{
         is_agg = pDef->xFunc==0;
+        if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
+          ExprSetProperty(pExpr, EP_Hint);
+          if( n==2 ){
+            pExpr->iTable = exprProbability(pList->a[1].pExpr);
+            if( pExpr->iTable<0 ){
+              sqlite3ErrorMsg(pParse, "second parameter to unlikely() must be "
+                                      "between 0.0 and 1.0");
+              pNC->nErr++;
+            }
+          }else{
+            pExpr->iTable = 100;
+          }             
+        }
       }
 #ifndef SQLITE_OMIT_AUTHORIZATION
       if( pDef ){
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 6b3fbe851..d8ed4eb04 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1752,7 +1752,8 @@ struct Expr {
 #endif
   int iTable;            /* TK_COLUMN: cursor number of table holding column
                          ** TK_REGISTER: register number
-                         ** TK_TRIGGER: 1 -> new, 0 -> old */
+                         ** TK_TRIGGER: 1 -> new, 0 -> old
+                         ** EP_Hint:  1000 times likelihood */
   ynVar iColumn;         /* TK_COLUMN: column index.  -1 for rowid.
                          ** TK_VARIABLE: variable number (always >= 1). */
   i16 iAgg;              /* Which entry in pAggInfo->aCol[] or ->aFunc[] */
@@ -1780,7 +1781,7 @@ struct Expr {
 #define EP_FixedDest  0x0200  /* Result needed in a specific register */
 #define EP_IntValue   0x0400  /* Integer value contained in u.iValue */
 #define EP_xIsSelect  0x0800  /* x.pSelect is valid (otherwise x.pList is) */
-#define EP_Hint       0x1000  /* Not used */
+#define EP_Hint       0x1000  /* The UNLIKELY() SQL function */
 #define EP_Reduced    0x2000  /* Expr struct is EXPR_REDUCEDSIZE bytes only */
 #define EP_TokenOnly  0x4000  /* Expr struct is EXPR_TOKENONLYSIZE bytes only */
 #define EP_Static     0x8000  /* Held in memory not obtained from malloc() */
diff --git a/src/where.c b/src/where.c
index 3c8a1eaac..a9905769a 100644
--- a/src/where.c
+++ b/src/where.c
@@ -52,12 +52,13 @@ typedef struct WhereOrSet WhereOrSet;
 ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
 ** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
 ** (Virtual tables can return a larger cost, but let's assume they do not.)
-** So all costs can be stored in a 16-bit unsigned integer without risk
+** So all costs can be stored in a 16-bit integer without risk
 ** of overflow.
 **
 ** Costs are estimates, so no effort is made to compute 10*log2(X) exactly.
-** Instead, a close estimate is used.  Any value of X<=1 is stored as 0.
-** X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.
+** Instead, a close estimate is used.  Any value of X=1 is stored as 0.
+** X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.  Negative values are allowed.
+** A WhereCost of -10 means 0.5.  WhereCost of -20 means 0.25.  And so forth.
 **
 ** The tool/wherecosttest.c source file implements a command-line program
 ** that will convert WhereCosts to integers, convert integers to WhereCosts
@@ -65,7 +66,7 @@ typedef struct WhereOrSet WhereOrSet;
 ** command-line program is a useful utility to have around when working with
 ** this module.
 */
-typedef unsigned short int WhereCost;
+typedef short int WhereCost;
 
 /*
 ** This object contains information needed to implement a single nested
@@ -268,6 +269,7 @@ struct WhereTerm {
     WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
     WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
   } u;
+  WhereCost truthProb;    /* Probability of truth for this expression */
   u16 eOperator;          /* A WO_xx value describing <op> */
   u8 wtFlags;             /* TERM_xxx bit flags.  See below */
   u8 nChild;              /* Number of children that must disable us */
@@ -642,6 +644,9 @@ static void whereClauseClear(WhereClause *pWC){
   }
 }
 
+/* Forward declaration */
+static WhereCost whereCost(tRowcnt x);
+
 /*
 ** Add a single new WhereTerm entry to the WhereClause object pWC.
 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
@@ -683,6 +688,11 @@ static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
     pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
   }
   pTerm = &pWC->a[idx = pWC->nTerm++];
+  if( p && ExprHasAnyProperty(p, EP_Hint) ){
+    pTerm->truthProb = whereCost(p->iTable) - 99;
+  }else{
+    pTerm->truthProb = -1;
+  }
   pTerm->pExpr = sqlite3ExprSkipCollate(p);
   pTerm->wtFlags = wtFlags;
   pTerm->pWC = pWC;
@@ -4258,6 +4268,32 @@ whereLoopInsert_noop:
 }
 
 /*
+** Adjust the WhereLoop.nOut value downward to account for terms of the
+** WHERE clause that reference the loop but which are not used by an
+** index.
+**
+** In the current implementation, the first extra WHERE clause term reduces
+** the number of output rows by a factor of 10 and each additional term
+** reduces the number of output rows by sqrt(2).
+*/
+static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
+  WhereTerm *pTerm;
+  Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
+  int x = 0;
+  int i;
+  for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
+    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) continue;
+    if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
+    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
+    x += pTerm->truthProb;
+  }
+  for(i=pLoop->nLTerm-1; i>=0; i--){
+    x -= pLoop->aLTerm[i]->truthProb;
+  }
+  if( x<0 ) pLoop->nOut += x;
+}
+
+/*
 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
 ** Try to match one more.
 **
@@ -4423,7 +4459,7 @@ static int whereLoopAddBtreeIndex(
     }
     /* Step cost for each output row */
     pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut);
-    /* TBD: Adjust nOut for additional constraints */
+    whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
     rc = whereLoopInsert(pBuilder, pNew);
     if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
      && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
@@ -4627,7 +4663,9 @@ static int whereLoopAddBtree(
       **     index scans so that a covering index scan will be favored over
       **     a table scan. */
       pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
+      whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
       rc = whereLoopInsert(pBuilder, pNew);
+      pNew->nOut = rSize;
       if( rc ) break;
     }else{
       Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
@@ -4659,7 +4697,9 @@ static int whereLoopAddBtree(
           ** which we will simplify to just N*log2(N) */
           pNew->rRun = rSize + rLogSize;
         }
+        whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
         rc = whereLoopInsert(pBuilder, pNew);
+        pNew->nOut = rSize;
         if( rc ) break;
       }
     }