/ Check-in [56549f45]
Login

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

Overview
Comment:Avoid unnecessary collating sequence and affinity restrictions on the use of transitivity. Add test cases to show that the restrictions are not needed.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | transitive-constraints
Files: files | file ages | folders
SHA1: 56549f45666b53876012df5c2bdf813474e10925
User & Date: drh 2013-01-17 16:18:55
Context
2013-01-17
16:43
Add the ability to disable transitive constraints using the sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS) interface. Closed-Leaf check-in: 593d67c8 user: drh tags: transitive-constraints
16:18
Avoid unnecessary collating sequence and affinity restrictions on the use of transitivity. Add test cases to show that the restrictions are not needed. check-in: 56549f45 user: drh tags: transitive-constraints
15:05
Make more aggressive use of transitivity in optimizing queries. Add a test case. check-in: d9676284 user: drh tags: transitive-constraints
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

683
684
685
686
687
688
689
690


691
692
693
694
695
696
697
698
699
700
701
702
703


704
705
706
707
708
709
710
....
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
....
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;
              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
              if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;


      
              /* Figure out the collation sequence required from an index for
              ** it to be useful for optimising expression pX. Store this
              ** value in variable pColl.
              */
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;


            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
................................................................................
      }
      pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

/*
** Check to see if pExpr is an expression of the form A==B where both
** A and B are columns with the same affinity and collating sequence.
** If A and B are equivalent, return true.
*/
static int isEquivalenceExpr(Parse *pParse, Expr *pExpr){
  const CollSeq *pCLeft, *pCRight;
  if( pExpr->op!=TK_EQ ) return 0;
  if( ExprHasProperty(pExpr, EP_FromJoin) ){
    return 0;
  }
  assert( sqlite3ExprSkipCollate(pExpr->pRight)->op==TK_COLUMN );
  assert( sqlite3ExprSkipCollate(pExpr->pLeft)->op==TK_COLUMN );
  if( sqlite3ExprAffinity(pExpr->pLeft)!=sqlite3ExprAffinity(pExpr->pRight) ){
    return 0;
  }
  pCLeft = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
  if( pCLeft ){
    pCRight = sqlite3ExprCollSeq(pParse, pExpr->pRight);
    if( pCRight && pCRight!=pCLeft ){
      return 0;
    }
  }
  return 1;
}

/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
** If the expression is of the form "<expr> <op> X" it gets commuted
................................................................................
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->wtFlags |= TERM_COPIED;
        if( isEquivalenceExpr(pParse, pExpr) ){
          pTerm->eOperator |= WO_EQUIV;
          eExtraOp = WO_EQUIV;
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }







|
>
>












|
>
>







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|







683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
....
1196
1197
1198
1199
1200
1201
1202


























1203
1204
1205
1206
1207
1208
1209
....
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;
              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
              if( !sqlite3IndexAffinityOk(pX, idxaff) ){
                continue;
              }
      
              /* Figure out the collation sequence required from an index for
              ** it to be useful for optimising expression pX. Store this
              ** value in variable pColl.
              */
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
                continue;
              }
            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
................................................................................
      }
      pTerm->eOperator = WO_NOOP;  /* case 1 trumps case 2 */
    }
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */



























/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
** If the expression is of the form "<expr> <op> X" it gets commuted
................................................................................
        idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( idxNew==0 ) return;
        pNew = &pWC->a[idxNew];
        pNew->iParent = idxTerm;
        pTerm = &pWC->a[idxTerm];
        pTerm->nChild = 1;
        pTerm->wtFlags |= TERM_COPIED;
        if( pExpr->op==TK_EQ && !ExprHasProperty(pExpr, EP_FromJoin) ){
          pTerm->eOperator |= WO_EQUIV;
          eExtraOp = WO_EQUIV;
        }
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }

Added test/transitive1.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
# 2013 April 17
#
# 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 script is testing of transitive WHERE clause constraints
#

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

do_execsql_test transitive1-100 {
  CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE);
  INSERT INTO t1 VALUES('abc','abc','Abc');
  INSERT INTO t1 VALUES('def','def','def');
  INSERT INTO t1 VALUES('ghi','ghi','GHI');
  CREATE INDEX t1a1 ON t1(a);
  CREATE INDEX t1a2 ON t1(a COLLATE nocase);

  SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF';
} {def def def}
do_execsql_test transitive1-110 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a;
} {def def def ghi ghi GHI}
do_execsql_test transitive1-120 {
  SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a;
} {abc abc Abc def def def}

do_execsql_test transitive1-200 {
  CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT);
  INSERT INTO t2 VALUES(100,100,100);
  INSERT INTO t2 VALUES(20,20,20);
  INSERT INTO t2 VALUES(3,3,3);

  SELECT * FROM t2 WHERE a=b AND c=b AND c=20;
} {20 20 20}
do_execsql_test transitive1-210 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a;
} {3 3 3 20 20 20}
do_execsql_test transitive1-220 {
  SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a;
} {20 20 20 100 100 100}

finish_test