SQLite

Check-in [b7830d232b]
Login

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

Overview
Comment:Also make sure an index that is a proper subset of some other index has a higher cost than that other index. Add test cases.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | query-plan-experiments
Files: files | file ages | folders
SHA1: b7830d232b073a197aa1092e78cb24e88cb10fd3
User & Date: drh 2014-03-31 19:49:00.374
Context
2014-03-31
20:05
Remove an unnecessary conditional. (Closed-Leaf check-in: 7473c4dfc1 user: drh tags: query-plan-experiments)
19:49
Also make sure an index that is a proper subset of some other index has a higher cost than that other index. Add test cases. (check-in: b7830d232b user: drh tags: query-plan-experiments)
18:24
Make sure that an index that covers a proper superset of the WHERE clause terms of some other index has a lower cost than the other index. (check-in: ea8b091004 user: drh tags: query-plan-experiments)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
︙︙
3708
3709
3710
3711
3712
3713
3714
3715

3716










3717

3718
3719
3720
3721
3722
3723
3724
3725


3726
3727
3728
3729

3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743

3744
3745
3746
3747
3748
3749
3750




3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761

      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Compare every WhereLoop X on the list p against pTemplate.  If:

**










**    (1) both X and pTemplate refer to the same table, and

**    (2) both X and pTemplate use a single index, and
**    (3) pTemplate uses all the same WHERE clause terms as X plus
**        at least one more term,
**
** then make sure the cost pTemplate is less than the cost of X, adjusting
** the cost of pTemplate downward if necessary.
**
** Example: When computing the query plan for the SELECT below:


**
**     CREATE TABLE t1(a,b,c,d);
**     CREATE INDEX t1abc ON t1(a,b,c);
**     CREATE INDEX t1bc ON t1(b,c);

**     SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
** 
** Make sure the cost of using three three columns of index t1abc is less
** than the cost of using both columns of t1bc.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  if( pTemplate->nLTerm==0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab==pTemplate->iTab
     && (p->wsFlags & WHERE_INDEXED)!=0
     && p->nLTerm<pTemplate->nLTerm
     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut<=pTemplate->nOut))

    ){
      int i, j;
      for(j=0, i=p->nLTerm-1; i>=0 && j>=0; i--){
        for(j=pTemplate->nLTerm-1; j>=0; j--){
          if( pTemplate->aLTerm[j]==p->aLTerm[i] ) break;
        }
      }




      if( j>=0 ){
        pTemplate->rRun = p->rRun;
        pTemplate->nOut = p->nOut - 1;
      }
    }
  }
}

/*
** Search the list of WhereLoops in *ppPrev looking for one that can be
** supplanted by pTemplate.








|
>
|
>
>
>
>
>
>
>
>
>
>
|
>
|
<
|

|
|

<
>
>

<
<
<
>
|
|
<
<



<

|
|
|


>

<
<
|
|
|
<
>
>
>
>
|
|
|
<








3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730

3731
3732
3733
3734
3735

3736
3737
3738



3739
3740
3741


3742
3743
3744

3745
3746
3747
3748
3749
3750
3751
3752


3753
3754
3755

3756
3757
3758
3759
3760
3761
3762

3763
3764
3765
3766
3767
3768
3769

      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if the set of WHERE clause terms used by pA is a proper
** subset of the WHERE clause terms used by pB.
*/
static int whereLoopProperSubset(const WhereLoop *pA, const WhereLoop *pB){
  int i, j;
  if( pA->nLTerm>=pB->nLTerm ) return 0;
  for(j=0, i=pA->nLTerm-1; i>=0 && j>=0; i--){
    for(j=pB->nLTerm-1; j>=0; j--){
      if( pB->aLTerm[j]==pA->aLTerm[i] ) break;
    }
  }
  return j>=0;
}

/*
** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so

** that:
**
**   (1) pTemplate costs less than any other WhereLoops that are a proper
**       subset of pTemplate
**

**   (2) pTemplate costs more than any other WhereLoops for which pTemplate
**       is a proper subset.
**



** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
** WHERE clause terms than Y and that every WHERE clause term used by X is
** also used by Y.


*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;

  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( p->nLTerm<pTemplate->nLTerm
     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut<=pTemplate->nOut))
     && whereLoopProperSubset(p, pTemplate)
    ){


      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else

    if( p->nLTerm>pTemplate->nLTerm
     && (p->rRun>pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut>=pTemplate->nOut))
     && whereLoopProperSubset(pTemplate, p)
    ){
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut + 1;

    }
  }
}

/*
** Search the list of WhereLoops in *ppPrev looking for one that can be
** supplanted by pTemplate.
︙︙
Added test/whereH.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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

# 2014-03-31
#
# 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 where one candidate index
# covers a proper superset of the WHERE clause terms of another
# candidate index.
#

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

do_execsql_test whereH-1.1 {
  CREATE TABLE t1(a,b,c,d);
  CREATE INDEX t1abc ON t1(a,b,c);
  CREATE INDEX t1bc ON t1(b,c);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
} {/INDEX t1abc /}
do_execsql_test whereH-1.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-2.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d);
  CREATE INDEX t1bc ON t1(b,c);
  CREATE INDEX t1abc ON t1(a,b,c);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
} {/INDEX t1abc /}
do_execsql_test whereH-2.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-3.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1cd ON t1(c,d);
  CREATE INDEX t1bcd ON t1(b,c,d);
  CREATE INDEX t1abcd ON t1(a,b,c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-3.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-4.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1cd ON t1(c,d);
  CREATE INDEX t1abcd ON t1(a,b,c,d);
  CREATE INDEX t1bcd ON t1(b,c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-4.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-5.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1bcd ON t1(b,c,d);
  CREATE INDEX t1cd ON t1(c,d);
  CREATE INDEX t1abcd ON t1(a,b,c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-5.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-6.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1bcd ON t1(b,c,d);
  CREATE INDEX t1abcd ON t1(a,b,c,d);
  CREATE INDEX t1cd ON t1(c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-6.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-7.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1abcd ON t1(a,b,c,d);
  CREATE INDEX t1bcd ON t1(b,c,d);
  CREATE INDEX t1cd ON t1(c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-7.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}

do_execsql_test whereH-8.1 {
  DROP TABLE t1;
  CREATE TABLE t1(a,b,c,d,e);
  CREATE INDEX t1abcd ON t1(a,b,c,d);
  CREATE INDEX t1cd ON t1(c,d);
  CREATE INDEX t1bcd ON t1(b,c,d);

  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {/INDEX t1abcd /}
do_execsql_test whereH-8.2 {
  EXPLAIN QUERY PLAN
  SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d;
} {~/TEMP B-TREE FOR ORDER BY/}



finish_test