SQLite

Check-in [9870e4c4fe]
Login

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

Overview
Comment:Fix for [2a5629202f]. When considering whether or not a UNIQUE index may be used to optimize an ORDER BY clause, do not assume that all index entries are distinct unless there is some reason to believe that the index contains no NULL values.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9870e4c4fef10112c987c40cb1b95255a7214202
User & Date: dan 2012-04-20 15:24:53.110
Original Comment: Fix for 2a5629202f. When considering whether or not a UNIQUE index may be used to optimize an ORDER BY clause, do not assume that all index entries are distinct unless there is some reason to believe that the index contains no NULL values.
References
2012-04-20
17:43 Ticket [2a5629202f] Malfunctioning interaction between a multi-term ORDER BY clause and UNIQUE index containing NULL values status still Closed with 1 other change (artifact: 1d908f1b6a user: dan)
Context
2012-04-20
16:59
Do not consider a DISTINCT clause redundant unless a subset of the result-set is collectively subject to a UNIQUE constraint and it can be guaranteed that all columns of the subset are NOT NULL (either due to NOT NULL constraints WHERE clause terms). Fix for [385a5b56b9]. (check-in: 7b8548b187 user: dan tags: trunk)
15:24
Fix for [2a5629202f]. When considering whether or not a UNIQUE index may be used to optimize an ORDER BY clause, do not assume that all index entries are distinct unless there is some reason to believe that the index contains no NULL values. (check-in: 9870e4c4fe user: dan tags: trunk)
12:02
Remove obsolete art. (check-in: 372a90e226 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
1714
1715
1716
1717
1718
1719
1720
1721




1722
1723
1724

1725

1726



1727



1728
1729
1730
1731
1732
1733
1734
1735
  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }
  if( pIdx->onError!=OE_None && i==pIdx->nColumn
      && (wsFlags & WHERE_COLUMN_NULL)==0
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){




    /* All terms of this index match some prefix of the ORDER BY clause
    ** and the index is UNIQUE and no terms on the tail of the ORDER BY
    ** clause reference other tables in a join.  If this is all true then

    ** the order by clause is superfluous.  Not that if the matching

    ** condition is IS NULL then the result is not necessarily unique



    ** even on a UNIQUE index, so disallow those cases. */



    return 1;
  }
  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating







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







1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }
  if( pIdx->onError!=OE_None && i==pIdx->nColumn
      && (wsFlags & WHERE_COLUMN_NULL)==0
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) 
  ){
    Column *aCol = pIdx->pTable->aCol;
    int i;

    /* All terms of this index match some prefix of the ORDER BY clause,
    ** the index is UNIQUE, and no terms on the tail of the ORDER BY
    ** refer to other tables in a join. So, assuming that the index entries
    ** visited contain no NULL values, then this index delivers rows in
    ** the required order.
    **
    ** It is not possible for any of the first nEqCol index fields to be
    ** NULL (since the corresponding "=" operator in the WHERE clause would 
    ** not be true). So if all remaining index columns have NOT NULL 
    ** constaints attached to them, we can be confident that the visited
    ** index entries are free of NULLs.  */
    for(i=nEqCol; i<pIdx->nColumn; i++){
      if( aCol[pIdx->aiColumn[i]].notNull==0 ) break;
    }
    return (i>=pIdx->nColumn);
  }
  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
Added test/tkt-2a5629202f.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
# 2012 April 19
#
# 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.
#
#***********************************************************************
# The tests in this file were used while developing the SQLite 4 code. 
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix tkt-2a5629202f

# This procedure executes the SQL.  Then it checks to see if the OP_Sort
# opcode was executed.  If an OP_Sort did occur, then "sort" is appended
# to the result.  If no OP_Sort happened, then "nosort" is appended.
#
# This procedure is used to check to make sure sorting is or is not
# occurring as expected.
#
proc cksort {sql} {
  set data [execsql $sql]
  if {[db status sort]} {set x sort} {set x nosort}
  lappend data $x
  return $data
}

do_execsql_test 1.1 {
  CREATE TABLE t8(b TEXT, c TEXT);
  INSERT INTO t8 VALUES('a',  'one');
  INSERT INTO t8 VALUES('b',  'two');
  INSERT INTO t8 VALUES(NULL, 'three');
  INSERT INTO t8 VALUES(NULL, 'four');
}

do_execsql_test 1.2 {
  SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
} {null/four null/three a/one b/two}

do_execsql_test 1.3 {
  CREATE UNIQUE INDEX i1 ON t8(b);
  SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
} {null/four null/three a/one b/two}

#-------------------------------------------------------------------------
#

do_execsql_test 2.1 {
  CREATE TABLE t2(a, b NOT NULL, c);
  CREATE UNIQUE INDEX t2ab ON t2(a, b);
  CREATE UNIQUE INDEX t2ba ON t2(b, a);
}

do_test 2.2 {
  cksort { SELECT * FROM t2 WHERE a = 10 ORDER BY a, b, c }
} {nosort}

do_test 2.3 {
  cksort { SELECT * FROM t2 WHERE b = 10 ORDER BY a, b, c }
} {sort}

do_test 2.4 {
  cksort { SELECT * FROM t2 WHERE a IS NULL ORDER BY a, b, c }
} {sort}

finish_test

Changes to test/where.test.
1101
1102
1103
1104
1105
1106
1107

1108
1109
1110
1111
1112

1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.4 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {

  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.6 {

  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 nosort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {







>



|

>



|







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
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.4 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.5 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.6 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {