SQLite

** start, stop, and step columns, and if present, it uses those constraints
** to bound the sequence of generated values.  If the equality constraints
** are missing, it uses 0 for start, 4294967295 for stop, and 1 for step.
** xBestIndex returns a small cost when both start and stop are available,
** and a very large cost if either start or stop are unavailable.  This
** encourages the query planner to order joins such that the bounds of the
** series are well-defined.
**
** Update on 2024-08-22:
** xBestIndex now also looks for equality and inequality constraints against
** the value column and uses those constraints as additional bounds against
** the sequence range.  Thus, a query like this:
**
**     SELECT value FROM generate_series($SA,$EA)
**      WHERE value BETWEEN $SB AND $EB;
**
** Is logically the same as:
**
**     SELECT value FROM generate_series(max($SA,$SB),min($EA,$EB));
**
** Constraints on the value column can server as substitutes for constraints
** on the hidden start and stop columns.  So, the following two queries
** are equivalent:
**
**     SELECT value FROM generate_series($S,$E);
**     SELECT value FROM generate_series WHERE value BETWEEN $S and $E;
**
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>
#include <limits.h>

  }
  return smBase + ((sqlite3_int64)ix)*smStep;
}

typedef unsigned char u8;

typedef struct SequenceSpec {
  sqlite3_int64 iOBase;        /* Original starting value ("start") */
  sqlite3_int64 iOTerm;        /* Original terminal value ("stop") */
  sqlite3_int64 iBase;         /* Starting value to actually use */
  sqlite3_int64 iTerm;         /* Terminal value to actually use */
  sqlite3_int64 iStep;         /* Increment ("step") */
  sqlite3_uint64 uSeqIndexMax; /* maximum sequence index (aka "n") */
  sqlite3_uint64 uSeqIndexNow; /* Current index during generation */
  sqlite3_int64 iValueNow;     /* Current value during generation */
  u8 isNotEOF;                 /* Sequence generation not exhausted */
  u8 isReversing;              /* Sequence is being reverse generated */
} SequenceSpec;

  sqlite3_vtab_cursor *cur,   /* The cursor */
  sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
  int i                       /* Which column to return */
){
  series_cursor *pCur = (series_cursor*)cur;
  sqlite3_int64 x = 0;
  switch( i ){
    case SERIES_COLUMN_START:  x = pCur->ss.iOBase;     break;
    case SERIES_COLUMN_STOP:   x = pCur->ss.iOTerm;     break;
    case SERIES_COLUMN_STEP:   x = pCur->ss.iStep;      break;
    default:                   x = pCur->ss.iValueNow;  break;
  }
  sqlite3_result_int64(ctx, x);
  return SQLITE_OK;
}

#ifndef LARGEST_UINT64
#define LARGEST_INT64  (0xffffffff|(((sqlite3_int64)0x7fffffff)<<32))
#define LARGEST_UINT64 (0xffffffff|(((sqlite3_uint64)0xffffffff)<<32))
#define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)
#endif

/*
** Return the rowid for the current row, logically equivalent to n+1 where
** "n" is the ascending integer in the aforesaid production definition.
*/
static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){

** once prior to any call to seriesColumn() or seriesRowid() or
** seriesEof().
**
** The query plan selected by seriesBestIndex is passed in the idxNum
** parameter.  (idxStr is not used in this implementation.)  idxNum
** is a bitmask showing which constraints are available:
**
**   0x0001:    start=VALUE
**   0x0002:    stop=VALUE
**   0x0004:    step=VALUE
**   0x0008:    descending order
**   0x0010:    ascending order
**   0x0020:    LIMIT  VALUE
**   0x0040:    OFFSET  VALUE
**   0x0080:    value=VALUE
**   0x0100:    value>=VALUE
**   0x0200:    value>VALUE
**   0x1000:    value<=VALUE
**   0x2000:    value<VALUE
**
** This routine should initialize the cursor and position it so that it
** is pointing at the first row, or pointing off the end of the table
** (so that seriesEof() will return true) if the table is empty.
*/
static int seriesFilter(
  sqlite3_vtab_cursor *pVtabCursor,
  int idxNum, const char *idxStrUnused,
  int argc, sqlite3_value **argv
){
  series_cursor *pCur = (series_cursor *)pVtabCursor;
  int i = 0;
  int returnNoRows = 0;
  sqlite3_int64 iMin = SMALLEST_INT64;
  sqlite3_int64 iMax = LARGEST_INT64;
  sqlite3_int64 iLimit = 0;
  sqlite3_int64 iOffset = 0;

  (void)idxStrUnused;
  if( idxNum & 0x01 ){
    pCur->ss.iBase = sqlite3_value_int64(argv[i++]);
  }else{
    pCur->ss.iBase = 0;
  }
  if( idxNum & 0x02 ){

      pCur->ss.iStep = 1;
    }else if( pCur->ss.iStep<0 ){
      if( (idxNum & 0x10)==0 ) idxNum |= 0x08;
    }
  }else{
    pCur->ss.iStep = 1;
  }

  /* If there are constraints on the value column but there are
  ** no constraints on  the start, stop, and step columns, then
  ** initialize the default range to be the entire range of 64-bit signed
  ** integers.  This range will contracted by the value column constraints
  ** further below.
  */
  if( (idxNum & 0x05)==0 && (idxNum & 0x0380)!=0 ){
    pCur->ss.iBase = SMALLEST_INT64;
  }
  if( (idxNum & 0x06)==0 && (idxNum & 0x3080)!=0 ){
    pCur->ss.iTerm = LARGEST_INT64;
  }
  pCur->ss.iOBase = pCur->ss.iBase;
  pCur->ss.iOTerm = pCur->ss.iTerm;

  /* Extract the LIMIT and OFFSET values, but do not apply them yet.
  ** The range must first be constrained by the limits on value.
  */
  if( idxNum & 0x20 ){
    iLimit = sqlite3_value_int64(argv[i++]);
    if( idxNum & 0x40 ){
      iOffset = sqlite3_value_int64(argv[i++]);
    }
  }

  if( idxNum & 0x3380 ){
    /* Extract the maximum range of output values determined by
    ** constraints on the "value" column.
    */
    if( idxNum & 0x0080 ){
      iMin = iMax = sqlite3_value_int64(argv[i++]);
    }else{
      if( idxNum & 0x0300 ){
        iMin = sqlite3_value_int64(argv[i++]);
        if( idxNum & 0x0200 ){
          if( iMin==LARGEST_INT64 ){
            returnNoRows = 1;
          }else{
            iMin++;
          }
        }
      }
      if( idxNum & 0x3000 ){
        iMax = sqlite3_value_int64(argv[i++]);
        if( idxNum & 0x2000 ){
          if( iMax==SMALLEST_INT64 ){
            returnNoRows = 1;
          }else{
            iMax--;
          }
        }
      }
      if( iMin>iMax ){
        returnNoRows = 1;
      }
    }

    /* Try to reduce the range of values to be generated based on
    ** constraints on the "value" column.
    */
    if( pCur->ss.iStep>0 ){
      sqlite3_int64 szStep = pCur->ss.iStep;
      if( pCur->ss.iBase<iMin ){
        sqlite3_uint64 d = iMin - pCur->ss.iBase;
        pCur->ss.iBase += ((d+szStep-1)/szStep)*szStep;
      }
      if( pCur->ss.iTerm>iMax ){
        sqlite3_uint64 d = pCur->ss.iTerm - iMax;
        pCur->ss.iTerm -= ((d+szStep-1)/szStep)*szStep;
      }
    }else{
      sqlite3_int64 szStep = -pCur->ss.iStep;
      assert( szStep>0 );
      if( pCur->ss.iBase>iMax ){
        sqlite3_uint64 d = pCur->ss.iBase - iMax;
        pCur->ss.iBase -= ((d+szStep-1)/szStep)*szStep;
      }
      if( pCur->ss.iTerm<iMin ){
        sqlite3_uint64 d = iMin - pCur->ss.iTerm;
        pCur->ss.iTerm += ((d+szStep-1)/szStep)*szStep;
      }
    }
  }

  /* Apply LIMIT and OFFSET constraints, if any */
  if( idxNum & 0x20 ){
    if( iOffset>0 ){
      pCur->ss.iBase += pCur->ss.iStep*iOffset;
    }

    if( iLimit>=0 ){
      sqlite3_int64 iTerm;
      iTerm = pCur->ss.iBase + (iLimit - 1)*pCur->ss.iStep;
      if( pCur->ss.iStep<0 ){
        if( iTerm>pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
      }else{
        if( iTerm<pCur->ss.iTerm ) pCur->ss.iTerm = iTerm;
      }
    }
  }


  for(i=0; i<argc; i++){
    if( sqlite3_value_type(argv[i])==SQLITE_NULL ){
      /* If any of the constraints have a NULL value, then return no rows.
      ** See ticket https://www.sqlite.org/src/info/fac496b61722daf2 */
      returnNoRows = 1;


      break;
    }
  }
  if( returnNoRows ){
    pCur->ss.iBase = 1;
    pCur->ss.iTerm = 0;
    pCur->ss.iStep = 1;
  }
  if( idxNum & 0x08 ){
    pCur->ss.isReversing = pCur->ss.iStep > 0;
  }else{
    pCur->ss.isReversing = pCur->ss.iStep < 0;
  }
  setupSequence( &pCur->ss );
  return SQLITE_OK;
}

/*
** SQLite will invoke this method one or more times while planning a query
** that uses the generate_series virtual table.  This routine needs to create
** a query plan for each invocation and compute an estimated cost for that
** plan.
**
** In this implementation idxNum is used to represent the
** query plan.  idxStr is unused.
**
** The query plan is represented by bits in idxNum:
**
**   0x0001  start = $num
**   0x0002  stop = $num
**   0x0004  step = $num
**   0x0008  output is in descending order
**   0x0010  output is in ascending order
**   0x0020  LIMIT $num
**   0x0040  OFFSET $num
**   0x0080  value = $num
**   0x0100  value >= $num
**   0x0200  value > $num
**   0x1000  value <= $num
**   0x2000  value < $num
**
** Only one of 0x0100 or 0x0200 will be returned.  Similarly, only
** one of 0x1000 or 0x2000 will be returned.  If the 0x0080 is set, then
** none of the 0xff00 bits will be set.
**
** The order of parameters passed to xFilter is as follows:
**
**    * The argument to start= if bit 0x0001 is in the idxNum mask
**    * The argument to stop= if bit 0x0002 is in the idxNum mask
**    * The argument to step= if bit 0x0004 is in the idxNum mask
**    * The argument to LIMIT if bit 0x0020 is in the idxNum mask
**    * The argument to OFFSET if bit 0x0040 is in the idxNum mask
**    * The argument to value=, or value>= or value> if any of
**      bits 0x0380 are in the idxNum mask
**    * The argument to value<= or value< if either of bits 0x3000
**      are in the mask
**
*/
static int seriesBestIndex(
  sqlite3_vtab *pVTab,
  sqlite3_index_info *pIdxInfo
){
  int i, j;              /* Loop over constraints */
  int idxNum = 0;        /* The query plan bitmask */
#ifndef ZERO_ARGUMENT_GENERATE_SERIES
  int bStartSeen = 0;    /* EQ constraint seen on the START column */
#endif
  int unusableMask = 0;  /* Mask of unusable constraints */
  int nArg = 0;          /* Number of arguments that seriesFilter() expects */
  int aIdx[7];           /* Constraints on start, stop, step, LIMIT, OFFSET,
                         ** and value.  aIdx[5] covers value=, value>=, and
                         ** value>,  aIdx[6] covers value<= and value< */
  const struct sqlite3_index_constraint *pConstraint;

  /* This implementation assumes that the start, stop, and step columns
  ** are the last three columns in the virtual table. */
  assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 );
  assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 );

  aIdx[0] = aIdx[1] = aIdx[2] = aIdx[3] = aIdx[4] = aIdx[5] = aIdx[6] = -1;
  pConstraint = pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){
    int iCol;    /* 0 for start, 1 for stop, 2 for step */
    int iMask;   /* bitmask for those column */
    int op = pConstraint->op;
    if( op>=SQLITE_INDEX_CONSTRAINT_LIMIT
     && op<=SQLITE_INDEX_CONSTRAINT_OFFSET
    ){
      if( pConstraint->usable==0 ){
        /* do nothing */
      }else if( op==SQLITE_INDEX_CONSTRAINT_LIMIT ){
        aIdx[3] = i;
        idxNum |= 0x20;
      }else{
        assert( op==SQLITE_INDEX_CONSTRAINT_OFFSET );
        aIdx[4] = i;
        idxNum |= 0x40;
      }
      continue;
    }
    if( pConstraint->iColumn==SERIES_COLUMN_VALUE ){
      switch( op ){
        case SQLITE_INDEX_CONSTRAINT_EQ:
        case SQLITE_INDEX_CONSTRAINT_IS: {
          idxNum |=  0x0080;
          idxNum &= ~0x3300;
          aIdx[5] = i;
          aIdx[6] = -1;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_GE: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x0100;
          idxNum &= ~0x0200;
          aIdx[5] = i;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_GT: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x0200;
          idxNum &= ~0x0100;
          aIdx[5] = i;
          bStartSeen = 1;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_LE: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x1000;
          idxNum &= ~0x2000;
          aIdx[6] = i;
          break;
        }
        case SQLITE_INDEX_CONSTRAINT_LT: {
          if( idxNum & 0x0080 ) break;
          idxNum |=  0x2000;
          idxNum &= ~0x1000;
          aIdx[6] = i;
          break;
        }
      }
      continue;
    }
    iCol = pConstraint->iColumn - SERIES_COLUMN_START;
    assert( iCol>=0 && iCol<=2 );
    iMask = 1 << iCol;
#ifndef ZERO_ARGUMENT_GENERATE_SERIES
    if( iCol==0 && op==SQLITE_INDEX_CONSTRAINT_EQ ){
      bStartSeen = 1;
    }

    }
  }
  if( aIdx[3]==0 ){
    /* Ignore OFFSET if LIMIT is omitted */
    idxNum &= ~0x60;
    aIdx[4] = 0;
  }
  for(i=0; i<7; i++){
    if( (j = aIdx[i])>=0 ){
      pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg;
      pIdxInfo->aConstraintUsage[j].omit =
         !SQLITE_SERIES_CONSTRAINT_VERIFY || i>=3;
    }
  }
  /* The current generate_column() implementation requires at least one

  }else{
    /* If either boundary is missing, we have to generate a huge span
    ** of numbers.  Make this case very expensive so that the query
    ** planner will work hard to avoid it. */
    pIdxInfo->estimatedRows = 2147483647;
  }
  pIdxInfo->idxNum = idxNum;
#ifdef SQLITE_INDEX_SCAN_HEX
  pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_HEX;
#endif
  return SQLITE_OK;
}

/*
** This following structure defines all the methods for the 
** generate_series virtual table.
*/

  QUERY PLAN
  `--MERGE (UNION ALL)
     |--LEFT
     |  `--MERGE (UNION ALL)
     |     |--LEFT
     |     |  `--MERGE (UNION ALL)
     |     |     |--LEFT
     |     |     |  `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     |     `--RIGHT
     |     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     `--RIGHT
     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     `--RIGHT
        `--MERGE (UNION ALL)
           |--LEFT
           |  `--MERGE (UNION ALL)
           |     |--LEFT
           |     |  `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
           |     `--RIGHT
           |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
           `--RIGHT
              `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
}

# Same test with the blanced-merge optimization
# disabled.  Should give the exact same answer.
#
optimization_control db balanced-merge off
db cache flush

     |     |--LEFT
     |     |  `--MERGE (UNION ALL)
     |     |     |--LEFT
     |     |     |  `--MERGE (UNION ALL)
     |     |     |     |--LEFT
     |     |     |     |  `--MERGE (UNION ALL)
     |     |     |     |     |--LEFT
     |     |     |     |     |  `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     |     |     |     `--RIGHT
     |     |     |     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     |     |     `--RIGHT
     |     |     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     |     `--RIGHT
     |     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     |     `--RIGHT
     |        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     `--RIGHT
        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
}

finish_test

  SELECT DISTINCT value FROM generate_series(1,x), t1 ORDER BY 1;
} {1 2 3}

do_eqp_test tabfunc01-3.10 {
  SELECT value FROM generate_series(1,10) ORDER BY value;
} {
  QUERY PLAN
  `--SCAN generate_series VIRTUAL TABLE INDEX 0x13:
}
do_eqp_test tabfunc01-3.11 {
  SELECT value FROM generate_series(1,10) ORDER BY +value;
} {
  QUERY PLAN
  |--SCAN generate_series VIRTUAL TABLE INDEX 0x3:
  `--USE TEMP B-TREE FOR ORDER BY
}
do_eqp_test tabfunc01-3.12 {
  SELECT value FROM generate_series(1,10) ORDER BY value, stop;
} {
  QUERY PLAN
  `--SCAN generate_series VIRTUAL TABLE INDEX 0x13:
}
do_eqp_test tabfunc01-3.13 {
  SELECT value FROM generate_series(1,10) ORDER BY stop, value;
} {
  QUERY PLAN
  |--SCAN generate_series VIRTUAL TABLE INDEX 0x3:
  `--USE TEMP B-TREE FOR ORDER BY
}


do_eqp_test tabfunc01-3.20 {
  WITH t1(a) AS (
    SELECT value FROM generate_series(0,10,2)
    UNION ALL
    SELECT value FROM generate_series(9,18,3)
  )
  SELECT * FROM t1 ORDER BY a;
} {
  QUERY PLAN
  `--MERGE (UNION ALL)
     |--LEFT
     |  `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
     `--RIGHT
        `--SCAN generate_series VIRTUAL TABLE INDEX 0x17:
}
  

# Eponymous virtual table exists in all schemas.
#
do_execsql_test tabfunc01-4.1 {
  SELECT * FROM main.generate_series(1,4)

proc query_plan_graph {sql} {
  db eval "EXPLAIN QUERY PLAN $sql" {
    set dx($id) $detail
    lappend cx($parent) $id
  }
  set a "\n  QUERY PLAN\n"
  append a [append_graph "  " dx cx 0]
  regsub -all {SUBQUERY 0x[A-F0-9]+\y} $a {SUBQUERY xxxxxx} a
  regsub -all {(MATERIALIZE|CO-ROUTINE|SUBQUERY) \d+\y} $a {\1 xxxxxx} a
  regsub -all {\((join|subquery)-\d+\)} $a {(\1-xxxxxx)} a
  return $a
}

# Helper routine for [query_plan_graph SQL]:
#