ext/misc/series.c

   1 /*
   2 ** 2015-08-18
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 **
  13 ** This file demonstrates how to create a table-valued-function using
  14 ** a virtual table.  This demo implements the generate_series() function
  15 ** which gives similar results to the eponymous function in PostgreSQL.
  16 ** Examples:
  17 **
  18 **      SELECT * FROM generate_series(0,100,5);
  19 **
  20 ** The query above returns integers from 0 through 100 counting by steps
  21 ** of 5.
  22 **
  23 **      SELECT * FROM generate_series(0,100);
  24 **
  25 ** Integers from 0 through 100 with a step size of 1.
  26 **
  27 **      SELECT * FROM generate_series(20) LIMIT 10;
  28 **
  29 ** Integers 20 through 29.
  30 **
  31 ** HOW IT WORKS
  32 **
  33 ** The generate_series "function" is really a virtual table with the
  34 ** following schema:
  35 **
  36 **     CREATE TABLE generate_series(
  37 **       value,
  38 **       start HIDDEN,
  39 **       stop HIDDEN,
  40 **       step HIDDEN
  41 **     );
  42 **
  43 ** Function arguments in queries against this virtual table are translated
  44 ** into equality constraints against successive hidden columns.  In other
  45 ** words, the following pairs of queries are equivalent to each other:
  46 **
  47 **    SELECT * FROM generate_series(0,100,5);
  48 **    SELECT * FROM generate_series WHERE start=0 AND stop=100 AND step=5;
  49 **
  50 **    SELECT * FROM generate_series(0,100);
  51 **    SELECT * FROM generate_series WHERE start=0 AND stop=100;
  52 **
  53 **    SELECT * FROM generate_series(20) LIMIT 10;
  54 **    SELECT * FROM generate_series WHERE start=20 LIMIT 10;
  55 **
  56 ** The generate_series virtual table implementation leaves the xCreate method
  57 ** set to NULL.  This means that it is not possible to do a CREATE VIRTUAL
  58 ** TABLE command with "generate_series" as the USING argument.  Instead, there
  59 ** is a single generate_series virtual table that is always available without
  60 ** having to be created first.
  61 **
  62 ** The xBestIndex method looks for equality constraints against the hidden
  63 ** start, stop, and step columns, and if present, it uses those constraints
  64 ** to bound the sequence of generated values.  If the equality constraints
  65 ** are missing, it uses 0 for start, 4294967295 for stop, and 1 for step.
  66 ** xBestIndex returns a small cost when both start and stop are available,
  67 ** and a very large cost if either start or stop are unavailable.  This
  68 ** encourages the query planner to order joins such that the bounds of the
  69 ** series are well-defined.
  70 */
  71 #include "sqlite3ext.h"
  72 SQLITE_EXTENSION_INIT1
  73 #include <assert.h>
  74 #include <string.h>
  75
  76 #ifndef SQLITE_OMIT_VIRTUALTABLE
  77
  78
  79 /* series_cursor is a subclass of sqlite3_vtab_cursor which will
  80 ** serve as the underlying representation of a cursor that scans
  81 ** over rows of the result
  82 */
  83 typedef struct series_cursor series_cursor;
  84 struct series_cursor {
  85   sqlite3_vtab_cursor base;  /* Base class - must be first */
  86   int isDesc;                /* True to count down rather than up */
  87   sqlite3_int64 iRowid;      /* The rowid */
  88   sqlite3_int64 iValue;      /* Current value ("value") */
  89   sqlite3_int64 mnValue;     /* Mimimum value ("start") */
  90   sqlite3_int64 mxValue;     /* Maximum value ("stop") */
  91   sqlite3_int64 iStep;       /* Increment ("step") */
  92 };
  93
  94 /*
  95 ** The seriesConnect() method is invoked to create a new
  96 ** series_vtab that describes the generate_series virtual table.
  97 **
  98 ** Think of this routine as the constructor for series_vtab objects.
  99 **
 100 ** All this routine needs to do is:
 101 **
 102 **    (1) Allocate the series_vtab object and initialize all fields.
 103 **
 104 **    (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
 105 **        result set of queries against generate_series will look like.
 106 */
 107 static int seriesConnect(
 108   sqlite3 *db,
 109   void *pUnused,
 110   int argcUnused, const char *const*argvUnused,
 111   sqlite3_vtab **ppVtab,
 112   char **pzErrUnused
 113 ){
 114   sqlite3_vtab *pNew;
 115   int rc;
 116
 117 /* Column numbers */
 118 #define SERIES_COLUMN_VALUE 0
 119 #define SERIES_COLUMN_START 1
 120 #define SERIES_COLUMN_STOP  2
 121 #define SERIES_COLUMN_STEP  3
 122
 123   (void)pUnused;
 124   (void)argcUnused;
 125   (void)argvUnused;
 126   (void)pzErrUnused;
 127   rc = sqlite3_declare_vtab(db,
 128      "CREATE TABLE x(value,start hidden,stop hidden,step hidden)");
 129   if( rc==SQLITE_OK ){
 130     pNew = *ppVtab = sqlite3_malloc( sizeof(*pNew) );
 131     if( pNew==0 ) return SQLITE_NOMEM;
 132     memset(pNew, 0, sizeof(*pNew));
 133     sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
 134   }
 135   return rc;
 136 }
 137
 138 /*
 139 ** This method is the destructor for series_cursor objects.
 140 */
 141 static int seriesDisconnect(sqlite3_vtab *pVtab){
 142   sqlite3_free(pVtab);
 143   return SQLITE_OK;
 144 }
 145
 146 /*
 147 ** Constructor for a new series_cursor object.
 148 */
 149 static int seriesOpen(sqlite3_vtab *pUnused, sqlite3_vtab_cursor **ppCursor){
 150   series_cursor *pCur;
 151   (void)pUnused;
 152   pCur = sqlite3_malloc( sizeof(*pCur) );
 153   if( pCur==0 ) return SQLITE_NOMEM;
 154   memset(pCur, 0, sizeof(*pCur));
 155   *ppCursor = &pCur->base;
 156   return SQLITE_OK;
 157 }
 158
 159 /*
 160 ** Destructor for a series_cursor.
 161 */
 162 static int seriesClose(sqlite3_vtab_cursor *cur){
 163   sqlite3_free(cur);
 164   return SQLITE_OK;
 165 }
 166
 167
 168 /*
 169 ** Advance a series_cursor to its next row of output.
 170 */
 171 static int seriesNext(sqlite3_vtab_cursor *cur){
 172   series_cursor *pCur = (series_cursor*)cur;
 173   if( pCur->isDesc ){
 174     pCur->iValue -= pCur->iStep;
 175   }else{
 176     pCur->iValue += pCur->iStep;
 177   }
 178   pCur->iRowid++;
 179   return SQLITE_OK;
 180 }
 181
 182 /*
 183 ** Return values of columns for the row at which the series_cursor
 184 ** is currently pointing.
 185 */
 186 static int seriesColumn(
 187   sqlite3_vtab_cursor *cur,   /* The cursor */
 188   sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
 189   int i                       /* Which column to return */
 190 ){
 191   series_cursor *pCur = (series_cursor*)cur;
 192   sqlite3_int64 x = 0;
 193   switch( i ){
 194     case SERIES_COLUMN_START:  x = pCur->mnValue; break;
 195     case SERIES_COLUMN_STOP:   x = pCur->mxValue; break;
 196     case SERIES_COLUMN_STEP:   x = pCur->iStep;   break;
 197     default:                   x = pCur->iValue;  break;
 198   }
 199   sqlite3_result_int64(ctx, x);
 200   return SQLITE_OK;
 201 }
 202
 203 /*
 204 ** Return the rowid for the current row. In this implementation, the
 205 ** first row returned is assigned rowid value 1, and each subsequent
 206 ** row a value 1 more than that of the previous.
 207 */
 208 static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
 209   series_cursor *pCur = (series_cursor*)cur;
 210   *pRowid = pCur->iRowid;
 211   return SQLITE_OK;
 212 }
 213
 214 /*
 215 ** Return TRUE if the cursor has been moved off of the last
 216 ** row of output.
 217 */
 218 static int seriesEof(sqlite3_vtab_cursor *cur){
 219   series_cursor *pCur = (series_cursor*)cur;
 220   if( pCur->isDesc ){
 221     return pCur->iValue < pCur->mnValue;
 222   }else{
 223     return pCur->iValue > pCur->mxValue;
 224   }
 225 }
 226
 227 /* True to cause run-time checking of the start=, stop=, and/or step=
 228 ** parameters.  The only reason to do this is for testing the
 229 ** constraint checking logic for virtual tables in the SQLite core.
 230 */
 231 #ifndef SQLITE_SERIES_CONSTRAINT_VERIFY
 232 # define SQLITE_SERIES_CONSTRAINT_VERIFY 0
 233 #endif
 234
 235 /*
 236 ** This method is called to "rewind" the series_cursor object back
 237 ** to the first row of output.  This method is always called at least
 238 ** once prior to any call to seriesColumn() or seriesRowid() or
 239 ** seriesEof().
 240 **
 241 ** The query plan selected by seriesBestIndex is passed in the idxNum
 242 ** parameter.  (idxStr is not used in this implementation.)  idxNum
 243 ** is a bitmask showing which constraints are available:
 244 **
 245 **    1:    start=VALUE
 246 **    2:    stop=VALUE
 247 **    4:    step=VALUE
 248 **
 249 ** Also, if bit 8 is set, that means that the series should be output
 250 ** in descending order rather than in ascending order.  If bit 16 is
 251 ** set, then output must appear in ascending order.
 252 **
 253 ** This routine should initialize the cursor and position it so that it
 254 ** is pointing at the first row, or pointing off the end of the table
 255 ** (so that seriesEof() will return true) if the table is empty.
 256 */
 257 static int seriesFilter(
 258   sqlite3_vtab_cursor *pVtabCursor,
 259   int idxNum, const char *idxStrUnused,
 260   int argc, sqlite3_value **argv
 261 ){
 262   series_cursor *pCur = (series_cursor *)pVtabCursor;
 263   int i = 0;
 264   (void)idxStrUnused;
 265   if( idxNum & 1 ){
 266     pCur->mnValue = sqlite3_value_int64(argv[i++]);
 267   }else{
 268     pCur->mnValue = 0;
 269   }
 270   if( idxNum & 2 ){
 271     pCur->mxValue = sqlite3_value_int64(argv[i++]);
 272   }else{
 273     pCur->mxValue = 0xffffffff;
 274   }
 275   if( idxNum & 4 ){
 276     pCur->iStep = sqlite3_value_int64(argv[i++]);
 277     if( pCur->iStep==0 ){
 278       pCur->iStep = 1;
 279     }else if( pCur->iStep<0 ){
 280       pCur->iStep = -pCur->iStep;
 281       if( (idxNum & 16)==0 ) idxNum |= 8;
 282     }
 283   }else{
 284     pCur->iStep = 1;
 285   }
 286   for(i=0; i<argc; i++){
 287     if( sqlite3_value_type(argv[i])==SQLITE_NULL ){
 288       /* If any of the constraints have a NULL value, then return no rows.
 289       ** See ticket https://www.sqlite.org/src/info/fac496b61722daf2 */
 290       pCur->mnValue = 1;
 291       pCur->mxValue = 0;
 292       break;
 293     }
 294   }
 295   if( idxNum & 8 ){
 296     pCur->isDesc = 1;
 297     pCur->iValue = pCur->mxValue;
 298     if( pCur->iStep>0 ){
 299       pCur->iValue -= (pCur->mxValue - pCur->mnValue)%pCur->iStep;
 300     }
 301   }else{
 302     pCur->isDesc = 0;
 303     pCur->iValue = pCur->mnValue;
 304   }
 305   pCur->iRowid = 1;
 306   return SQLITE_OK;
 307 }
 308
 309 /*
 310 ** SQLite will invoke this method one or more times while planning a query
 311 ** that uses the generate_series virtual table.  This routine needs to create
 312 ** a query plan for each invocation and compute an estimated cost for that
 313 ** plan.
 314 **
 315 ** In this implementation idxNum is used to represent the
 316 ** query plan.  idxStr is unused.
 317 **
 318 ** The query plan is represented by bits in idxNum:
 319 **
 320 **  (1)  start = $value  -- constraint exists
 321 **  (2)  stop = $value   -- constraint exists
 322 **  (4)  step = $value   -- constraint exists
 323 **  (8)  output in descending order
 324 */
 325 static int seriesBestIndex(
 326   sqlite3_vtab *pVTab,
 327   sqlite3_index_info *pIdxInfo
 328 ){
 329   int i, j;              /* Loop over constraints */
 330   int idxNum = 0;        /* The query plan bitmask */
 331   int bStartSeen = 0;    /* EQ constraint seen on the START column */
 332   int unusableMask = 0;  /* Mask of unusable constraints */
 333   int nArg = 0;          /* Number of arguments that seriesFilter() expects */
 334   int aIdx[3];           /* Constraints on start, stop, and step */
 335   const struct sqlite3_index_constraint *pConstraint;
 336
 337   /* This implementation assumes that the start, stop, and step columns
 338   ** are the last three columns in the virtual table. */
 339   assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 );
 340   assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 );
 341
 342   aIdx[0] = aIdx[1] = aIdx[2] = -1;
 343   pConstraint = pIdxInfo->aConstraint;
 344   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
 345     int iCol;    /* 0 for start, 1 for stop, 2 for step */
 346     int iMask;   /* bitmask for those column */
 347     if( pConstraint->iColumn<SERIES_COLUMN_START ) continue;
 348     iCol = pConstraint->iColumn - SERIES_COLUMN_START;
 349     assert( iCol>=0 && iCol<=2 );
 350     iMask = 1 << iCol;
 351     if( iCol==0 ) bStartSeen = 1;
 352     if( pConstraint->usable==0 ){
 353       unusableMask |=  iMask;
 354       continue;
 355     }else if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){
 356       idxNum |= iMask;
 357       aIdx[iCol] = i;
 358     }
 359   }
 360   for(i=0; i<3; i++){
 361     if( (j = aIdx[i])>=0 ){
 362       pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg;
 363       pIdxInfo->aConstraintUsage[j].omit = !SQLITE_SERIES_CONSTRAINT_VERIFY;
 364     }
 365   }
 366   /* The current generate_column() implementation requires at least one
 367   ** argument (the START value).  Legacy versions assumed START=0 if the
 368   ** first argument was omitted.  Compile with -DZERO_ARGUMENT_GENERATE_SERIES
 369   ** to obtain the legacy behavior */
 370 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
 371   if( !bStartSeen ){
 372     sqlite3_free(pVTab->zErrMsg);
 373     pVTab->zErrMsg = sqlite3_mprintf(
 374         "first argument to \"generate_series()\" missing or unusable");
 375     return SQLITE_ERROR;
 376   }
 377 #endif
 378   if( (unusableMask & ~idxNum)!=0 ){
 379     /* The start, stop, and step columns are inputs.  Therefore if there
 380     ** are unusable constraints on any of start, stop, or step then
 381     ** this plan is unusable */
 382     return SQLITE_CONSTRAINT;
 383   }
 384   if( (idxNum & 3)==3 ){
 385     /* Both start= and stop= boundaries are available.  This is the
 386     ** the preferred case */
 387     pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0));
 388     pIdxInfo->estimatedRows = 1000;
 389     if( pIdxInfo->nOrderBy==1 ){
 390       if( pIdxInfo->aOrderBy[0].desc ){
 391         idxNum |= 8;
 392       }else{
 393         idxNum |= 16;
 394       }
 395       pIdxInfo->orderByConsumed = 1;
 396     }
 397   }else{
 398     /* If either boundary is missing, we have to generate a huge span
 399     ** of numbers.  Make this case very expensive so that the query
 400     ** planner will work hard to avoid it. */
 401     pIdxInfo->estimatedRows = 2147483647;
 402   }
 403   pIdxInfo->idxNum = idxNum;
 404   return SQLITE_OK;
 405 }
 406
 407 /*
 408 ** This following structure defines all the methods for the
 409 ** generate_series virtual table.
 410 */
 411 static sqlite3_module seriesModule = {
 412   0,                         /* iVersion */
 413   0,                         /* xCreate */
 414   seriesConnect,             /* xConnect */
 415   seriesBestIndex,           /* xBestIndex */
 416   seriesDisconnect,          /* xDisconnect */
 417   0,                         /* xDestroy */
 418   seriesOpen,                /* xOpen - open a cursor */
 419   seriesClose,               /* xClose - close a cursor */
 420   seriesFilter,              /* xFilter - configure scan constraints */
 421   seriesNext,                /* xNext - advance a cursor */
 422   seriesEof,                 /* xEof - check for end of scan */
 423   seriesColumn,              /* xColumn - read data */
 424   seriesRowid,               /* xRowid - read data */
 425   0,                         /* xUpdate */
 426   0,                         /* xBegin */
 427   0,                         /* xSync */
 428   0,                         /* xCommit */
 429   0,                         /* xRollback */
 430   0,                         /* xFindMethod */
 431   0,                         /* xRename */
 432   0,                         /* xSavepoint */
 433   0,                         /* xRelease */
 434   0,                         /* xRollbackTo */
 435   0                          /* xShadowName */
 436 };
 437
 438 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 439
 440 #ifdef _WIN32
 441 __declspec(dllexport)
 442 #endif
 443 int sqlite3_series_init(
 444   sqlite3 *db,
 445   char **pzErrMsg,
 446   const sqlite3_api_routines *pApi
 447 ){
 448   int rc = SQLITE_OK;
 449   SQLITE_EXTENSION_INIT2(pApi);
 450 #ifndef SQLITE_OMIT_VIRTUALTABLE
 451   if( sqlite3_libversion_number()<3008012 && pzErrMsg!=0 ){
 452     *pzErrMsg = sqlite3_mprintf(
 453         "generate_series() requires SQLite 3.8.12 or later");
 454     return SQLITE_ERROR;
 455   }
 456   rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0);
 457 #endif
 458   return rc;
 459 }