/ Check-in [5c243eec]
Login

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

Overview
Comment:When the left-hand side of a WHERE clause contraint is a UNIQUE column, and that term of the WHERE clause is not used for indexing, assume that the term reduces the number of output rows by half. This is one proposed fix for ticket [e8b674241947eb3ba4]
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | unique-constraint-weights
Files: files | file ages | folders
SHA3-256: 5c243eec7bcccda3f97c20c2f8a44e2811807615cf0ef378bb548f0791c55964
User & Date: drh 2018-10-05 20:09:07
Context
2018-10-05
20:09
When the left-hand side of a WHERE clause contraint is a UNIQUE column, and that term of the WHERE clause is not used for indexing, assume that the term reduces the number of output rows by half. This is one proposed fix for ticket [e8b674241947eb3ba4] Leaf check-in: 5c243eec user: drh tags: unique-constraint-weights
15:10
Changes to geopoly to silience false-positive warnings coming out of clang. check-in: 11d9015f user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtreeC.test.

173
174
175
176
177
178
179
180

181
182
183
184
185
186
187
...
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
} {1 1 3 {}}

#--------------------------------------------------------------------
# Test that the sqlite_stat1 data is used correctly.
#
reset_db
do_execsql_test 5.1 {
  CREATE TABLE t1(x PRIMARY KEY, y);

  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2, +d1);

  INSERT INTO t1(x) VALUES(1);
  INSERT INTO t1(x) SELECT x+1 FROM t1;   --   2
  INSERT INTO t1(x) SELECT x+2 FROM t1;   --   4
  INSERT INTO t1(x) SELECT x+4 FROM t1;   --   8
  INSERT INTO t1(x) SELECT x+8 FROM t1;   --  16
................................................................................
db close
sqlite3 db test.db
do_eqp_test 5.4 {
  SELECT * FROM t1, rt WHERE x==id;
} {
  QUERY PLAN
  |--SCAN TABLE rt VIRTUAL TABLE INDEX 2:
  `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (x=?)
}

# Delete the ANALYZE data. "t1" should be the outer loop again.
#
do_execsql_test 5.5 { DROP TABLE sqlite_stat1; }
db close
sqlite3 db test.db







|
>







 







|







173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
...
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
} {1 1 3 {}}

#--------------------------------------------------------------------
# Test that the sqlite_stat1 data is used correctly.
#
reset_db
do_execsql_test 5.1 {
  CREATE TABLE t1(x, y);
  CREATE INDEX t1x ON t1(x);
  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2, +d1);

  INSERT INTO t1(x) VALUES(1);
  INSERT INTO t1(x) SELECT x+1 FROM t1;   --   2
  INSERT INTO t1(x) SELECT x+2 FROM t1;   --   4
  INSERT INTO t1(x) SELECT x+4 FROM t1;   --   8
  INSERT INTO t1(x) SELECT x+8 FROM t1;   --  16
................................................................................
db close
sqlite3 db test.db
do_eqp_test 5.4 {
  SELECT * FROM t1, rt WHERE x==id;
} {
  QUERY PLAN
  |--SCAN TABLE rt VIRTUAL TABLE INDEX 2:
  `--SEARCH TABLE t1 USING INDEX t1x (x=?)
}

# Delete the ANALYZE data. "t1" should be the outer loop again.
#
do_execsql_test 5.5 { DROP TABLE sqlite_stat1; }
db close
sqlite3 db test.db

Changes to src/where.c.

2472
2473
2474
2475
2476
2477
2478













2479
2480
2481
2482
2483
2484
2485
     && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
    ){
      continue;
    }

    if( IsUniqueIndex(pProbe) && saved_nEq==pProbe->nKeyCol-1 ){
      pBuilder->bldFlags |= SQLITE_BLDF_UNIQUE;













    }else{
      pBuilder->bldFlags |= SQLITE_BLDF_INDEXED;
    }
    pNew->wsFlags = saved_wsFlags;
    pNew->u.btree.nEq = saved_nEq;
    pNew->u.btree.nBtm = saved_nBtm;
    pNew->u.btree.nTop = saved_nTop;







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







2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
     && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
    ){
      continue;
    }

    if( IsUniqueIndex(pProbe) && saved_nEq==pProbe->nKeyCol-1 ){
      pBuilder->bldFlags |= SQLITE_BLDF_UNIQUE;
      if( pProbe->nKeyCol==1
       && pTerm->truthProb>=0
       && (pTerm->eOperator & (WO_EQ|WO_IS|WO_IN))!=0
      ){
        /* If the LHS of an == or IS or IN operator is unique, then
        ** make the guess that the truth probability of the expression is 50%.
        ** This is probably an overestimate, but we want to be safe.  Without
        ** this guess, the truth probability would be 93.75%, which is usually
        ** a little too high for such a constraint, resulting in an output row
        ** count that is too large, and throwing off the calcualations on the
        ** cost of an external sort. */
        pTerm->truthProb = -10;
      }
    }else{
      pBuilder->bldFlags |= SQLITE_BLDF_INDEXED;
    }
    pNew->wsFlags = saved_wsFlags;
    pNew->u.btree.nEq = saved_nEq;
    pNew->u.btree.nBtm = saved_nBtm;
    pNew->u.btree.nTop = saved_nTop;

Changes to test/whereF.test.

48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
..
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
source $testdir/tester.tcl
set testprefix whereF

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_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"
} {







|
|







 







|
|
|







48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
..
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
source $testdir/tester.tcl
set testprefix whereF

do_execsql_test 1.0 {
  PRAGMA automatic_index = 0;
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(d, e, f);
  CREATE INDEX i1 ON t1(a);
  CREATE 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_execsql_test 2.0 {
  DROP TABLE t1;
  DROP TABLE t2;
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(d, e, f);

  CREATE INDEX i1 ON t1(a);
  CREATE INDEX i2 ON t1(b);
  CREATE 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"
} {

Changes to test/whereG.test.

147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
       AND album.aid=track.aid;
  }
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}

# Commuting a term of the WHERE clause should not change the query plan
#
do_execsql_test whereG-3.0 {
  CREATE TABLE a(a1 PRIMARY KEY, a2);
  CREATE TABLE b(b1 PRIMARY KEY, b2);
} {}
do_eqp_test whereG-3.1 {
  SELECT * FROM a, b WHERE b1=a1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.2 {
  SELECT * FROM a, b WHERE a1=b1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}







|
|







147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
       AND album.aid=track.aid;
  }
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}

# Commuting a term of the WHERE clause should not change the query plan
#
do_execsql_test whereG-3.0 {
  CREATE TABLE a(a1, a2);  CREATE INDEX a_1 ON a(a1);
  CREATE TABLE b(b1, b2);  CREATE INDEX b_1 ON b(b1);
} {}
do_eqp_test whereG-3.1 {
  SELECT * FROM a, b WHERE b1=a1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.2 {
  SELECT * FROM a, b WHERE a1=b1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}

Changes to test/whereL.test.

43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
do_eqp_test 120 {
  SELECT * FROM t1, t2, t3
   WHERE t1.a=t2.a AND t2.a=t3.j AND t3.j=5
  ORDER BY t1.a;
} {
  QUERY PLAN
  |--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
  |--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?)
  `--SCAN TABLE t3
}

# Constant propagation in the face of collating sequences:
#
do_execsql_test 200 {
  CREATE TABLE c3(x COLLATE binary, y COLLATE nocase, z COLLATE binary);
  CREATE INDEX c3x ON c3(x);







|
|







43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
do_eqp_test 120 {
  SELECT * FROM t1, t2, t3
   WHERE t1.a=t2.a AND t2.a=t3.j AND t3.j=5
  ORDER BY t1.a;
} {
  QUERY PLAN
  |--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?)
  |--SEARCH TABLE t2 USING AUTOMATIC PARTIAL COVERING INDEX (a=?)
  `--SEARCH TABLE t3 USING AUTOMATIC PARTIAL COVERING INDEX (j=?)
}

# Constant propagation in the face of collating sequences:
#
do_execsql_test 200 {
  CREATE TABLE c3(x COLLATE binary, y COLLATE nocase, z COLLATE binary);
  CREATE INDEX c3x ON c3(x);

Changes to test/with3.test.

122
123
124
125
126
127
128
129
130
131
132
133
  |  |  |--SCAN CONSTANT ROW
  |  |  `--SCALAR SUBQUERY
  |  |     `--SCAN TABLE w2
  |  `--RECURSIVE STEP
  |     |--SCAN TABLE w1
  |     `--SCAN TABLE c
  |--SCAN SUBQUERY xxxxxx
  |--SEARCH TABLE w2 USING INTEGER PRIMARY KEY (rowid=?)
  `--SEARCH TABLE w1 USING INTEGER PRIMARY KEY (rowid=?)
}

finish_test







|
|



122
123
124
125
126
127
128
129
130
131
132
133
  |  |  |--SCAN CONSTANT ROW
  |  |  `--SCALAR SUBQUERY
  |  |     `--SCAN TABLE w2
  |  `--RECURSIVE STEP
  |     |--SCAN TABLE w1
  |     `--SCAN TABLE c
  |--SCAN SUBQUERY xxxxxx
  |--SEARCH TABLE w1 USING INTEGER PRIMARY KEY (rowid=?)
  `--SEARCH TABLE w2 USING INTEGER PRIMARY KEY (rowid=?)
}

finish_test