ext/misc/series.c

   1 /*
   2 ** 2015-08-18, 2023-04-28
   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 the same results as the eponymous function in PostgreSQL,
  16 ** within the limitation that its arguments are signed 64-bit integers.
  17 **
  18 ** Considering its equivalents to generate_series(start,stop,step): A
  19 ** value V[n] sequence is produced for integer n ascending from 0 where
  20 **  ( V[n] == start + n * step  &&  sgn(V[n] - stop) * sgn(step) >= 0 )
  21 ** for each produced value (independent of production time ordering.)
  22 **
  23 ** All parameters must be either integer or convertable to integer.
  24 ** The start parameter is required.
  25 ** The stop parameter defaults to (1<<32)-1 (aka 4294967295 or 0xffffffff)
  26 ** The step parameter defaults to 1 and 0 is treated as 1.
  27 **
  28 ** Examples:
  29 **
  30 **      SELECT * FROM generate_series(0,100,5);
  31 **
  32 ** The query above returns integers from 0 through 100 counting by steps
  33 ** of 5.
  34 **
  35 **      SELECT * FROM generate_series(0,100);
  36 **
  37 ** Integers from 0 through 100 with a step size of 1.
  38 **
  39 **      SELECT * FROM generate_series(20) LIMIT 10;
  40 **
  41 ** Integers 20 through 29.
  42 **
  43 **      SELECT * FROM generate_series(0,-100,-5);
  44 **
  45 ** Integers 0 -5 -10 ... -100.
  46 **
  47 **      SELECT * FROM generate_series(0,-1);
  48 **
  49 ** Empty sequence.
  50 **
  51 ** HOW IT WORKS
  52 **
  53 ** The generate_series "function" is really a virtual table with the
  54 ** following schema:
  55 **
  56 **     CREATE TABLE generate_series(
  57 **       value,
  58 **       start HIDDEN,
  59 **       stop HIDDEN,
  60 **       step HIDDEN
  61 **     );
  62 **
  63 ** The virtual table also has a rowid, logically equivalent to n+1 where
  64 ** "n" is the ascending integer in the aforesaid production definition.
  65 **
  66 ** Function arguments in queries against this virtual table are translated
  67 ** into equality constraints against successive hidden columns.  In other
  68 ** words, the following pairs of queries are equivalent to each other:
  69 **
  70 **    SELECT * FROM generate_series(0,100,5);
  71 **    SELECT * FROM generate_series WHERE start=0 AND stop=100 AND step=5;
  72 **
  73 **    SELECT * FROM generate_series(0,100);
  74 **    SELECT * FROM generate_series WHERE start=0 AND stop=100;
  75 **
  76 **    SELECT * FROM generate_series(20) LIMIT 10;
  77 **    SELECT * FROM generate_series WHERE start=20 LIMIT 10;
  78 **
  79 ** The generate_series virtual table implementation leaves the xCreate method
  80 ** set to NULL.  This means that it is not possible to do a CREATE VIRTUAL
  81 ** TABLE command with "generate_series" as the USING argument.  Instead, there
  82 ** is a single generate_series virtual table that is always available without
  83 ** having to be created first.
  84 **
  85 ** The xBestIndex method looks for equality constraints against the hidden
  86 ** start, stop, and step columns, and if present, it uses those constraints
  87 ** to bound the sequence of generated values.  If the equality constraints
  88 ** are missing, it uses 0 for start, 4294967295 for stop, and 1 for step.
  89 ** xBestIndex returns a small cost when both start and stop are available,
  90 ** and a very large cost if either start or stop are unavailable.  This
  91 ** encourages the query planner to order joins such that the bounds of the
  92 ** series are well-defined.
  93 */
  94 #include "sqlite3ext.h"
  95 SQLITE_EXTENSION_INIT1
  96 #include <assert.h>
  97 #include <string.h>
  98 #include <limits.h>
  99
 100 #ifndef SQLITE_OMIT_VIRTUALTABLE
 101 /*
 102 ** Return that member of a generate_series(...) sequence whose 0-based
 103 ** index is ix. The 0th member is given by smBase. The sequence members
 104 ** progress per ix increment by smStep.
 105 */
 106 static sqlite3_int64 genSeqMember(
 107   sqlite3_int64 smBase,
 108   sqlite3_int64 smStep,
 109   sqlite3_uint64 ix
 110 ){
 111   static const sqlite3_uint64 mxI64 =
 112       ((sqlite3_uint64)0x7fffffff)<<32 | 0xffffffff;
 113   if( ix>=mxI64 ){
 114     /* Get ix into signed i64 range. */
 115     ix -= mxI64;
 116     /* With 2's complement ALU, this next can be 1 step, but is split into
 117      * 2 for UBSAN's satisfaction (and hypothetical 1's complement ALUs.) */
 118     smBase += (mxI64/2) * smStep;
 119     smBase += (mxI64 - mxI64/2) * smStep;
 120   }
 121   /* Under UBSAN (or on 1's complement machines), must do this last term
 122    * in steps to avoid the dreaded (and harmless) signed multiply overlow. */
 123   if( ix>=2 ){
 124     sqlite3_int64 ix2 = (sqlite3_int64)ix/2;
 125     smBase += ix2*smStep;
 126     ix -= ix2;
 127   }
 128   return smBase + ((sqlite3_int64)ix)*smStep;
 129 }
 130
 131 typedef unsigned char u8;
 132
 133 typedef struct SequenceSpec {
 134   sqlite3_int64 iBase;         /* Starting value ("start") */
 135   sqlite3_int64 iTerm;         /* Given terminal value ("stop") */
 136   sqlite3_int64 iStep;         /* Increment ("step") */
 137   sqlite3_uint64 uSeqIndexMax; /* maximum sequence index (aka "n") */
 138   sqlite3_uint64 uSeqIndexNow; /* Current index during generation */
 139   sqlite3_int64 iValueNow;     /* Current value during generation */
 140   u8 isNotEOF;                 /* Sequence generation not exhausted */
 141   u8 isReversing;              /* Sequence is being reverse generated */
 142 } SequenceSpec;
 143
 144 /*
 145 ** Prepare a SequenceSpec for use in generating an integer series
 146 ** given initialized iBase, iTerm and iStep values. Sequence is
 147 ** initialized per given isReversing. Other members are computed.
 148 */
 149 static void setupSequence( SequenceSpec *pss ){
 150   int bSameSigns;
 151   pss->uSeqIndexMax = 0;
 152   pss->isNotEOF = 0;
 153   bSameSigns = (pss->iBase < 0)==(pss->iTerm < 0);
 154   if( pss->iTerm < pss->iBase ){
 155     sqlite3_uint64 nuspan = 0;
 156     if( bSameSigns ){
 157       nuspan = (sqlite3_uint64)(pss->iBase - pss->iTerm);
 158     }else{
 159       /* Under UBSAN (or on 1's complement machines), must do this in steps.
 160        * In this clause, iBase>=0 and iTerm<0 . */
 161       nuspan = 1;
 162       nuspan += pss->iBase;
 163       nuspan += -(pss->iTerm+1);
 164     }
 165     if( pss->iStep<0 ){
 166       pss->isNotEOF = 1;
 167       if( nuspan==ULONG_MAX ){
 168         pss->uSeqIndexMax = ( pss->iStep>LLONG_MIN )? nuspan/-pss->iStep : 1;
 169       }else if( pss->iStep>LLONG_MIN ){
 170         pss->uSeqIndexMax = nuspan/-pss->iStep;
 171       }
 172     }
 173   }else if( pss->iTerm > pss->iBase ){
 174     sqlite3_uint64 puspan = 0;
 175     if( bSameSigns ){
 176       puspan = (sqlite3_uint64)(pss->iTerm - pss->iBase);
 177     }else{
 178       /* Under UBSAN (or on 1's complement machines), must do this in steps.
 179        * In this clause, iTerm>=0 and iBase<0 . */
 180       puspan = 1;
 181       puspan += pss->iTerm;
 182       puspan += -(pss->iBase+1);
 183     }
 184     if( pss->iStep>0 ){
 185       pss->isNotEOF = 1;
 186       pss->uSeqIndexMax = puspan/pss->iStep;
 187     }
 188   }else if( pss->iTerm == pss->iBase ){
 189       pss->isNotEOF = 1;
 190       pss->uSeqIndexMax = 0;
 191   }
 192   pss->uSeqIndexNow = (pss->isReversing)? pss->uSeqIndexMax : 0;
 193   pss->iValueNow = (pss->isReversing)
 194     ? genSeqMember(pss->iBase, pss->iStep, pss->uSeqIndexMax)
 195     : pss->iBase;
 196 }
 197
 198 /*
 199 ** Progress sequence generator to yield next value, if any.
 200 ** Leave its state to either yield next value or be at EOF.
 201 ** Return whether there is a next value, or 0 at EOF.
 202 */
 203 static int progressSequence( SequenceSpec *pss ){
 204   if( !pss->isNotEOF ) return 0;
 205   if( pss->isReversing ){
 206     if( pss->uSeqIndexNow > 0 ){
 207       pss->uSeqIndexNow--;
 208       pss->iValueNow -= pss->iStep;
 209     }else{
 210       pss->isNotEOF = 0;
 211     }
 212   }else{
 213     if( pss->uSeqIndexNow < pss->uSeqIndexMax ){
 214       pss->uSeqIndexNow++;
 215       pss->iValueNow += pss->iStep;
 216     }else{
 217       pss->isNotEOF = 0;
 218     }
 219   }
 220   return pss->isNotEOF;
 221 }
 222
 223 /* series_cursor is a subclass of sqlite3_vtab_cursor which will
 224 ** serve as the underlying representation of a cursor that scans
 225 ** over rows of the result
 226 */
 227 typedef struct series_cursor series_cursor;
 228 struct series_cursor {
 229   sqlite3_vtab_cursor base;  /* Base class - must be first */
 230   SequenceSpec ss;           /* (this) Derived class data */
 231 };
 232
 233 /*
 234 ** The seriesConnect() method is invoked to create a new
 235 ** series_vtab that describes the generate_series virtual table.
 236 **
 237 ** Think of this routine as the constructor for series_vtab objects.
 238 **
 239 ** All this routine needs to do is:
 240 **
 241 **    (1) Allocate the series_vtab object and initialize all fields.
 242 **
 243 **    (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
 244 **        result set of queries against generate_series will look like.
 245 */
 246 static int seriesConnect(
 247   sqlite3 *db,
 248   void *pUnused,
 249   int argcUnused, const char *const*argvUnused,
 250   sqlite3_vtab **ppVtab,
 251   char **pzErrUnused
 252 ){
 253   sqlite3_vtab *pNew;
 254   int rc;
 255
 256 /* Column numbers */
 257 #define SERIES_COLUMN_VALUE 0
 258 #define SERIES_COLUMN_START 1
 259 #define SERIES_COLUMN_STOP  2
 260 #define SERIES_COLUMN_STEP  3
 261
 262   (void)pUnused;
 263   (void)argcUnused;
 264   (void)argvUnused;
 265   (void)pzErrUnused;
 266   rc = sqlite3_declare_vtab(db,
 267      "CREATE TABLE x(value,start hidden,stop hidden,step hidden)");
 268   if( rc==SQLITE_OK ){
 269     pNew = *ppVtab = sqlite3_malloc( sizeof(*pNew) );
 270     if( pNew==0 ) return SQLITE_NOMEM;
 271     memset(pNew, 0, sizeof(*pNew));
 272     sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
 273   }
 274   return rc;
 275 }
 276
 277 /*
 278 ** This method is the destructor for series_cursor objects.
 279 */
 280 static int seriesDisconnect(sqlite3_vtab *pVtab){
 281   sqlite3_free(pVtab);
 282   return SQLITE_OK;
 283 }
 284
 285 /*
 286 ** Constructor for a new series_cursor object.
 287 */
 288 static int seriesOpen(sqlite3_vtab *pUnused, sqlite3_vtab_cursor **ppCursor){
 289   series_cursor *pCur;
 290   (void)pUnused;
 291   pCur = sqlite3_malloc( sizeof(*pCur) );
 292   if( pCur==0 ) return SQLITE_NOMEM;
 293   memset(pCur, 0, sizeof(*pCur));
 294   *ppCursor = &pCur->base;
 295   return SQLITE_OK;
 296 }
 297
 298 /*
 299 ** Destructor for a series_cursor.
 300 */
 301 static int seriesClose(sqlite3_vtab_cursor *cur){
 302   sqlite3_free(cur);
 303   return SQLITE_OK;
 304 }
 305
 306
 307 /*
 308 ** Advance a series_cursor to its next row of output.
 309 */
 310 static int seriesNext(sqlite3_vtab_cursor *cur){
 311   series_cursor *pCur = (series_cursor*)cur;
 312   progressSequence( & pCur->ss );
 313   return SQLITE_OK;
 314 }
 315
 316 /*
 317 ** Return values of columns for the row at which the series_cursor
 318 ** is currently pointing.
 319 */
 320 static int seriesColumn(
 321   sqlite3_vtab_cursor *cur,   /* The cursor */
 322   sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
 323   int i                       /* Which column to return */
 324 ){
 325   series_cursor *pCur = (series_cursor*)cur;
 326   sqlite3_int64 x = 0;
 327   switch( i ){
 328     case SERIES_COLUMN_START:  x = pCur->ss.iBase; break;
 329     case SERIES_COLUMN_STOP:   x = pCur->ss.iTerm; break;
 330     case SERIES_COLUMN_STEP:   x = pCur->ss.iStep;   break;
 331     default:                   x = pCur->ss.iValueNow;  break;
 332   }
 333   sqlite3_result_int64(ctx, x);
 334   return SQLITE_OK;
 335 }
 336
 337 #ifndef LARGEST_UINT64
 338 #define LARGEST_UINT64 (0xffffffff|(((sqlite3_uint64)0xffffffff)<<32))
 339 #endif
 340
 341 /*
 342 ** Return the rowid for the current row, logically equivalent to n+1 where
 343 ** "n" is the ascending integer in the aforesaid production definition.
 344 */
 345 static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
 346   series_cursor *pCur = (series_cursor*)cur;
 347   sqlite3_uint64 n = pCur->ss.uSeqIndexNow;
 348   *pRowid = (sqlite3_int64)((n<LARGEST_UINT64)? n+1 : 0);
 349   return SQLITE_OK;
 350 }
 351
 352 /*
 353 ** Return TRUE if the cursor has been moved off of the last
 354 ** row of output.
 355 */
 356 static int seriesEof(sqlite3_vtab_cursor *cur){
 357   series_cursor *pCur = (series_cursor*)cur;
 358   return !pCur->ss.isNotEOF;
 359 }
 360
 361 /* True to cause run-time checking of the start=, stop=, and/or step=
 362 ** parameters.  The only reason to do this is for testing the
 363 ** constraint checking logic for virtual tables in the SQLite core.
 364 */
 365 #ifndef SQLITE_SERIES_CONSTRAINT_VERIFY
 366 # define SQLITE_SERIES_CONSTRAINT_VERIFY 0
 367 #endif
 368
 369 /*
 370 ** This method is called to "rewind" the series_cursor object back
 371 ** to the first row of output.  This method is always called at least
 372 ** once prior to any call to seriesColumn() or seriesRowid() or
 373 ** seriesEof().
 374 **
 375 ** The query plan selected by seriesBestIndex is passed in the idxNum
 376 ** parameter.  (idxStr is not used in this implementation.)  idxNum
 377 ** is a bitmask showing which constraints are available:
 378 **
 379 **   0x01:    start=VALUE
 380 **   0x02:    stop=VALUE
 381 **   0x04:    step=VALUE
 382 **   0x08:    descending order
 383 **   0x10:    ascending order
 384 **   0x20:    LIMIT  VALUE
 385 **   0x40:    OFFSET  VALUE
 386 **
 387 ** This routine should initialize the cursor and position it so that it
 388 ** is pointing at the first row, or pointing off the end of the table
 389 ** (so that seriesEof() will return true) if the table is empty.
 390 */
 391 static int seriesFilter(
 392   sqlite3_vtab_cursor *pVtabCursor,
 393   int idxNum, const char *idxStrUnused,
 394   int argc, sqlite3_value **argv
 395 ){
 396   series_cursor *pCur = (series_cursor *)pVtabCursor;
 397   int i = 0;
 398   (void)idxStrUnused;
 399   if( idxNum & 0x01 ){
 400     pCur->ss.iBase = sqlite3_value_int64(argv[i++]);
 401   }else{
 402     pCur->ss.iBase = 0;
 403   }
 404   if( idxNum & 0x02 ){
 405     pCur->ss.iTerm = sqlite3_value_int64(argv[i++]);
 406   }else{
 407     pCur->ss.iTerm = 0xffffffff;
 408   }
 409   if( idxNum & 0x04 ){
 410     pCur->ss.iStep = sqlite3_value_int64(argv[i++]);
 411     if( pCur->ss.iStep==0 ){
 412       pCur->ss.iStep = 1;
 413     }else if( pCur->ss.iStep<0 ){
 414       if( (idxNum & 0x10)==0 ) idxNum |= 0x08;
 415     }
 416   }else{
 417     pCur->ss.iStep = 1;
 418   }
 419   if( idxNum & 0x20 ){
 420     sqlite3_int64 iLimit = sqlite3_value_int64(argv[i++]);
 421     sqlite3_int64 iTerm;
 422     if( idxNum & 0x40 ){
 423       sqlite3_int64 iOffset = sqlite3_value_int64(argv[i++]);
 424       if( iOffset>0 ){
 425         pCur->ss.iBase += pCur->ss.iStep*iOffset;
 426       }
 427     }
 428     if( iLimit>=0 ){
 429       iTerm = pCur->ss.iBase + (iLimit - 1)*pCur->ss.iStep;
 430       if( pCur->ss.iStep<0 ){
 431         if( iTerm>pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
 432       }else{
 433         if( iTerm<pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
 434       }
 435     }
 436   }
 437   for(i=0; i<argc; i++){
 438     if( sqlite3_value_type(argv[i])==SQLITE_NULL ){
 439       /* If any of the constraints have a NULL value, then return no rows.
 440       ** See ticket https://www.sqlite.org/src/info/fac496b61722daf2 */
 441       pCur->ss.iBase = 1;
 442       pCur->ss.iTerm = 0;
 443       pCur->ss.iStep = 1;
 444       break;
 445     }
 446   }
 447   if( idxNum & 0x08 ){
 448     pCur->ss.isReversing = pCur->ss.iStep > 0;
 449   }else{
 450     pCur->ss.isReversing = pCur->ss.iStep < 0;
 451   }
 452   setupSequence( &pCur->ss );
 453   return SQLITE_OK;
 454 }
 455
 456 /*
 457 ** SQLite will invoke this method one or more times while planning a query
 458 ** that uses the generate_series virtual table.  This routine needs to create
 459 ** a query plan for each invocation and compute an estimated cost for that
 460 ** plan.
 461 **
 462 ** In this implementation idxNum is used to represent the
 463 ** query plan.  idxStr is unused.
 464 **
 465 ** The query plan is represented by bits in idxNum:
 466 **
 467 **   0x01  start = $value  -- constraint exists
 468 **   0x02  stop = $value   -- constraint exists
 469 **   0x04  step = $value   -- constraint exists
 470 **   0x08  output is in descending order
 471 **   0x10  output is in ascending order
 472 **   0x20  LIMIT $value    -- constraint exists
 473 **   0x40  OFFSET $value   -- constraint exists
 474 */
 475 static int seriesBestIndex(
 476   sqlite3_vtab *pVTab,
 477   sqlite3_index_info *pIdxInfo
 478 ){
 479   int i, j;              /* Loop over constraints */
 480   int idxNum = 0;        /* The query plan bitmask */
 481 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
 482   int bStartSeen = 0;    /* EQ constraint seen on the START column */
 483 #endif
 484   int unusableMask = 0;  /* Mask of unusable constraints */
 485   int nArg = 0;          /* Number of arguments that seriesFilter() expects */
 486   int aIdx[5];           /* Constraints on start, stop, step, LIMIT, OFFSET */
 487   const struct sqlite3_index_constraint *pConstraint;
 488
 489   /* This implementation assumes that the start, stop, and step columns
 490   ** are the last three columns in the virtual table. */
 491   assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 );
 492   assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 );
 493
 494   aIdx[0] = aIdx[1] = aIdx[2] = aIdx[3] = aIdx[4] = -1;
 495   pConstraint = pIdxInfo->aConstraint;
 496   for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
 497     int iCol;    /* 0 for start, 1 for stop, 2 for step */
 498     int iMask;   /* bitmask for those column */
 499     int op = pConstraint->op;
 500     if( op>=SQLITE_INDEX_CONSTRAINT_LIMIT
 501      && op<=SQLITE_INDEX_CONSTRAINT_OFFSET
 502     ){
 503       if( pConstraint->usable==0 ){
 504         /* do nothing */
 505       }else if( op==SQLITE_INDEX_CONSTRAINT_LIMIT ){
 506         aIdx[3] = i;
 507         idxNum |= 0x20;
 508       }else{
 509         assert( op==SQLITE_INDEX_CONSTRAINT_OFFSET );
 510         aIdx[4] = i;
 511         idxNum |= 0x40;
 512       }
 513       continue;
 514     }
 515     if( pConstraint->iColumn<SERIES_COLUMN_START ) continue;
 516     iCol = pConstraint->iColumn - SERIES_COLUMN_START;
 517     assert( iCol>=0 && iCol<=2 );
 518     iMask = 1 << iCol;
 519 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
 520     if( iCol==0 && op==SQLITE_INDEX_CONSTRAINT_EQ ){
 521       bStartSeen = 1;
 522     }
 523 #endif
 524     if( pConstraint->usable==0 ){
 525       unusableMask |=  iMask;
 526       continue;
 527     }else if( op==SQLITE_INDEX_CONSTRAINT_EQ ){
 528       idxNum |= iMask;
 529       aIdx[iCol] = i;
 530     }
 531   }
 532   if( aIdx[3]==0 ){
 533     /* Ignore OFFSET if LIMIT is omitted */
 534     idxNum &= ~0x60;
 535     aIdx[4] = 0;
 536   }
 537   for(i=0; i<5; i++){
 538     if( (j = aIdx[i])>=0 ){
 539       pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg;
 540       pIdxInfo->aConstraintUsage[j].omit =
 541          !SQLITE_SERIES_CONSTRAINT_VERIFY || i>=3;
 542     }
 543   }
 544   /* The current generate_column() implementation requires at least one
 545   ** argument (the START value).  Legacy versions assumed START=0 if the
 546   ** first argument was omitted.  Compile with -DZERO_ARGUMENT_GENERATE_SERIES
 547   ** to obtain the legacy behavior */
 548 #ifndef ZERO_ARGUMENT_GENERATE_SERIES
 549   if( !bStartSeen ){
 550     sqlite3_free(pVTab->zErrMsg);
 551     pVTab->zErrMsg = sqlite3_mprintf(
 552         "first argument to \"generate_series()\" missing or unusable");
 553     return SQLITE_ERROR;
 554   }
 555 #endif
 556   if( (unusableMask & ~idxNum)!=0 ){
 557     /* The start, stop, and step columns are inputs.  Therefore if there
 558     ** are unusable constraints on any of start, stop, or step then
 559     ** this plan is unusable */
 560     return SQLITE_CONSTRAINT;
 561   }
 562   if( (idxNum & 0x03)==0x03 ){
 563     /* Both start= and stop= boundaries are available.  This is the
 564     ** the preferred case */
 565     pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0));
 566     pIdxInfo->estimatedRows = 1000;
 567     if( pIdxInfo->nOrderBy>=1 && pIdxInfo->aOrderBy[0].iColumn==0 ){
 568       if( pIdxInfo->aOrderBy[0].desc ){
 569         idxNum |= 0x08;
 570       }else{
 571         idxNum |= 0x10;
 572       }
 573       pIdxInfo->orderByConsumed = 1;
 574     }
 575   }else if( (idxNum & 0x21)==0x21 ){
 576     /* We have start= and LIMIT */
 577     pIdxInfo->estimatedRows = 2500;
 578   }else{
 579     /* If either boundary is missing, we have to generate a huge span
 580     ** of numbers.  Make this case very expensive so that the query
 581     ** planner will work hard to avoid it. */
 582     pIdxInfo->estimatedRows = 2147483647;
 583   }
 584   pIdxInfo->idxNum = idxNum;
 585   return SQLITE_OK;
 586 }
 587
 588 /*
 589 ** This following structure defines all the methods for the
 590 ** generate_series virtual table.
 591 */
 592 static sqlite3_module seriesModule = {
 593   0,                         /* iVersion */
 594   0,                         /* xCreate */
 595   seriesConnect,             /* xConnect */
 596   seriesBestIndex,           /* xBestIndex */
 597   seriesDisconnect,          /* xDisconnect */
 598   0,                         /* xDestroy */
 599   seriesOpen,                /* xOpen - open a cursor */
 600   seriesClose,               /* xClose - close a cursor */
 601   seriesFilter,              /* xFilter - configure scan constraints */
 602   seriesNext,                /* xNext - advance a cursor */
 603   seriesEof,                 /* xEof - check for end of scan */
 604   seriesColumn,              /* xColumn - read data */
 605   seriesRowid,               /* xRowid - read data */
 606   0,                         /* xUpdate */
 607   0,                         /* xBegin */
 608   0,                         /* xSync */
 609   0,                         /* xCommit */
 610   0,                         /* xRollback */
 611   0,                         /* xFindMethod */
 612   0,                         /* xRename */
 613   0,                         /* xSavepoint */
 614   0,                         /* xRelease */
 615   0,                         /* xRollbackTo */
 616   0,                         /* xShadowName */
 617   0                          /* xIntegrity */
 618 };
 619
 620 #endif /* SQLITE_OMIT_VIRTUALTABLE */
 621
 622 #ifdef _WIN32
 623 __declspec(dllexport)
 624 #endif
 625 int sqlite3_series_init(
 626   sqlite3 *db,
 627   char **pzErrMsg,
 628   const sqlite3_api_routines *pApi
 629 ){
 630   int rc = SQLITE_OK;
 631   SQLITE_EXTENSION_INIT2(pApi);
 632 #ifndef SQLITE_OMIT_VIRTUALTABLE
 633   if( sqlite3_libversion_number()<3008012 && pzErrMsg!=0 ){
 634     *pzErrMsg = sqlite3_mprintf(
 635         "generate_series() requires SQLite 3.8.12 or later");
 636     return SQLITE_ERROR;
 637   }
 638   rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0);
 639 #endif
 640   return rc;
 641 }