Documentation Source Text

Check-in [9b1dc53b75]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Update the change log to show the skip-scan optimization and other recent changes. Add documentation on skip-scan.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:9b1dc53b75a9dc9251f2620470bcaee01f1644b6
User & Date: drh 2013-11-13 22:39:08
Context
2013-11-15
16:22
Fix a typo in the WITHOUT ROWID documentation. check-in: 5725d732c9 user: drh tags: trunk
2013-11-13
22:39
Update the change log to show the skip-scan optimization and other recent changes. Add documentation on skip-scan. check-in: 9b1dc53b75 user: drh tags: trunk
2013-11-11
23:27
Documentation updates associated with WITHOUT ROWID and the extension of the sqlite3_index_info object. check-in: 21034f356e user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/changes.in.

16
17
18
19
20
21
22

23
24
25
26
27







28
29
30
31
32
33
34
  global nChng aChng
  set aChng($nChng) [list $date $desc $options]
  incr nChng
}

chng {2013-12-?? (3.8.2)} {
<li>Added support for [WITHOUT ROWID] tables.

<li>Extended the [virtual table] interface, and in particular the
    [sqlite3_index_info] object to allow a virtual table to report its estimate
    on the number of rows that will be returned by a query.
<li>Update the [R-Tree extension] to make use of the enhanced virtual table
    interface.







}

chng {2013-10-17 (3.8.1)} {
<li>Added the [unlikely()] and [likelihood()] SQL functions to be used
    as hints to the query planner.
<li>Enhancements to the query planner:
<ul>







>





>
>
>
>
>
>
>







16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  global nChng aChng
  set aChng($nChng) [list $date $desc $options]
  incr nChng
}

chng {2013-12-?? (3.8.2)} {
<li>Added support for [WITHOUT ROWID] tables.
<li>Added the [skip-scan optimization] to the query planner.
<li>Extended the [virtual table] interface, and in particular the
    [sqlite3_index_info] object to allow a virtual table to report its estimate
    on the number of rows that will be returned by a query.
<li>Update the [R-Tree extension] to make use of the enhanced virtual table
    interface.
<li>Add the [SQLITE_ENABLE_EXPLAIN_COMMENTS] compile-time option.
<li>Enhanced the comments that are inserted into [EXPLAIN] output when the
    [SQLITE_ENABLE_EXPLAIN_COMMENTS] compile-time option is enabled.
<li>Enhanced the ".explain" output formatting of the [command-line shell]
    so that loops are indented to better show the structure of the program.
<li>Enhanced the ".timer" feature of the [command-line shell] so that it
    shows wall-clock time in addition to system and user times.
}

chng {2013-10-17 (3.8.1)} {
<li>Added the [unlikely()] and [likelihood()] SQL functions to be used
    as hints to the query planner.
<li>Enhancements to the query planner:
<ul>

Changes to pages/compile.in.

459
460
461
462
463
464
465












466
467
468
469
470
471
472
  <li> [sqlite3_column_table_name()] </li>
  <li> [sqlite3_column_table_name16()] </li>
  <li> [sqlite3_column_origin_name()] </li>
  <li> [sqlite3_column_origin_name16()] </li>
  <li> [sqlite3_table_column_metadata()] </li>
  </ul>
}













COMPILE_OPTION {SQLITE_ENABLE_FTS3} {
  When this option is defined in the [amalgamation], version 3
  of the full-text search engine is added to the build automatically.
}

COMPILE_OPTION {SQLITE_ENABLE_FTS3_PARENTHESIS} {







>
>
>
>
>
>
>
>
>
>
>
>







459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
  <li> [sqlite3_column_table_name()] </li>
  <li> [sqlite3_column_table_name16()] </li>
  <li> [sqlite3_column_origin_name()] </li>
  <li> [sqlite3_column_origin_name16()] </li>
  <li> [sqlite3_table_column_metadata()] </li>
  </ul>
}

COMPILE_OPTION {SQLITE_ENABLE_EXPLAIN_COMMENTS} {
  This option adds extra logic to SQLite that inserts comment text into the
  output of [EXPLAIN].  These extra comments use extra memory, thus
  making [prepared statements] larger and very slightly slower, and so they are
  turned off by default and in most application.  But some applications, such
  as the [command-line shell] for SQLite, value clarity of EXPLAIN output
  over raw performance and so this compile-time option is available to them.
  The SQLITE_ENABLE_EXPLAIN_COMMENTS compile-time option is also enabled
  automatically if [SQLITE_DEBUG] is enabled.
}


COMPILE_OPTION {SQLITE_ENABLE_FTS3} {
  When this option is defined in the [amalgamation], version 3
  of the full-text search engine is added to the build automatically.
}

COMPILE_OPTION {SQLITE_ENABLE_FTS3_PARENTHESIS} {

Changes to pages/optoverview.in.

122
123
124
125
126
127
128
129
130
131

132

133
134
135
136
137
138
139
...
431
432
433
434
435
436
437
438
















































































































439
440
441
442
443
444
445
PARAGRAPH {
  ^It is not necessary for every column of an index to appear in a
  WHERE clause term in order for that index to be used. 
  ^But there can not be gaps in the columns of the index that are used.
  ^Thus for the example index above, if there is no WHERE clause term
  that constraints column c, then terms that constrain columns a and b can
  be used with the index but not terms that constraint columns d through z.
  ^Similarly, no index column will be used (for indexing purposes)
  that is to the right of a 
  column that is constrained only by inequalities.

}

HEADING 2 {Index term usage examples} idxexamp
PARAGRAPH {
  ^(For the index above and WHERE clause like this:
}
CODE {
  ... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
}
................................................................................
  to the right-hand side parameter has changed since the previous run.
  This reparse and recompile is essentially the same action that occurs
  following a schema change.  The recompile is necessary so that the query
  planner can examine the new value bound to the right-hand side of the
  LIKE or GLOB operator and determine whether or not to employ the
  optimization described above.
}
  

















































































































HEADING 1 {Joins} joins

PARAGRAPH {
  ^The ON and USING clauses of an inner join are converted into additional
  terms of the WHERE clause prior to WHERE clause analysis described
  above in paragraph 1.0.  ^(Thus with SQLite, there is no computational







|
|

>

>







 







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
...
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
PARAGRAPH {
  ^It is not necessary for every column of an index to appear in a
  WHERE clause term in order for that index to be used. 
  ^But there can not be gaps in the columns of the index that are used.
  ^Thus for the example index above, if there is no WHERE clause term
  that constraints column c, then terms that constrain columns a and b can
  be used with the index but not terms that constraint columns d through z.
  ^Similarly, index columns will not normally be used (for indexing purposes)
  if they are to the right of a 
  column that is constrained only by inequalities.
  (See the [skip-scan optimization] below for the exception.)
}

HEADING 2 {Index term usage examples} idxexamp
PARAGRAPH {
  ^(For the index above and WHERE clause like this:
}
CODE {
  ... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
}
................................................................................
  to the right-hand side parameter has changed since the previous run.
  This reparse and recompile is essentially the same action that occurs
  following a schema change.  The recompile is necessary so that the query
  planner can examine the new value bound to the right-hand side of the
  LIKE or GLOB operator and determine whether or not to employ the
  optimization described above.
}

HEADING 1 {The Skip-Scan Optimization} skipscan \
  {skip-scan optimization} skip-scan

PARAGRAPH {
  The general rule is that indexes are only useful if there are 
  WHERE-clause constraints on the left-most columns of the index.
  However, in some cases,
  SQLite is able to use an index even if the first few columns of
  the index are omitted from the WHERE clause but later columns 
  are included.
}

PARAGRAPH {
  Consider a table such as the following:
}

CODE {
  CREATE TABLE people(
    name TEXT PRIMARY KEY,
    role TEXT NOT NULL,
    height INT NOT NULL, -- in cm
    CHECK( role IN ('student','teacher') )
  );
  CREATE INDEX people_idx1 ON people(role, height);
}

PARAGRAPH {
  The people table has one entry for each person in a large
  organization.  Each person is either a "student" or a "teacher",
  as determined by the "role" field.  And we record the height in
  centimeters of each person.  The role and height are indexed.
  Notice that the left-most column of the index is not very
  selective - it only contains two possible values.
}

PARAGRAPH {
  Now consider a query to find the names of everyone in the
  organization that is 180cm tall or taller:
}

CODE {
  SELECT name FROM people WHERE height>=180;
}

PARAGRAPH {
  Because the left-most column of the index does not appear in the
  WHERE clause of the query, one is tempted to conclude that the
  index is not usable here.  But SQLite is able to use the index.
  Conceptually, what SQLite does in this case is transform the
  query into something like the following:
}

CODE {
  SELECT name FROM people
   WHERE role IN (SELECT DISTINCT role FROM people)
     AND height>=180;
}

PARAGRAPH {
  Or this:
}

CODE {
  SELECT name FROM people WHERE role='teacher' AND height>=180
  UNION ALL
  SELECT name FROM people WHERE role='student' AND height>=180;
}

PARAGRAPH {
  The key word above is "conceptually".  SQLite does not really transform
  the query.  But the transformations help to convey a sense of how
  SQLite goes about running the query.  The plan goes like this:
  SQLite locates the first possible value for "role", which it
  can do by rewinding the "people_idx1" index to the beginning and reading
  the first record.  SQLite stores this first "role" value in an
  internal variable that we will here call "$role".  Then SQLite
  runs a query like: "SELECT name FROM people WHERE role=$role AND height>=180".
  This query has an equality constraint on the left-most column of the
  index and so the index can be used to resolve that query.  Once
  that query is finished, SQLite then uses the "people_idx1" index to
  locate the next value of the "role" column, using code that is logically
  similar to "SELECT role FROM people WHERE role>$role".  This new "role"
  value overwrites the $role variable, and the process repeats until all
  possible values for "role" have been examined.
}

PARAGRAPH {
  We call this kind of index usage a "skip-scan" because the database
  engine is basically doing a full scan of the index but it optimizes the
  scan (making it less than "full") by occasionally jumping ahead to the
  next candidate value.
}

PARAGRAPH {
  SQLite might use a skip-scan on an index if it knows that the first
  one or more columns contain only a small number of distinct values.
  If there are too many
  distinct values in the left-most columns of the index, then it would
  be faster to do an ordinary full table scan, and so SQLite will choose
  that option instead.
}

PARAGRAPH {
  The only way that SQLite can know that the left-most columns of an index
  have few distinct values is if the [ANALYZE] command has been run
  on the database.
  Without the results of ANALYZE, SQLite has to guess at the "shape" of
  the data in the table, and the default guess is that there are many
  distinct values for the left-most column of an index, far too many
  to make a skip-scan practical.  Hence, a skip-scan is never used on a
  database that has not been analyzed.
}

HEADING 1 {Joins} joins

PARAGRAPH {
  ^The ON and USING clauses of an inner join are converted into additional
  terms of the WHERE clause prior to WHERE clause analysis described
  above in paragraph 1.0.  ^(Thus with SQLite, there is no computational