| 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. In other words, 0, 5, 10, 15, ..., 90, 95, 100. There are a total |
| 34 |
** of 21 rows. |
| 35 |
** |
| 36 |
** SELECT * FROM generate_series(0,100); |
| 37 |
** |
| 38 |
** Integers from 0 through 100 with a step size of 1. 101 rows. |
| 39 |
** |
| 40 |
** SELECT * FROM generate_series(20) LIMIT 10; |
| 41 |
** |
| 42 |
** Integers 20 through 29. 10 rows. |
| 43 |
** |
| 44 |
** SELECT * FROM generate_series(0,-100,-5); |
| 45 |
** |
| 46 |
** Integers 0 -5 -10 ... -100. 21 rows. |
| 47 |
** |
| 48 |
** SELECT * FROM generate_series(0,-1); |
| 49 |
** |
| 50 |
** Empty sequence. |
| 51 |
** |
| 52 |
** HOW IT WORKS |
| 53 |
** |
| 54 |
** The generate_series "function" is really a virtual table with the |
| 55 |
** following schema: |
| 56 |
** |
| 57 |
** CREATE TABLE generate_series( |
| 58 |
** value, |
| 59 |
** start HIDDEN, |
| 60 |
** stop HIDDEN, |
| 61 |
** step HIDDEN |
| 62 |
** ); |
| 63 |
** |
| 64 |
** The virtual table also has a rowid which is an alias for the value. |
| 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 |
** Update on 2024-08-22: |
| 95 |
** xBestIndex now also looks for equality and inequality constraints against |
| 96 |
** the value column and uses those constraints as additional bounds against |
| 97 |
** the sequence range. Thus, a query like this: |
| 98 |
** |
| 99 |
** SELECT value FROM generate_series($SA,$EA) |
| 100 |
** WHERE value BETWEEN $SB AND $EB; |
| 101 |
** |
| 102 |
** Is logically the same as: |
| 103 |
** |
| 104 |
** SELECT value FROM generate_series(max($SA,$SB),min($EA,$EB)); |
| 105 |
** |
| 106 |
** Constraints on the value column can server as substitutes for constraints |
| 107 |
** on the hidden start and stop columns. So, the following two queries |
| 108 |
** are equivalent: |
| 109 |
** |
| 110 |
** SELECT value FROM generate_series($S,$E); |
| 111 |
** SELECT value FROM generate_series WHERE value BETWEEN $S and $E; |
| 112 |
** |
| 113 |
*/ |
| 114 |
#include "sqlite3ext.h" |
| 115 |
SQLITE_EXTENSION_INIT1 |
| 116 |
#include <assert.h> |
| 117 |
#include <string.h> |
| 118 |
#include <limits.h> |
| 119 |
#include <math.h> |
| 120 |
|
| 121 |
#ifndef SQLITE_OMIT_VIRTUALTABLE |
| 122 |
|
| 123 |
/* series_cursor is a subclass of sqlite3_vtab_cursor which will |
| 124 |
** serve as the underlying representation of a cursor that scans |
| 125 |
** over rows of the result. |
| 126 |
** |
| 127 |
** iOBase, iOTerm, and iOStep are the original values of the |
| 128 |
** start=, stop=, and step= constraints on the query. These are |
| 129 |
** the values reported by the start, stop, and step columns of the |
| 130 |
** virtual table. |
| 131 |
** |
| 132 |
** iBase, iTerm, iStep, and bDescp are the actual values used to generate |
| 133 |
** the sequence. These might be different from the iOxxxx values. |
| 134 |
** For example in |
| 135 |
** |
| 136 |
** SELECT value FROM generate_series(1,11,2) |
| 137 |
** WHERE value BETWEEN 4 AND 8; |
| 138 |
** |
| 139 |
** The iOBase is 1, but the iBase is 5. iOTerm is 11 but iTerm is 7. |
| 140 |
** Another example: |
| 141 |
** |
| 142 |
** SELECT value FROM generate_series(1,15,3) ORDER BY value DESC; |
| 143 |
** |
| 144 |
** The cursor initialization for the above query is: |
| 145 |
** |
| 146 |
** iOBase = 1 iBase = 13 |
| 147 |
** iOTerm = 15 iTerm = 1 |
| 148 |
** iOStep = 3 iStep = 3 bDesc = 1 |
| 149 |
** |
| 150 |
** The actual step size is unsigned so that can have a value of |
| 151 |
** +9223372036854775808 which is needed for querys like this: |
| 152 |
** |
| 153 |
** SELECT value |
| 154 |
** FROM generate_series(9223372036854775807, |
| 155 |
** -9223372036854775808, |
| 156 |
** -9223372036854775808) |
| 157 |
** ORDER BY value ASC; |
| 158 |
** |
| 159 |
** The setup for the previous query will be: |
| 160 |
** |
| 161 |
** iOBase = 9223372036854775807 iBase = -1 |
| 162 |
** iOTerm = -9223372036854775808 iTerm = 9223372036854775807 |
| 163 |
** iOStep = -9223372036854775808 iStep = 9223372036854775808 bDesc = 0 |
| 164 |
*/ |
| 165 |
typedef unsigned char u8; |
| 166 |
typedef struct series_cursor series_cursor; |
| 167 |
struct series_cursor { |
| 168 |
sqlite3_vtab_cursor base; /* Base class - must be first */ |
| 169 |
sqlite3_int64 iOBase; /* Original starting value ("start") */ |
| 170 |
sqlite3_int64 iOTerm; /* Original terminal value ("stop") */ |
| 171 |
sqlite3_int64 iOStep; /* Original step value */ |
| 172 |
sqlite3_int64 iBase; /* Starting value to actually use */ |
| 173 |
sqlite3_int64 iTerm; /* Terminal value to actually use */ |
| 174 |
sqlite3_uint64 iStep; /* The step size */ |
| 175 |
sqlite3_int64 iValue; /* Current value */ |
| 176 |
u8 bDesc; /* iStep is really negative */ |
| 177 |
u8 bDone; /* True if stepped past last element */ |
| 178 |
}; |
| 179 |
|
| 180 |
/* |
| 181 |
** Computed the difference between two 64-bit signed integers using a |
| 182 |
** convoluted computation designed to work around the silly restriction |
| 183 |
** against signed integer overflow in C. |
| 184 |
*/ |
| 185 |
static sqlite3_uint64 span64(sqlite3_int64 a, sqlite3_int64 b){ |
| 186 |
assert( a>=b ); |
| 187 |
return (*(sqlite3_uint64*)&a) - (*(sqlite3_uint64*)&b); |
| 188 |
} |
| 189 |
|
| 190 |
/* |
| 191 |
** Add or substract an unsigned 64-bit integer from a signed 64-bit integer |
| 192 |
** and return the new signed 64-bit integer. |
| 193 |
*/ |
| 194 |
static sqlite3_int64 add64(sqlite3_int64 a, sqlite3_uint64 b){ |
| 195 |
sqlite3_uint64 x = *(sqlite3_uint64*)&a; |
| 196 |
x += b; |
| 197 |
return *(sqlite3_int64*)&x; |
| 198 |
} |
| 199 |
static sqlite3_int64 sub64(sqlite3_int64 a, sqlite3_uint64 b){ |
| 200 |
sqlite3_uint64 x = *(sqlite3_uint64*)&a; |
| 201 |
x -= b; |
| 202 |
return *(sqlite3_int64*)&x; |
| 203 |
} |
| 204 |
|
| 205 |
/* |
| 206 |
** The seriesConnect() method is invoked to create a new |
| 207 |
** series_vtab that describes the generate_series virtual table. |
| 208 |
** |
| 209 |
** Think of this routine as the constructor for series_vtab objects. |
| 210 |
** |
| 211 |
** All this routine needs to do is: |
| 212 |
** |
| 213 |
** (1) Allocate the series_vtab object and initialize all fields. |
| 214 |
** |
| 215 |
** (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the |
| 216 |
** result set of queries against generate_series will look like. |
| 217 |
*/ |
| 218 |
static int seriesConnect( |
| 219 |
sqlite3 *db, |
| 220 |
void *pUnused, |
| 221 |
int argcUnused, const char *const*argvUnused, |
| 222 |
sqlite3_vtab **ppVtab, |
| 223 |
char **pzErrUnused |
| 224 |
){ |
| 225 |
sqlite3_vtab *pNew; |
| 226 |
int rc; |
| 227 |
|
| 228 |
/* Column numbers */ |
| 229 |
#define SERIES_COLUMN_ROWID (-1) |
| 230 |
#define SERIES_COLUMN_VALUE 0 |
| 231 |
#define SERIES_COLUMN_START 1 |
| 232 |
#define SERIES_COLUMN_STOP 2 |
| 233 |
#define SERIES_COLUMN_STEP 3 |
| 234 |
|
| 235 |
(void)pUnused; |
| 236 |
(void)argcUnused; |
| 237 |
(void)argvUnused; |
| 238 |
(void)pzErrUnused; |
| 239 |
rc = sqlite3_declare_vtab(db, |
| 240 |
"CREATE TABLE x(value,start hidden,stop hidden,step hidden)"); |
| 241 |
if( rc==SQLITE_OK ){ |
| 242 |
pNew = *ppVtab = sqlite3_malloc64( sizeof(*pNew) ); |
| 243 |
if( pNew==0 ) return SQLITE_NOMEM; |
| 244 |
memset(pNew, 0, sizeof(*pNew)); |
| 245 |
sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS); |
| 246 |
} |
| 247 |
return rc; |
| 248 |
} |
| 249 |
|
| 250 |
/* |
| 251 |
** This method is the destructor for series_cursor objects. |
| 252 |
*/ |
| 253 |
static int seriesDisconnect(sqlite3_vtab *pVtab){ |
| 254 |
sqlite3_free(pVtab); |
| 255 |
return SQLITE_OK; |
| 256 |
} |
| 257 |
|
| 258 |
/* |
| 259 |
** Constructor for a new series_cursor object. |
| 260 |
*/ |
| 261 |
static int seriesOpen(sqlite3_vtab *pUnused, sqlite3_vtab_cursor **ppCursor){ |
| 262 |
series_cursor *pCur; |
| 263 |
(void)pUnused; |
| 264 |
pCur = sqlite3_malloc64( sizeof(*pCur) ); |
| 265 |
if( pCur==0 ) return SQLITE_NOMEM; |
| 266 |
memset(pCur, 0, sizeof(*pCur)); |
| 267 |
*ppCursor = &pCur->base; |
| 268 |
return SQLITE_OK; |
| 269 |
} |
| 270 |
|
| 271 |
/* |
| 272 |
** Destructor for a series_cursor. |
| 273 |
*/ |
| 274 |
static int seriesClose(sqlite3_vtab_cursor *cur){ |
| 275 |
sqlite3_free(cur); |
| 276 |
return SQLITE_OK; |
| 277 |
} |
| 278 |
|
| 279 |
|
| 280 |
/* |
| 281 |
** Advance a series_cursor to its next row of output. |
| 282 |
*/ |
| 283 |
static int seriesNext(sqlite3_vtab_cursor *cur){ |
| 284 |
series_cursor *pCur = (series_cursor*)cur; |
| 285 |
if( pCur->iValue==pCur->iTerm ){ |
| 286 |
pCur->bDone = 1; |
| 287 |
}else if( pCur->bDesc ){ |
| 288 |
pCur->iValue = sub64(pCur->iValue, pCur->iStep); |
| 289 |
assert( pCur->iValue>=pCur->iTerm ); |
| 290 |
}else{ |
| 291 |
pCur->iValue = add64(pCur->iValue, pCur->iStep); |
| 292 |
assert( pCur->iValue<=pCur->iTerm ); |
| 293 |
} |
| 294 |
return SQLITE_OK; |
| 295 |
} |
| 296 |
|
| 297 |
/* |
| 298 |
** Return values of columns for the row at which the series_cursor |
| 299 |
** is currently pointing. |
| 300 |
*/ |
| 301 |
static int seriesColumn( |
| 302 |
sqlite3_vtab_cursor *cur, /* The cursor */ |
| 303 |
sqlite3_context *ctx, /* First argument to sqlite3_result_...() */ |
| 304 |
int i /* Which column to return */ |
| 305 |
){ |
| 306 |
series_cursor *pCur = (series_cursor*)cur; |
| 307 |
sqlite3_int64 x = 0; |
| 308 |
switch( i ){ |
| 309 |
case SERIES_COLUMN_START: x = pCur->iOBase; break; |
| 310 |
case SERIES_COLUMN_STOP: x = pCur->iOTerm; break; |
| 311 |
case SERIES_COLUMN_STEP: x = pCur->iOStep; break; |
| 312 |
default: x = pCur->iValue; break; |
| 313 |
} |
| 314 |
sqlite3_result_int64(ctx, x); |
| 315 |
return SQLITE_OK; |
| 316 |
} |
| 317 |
|
| 318 |
#ifndef LARGEST_UINT64 |
| 319 |
#define LARGEST_INT64 ((sqlite3_int64)0x7fffffffffffffffLL) |
| 320 |
#define LARGEST_UINT64 ((sqlite3_uint64)0xffffffffffffffffULL) |
| 321 |
#define SMALLEST_INT64 ((sqlite3_int64)0x8000000000000000LL) |
| 322 |
#endif |
| 323 |
|
| 324 |
/* |
| 325 |
** The rowid is the same as the value. |
| 326 |
*/ |
| 327 |
static int seriesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ |
| 328 |
series_cursor *pCur = (series_cursor*)cur; |
| 329 |
*pRowid = pCur->iValue; |
| 330 |
return SQLITE_OK; |
| 331 |
} |
| 332 |
|
| 333 |
/* |
| 334 |
** Return TRUE if the cursor has been moved off of the last |
| 335 |
** row of output. |
| 336 |
*/ |
| 337 |
static int seriesEof(sqlite3_vtab_cursor *cur){ |
| 338 |
series_cursor *pCur = (series_cursor*)cur; |
| 339 |
return pCur->bDone; |
| 340 |
} |
| 341 |
|
| 342 |
/* True to cause run-time checking of the start=, stop=, and/or step= |
| 343 |
** parameters. The only reason to do this is for testing the |
| 344 |
** constraint checking logic for virtual tables in the SQLite core. |
| 345 |
*/ |
| 346 |
#ifndef SQLITE_SERIES_CONSTRAINT_VERIFY |
| 347 |
# define SQLITE_SERIES_CONSTRAINT_VERIFY 0 |
| 348 |
#endif |
| 349 |
|
| 350 |
/* |
| 351 |
** Return the number of steps between pCur->iBase and pCur->iTerm if |
| 352 |
** the step width is pCur->iStep. |
| 353 |
*/ |
| 354 |
static sqlite3_uint64 seriesSteps(series_cursor *pCur){ |
| 355 |
if( pCur->bDesc ){ |
| 356 |
assert( pCur->iBase >= pCur->iTerm ); |
| 357 |
return span64(pCur->iBase, pCur->iTerm)/pCur->iStep; |
| 358 |
}else{ |
| 359 |
assert( pCur->iBase <= pCur->iTerm ); |
| 360 |
return span64(pCur->iTerm, pCur->iBase)/pCur->iStep; |
| 361 |
} |
| 362 |
} |
| 363 |
|
| 364 |
#if defined(SQLITE_ENABLE_MATH_FUNCTIONS) || defined(_WIN32) |
| 365 |
/* |
| 366 |
** Case 1 (the most common case): |
| 367 |
** The standard math library is available so use ceil() and floor() from there. |
| 368 |
*/ |
| 369 |
static double seriesCeil(double r){ return ceil(r); } |
| 370 |
static double seriesFloor(double r){ return floor(r); } |
| 371 |
#elif defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 372 |
/* |
| 373 |
** Case 2 (2nd most common): Use GCC/Clang builtins |
| 374 |
*/ |
| 375 |
static double seriesCeil(double r){ return __builtin_ceil(r); } |
| 376 |
static double seriesFloor(double r){ return __builtin_floor(r); } |
| 377 |
#else |
| 378 |
/* |
| 379 |
** Case 3 (rarely happens): Use home-grown ceil() and floor() routines. |
| 380 |
*/ |
| 381 |
static double seriesCeil(double r){ |
| 382 |
sqlite3_int64 x; |
| 383 |
if( r!=r ) return r; |
| 384 |
if( r<=(-4503599627370496.0) ) return r; |
| 385 |
if( r>=(+4503599627370496.0) ) return r; |
| 386 |
x = (sqlite3_int64)r; |
| 387 |
if( r==(double)x ) return r; |
| 388 |
if( r>(double)x ) x++; |
| 389 |
return (double)x; |
| 390 |
} |
| 391 |
static double seriesFloor(double r){ |
| 392 |
sqlite3_int64 x; |
| 393 |
if( r!=r ) return r; |
| 394 |
if( r<=(-4503599627370496.0) ) return r; |
| 395 |
if( r>=(+4503599627370496.0) ) return r; |
| 396 |
x = (sqlite3_int64)r; |
| 397 |
if( r==(double)x ) return r; |
| 398 |
if( r<(double)x ) x--; |
| 399 |
return (double)x; |
| 400 |
} |
| 401 |
#endif |
| 402 |
|
| 403 |
/* |
| 404 |
** This method is called to "rewind" the series_cursor object back |
| 405 |
** to the first row of output. This method is always called at least |
| 406 |
** once prior to any call to seriesColumn() or seriesRowid() or |
| 407 |
** seriesEof(). |
| 408 |
** |
| 409 |
** The query plan selected by seriesBestIndex is passed in the idxNum |
| 410 |
** parameter. (idxStr is not used in this implementation.) idxNum |
| 411 |
** is a bitmask showing which constraints are available: |
| 412 |
** |
| 413 |
** 0x0001: start=VALUE |
| 414 |
** 0x0002: stop=VALUE |
| 415 |
** 0x0004: step=VALUE |
| 416 |
** 0x0008: descending order |
| 417 |
** 0x0010: ascending order |
| 418 |
** 0x0020: LIMIT VALUE |
| 419 |
** 0x0040: OFFSET VALUE |
| 420 |
** 0x0080: value=VALUE |
| 421 |
** 0x0100: value>=VALUE |
| 422 |
** 0x0200: value>VALUE |
| 423 |
** 0x1000: value<=VALUE |
| 424 |
** 0x2000: value<VALUE |
| 425 |
** |
| 426 |
** This routine should initialize the cursor and position it so that it |
| 427 |
** is pointing at the first row, or pointing off the end of the table |
| 428 |
** (so that seriesEof() will return true) if the table is empty. |
| 429 |
*/ |
| 430 |
static int seriesFilter( |
| 431 |
sqlite3_vtab_cursor *pVtabCursor, |
| 432 |
int idxNum, const char *idxStrUnused, |
| 433 |
int argc, sqlite3_value **argv |
| 434 |
){ |
| 435 |
series_cursor *pCur = (series_cursor *)pVtabCursor; |
| 436 |
int iArg = 0; /* Arguments used so far */ |
| 437 |
int i; /* Loop counter */ |
| 438 |
sqlite3_int64 iMin = SMALLEST_INT64; /* Smallest allowed output value */ |
| 439 |
sqlite3_int64 iMax = LARGEST_INT64; /* Largest allowed output value */ |
| 440 |
sqlite3_int64 iLimit = 0; /* if >0, the value of the LIMIT */ |
| 441 |
sqlite3_int64 iOffset = 0; /* if >0, the value of the OFFSET */ |
| 442 |
|
| 443 |
(void)idxStrUnused; |
| 444 |
|
| 445 |
/* If any constraints have a NULL value, then return no rows. |
| 446 |
** See ticket https://sqlite.org/src/info/fac496b61722daf2 |
| 447 |
*/ |
| 448 |
for(i=0; i<argc; i++){ |
| 449 |
if( sqlite3_value_type(argv[i])==SQLITE_NULL ){ |
| 450 |
goto series_no_rows; |
| 451 |
} |
| 452 |
} |
| 453 |
|
| 454 |
/* Capture the three HIDDEN parameters to the virtual table and insert |
| 455 |
** default values for any parameters that are omitted. |
| 456 |
*/ |
| 457 |
if( idxNum & 0x01 ){ |
| 458 |
pCur->iOBase = sqlite3_value_int64(argv[iArg++]); |
| 459 |
}else{ |
| 460 |
pCur->iOBase = 0; |
| 461 |
} |
| 462 |
if( idxNum & 0x02 ){ |
| 463 |
pCur->iOTerm = sqlite3_value_int64(argv[iArg++]); |
| 464 |
}else{ |
| 465 |
pCur->iOTerm = 0xffffffff; |
| 466 |
} |
| 467 |
if( idxNum & 0x04 ){ |
| 468 |
pCur->iOStep = sqlite3_value_int64(argv[iArg++]); |
| 469 |
if( pCur->iOStep==0 ) pCur->iOStep = 1; |
| 470 |
}else{ |
| 471 |
pCur->iOStep = 1; |
| 472 |
} |
| 473 |
|
| 474 |
/* If there are constraints on the value column but there are |
| 475 |
** no constraints on the start, stop, and step columns, then |
| 476 |
** initialize the default range to be the entire range of 64-bit signed |
| 477 |
** integers. This range will contracted by the value column constraints |
| 478 |
** further below. |
| 479 |
*/ |
| 480 |
if( (idxNum & 0x05)==0 && (idxNum & 0x0380)!=0 ){ |
| 481 |
pCur->iOBase = SMALLEST_INT64; |
| 482 |
} |
| 483 |
if( (idxNum & 0x06)==0 && (idxNum & 0x3080)!=0 ){ |
| 484 |
pCur->iOTerm = LARGEST_INT64; |
| 485 |
} |
| 486 |
pCur->iBase = pCur->iOBase; |
| 487 |
pCur->iTerm = pCur->iOTerm; |
| 488 |
if( pCur->iOStep>0 ){ |
| 489 |
pCur->iStep = pCur->iOStep; |
| 490 |
}else if( pCur->iOStep>SMALLEST_INT64 ){ |
| 491 |
pCur->iStep = -pCur->iOStep; |
| 492 |
}else{ |
| 493 |
pCur->iStep = LARGEST_INT64; |
| 494 |
pCur->iStep++; |
| 495 |
} |
| 496 |
pCur->bDesc = pCur->iOStep<0; |
| 497 |
if( pCur->bDesc==0 && pCur->iBase>pCur->iTerm ){ |
| 498 |
goto series_no_rows; |
| 499 |
} |
| 500 |
if( pCur->bDesc!=0 && pCur->iBase<pCur->iTerm ){ |
| 501 |
goto series_no_rows; |
| 502 |
} |
| 503 |
|
| 504 |
/* Extract the LIMIT and OFFSET values, but do not apply them yet. |
| 505 |
** The range must first be constrained by the limits on value. |
| 506 |
*/ |
| 507 |
if( idxNum & 0x20 ){ |
| 508 |
iLimit = sqlite3_value_int64(argv[iArg++]); |
| 509 |
if( idxNum & 0x40 ){ |
| 510 |
iOffset = sqlite3_value_int64(argv[iArg++]); |
| 511 |
} |
| 512 |
} |
| 513 |
|
| 514 |
/* Narrow the range of iMin and iMax (the minimum and maximum outputs) |
| 515 |
** based on equality and inequality constraints on the "value" column. |
| 516 |
*/ |
| 517 |
if( idxNum & 0x3380 ){ |
| 518 |
if( idxNum & 0x0080 ){ /* value=X */ |
| 519 |
if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){ |
| 520 |
double r = sqlite3_value_double(argv[iArg++]); |
| 521 |
if( r==seriesCeil(r) |
| 522 |
&& r>=(double)SMALLEST_INT64 |
| 523 |
&& r<=(double)LARGEST_INT64 |
| 524 |
){ |
| 525 |
iMin = iMax = (sqlite3_int64)r; |
| 526 |
}else{ |
| 527 |
goto series_no_rows; |
| 528 |
} |
| 529 |
}else{ |
| 530 |
iMin = iMax = sqlite3_value_int64(argv[iArg++]); |
| 531 |
} |
| 532 |
}else{ |
| 533 |
if( idxNum & 0x0300 ){ /* value>X or value>=X */ |
| 534 |
if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){ |
| 535 |
double r = sqlite3_value_double(argv[iArg++]); |
| 536 |
if( r<(double)SMALLEST_INT64 ){ |
| 537 |
iMin = SMALLEST_INT64; |
| 538 |
}else if( (idxNum & 0x0200)!=0 && r==seriesCeil(r) ){ |
| 539 |
iMin = (sqlite3_int64)seriesCeil(r)+1; |
| 540 |
}else{ |
| 541 |
iMin = (sqlite3_int64)seriesCeil(r); |
| 542 |
} |
| 543 |
}else{ |
| 544 |
iMin = sqlite3_value_int64(argv[iArg++]); |
| 545 |
if( (idxNum & 0x0200)!=0 ){ |
| 546 |
if( iMin==LARGEST_INT64 ){ |
| 547 |
goto series_no_rows; |
| 548 |
}else{ |
| 549 |
iMin++; |
| 550 |
} |
| 551 |
} |
| 552 |
} |
| 553 |
} |
| 554 |
if( idxNum & 0x3000 ){ /* value<X or value<=X */ |
| 555 |
if( sqlite3_value_numeric_type(argv[iArg])==SQLITE_FLOAT ){ |
| 556 |
double r = sqlite3_value_double(argv[iArg++]); |
| 557 |
if( r>(double)LARGEST_INT64 ){ |
| 558 |
iMax = LARGEST_INT64; |
| 559 |
}else if( (idxNum & 0x2000)!=0 && r==seriesFloor(r) ){ |
| 560 |
iMax = ((sqlite3_int64)r)-1; |
| 561 |
}else{ |
| 562 |
iMax = (sqlite3_int64)seriesFloor(r); |
| 563 |
} |
| 564 |
}else{ |
| 565 |
iMax = sqlite3_value_int64(argv[iArg++]); |
| 566 |
if( idxNum & 0x2000 ){ |
| 567 |
if( iMax==SMALLEST_INT64 ){ |
| 568 |
goto series_no_rows; |
| 569 |
}else{ |
| 570 |
iMax--; |
| 571 |
} |
| 572 |
} |
| 573 |
} |
| 574 |
} |
| 575 |
if( iMin>iMax ){ |
| 576 |
goto series_no_rows; |
| 577 |
} |
| 578 |
} |
| 579 |
|
| 580 |
/* Try to reduce the range of values to be generated based on |
| 581 |
** constraints on the "value" column. |
| 582 |
*/ |
| 583 |
if( pCur->bDesc==0 ){ |
| 584 |
if( pCur->iBase<iMin ){ |
| 585 |
sqlite3_uint64 span = span64(iMin,pCur->iBase); |
| 586 |
pCur->iBase = add64(pCur->iBase, (span/pCur->iStep)*pCur->iStep); |
| 587 |
if( pCur->iBase<iMin ){ |
| 588 |
if( pCur->iBase > sub64(LARGEST_INT64, pCur->iStep) ){ |
| 589 |
goto series_no_rows; |
| 590 |
} |
| 591 |
pCur->iBase = add64(pCur->iBase, pCur->iStep); |
| 592 |
} |
| 593 |
} |
| 594 |
if( pCur->iTerm>iMax ){ |
| 595 |
pCur->iTerm = iMax; |
| 596 |
} |
| 597 |
}else{ |
| 598 |
if( pCur->iBase>iMax ){ |
| 599 |
sqlite3_uint64 span = span64(pCur->iBase,iMax); |
| 600 |
pCur->iBase = sub64(pCur->iBase, (span/pCur->iStep)*pCur->iStep); |
| 601 |
if( pCur->iBase>iMax ){ |
| 602 |
if( pCur->iBase < add64(SMALLEST_INT64, pCur->iStep) ){ |
| 603 |
goto series_no_rows; |
| 604 |
} |
| 605 |
pCur->iBase = sub64(pCur->iBase, pCur->iStep); |
| 606 |
} |
| 607 |
} |
| 608 |
if( pCur->iTerm<iMin ){ |
| 609 |
pCur->iTerm = iMin; |
| 610 |
} |
| 611 |
} |
| 612 |
} |
| 613 |
|
| 614 |
/* Adjust iTerm so that it is exactly the last value of the series. |
| 615 |
*/ |
| 616 |
if( pCur->bDesc==0 ){ |
| 617 |
if( pCur->iBase>pCur->iTerm ){ |
| 618 |
goto series_no_rows; |
| 619 |
} |
| 620 |
pCur->iTerm = sub64(pCur->iTerm, |
| 621 |
span64(pCur->iTerm,pCur->iBase) % pCur->iStep); |
| 622 |
}else{ |
| 623 |
if( pCur->iBase<pCur->iTerm ){ |
| 624 |
goto series_no_rows; |
| 625 |
} |
| 626 |
pCur->iTerm = add64(pCur->iTerm, |
| 627 |
span64(pCur->iBase,pCur->iTerm) % pCur->iStep); |
| 628 |
} |
| 629 |
|
| 630 |
/* Transform the series generator to output values in the requested |
| 631 |
** order. |
| 632 |
*/ |
| 633 |
if( ((idxNum & 0x0008)!=0 && pCur->bDesc==0) |
| 634 |
|| ((idxNum & 0x0010)!=0 && pCur->bDesc!=0) |
| 635 |
){ |
| 636 |
sqlite3_int64 tmp = pCur->iBase; |
| 637 |
pCur->iBase = pCur->iTerm; |
| 638 |
pCur->iTerm = tmp; |
| 639 |
pCur->bDesc = !pCur->bDesc; |
| 640 |
} |
| 641 |
|
| 642 |
/* Apply LIMIT and OFFSET constraints, if any */ |
| 643 |
assert( pCur->iStep!=0 ); |
| 644 |
if( idxNum & 0x20 ){ |
| 645 |
if( iOffset>0 ){ |
| 646 |
if( seriesSteps(pCur) < (sqlite3_uint64)iOffset ){ |
| 647 |
goto series_no_rows; |
| 648 |
}else if( pCur->bDesc ){ |
| 649 |
pCur->iBase = sub64(pCur->iBase, pCur->iStep*iOffset); |
| 650 |
}else{ |
| 651 |
pCur->iBase = add64(pCur->iBase, pCur->iStep*iOffset); |
| 652 |
} |
| 653 |
} |
| 654 |
if( iLimit>=0 && seriesSteps(pCur) > (sqlite3_uint64)iLimit ){ |
| 655 |
pCur->iTerm = add64(pCur->iBase, (iLimit - 1)*pCur->iStep); |
| 656 |
} |
| 657 |
} |
| 658 |
pCur->iValue = pCur->iBase; |
| 659 |
pCur->bDone = 0; |
| 660 |
return SQLITE_OK; |
| 661 |
|
| 662 |
series_no_rows: |
| 663 |
pCur->iBase = 0; |
| 664 |
pCur->iTerm = 0; |
| 665 |
pCur->iStep = 1; |
| 666 |
pCur->bDesc = 0; |
| 667 |
pCur->bDone = 1; |
| 668 |
return SQLITE_OK; |
| 669 |
} |
| 670 |
|
| 671 |
/* |
| 672 |
** SQLite will invoke this method one or more times while planning a query |
| 673 |
** that uses the generate_series virtual table. This routine needs to create |
| 674 |
** a query plan for each invocation and compute an estimated cost for that |
| 675 |
** plan. |
| 676 |
** |
| 677 |
** In this implementation idxNum is used to represent the |
| 678 |
** query plan. idxStr is unused. |
| 679 |
** |
| 680 |
** The query plan is represented by bits in idxNum: |
| 681 |
** |
| 682 |
** 0x0001 start = $num |
| 683 |
** 0x0002 stop = $num |
| 684 |
** 0x0004 step = $num |
| 685 |
** 0x0008 output is in descending order |
| 686 |
** 0x0010 output is in ascending order |
| 687 |
** 0x0020 LIMIT $num |
| 688 |
** 0x0040 OFFSET $num |
| 689 |
** 0x0080 value = $num |
| 690 |
** 0x0100 value >= $num |
| 691 |
** 0x0200 value > $num |
| 692 |
** 0x1000 value <= $num |
| 693 |
** 0x2000 value < $num |
| 694 |
** |
| 695 |
** Only one of 0x0100 or 0x0200 will be returned. Similarly, only |
| 696 |
** one of 0x1000 or 0x2000 will be returned. If the 0x0080 is set, then |
| 697 |
** none of the 0xff00 bits will be set. |
| 698 |
** |
| 699 |
** The order of parameters passed to xFilter is as follows: |
| 700 |
** |
| 701 |
** * The argument to start= if bit 0x0001 is in the idxNum mask |
| 702 |
** * The argument to stop= if bit 0x0002 is in the idxNum mask |
| 703 |
** * The argument to step= if bit 0x0004 is in the idxNum mask |
| 704 |
** * The argument to LIMIT if bit 0x0020 is in the idxNum mask |
| 705 |
** * The argument to OFFSET if bit 0x0040 is in the idxNum mask |
| 706 |
** * The argument to value=, or value>= or value> if any of |
| 707 |
** bits 0x0380 are in the idxNum mask |
| 708 |
** * The argument to value<= or value< if either of bits 0x3000 |
| 709 |
** are in the mask |
| 710 |
** |
| 711 |
*/ |
| 712 |
static int seriesBestIndex( |
| 713 |
sqlite3_vtab *pVTab, |
| 714 |
sqlite3_index_info *pIdxInfo |
| 715 |
){ |
| 716 |
int i, j; /* Loop over constraints */ |
| 717 |
int idxNum = 0; /* The query plan bitmask */ |
| 718 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 719 |
int bStartSeen = 0; /* EQ constraint seen on the START column */ |
| 720 |
#endif |
| 721 |
int unusableMask = 0; /* Mask of unusable constraints */ |
| 722 |
int nArg = 0; /* Number of arguments that seriesFilter() expects */ |
| 723 |
int aIdx[7]; /* Constraints on start, stop, step, LIMIT, OFFSET, |
| 724 |
** and value. aIdx[5] covers value=, value>=, and |
| 725 |
** value>, aIdx[6] covers value<= and value< */ |
| 726 |
const struct sqlite3_index_constraint *pConstraint; |
| 727 |
|
| 728 |
/* This implementation assumes that the start, stop, and step columns |
| 729 |
** are the last three columns in the virtual table. */ |
| 730 |
assert( SERIES_COLUMN_STOP == SERIES_COLUMN_START+1 ); |
| 731 |
assert( SERIES_COLUMN_STEP == SERIES_COLUMN_START+2 ); |
| 732 |
|
| 733 |
aIdx[0] = aIdx[1] = aIdx[2] = aIdx[3] = aIdx[4] = aIdx[5] = aIdx[6] = -1; |
| 734 |
pConstraint = pIdxInfo->aConstraint; |
| 735 |
for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){ |
| 736 |
int iCol; /* 0 for start, 1 for stop, 2 for step */ |
| 737 |
int iMask; /* bitmask for those column */ |
| 738 |
int op = pConstraint->op; |
| 739 |
if( op>=SQLITE_INDEX_CONSTRAINT_LIMIT |
| 740 |
&& op<=SQLITE_INDEX_CONSTRAINT_OFFSET |
| 741 |
){ |
| 742 |
if( pConstraint->usable==0 ){ |
| 743 |
/* do nothing */ |
| 744 |
}else if( op==SQLITE_INDEX_CONSTRAINT_LIMIT ){ |
| 745 |
aIdx[3] = i; |
| 746 |
idxNum |= 0x20; |
| 747 |
}else{ |
| 748 |
assert( op==SQLITE_INDEX_CONSTRAINT_OFFSET ); |
| 749 |
aIdx[4] = i; |
| 750 |
idxNum |= 0x40; |
| 751 |
} |
| 752 |
continue; |
| 753 |
} |
| 754 |
if( pConstraint->iColumn<SERIES_COLUMN_START ){ |
| 755 |
if( (pConstraint->iColumn==SERIES_COLUMN_VALUE || |
| 756 |
pConstraint->iColumn==SERIES_COLUMN_ROWID) |
| 757 |
&& pConstraint->usable |
| 758 |
){ |
| 759 |
switch( op ){ |
| 760 |
case SQLITE_INDEX_CONSTRAINT_EQ: |
| 761 |
case SQLITE_INDEX_CONSTRAINT_IS: { |
| 762 |
idxNum |= 0x0080; |
| 763 |
idxNum &= ~0x3300; |
| 764 |
aIdx[5] = i; |
| 765 |
aIdx[6] = -1; |
| 766 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 767 |
bStartSeen = 1; |
| 768 |
#endif |
| 769 |
break; |
| 770 |
} |
| 771 |
case SQLITE_INDEX_CONSTRAINT_GE: { |
| 772 |
if( idxNum & 0x0080 ) break; |
| 773 |
idxNum |= 0x0100; |
| 774 |
idxNum &= ~0x0200; |
| 775 |
aIdx[5] = i; |
| 776 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 777 |
bStartSeen = 1; |
| 778 |
#endif |
| 779 |
break; |
| 780 |
} |
| 781 |
case SQLITE_INDEX_CONSTRAINT_GT: { |
| 782 |
if( idxNum & 0x0080 ) break; |
| 783 |
idxNum |= 0x0200; |
| 784 |
idxNum &= ~0x0100; |
| 785 |
aIdx[5] = i; |
| 786 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 787 |
bStartSeen = 1; |
| 788 |
#endif |
| 789 |
break; |
| 790 |
} |
| 791 |
case SQLITE_INDEX_CONSTRAINT_LE: { |
| 792 |
if( idxNum & 0x0080 ) break; |
| 793 |
idxNum |= 0x1000; |
| 794 |
idxNum &= ~0x2000; |
| 795 |
aIdx[6] = i; |
| 796 |
break; |
| 797 |
} |
| 798 |
case SQLITE_INDEX_CONSTRAINT_LT: { |
| 799 |
if( idxNum & 0x0080 ) break; |
| 800 |
idxNum |= 0x2000; |
| 801 |
idxNum &= ~0x1000; |
| 802 |
aIdx[6] = i; |
| 803 |
break; |
| 804 |
} |
| 805 |
} |
| 806 |
} |
| 807 |
continue; |
| 808 |
} |
| 809 |
iCol = pConstraint->iColumn - SERIES_COLUMN_START; |
| 810 |
assert( iCol>=0 && iCol<=2 ); |
| 811 |
iMask = 1 << iCol; |
| 812 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 813 |
if( iCol==0 && op==SQLITE_INDEX_CONSTRAINT_EQ ){ |
| 814 |
bStartSeen = 1; |
| 815 |
} |
| 816 |
#endif |
| 817 |
if( pConstraint->usable==0 ){ |
| 818 |
unusableMask |= iMask; |
| 819 |
continue; |
| 820 |
}else if( op==SQLITE_INDEX_CONSTRAINT_EQ ){ |
| 821 |
idxNum |= iMask; |
| 822 |
aIdx[iCol] = i; |
| 823 |
} |
| 824 |
} |
| 825 |
if( aIdx[3]==0 ){ |
| 826 |
/* Ignore OFFSET if LIMIT is omitted */ |
| 827 |
idxNum &= ~0x60; |
| 828 |
aIdx[4] = 0; |
| 829 |
} |
| 830 |
for(i=0; i<7; i++){ |
| 831 |
if( (j = aIdx[i])>=0 ){ |
| 832 |
pIdxInfo->aConstraintUsage[j].argvIndex = ++nArg; |
| 833 |
pIdxInfo->aConstraintUsage[j].omit = |
| 834 |
!SQLITE_SERIES_CONSTRAINT_VERIFY || i>=3; |
| 835 |
} |
| 836 |
} |
| 837 |
/* The current generate_column() implementation requires at least one |
| 838 |
** argument (the START value). Legacy versions assumed START=0 if the |
| 839 |
** first argument was omitted. Compile with -DZERO_ARGUMENT_GENERATE_SERIES |
| 840 |
** to obtain the legacy behavior */ |
| 841 |
#ifndef ZERO_ARGUMENT_GENERATE_SERIES |
| 842 |
if( !bStartSeen ){ |
| 843 |
sqlite3_free(pVTab->zErrMsg); |
| 844 |
pVTab->zErrMsg = sqlite3_mprintf( |
| 845 |
"first argument to \"generate_series()\" missing or unusable"); |
| 846 |
return SQLITE_ERROR; |
| 847 |
} |
| 848 |
#endif |
| 849 |
if( (unusableMask & ~idxNum)!=0 ){ |
| 850 |
/* The start, stop, and step columns are inputs. Therefore if there |
| 851 |
** are unusable constraints on any of start, stop, or step then |
| 852 |
** this plan is unusable */ |
| 853 |
return SQLITE_CONSTRAINT; |
| 854 |
} |
| 855 |
if( (idxNum & 0x03)==0x03 ){ |
| 856 |
/* Both start= and stop= boundaries are available. This is the |
| 857 |
** the preferred case */ |
| 858 |
pIdxInfo->estimatedCost = (double)(2 - ((idxNum&4)!=0)); |
| 859 |
pIdxInfo->estimatedRows = 1000; |
| 860 |
if( pIdxInfo->nOrderBy>=1 && pIdxInfo->aOrderBy[0].iColumn==0 ){ |
| 861 |
if( pIdxInfo->aOrderBy[0].desc ){ |
| 862 |
idxNum |= 0x08; |
| 863 |
}else{ |
| 864 |
idxNum |= 0x10; |
| 865 |
} |
| 866 |
pIdxInfo->orderByConsumed = 1; |
| 867 |
} |
| 868 |
}else if( (idxNum & 0x21)==0x21 ){ |
| 869 |
/* We have start= and LIMIT */ |
| 870 |
pIdxInfo->estimatedRows = 2500; |
| 871 |
}else{ |
| 872 |
/* If either boundary is missing, we have to generate a huge span |
| 873 |
** of numbers. Make this case very expensive so that the query |
| 874 |
** planner will work hard to avoid it. */ |
| 875 |
pIdxInfo->estimatedRows = 2147483647; |
| 876 |
} |
| 877 |
pIdxInfo->idxNum = idxNum; |
| 878 |
#ifdef SQLITE_INDEX_SCAN_HEX |
| 879 |
pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_HEX; |
| 880 |
#endif |
| 881 |
return SQLITE_OK; |
| 882 |
} |
| 883 |
|
| 884 |
/* |
| 885 |
** This following structure defines all the methods for the |
| 886 |
** generate_series virtual table. |
| 887 |
*/ |
| 888 |
static sqlite3_module seriesModule = { |
| 889 |
0, /* iVersion */ |
| 890 |
0, /* xCreate */ |
| 891 |
seriesConnect, /* xConnect */ |
| 892 |
seriesBestIndex, /* xBestIndex */ |
| 893 |
seriesDisconnect, /* xDisconnect */ |
| 894 |
0, /* xDestroy */ |
| 895 |
seriesOpen, /* xOpen - open a cursor */ |
| 896 |
seriesClose, /* xClose - close a cursor */ |
| 897 |
seriesFilter, /* xFilter - configure scan constraints */ |
| 898 |
seriesNext, /* xNext - advance a cursor */ |
| 899 |
seriesEof, /* xEof - check for end of scan */ |
| 900 |
seriesColumn, /* xColumn - read data */ |
| 901 |
seriesRowid, /* xRowid - read data */ |
| 902 |
0, /* xUpdate */ |
| 903 |
0, /* xBegin */ |
| 904 |
0, /* xSync */ |
| 905 |
0, /* xCommit */ |
| 906 |
0, /* xRollback */ |
| 907 |
0, /* xFindMethod */ |
| 908 |
0, /* xRename */ |
| 909 |
0, /* xSavepoint */ |
| 910 |
0, /* xRelease */ |
| 911 |
0, /* xRollbackTo */ |
| 912 |
0, /* xShadowName */ |
| 913 |
0 /* xIntegrity */ |
| 914 |
}; |
| 915 |
|
| 916 |
#endif /* SQLITE_OMIT_VIRTUALTABLE */ |
| 917 |
|
| 918 |
#ifdef _WIN32 |
| 919 |
__declspec(dllexport) |
| 920 |
#endif |
| 921 |
int sqlite3_series_init( |
| 922 |
sqlite3 *db, |
| 923 |
char **pzErrMsg, |
| 924 |
const sqlite3_api_routines *pApi |
| 925 |
){ |
| 926 |
int rc = SQLITE_OK; |
| 927 |
SQLITE_EXTENSION_INIT2(pApi); |
| 928 |
#ifndef SQLITE_OMIT_VIRTUALTABLE |
| 929 |
if( sqlite3_libversion_number()<3008012 && pzErrMsg!=0 ){ |
| 930 |
*pzErrMsg = sqlite3_mprintf( |
| 931 |
"generate_series() requires SQLite 3.8.12 or later"); |
| 932 |
return SQLITE_ERROR; |
| 933 |
} |
| 934 |
rc = sqlite3_create_module(db, "generate_series", &seriesModule, 0); |
| 935 |
#endif |
| 936 |
return rc; |
| 937 |
} |