Documentation Source Text

Check-in [fc0e9baa66]
Login

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

Overview
Comment:Enhancements to the optoverview.html document: Added discussion of partial sorting and fixed the conditions for query flattening.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fc0e9baa66be99ee6c6a235affa1da004647ec06
User & Date: drh 2014-05-25 20:08:23.545
Context
2014-05-25
20:11
Another accidental fork merge. (check-in: b1b9dd90bb user: drh tags: trunk)
20:08
Enhancements to the optoverview.html document: Added discussion of partial sorting and fixed the conditions for query flattening. (check-in: fc0e9baa66 user: drh tags: trunk)
2014-05-24
17:16
Further improvements to the opcodes.html documentation generator. (check-in: 4f034b4e83 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to pages/changes.in.
15
16
17
18
19
20
21

22
23
24
25
26
27
28
29
proc chng {date desc {options {}}} {
  global nChng aChng
  set aChng($nChng) [list $date $desc $options]
  incr nChng
}

chng {2014-06-?? (3.8.5)} {

<li>Added support for sorting subsets of the result when the result comes out of the query
    engine already partially sorted.
<li>Enhance the query planner so that it always prefers an index that uses a superset of
    WHERE clause terms relative to some other index.
<li>Improvements to the [automerge command] of [FTS4] to better control the index size
    for a full-text index that is subject to a large number of updates.
<li>Added the [SQLITE_TESTCTRL_BYTEORDER] test control.
<li>Added the [sqlite3_rtree_query_callback()] interface to [R-Tree extension]







>
|







15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
proc chng {date desc {options {}}} {
  global nChng aChng
  set aChng($nChng) [list $date $desc $options]
  incr nChng
}

chng {2014-06-?? (3.8.5)} {
<li>Added support for [sorting subsets of the result]
    when the result comes out of the query
    engine already partially sorted.
<li>Enhance the query planner so that it always prefers an index that uses a superset of
    WHERE clause terms relative to some other index.
<li>Improvements to the [automerge command] of [FTS4] to better control the index size
    for a full-text index that is subject to a large number of updates.
<li>Added the [SQLITE_TESTCTRL_BYTEORDER] test control.
<li>Added the [sqlite3_rtree_query_callback()] interface to [R-Tree extension]
Changes to pages/optoverview.in.
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989




















990
991
992
993
994
995
996
HEADING 1 {ORDER BY optimizations} order_by

PARAGRAPH {
  ^SQLite attempts to use an index to satisfy the ORDER BY clause of a
  query when possible.
  ^When faced with the choice of using an index to satisfy WHERE clause
  constraints or satisfying an ORDER BY clause, SQLite does the same
  work analysis described above
  and chooses the index that it believes will result in the fastest answer.
}

PARAGRAPH {
  ^SQLite will also attempt to use indices to help satisfy GROUP BY clauses
  and the DISTINCT keyword.  If the nested loops of the join can be arranged
  such that are equivalent for the GROUP BY or for the DISTINCT are
  consecutive, then the GROUP BY or DISTINCT logic can determine if the 
  current row is part of the same group or if the current row is distinct
  simply by comparing the current row to the previous row.
  This can be much faster than the alternative of comparing each row to
  all prior rows.
}





















HEADING 1 {Subquery flattening} flattening
hd_keywords {flattening optimization}

PARAGRAPH {
  When a subquery occurs in the FROM clause of a SELECT, the simplest
  behavior is to evaluate the subquery into a transient table, then run







|






|






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







969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
HEADING 1 {ORDER BY optimizations} order_by

PARAGRAPH {
  ^SQLite attempts to use an index to satisfy the ORDER BY clause of a
  query when possible.
  ^When faced with the choice of using an index to satisfy WHERE clause
  constraints or satisfying an ORDER BY clause, SQLite does the same
  cost analysis described above
  and chooses the index that it believes will result in the fastest answer.
}

PARAGRAPH {
  ^SQLite will also attempt to use indices to help satisfy GROUP BY clauses
  and the DISTINCT keyword.  If the nested loops of the join can be arranged
  such that rows that are equivalent for the GROUP BY or for the DISTINCT are
  consecutive, then the GROUP BY or DISTINCT logic can determine if the 
  current row is part of the same group or if the current row is distinct
  simply by comparing the current row to the previous row.
  This can be much faster than the alternative of comparing each row to
  all prior rows.
}

HEADING 2 {Partial ORDER BY Via Index} partsort
hd_keywords {sorting subsets of the result}

PARAGRAPH {
  If a query contains an ORDER BY clause with multiple terms, it might
  be that SQLite can use indices to cause rows to come out in the order
  of some prefix of the terms in the ORDER BY but that later terms in
  the ORDER BY are not satisfied.  In that case, SQLite does block sorting.
  Suppose the ORDER BY clause has four terms and the natural order of the
  query results in rows appearing in order of the first two terms.  As
  each row is output by the query engine and enters the sorter, the 
  outputs in the current row corresponding to the first two terms of 
  the ORDER BY are comparied against the previous row.  If they have
  changed, the current sort is finished and output and a new sort is
  started.  This results in a slightly faster sort.  But the bigger
  advantages are that many fewer rows need to be held in memory,
  reducing memory requirements, and outputs can begin to appear before
  the core query has run to completion.
}

HEADING 1 {Subquery flattening} flattening
hd_keywords {flattening optimization}

PARAGRAPH {
  When a subquery occurs in the FROM clause of a SELECT, the simplest
  behavior is to evaluate the subquery into a transient table, then run
1014
1015
1016
1017
1018
1019
1020
1021


1022
1023
1024
1025
1026

1027
1028

1029
1030
1031
1032
1033
1034

1035

1036
1037
1038

1039
1040

1041
1042

1043
1044
1045

1046
1047
1048

1049
1050


1051
1052
1053
1054

1055
1056
1057

1058
1059
1060

1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074

1075
1076
1077
1078

1079
1080
1081

1082
1083









1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101


1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
  Would be rewritten using query flattening as:
}
CODE {
  SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
}
PARAGRAPH {)^
  There is a long list of conditions that must all be met in order for
  query flattening to occur.


}
PARAGRAPH {
  <ol>
  <li>  ^The subquery and the outer query do not both use aggregates.


  <li>  ^The subquery is not an aggregate or the outer query is not a join.


  <li>  ^The subquery is not the right operand of a left outer join.

  <li>  ^The subquery is not DISTINCT or the outer query is not a join.

  <li>  ^The subquery is not DISTINCT or the outer query does not use
        aggregates.



  <li>  ^The subquery does not use aggregates or the outer query is not
        DISTINCT.


  <li>  ^The subquery has a FROM clause.


  <li>  ^The subquery does not use LIMIT or the outer query is not a join.


  <li>  ^The subquery does not use LIMIT or the outer query does not use
        aggregates.


  <li>  ^The subquery does not use aggregates or the outer query does not
        use LIMIT.


  <li>  ^The subquery and the outer query do not both have ORDER BY clauses.



  <li>  ^The subquery and outer query do not both use LIMIT.

  <li>  ^The subquery does not use OFFSET.


  <li>  ^The outer query is not part of a compound select or the
        subquery does not have both an ORDER BY and a LIMIT clause.


  <li>  ^The outer query is not an aggregate or the subquery does
        not contain ORDER BY. 


  <li>  ^(The sub-query is not a compound select, or it is a UNION ALL 
        compound clause made up entirely of non-aggregate queries, and 
        the parent query:

        <ul>
        <li> is not itself part of a compound select,
        <li> is not an aggregate or DISTINCT query, and
        <li> has no other tables or sub-selects in the FROM clause.
        </ul>)^

        ^The parent and sub-query may contain WHERE clauses. ^Subject to
        rules (11), (12) and (13), they may also contain ORDER BY,
        LIMIT and OFFSET clauses.


  <li>  ^If the sub-query is a compound select, then all terms of the
        ORDER by clause of the parent must be simple references to 
        columns of the sub-query.


  <li>  ^The subquery does not use LIMIT or the outer query does not
        have a WHERE clause.


  <li>  ^If the sub-query is a compound select, then it must not use
        an ORDER BY clause.









  </ol>
}
PARAGRAPH {
  The casual reader is not expected to understand or remember any part of
  the list above.  The point of this list is to demonstrate
  that the decision of whether or not to flatten a query is complex.
  
}
PARAGRAPH {
  Query flattening is an important optimization when views are used as
  each use of a view is translated into a subquery.
}

HEADING 1 {The MIN/MAX optimization} minmax

PARAGRAPH {
  ^(Queries of the following forms will be optimized to run in logarithmic
  time assuming appropriate indices exist:


}
CODE {
  SELECT MIN(x) FROM table;
  SELECT MAX(x) FROM table;
}
PARAGRAPH {)^
  ^In order for these optimizations to occur, they must appear in exactly
  the form shown above - changing only the name of the table and column.
  ^It is not permissible to add a WHERE clause or do any arithmetic on the
  result.  ^The result set must contain a single column.
  ^The column in the MIN or MAX function must be an indexed column.
}

HEADING 1 {Automatic Indices} autoindex {automatic indexing} {Automatic indexing}

PARAGRAPH {
  ^(When no indices are available to aid the evaluation of a query, SQLite
  might create an automatic index that lasts only for the duration







|
>
>



|

>
|

>
|

|

<
<
>

>
|


>
|

>
|

>
|
|

>
|
|

>
|

>
>
|

|

>
|
|

>
|
|

>
|
|
|

|
|
|
|
|

|
|
|

>
|
|
|

>
|
|

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
















|
|
>
>



|
<
<
<
<
<
<
<







1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056


1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153







1154
1155
1156
1157
1158
1159
1160
  Would be rewritten using query flattening as:
}
CODE {
  SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
}
PARAGRAPH {)^
  There is a long list of conditions that must all be met in order for
  query flattening to occur.  Some of the constraints are marked as 
  obsolete by italic text.  These extra constraints are retained in the
  documentation to preserve the numbering of the other constraints.
}
PARAGRAPH {
  <ol>
  <li value="1">  ^The subquery and the outer query do not both use aggregates.

  <li value="2">
  ^The subquery is not an aggregate or the outer query is not a join.

  <li value="3">
  ^The subquery is not the right operand of a left outer join.

  <li value="4">  ^The subquery is not DISTINCT.



  <li value="5"> <i>(Subsumed into constraint 4)</i>

  <li value="6">
        ^The subquery does not use aggregates or the outer query is not
        DISTINCT.

  <li value="7">
  ^The subquery has a FROM clause.

  <li value="8">
  ^The subquery does not use LIMIT or the outer query is not a join.

  <li value="9">
  ^The subquery does not use LIMIT or the outer query does not use
  aggregates.

  <li value="10">
  ^The subquery does not use aggregates or the outer query does not
  use LIMIT.

  <li value="11">
  ^The subquery and the outer query do not both have ORDER BY clauses.

  <li value="12"> <i>(Subsumed into constraint 3)</i>

  <li value="13">  ^The subquery and outer query do not both use LIMIT.

  <li value="14">  ^The subquery does not use OFFSET.

  <li value="15">
  ^The outer query is not part of a compound select or the
  subquery does not have a LIMIT clause.

  <li value="16">
  ^The outer query is not an aggregate or the subquery does
  not contain ORDER BY. 

  <li value="17">
  ^(The sub-query is not a compound select, or it is a UNION ALL 
  compound clause made up entirely of non-aggregate queries, and 
  the parent query:

  <ul>
  <li> is not itself part of a compound select,
  <li> is not an aggregate or DISTINCT query, and
  <li> is not a join.
  </ul>)^

  ^The parent and sub-query may contain WHERE clauses. ^Subject to
  rules (11), (12) and (13), they may also contain ORDER BY,
  LIMIT and OFFSET clauses.

  <li value="18">
  ^If the sub-query is a compound select, then all terms of the
  ORDER by clause of the parent must be simple references to 
  columns of the sub-query.

  <li value="19">
  ^The subquery does not use LIMIT or the outer query does not
  have a WHERE clause.

  <li value="20">
  ^If the sub-query is a compound select, then it must not use
  an ORDER BY clause.

  <li value="21">
  ^The subquery does not use LIMIT or the outer query is not
  DISTINCT.

  <li value="22"> ^The subquery is not a recursive CTE.

  <li value="23"> ^The parent is not a recursive CTE, or the sub-query
  is not a compound query.
  </ol>
}
PARAGRAPH {
  The casual reader is not expected to understand or remember any part of
  the list above.  The point of this list is to demonstrate
  that the decision of whether or not to flatten a query is complex.
  
}
PARAGRAPH {
  Query flattening is an important optimization when views are used as
  each use of a view is translated into a subquery.
}

HEADING 1 {The MIN/MAX optimization} minmax

PARAGRAPH {
  ^(Queries that contain a single MIN() or MAX() aggregate function whose
  argument is the left-most column of an index might be satisfied
  by doing a single index lookup rather than by scanning the entire table.)^
  Examples:
}
CODE {
  SELECT MIN(x) FROM table;
  SELECT MAX(x)+1 FROM table;







}

HEADING 1 {Automatic Indices} autoindex {automatic indexing} {Automatic indexing}

PARAGRAPH {
  ^(When no indices are available to aid the evaluation of a query, SQLite
  might create an automatic index that lasts only for the duration