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 *pAux,
 110   int argc, const char *const*argv,
 111   sqlite3_vtab **ppVtab,
 112   char **pzErr
 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   rc = sqlite3_declare_vtab(db,
 124      "CREATE TABLE x(value,start hidden,stop hidden,step hidden)");
 125   if( rc==SQLITE_OK ){
 126     pNew = *ppVtab = sqlite3_malloc( sizeof(*pNew) );
 127     if( pNew==0 ) return SQLITE_NOMEM;
 128     memset(pNew, 0, sizeof(*pNew));
 129   }
 130   return rc;
 131 }
 132
 133 /*
 134 ** This method is the destructor for series_cursor objects.
 135 */
 136 static int seriesDisconnect(sqlite3_vtab *pVtab){
 137   sqlite3_free(pVtab);
 138   return SQLITE_OK;
 139 }
 140
 141 /*
 142 ** Constructor for a new series_cursor object.
 143 */
 144 static int seriesOpen(sqlite3_vtab *p, sqlite3_vtab_cursor **ppCursor){
 145   series_cursor *pCur;
 146   pCur = sqlite3_malloc( sizeof(*pCur) );
 147   if( pCur==0 ) return SQLITE_NOMEM;
 148   memset(pCur, 0, sizeof(*pCur));
 149   *ppCursor = &pCur->base;
 150   return SQLITE_OK;
 151 }
 152
 153 /*
 154 ** Destructor for a series_cursor.
 155 */
 156 static int seriesClose(sqlite3_vtab_cursor *cur){
 157   sqlite3_free(cur);
 158   return SQLITE_OK;
 159 }
 160
 161
 162 /*
 163 ** Advance a series_cursor to its next row of output.
 164 */
 165 static int seriesNext(sqlite3_vtab_cursor *cur){
 166   series_cursor *pCur = (series_cursor*)cur;
 167   if( pCur->isDesc ){
 168     pCur->iValue -= pCur->iStep;
 169   }else{
 170     pCur->iValue += pCur->iStep;
 171   }
 172   pCur->iRowid++;
 173   return SQLITE_OK;
 174 }
 175
 176 /*
 177 ** Return values of columns for the row at which the series_cursor
 178 ** is currently pointing.
 179 */
 180 static int seriesColumn(
 181   sqlite3_vtab_cursor *cur,   /* The cursor */
 182   sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
 183   int i                       /* Which column to return */
 184 ){
 185   series_cursor *pCur = (series_cursor*)cur;
 186   sqlite3_int64 x = 0;
 187   switch( i ){
 188     case SERIES_COLUMN_START:  x = pCur->mnValue; break;
 189     case SERIES_COLUMN_STOP:   x = pCur->mxValue; break;
 190     case SERIES_COLUMN_STEP:   x = pCur->iStep;   break;
 191     default:                   x = pCur->iValue;  break;
 192   }
 193   sqlite3_result_int64(ctx, x);
 194   return SQLITE_OK;
 195 }
 196
 197 /*
 198 ** Return the rowid for the current row. In this implementation, the
 199 ** first row returned is assigned rowid value 1, and each subsequent
 200 ** row a value 1 more than that of the previous.
 201 */
 202 static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
 203   series_cursor *pCur = (series_cursor*)cur;
 204   *pRowid = pCur->iRowid;
 205   return SQLITE_OK;
 206 }
 207
 208 /*
 209 ** Return TRUE if the cursor has been moved off of the last
 210 ** row of output.
 211 */
 212 static int seriesEof(sqlite3_vtab_cursor *cur){
 213   series_cursor *pCur = (series_cursor*)cur;
 214   if( pCur->isDesc ){
 215     return pCur->iValue < pCur->mnValue;
 216   }else{
 217     return pCur->iValue > pCur->mxValue;
 218   }
 219 }
 220
 221 /* True to cause run-time checking of the start=, stop=, and/or step=
 222 ** parameters.  The only reason to do this is for testing the
 223 ** constraint checking logic for virtual tables in the SQLite core.
 224 */
 225 #ifndef SQLITE_SERIES_CONSTRAINT_VERIFY
 226 # define SQLITE_SERIES_CONSTRAINT_VERIFY 0
 227 #endif
 228
 229 /*
 230 ** This method is called to "rewind" the series_cursor object back
 231 ** to the first row of output.  This method is always called at least
 232 ** once prior to any call to seriesColumn() or seriesRowid() or
 233 ** seriesEof().
 234 **
 235 ** The query plan selected by seriesBestIndex is passed in the idxNum
 236 ** parameter.  (idxStr is not used in this implementation.)  idxNum
 237 ** is a bitmask showing which constraints are available:
 238 **
 239 **    1:    start=VALUE
 240 **    2:    stop=VALUE
 241 **    4:    step=VALUE
 242 **
 243 ** Also, if bit 8 is set, that means that the series should be output
 244 ** in descending order rather than in ascending order.
 245 **
 246 ** This routine should initialize the cursor and position it so that it
 247 ** is pointing at the first row, or pointing off the end of the table
 248 ** (so that seriesEof() will return true) if the table is empty.
 249 */
 250 static int seriesFilter(
 251   sqlite3_vtab_cursor *pVtabCursor,
 252   int idxNum, const char *idxStr,
 253   int argc, sqlite3_value **argv
 254 ){
 255   series_cursor *pCur = (series_cursor *)pVtabCursor;
 256   int i = 0;
 257   if( idxNum & 1 ){
 258     pCur->mnValue = sqlite3_value_int64(argv[i++]);
 259   }else{
 260     pCur->mnValue = 0;
 261   }
 262   if( idxNum & 2 ){
 263     pCur->mxValue = sqlite3_value_int64(argv[i++]);
 264   }else{
 265     pCur->mxValue = 0xffffffff;
 266   }
 267   if( idxNum & 4 ){
 268     pCur->iStep = sqlite3_value_int64(argv[i++]);
 269     if( pCur->iStep<1 ) pCur->iStep = 1;
 270   }else{
 271     pCur->iStep = 1;
 272   }
 273   if( idxNum & 8 ){
 274     pCur->isDesc = 1;
 275     pCur->iValue = pCur->mxValue;
 276     if( pCur->iStep>0 ){
 277       pCur->iValue -= (pCur->mxValue - pCur->mnValue)%pCur->iStep;
 278     }
 279   }else{
 280     pCur->isDesc = 0;
 281     pCur->iValue = pCur->mnValue;
 282   }
 283   pCur->iRowid = 1;
 284   return SQLITE_OK;
 285 }
 286
 287 /*
 288 ** SQLite will invoke this method one or more times while planning a query
 289 ** that uses the generate_series virtual table.  This routine needs to create
 290 ** a query plan for each invocation and compute an estimated cost for that
 291 ** plan.
 292 **
 293 ** In this implementation idxNum is used to represent the
 294 ** query plan.  idxStr is unused.
 295 **
 296 ** The query plan is represented by bits in idxNum:
 297 **
 298 **  (1)  start = $value  -- constraint exists
 299 **  (2)  stop = $value   -- constraint exists
 300 **  (4)  step = $value   -- constraint exists
 301 **  (8)  output in descending order
 302 */
 303 static int seriesBestIndex(
 304   sqlite3_vtab *tab,
 305   sqlite3_index_info *pIdxInfo
 306 ){
 307   int i;                 /* Loop over constraints */
 308   int idxNum = 0;        /* The query plan bitmask */
 309   int startIdx = -1;     /* Index of the start= constraint, or -1 if none */
 310   int stopIdx = -1;      /* Index of the stop= constraint, or -1 if none */
 311   int stepIdx = -1;      /* Index of the step= constraint, or -1 if none */
 312   int nArg = 0;          /* Number of arguments that seriesFilter() expects */
 313
 314   const struct sqlite3_index_constraint *pConstraint;
 315   pConstraint = pIdxInfo->aConstraint;
 316   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
 317     if( pConstraint->usable==0 ) continue;
 318     if( pConstraint->op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
 319     switch( pConstraint->iColumn ){
 320       case SERIES_COLUMN_START:
 321         startIdx = i;
 322         idxNum |= 1;
 323         break;
 324       case SERIES_COLUMN_STOP:
 325         stopIdx = i;
 326         idxNum |= 2;
 327         break;
 328       case SERIES_COLUMN_STEP:
 329         stepIdx = i;
 330         idxNum |= 4;
 331         break;
 332     }
 333   }
 334   if( startIdx>=0 ){
 335     pIdxInfo->aConstraintUsage[startIdx].argvIndex = ++nArg;
 336     pIdxInfo->aConstraintUsage[startIdx].omit= !SQLITE_SERIES_CONSTRAINT_VERIFY;
 337   }
 338   if( stopIdx>=0 ){
 339     pIdxInfo->aConstraintUsage[stopIdx].argvIndex = ++nArg;
 340     pIdxInfo->aConstraintUsage[stopIdx].omit = !SQLITE_SERIES_CONSTRAINT_VERIFY;
 341   }
 342   if( stepIdx>=0 ){
 343     pIdxInfo->aConstraintUsage[stepIdx].argvIndex = ++nArg;
 344     pIdxInfo->aConstraintUsage[stepIdx].omit = !SQLITE_SERIES_CONSTRAINT_VERIFY;
 345   }
 346   if( (idxNum & 3)==3 ){
 347     /* Both start= and stop= boundaries are available.  This is the
 348     ** the preferred case */
 349     pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0));
 350     pIdxInfo->estimatedRows = 1000;
 351     if( pIdxInfo->nOrderBy==1 ){
 352       if( pIdxInfo->aOrderBy[0].desc ) idxNum |= 8;
 353       pIdxInfo->orderByConsumed = 1;
 354     }
 355   }else{
 356     /* If either boundary is missing, we have to generate a huge span
 357     ** of numbers.  Make this case very expensive so that the query
 358     ** planner will work hard to avoid it. */
 359     pIdxInfo->estimatedCost = (double)2147483647;
 360     pIdxInfo->estimatedRows = 2147483647;
 361   }
 362   pIdxInfo->idxNum = idxNum;
 363   return SQLITE_OK;
 364 }
 365
 366 /*
 367 ** This following structure defines all the methods for the
 368 ** generate_series virtual table.
 369 */
 370 static sqlite3_module seriesModule = {
 371   0,                         /* iVersion */
 372   0,                         /* xCreate */
 373   seriesConnect,             /* xConnect */
 374   seriesBestIndex,           /* xBestIndex */
 375   seriesDisconnect,          /* xDisconnect */
 376   0,                         /* xDestroy */
 377   seriesOpen,                /* xOpen - open a cursor */
 378   seriesClose,               /* xClose - close a cursor */
 379   seriesFilter,              /* xFilter - configure scan constraints */
 380   seriesNext,                /* xNext - advance a cursor */
 381   seriesEof,                 /* xEof - check for end of scan */
 382   seriesColumn,              /* xColumn - read data */
 383   seriesRowid,               /* xRowid - read data */
 384   0,                         /* xUpdate */
 385   0,                         /* xBegin */
 386   0,                         /* xSync */
 387   0,                         /* xCommit */
 388   0,                         /* xRollback */
 389   0,                         /* xFindMethod */
 390   0,                         /* xRename */
 391 };
 392
 393 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 394
 395 #ifdef _WIN32
 396 __declspec(dllexport)
 397 #endif
 398 int sqlite3_series_init(
 399   sqlite3 *db,
 400   char **pzErrMsg,
 401   const sqlite3_api_routines *pApi
 402 ){
 403   int rc = SQLITE_OK;
 404   SQLITE_EXTENSION_INIT2(pApi);
 405 #ifndef SQLITE_OMIT_VIRTUALTABLE
 406   if( sqlite3_libversion_number()<3008012 ){
 407     *pzErrMsg = sqlite3_mprintf(
 408         "generate_series() requires SQLite 3.8.12 or later");
 409     return SQLITE_ERROR;
 410   }
 411   rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0);
 412 #endif
 413   return rc;
 414 }