SQLite

Check-in [4f07661279]
Login

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

Overview
Comment:Disable an overzealous optimization the omitted sorting on a join if the first table gave a unique result. The sort can only be omitted if all tables in the join are unique. Ticket #1358. (CVS 2589)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4f07661279fb11a06b3ddffeda672f077c0d306a
User & Date: drh 2005-08-13 16:13:05.000
Context
2005-08-13
17:17
Give the same access permissions to journal files as is given to databases. (CVS 2590) (check-in: 7961ec0ccb user: drh tags: trunk)
16:13
Disable an overzealous optimization the omitted sorting on a join if the first table gave a unique result. The sort can only be omitted if all tables in the join are unique. Ticket #1358. (CVS 2589) (check-in: 4f07661279 user: drh tags: trunk)
13:40
Fix a comment in printf. (CVS 2588) (check-in: 1054685f15 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.160 2005/08/12 22:56:09 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.161 2005/08/13 16:13:05 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".  pIdx is an index on pTab.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints.  Any of these columns may be missing from the ORDER BY
** clause and the match can still be a success.
**
** If the index is UNIQUE, then the ORDER BY clause is allowed to have
** additional terms past the end of the index and the match will still
** be a success.
**
** All terms of the ORDER BY that match against the index must be either
** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
** index do not need to satisfy this constraint.)  The *pbRev value is
** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
** the ORDER BY clause is all ASC.
*/
static int isSortingIndex(







<
<
<
<







715
716
717
718
719
720
721




722
723
724
725
726
727
728
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".  pIdx is an index on pTab.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints.  Any of these columns may be missing from the ORDER BY
** clause and the match can still be a success.
**




** All terms of the ORDER BY that match against the index must be either
** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
** index do not need to satisfy this constraint.)  The *pbRev value is
** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
** the ORDER BY clause is all ASC.
*/
static int isSortingIndex(
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
      sortOrder = pTerm->sortOrder;
    }
    j++;
    pTerm++;
  }

  /* The index can be used for sorting if all terms of the ORDER BY clause
  ** or covered or if we ran out of index columns and the it is a UNIQUE
  ** index.
  */
  if( j>=nTerm || (i>=pIdx->nColumn && pIdx->onError!=OE_None) ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
    return 1;
  }
  return 0;
}

/*







<
|

|







783
784
785
786
787
788
789

790
791
792
793
794
795
796
797
798
799
      sortOrder = pTerm->sortOrder;
    }
    j++;
    pTerm++;
  }

  /* The index can be used for sorting if all terms of the ORDER BY clause

  ** are covered.
  */
  if( j>=nTerm ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
    return 1;
  }
  return 0;
}

/*
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846

/*
** Prepare a crude estimate of the logorithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operatings with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
**
** We can assume N>=1.0;
*/
static double estLog(double N){
  double logN = 1.0;
  double x = 10.0;
  while( N>x ){
    logN = logN+1.0;
    x *= 10;
  }
  return logN;
}

/*
** Find the best index for accessing a particular table.  Return a pointer







<
<





|







820
821
822
823
824
825
826


827
828
829
830
831
832
833
834
835
836
837
838
839

/*
** Prepare a crude estimate of the logorithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operatings with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.


*/
static double estLog(double N){
  double logN = 1.0;
  double x = 10.0;
  while( N>x ){
    logN += 1.0;
    x *= 10;
  }
  return logN;
}

/*
** Find the best index for accessing a particular table.  Return a pointer
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (flags & WHERE_COLUMN_IN)==0 &&
        isSortingIndex(pParse, pProbe, pSrc->pTab, iCur, pOrderBy, nEq, &rev) ){
        if( flags==0 ){
          flags = WHERE_COLUMN_RANGE;
        }
        flags |= WHERE_ORDERBY;
        if( rev ){
          flags |= WHERE_REVERSE;
        }







|







1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
      }
    }

    /* Add the additional cost of sorting if that is a factor.
    */
    if( pOrderBy ){
      if( (flags & WHERE_COLUMN_IN)==0 &&
           isSortingIndex(pParse,pProbe,pSrc->pTab,iCur,pOrderBy,nEq,&rev) ){
        if( flags==0 ){
          flags = WHERE_COLUMN_RANGE;
        }
        flags |= WHERE_ORDERBY;
        if( rev ){
          flags |= WHERE_REVERSE;
        }
Changes to test/sort.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2001 September 15.
#
# 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 CREATE TABLE statement.
#
# $Id: sort.test,v 1.21 2005/08/13 12:59:16 drh Exp $

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

# Create a bunch of data to sort against
#
do_test sort-1.0 {













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2001 September 15.
#
# 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 CREATE TABLE statement.
#
# $Id: sort.test,v 1.22 2005/08/13 16:13:06 drh Exp $

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

# Create a bunch of data to sort against
#
do_test sort-1.0 {
426
427
428
429
430
431
432
433
















434
  }
} {3 2 1}
do_test sort-10.3 {
  execsql {
    SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;
  }
} {2 1}

















finish_test








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

426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
  }
} {3 2 1}
do_test sort-10.3 {
  execsql {
    SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;
  }
} {2 1}

# ticket #1358.  Just because one table in a join gives a unique
# result does not mean they all do.  We cannot disable sorting unless
# all tables in the join give unique results.
#
do_test sort-11.1 {
  execsql {
    create table t8(a unique, b, c);
    insert into t8 values(1,2,3);
    insert into t8 values(2,3,4);
    create table t9(x,y);
    insert into t9 values(2,4);
    insert into t9 values(2,3);
    select y from t8, t9 where a=1 order by a, y;
  }
} {3 4}

finish_test
Changes to test/where2.test.
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.4 2005/07/29 19:43:59 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#    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 use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.5 2005/08/13 16:13:06 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
234
235
236
237
238
239
240




241









242


















243
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}


































finish_test







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

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
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} {1 0 4 4 2 1 9 10 sort a i1w b i1zyx}

# Unique queries (queries that are guaranteed to return only a single
# row of result) do not call the sorter.  But all tables must give
# a unique result.  If any one table in the join does not give a unique
# result then sorting is necessary.
#
do_test where2-7.1 {
  cksort {
    create table t8(a unique, b, c);
    insert into t8 values(1,2,3);
    insert into t8 values(2,3,4);
    create table t9(x,y);
    insert into t9 values(2,4);
    insert into t9 values(2,3);
    select y from t8, t9 where a=1 order by a, y;
  }
} {3 4 sort}
do_test where2-7.2 {
  cksort {
    select * from t8 where a=1 order by b, c
  }
} {1 2 3 nosort}
do_test where2-7.3 {
  cksort {
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 sort}
do_test where2-7.4 {
  cksort {
    create unique index i9y on t9(y);
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 nosort}

finish_test