/ Check-in [94255634]
Login

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

Overview
Comment:Try to take into account the cost of inner loops when selecting which table of a join to use for the outer loop.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | inner-loop-cost
Files: files | file ages | folders
SHA1: 942556342a332b04a11169bb04f387d741ef9488
User & Date: drh 2012-11-09 17:59:26
Context
2012-11-09
18:22
Disable the table selection rule that tried to prevent full table scans from migrating to the outer loop unless they were optimal. The new scaling of outer-loop costs by cost of inner loops obviates the need for that step. And, in fact, that step causes problems with the new inner-loop cost accounting. Closed-Leaf check-in: 51bfd63b user: drh tags: inner-loop-cost
17:59
Try to take into account the cost of inner loops when selecting which table of a join to use for the outer loop. check-in: 94255634 user: drh tags: inner-loop-cost
2012-11-06
20:39
Adjust the SQLITE_DBSTATUS_STMT_USED calculation to take the modified usage of sqlite3VdbeClearObject() into account. check-in: 82eb7ead user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

1963
1964
1965
1966
1967
1968
1969

1970
1971
1972
1973
1974
1975
1976
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;


  /* The following field is really not part of the current level.  But
  ** we need a place to cache virtual table index information for each
  ** virtual table in the FROM clause and the WhereLevel structure is
  ** a convenient place since there is one WhereLevel for each FROM clause
  ** element.
  */







>







1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;
  double rOptCost;      /* "Optimal" cost for this level */

  /* The following field is really not part of the current level.  But
  ** we need a place to cache virtual table index information for each
  ** virtual table in the FROM clause and the WhereLevel structure is
  ** a convenient place since there is one WhereLevel for each FROM clause
  ** element.
  */

Changes to src/where.c.

4740
4741
4742
4743
4744
4745
4746










4747
4748
4749
4750
4751
4752
4753
....
5098
5099
5100
5101
5102
5103
5104













5105
5106
5107
5108
5109
5110
5111
....
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
      }
    }
    whereClauseClear(pWInfo->pWC);
    sqlite3DbFree(db, pWInfo);
  }
}












/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
        assert( sWBI.pSrc->pIndex==0 
                  || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );

        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
          notIndexed |= m;
        }














        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.  (In other words, it must not depend on tables
        **       in inner loops.)
        **
................................................................................
        **       An indexable full-table-scan from reaching rule (3).
        **
        **   (4) The plan cost must be lower than prior plans, where "cost"
        **       is defined by the compareCost() function above. 
        */
        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          WHERETRACE(("   === table %d (%s) is best so far\n"
                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,







>
>
>
>
>
>
>
>
>
>







 







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







 







|
|







4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
....
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
....
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
      }
    }
    whereClauseClear(pWInfo->pWC);
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if the wsFlags indicate that a full table scan (or a
** full scan of a covering index) is indicated.
*/
static int isFullscan(unsigned wsFlags){
  if( wsFlags & WHERE_COVER_SCAN ) return 1;
  if( (wsFlags & WHERE_NOT_FULLSCAN)==0 ) return 1;
  return 0;
}


/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
        assert( sWBI.pSrc->pIndex==0 
                  || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );

        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
          notIndexed |= m;
        }
        if( isOptimal ){
          pWInfo->a[j].rOptCost = sWBI.cost.rCost;
        }else if( iFrom<nTabList-1 ){
          /* If two or more tables have nearly the same outer loop cost,
          ** very different inner loop (optimal) cost, we want to choose
          ** for the outer loop that table which benefits the least from
          ** being in the inner loop.  The following code scales the 
          ** outer loop cost estimate to accomplish that. */
          WHERETRACE(("   scaling cost from %.1f to %.1f\n",
                      sWBI.cost.rCost,
                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));
          sWBI.cost.rCost /= pWInfo->a[j].rOptCost;
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.  (In other words, it must not depend on tables
        **       in inner loops.)
        **
................................................................................
        **       An indexable full-table-scan from reaching rule (3).
        **
        **   (4) The plan cost must be lower than prior plans, where "cost"
        **       is defined by the compareCost() function above. 
        */
        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                || isFullscan(bestPlan.plan.wsFlags)
                || !isFullscan(sWBI.cost.plan.wsFlags))
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          WHERETRACE(("   === table %d (%s) is best so far\n"
                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,

Changes to test/orderby1.test.

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
...
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
...
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 1.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 1.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 1.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 1.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 1.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 1.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 1.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 1.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 1.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# optimized out

do_test 1.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 1.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 1.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out


# Reconstruct the test data to use indices rather than integer primary keys.
#
do_test 2.0 {
................................................................................
        (20, 1, 'two-a'),
        (3,  1, 'three-a');
    COMMIT;
  }
} {}
do_test 2.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 2.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

do_test 2.1c {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.1d {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 2.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 2.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 2.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 2.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 2.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 2.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 2.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 2.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 2.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# optimized out

do_test 2.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 2.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 2.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out


# Generate another test dataset, but this time using mixed ASC/DESC indices.
#
do_test 3.0 {
................................................................................
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 3.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# Verify that the ORDER BY clause is optimized out
#
do_test 3.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 3.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# The output is sorted manually in this case.
#
do_test 3.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 3.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 3.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Without the mixed ASC/DESC on ORDER BY
#
do_test 3.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 3.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
do_test 3.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 3.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 3.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 3.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# optimzed out


do_test 3.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 3.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 3.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# inverted ASC/DESC is optimized out


finish_test







|








|








|








|









|





|









|




|





|






|




|





|





|




|





|







 







|








|





|





|








|








|









|





|









|




|





|






|




|





|





|




|





|







 







|








|








|








|









|





|









|




|





|






|




|





|






|




|





|





44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
...
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
...
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 1.1a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 1.2a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 1.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 1.4a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 1.4b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 1.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 1.5a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 1.5b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 1.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# optimized out

do_test 1.6a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 1.6b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 1.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out


# Reconstruct the test data to use indices rather than integer primary keys.
#
do_test 2.0 {
................................................................................
        (20, 1, 'two-a'),
        (3,  1, 'three-a');
    COMMIT;
  }
} {}
do_test 2.1a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 2.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

do_test 2.1c {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.1d {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 2.2a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 2.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 2.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 2.4a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 2.4b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 2.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 2.5a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 2.5b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 2.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# optimized out

do_test 2.6a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 2.6b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 2.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out


# Generate another test dataset, but this time using mixed ASC/DESC indices.
#
do_test 3.0 {
................................................................................
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 3.1a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# Verify that the ORDER BY clause is optimized out
#
do_test 3.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 3.2a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# The output is sorted manually in this case.
#
do_test 3.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 3.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 3.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Without the mixed ASC/DESC on ORDER BY
#
do_test 3.4a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 3.4b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
do_test 3.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 3.5a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 3.5b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 3.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# optimzed out


do_test 3.6a {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 3.6b {
  db eval {
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 3.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# inverted ASC/DESC is optimized out


finish_test

Added test/whereE.test.





























































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 2012 November 9
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the query planner to make sure it
# is making good planning decisions.
#


set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix whereE

do_execsql_test 1.1 {
  CREATE TABLE t1(a,b);
  INSERT INTO t1 VALUES(1,10), (2,20), (3,30), (2,22), (3, 33);
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  ALTER TABLE t1 ADD COLUMN c;
  UPDATE t1 SET c=a*rowid+10000;
  CREATE INDEX t1ab ON t1(a,b);
  
  CREATE TABLE t2(x,y);
  INSERT INTO t2 VALUES(4,44),(5,55),(6,66),(7,77);
  INSERT INTO t2 SELECT x+4, (x+4)*11 FROM t2;
  INSERT INTO t2 SELECT x+8, (x+8)*11 FROM t2;
  INSERT INTO t2 SELECT x+16, (x+16)*11 FROM t2;
  INSERT INTO t2 SELECT x+32, (x+32)*11 FROM t2;
  INSERT INTO t2 SELECT x+64, (x+32)*11 FROM t2;
  ALTER TABLE t2 ADD COLUMN z;
  UPDATE t2 SET z=2;
  CREATE UNIQUE INDEX t2zx ON t2(z,x);

  EXPLAIN QUERY PLAN SELECT x FROM t1, t2 WHERE a=z AND c=x;
} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/}
do_execsql_test 1.2 {
  EXPLAIN QUERY PLAN SELECT x FROM t2, t1 WHERE a=z AND c=x;
} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/}
do_execsql_test 1.3 {
  ANALYZE;
  EXPLAIN QUERY PLAN SELECT x FROM t1, t2 WHERE a=z AND c=x;
} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/}
do_execsql_test 1.4 {
  EXPLAIN QUERY PLAN SELECT x FROM t2, t1 WHERE a=z AND c=x;
} {/.*SCAN TABLE t1 .*SEARCH TABLE t2 .*/}

finish_test

Added test/whereF.test.







































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# 2012 November 9
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
# Test cases for query planning decisions.


#
# The tests in this file demonstrate the behaviour of the query planner
# in determining the order in which joined tables are scanned.
#
# Assume there are two tables being joined - t1 and t2. Each has a cost
# if it is the outer loop, and a cost if it is the inner loop. As follows:
#
#   t1(outer) - cost of scanning t1 as the outer loop.
#   t1(inner) - cost of scanning t1 as the inner loop.
#   t2(outer) - cost of scanning t2 as the outer loop.
#   t2(inner) - cost of scanning t2 as the inner loop.
#
# Depending on the order in which the planner nests the scans, the total
# cost of the join query is one of:
#
#   t1(outer) * t2(inner)
#   t2(outer) * t1(inner)
#
# The tests in this file attempt to verify that the planner nests joins in
# the correct order when the following are true:
#
#   + (t1(outer) * t2(inner)) > (t1(inner) * t2(outer)
#   +  t1(outer) < t2(outer)
#
# In other words, when the best overall query plan has t2 as the outer loop,
# but when the outer loop is considered independent of the inner, t1 is the
# most efficient choice.
#
# In order to make them more predictable, automatic indexes are turned off for
# the tests in this file.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix x

do_execsql_test 1.0 {
  PRAGMA automatic_index = 0;
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(d, e, f);
  CREATE UNIQUE INDEX i1 ON t1(a);
  CREATE UNIQUE INDEX i2 ON t2(d);
} {}

foreach {tn sql} {
  1 "SELECT * FROM t1,           t2 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10"
  2 "SELECT * FROM t2,           t1 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10"
  3 "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10"
} {
  do_test 1.$tn {
    db eval "EXPLAIN QUERY PLAN $sql"
   } {/.*SCAN TABLE t2 .*SEARCH TABLE t1 .*/}
}

do_execsql_test 2.0 {
  DROP TABLE t1;
  DROP TABLE t2;
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(d, e, f);

  CREATE UNIQUE INDEX i1 ON t1(a);
  CREATE UNIQUE INDEX i2 ON t1(b);
  CREATE UNIQUE INDEX i3 ON t2(d);
} {}

foreach {tn sql} {
  1 "SELECT * FROM t1,           t2 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"
  2 "SELECT * FROM t2,           t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"
  3 "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"
} {
  do_test 2.$tn {
    db eval "EXPLAIN QUERY PLAN $sql"
   } {/.*SCAN TABLE t2 .*SEARCH TABLE t1 .*/}
}

do_execsql_test 3.0 {
  DROP TABLE t1;
  DROP TABLE t2;
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(d, e, f);

  CREATE UNIQUE INDEX i1 ON t1(a, b);
  CREATE INDEX i2 ON t2(d);
} {}

foreach {tn sql} {
  1 {SELECT t1.a, t1.b, t2.d, t2.e FROM t1, t2 
     WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)}

  2 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2, t1 
     WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)}

  3 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2 CROSS JOIN t1 
     WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)}
} {
  do_test 3.$tn {
    db eval "EXPLAIN QUERY PLAN $sql"
   } {/.*SCAN TABLE t2 .*SEARCH TABLE t1 .*/}
}

finish_test