/ Changes On Branch exp-indexed-clause
Login

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

Changes In Branch exp-indexed-clause Excluding Merge-Ins

This is equivalent to a diff from fd8b8c4196 to 991a76bf42

2018-05-14
22:46
Make more aggressive use of automatic indexes when processing materalized views and subqueries. (check-in: 172f5bd27e user: drh tags: trunk)
18:09
The restriction on using automatic indexes for low cardinality loops only applies if the cardinality is restricted by a LIMIT clause. (Closed-Leaf check-in: 991a76bf42 user: drh tags: exp-indexed-clause)
17:12
Experimental syntax enhancement for an "INDEXED" keyword following a FROM-clause subquery that indicates that an automatic index on that subquery is suggested. (check-in: 32b3d11050 user: drh tags: exp-indexed-clause)
15:26
Convert the schema creation logic in the rtree extension to use the new sqlite3_str interface. (check-in: fd8b8c4196 user: drh tags: trunk)
12:23
Fix typo in the shell.c source file. (check-in: 389dc0a901 user: mistachkin tags: trunk)

Changes to src/build.c.

3923
3924
3925
3926
3927
3928
3929

3930
3931
3932
3933




3934
3935
3936
3937
3938
3939
3940
  if( p && pIndexedBy->n>0 ){
    struct SrcList_item *pItem;
    assert( p->nSrc>0 );
    pItem = &p->a[p->nSrc-1];
    assert( pItem->fg.notIndexed==0 );
    assert( pItem->fg.isIndexedBy==0 );
    assert( pItem->fg.isTabFunc==0 );

    if( pIndexedBy->n==1 && !pIndexedBy->z ){
      /* A "NOT INDEXED" clause was supplied. See parse.y 
      ** construct "indexed_opt" for details. */
      pItem->fg.notIndexed = 1;




    }else{
      pItem->u1.zIndexedBy = sqlite3NameFromToken(pParse->db, pIndexedBy);
      pItem->fg.isIndexedBy = 1;
    }
  }
}








>
|
<
<
|
>
>
>
>







3923
3924
3925
3926
3927
3928
3929
3930
3931


3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
  if( p && pIndexedBy->n>0 ){
    struct SrcList_item *pItem;
    assert( p->nSrc>0 );
    pItem = &p->a[p->nSrc-1];
    assert( pItem->fg.notIndexed==0 );
    assert( pItem->fg.isIndexedBy==0 );
    assert( pItem->fg.isTabFunc==0 );
    if( pIndexedBy->n>=1 && !pIndexedBy->z ){
      if( pIndexedBy->n==1 ){


        pItem->fg.notIndexed = 1;
      }else{
        assert( pIndexedBy->n==2 );
        pItem->fg.useAutoIdx = 1;
      }
    }else{
      pItem->u1.zIndexedBy = sqlite3NameFromToken(pParse->db, pIndexedBy);
      pItem->fg.isIndexedBy = 1;
    }
  }
}

Changes to src/parse.y.

648
649
650
651
652
653
654
655
656

657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679

680
681
682
683
684
685
686
seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) LP exprlist(E) RP as(Z)
                  on_opt(N) using_opt(U). {
  A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U);
  sqlite3SrcListFuncArgs(pParse, A, E);
}
%ifndef SQLITE_OMIT_SUBQUERY
  seltablist(A) ::= stl_prefix(A) LP select(S) RP
                    as(Z) on_opt(N) using_opt(U). {
    A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,S,N,U);

  }
  seltablist(A) ::= stl_prefix(A) LP seltablist(F) RP
                    as(Z) on_opt(N) using_opt(U). {
    if( A==0 && Z.n==0 && N==0 && U==0 ){
      A = F;
    }else if( F->nSrc==1 ){
      A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,0,N,U);
      if( A ){
        struct SrcList_item *pNew = &A->a[A->nSrc-1];
        struct SrcList_item *pOld = F->a;
        pNew->zName = pOld->zName;
        pNew->zDatabase = pOld->zDatabase;
        pNew->pSelect = pOld->pSelect;
        pOld->zName = pOld->zDatabase = 0;
        pOld->pSelect = 0;
      }
      sqlite3SrcListDelete(pParse->db, F);
    }else{
      Select *pSubquery;
      sqlite3SrcListShiftJoinType(F);
      pSubquery = sqlite3SelectNew(pParse,0,F,0,0,0,0,SF_NestedFrom,0);
      A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,pSubquery,N,U);
    }

  }
%endif  SQLITE_OMIT_SUBQUERY

%type dbnm {Token}
dbnm(A) ::= .          {A.z=0; A.n=0;}
dbnm(A) ::= DOT nm(X). {A = X;}








|

>


|




















>







648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) LP exprlist(E) RP as(Z)
                  on_opt(N) using_opt(U). {
  A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U);
  sqlite3SrcListFuncArgs(pParse, A, E);
}
%ifndef SQLITE_OMIT_SUBQUERY
  seltablist(A) ::= stl_prefix(A) LP select(S) RP
                    as(Z) indexed_opt(I) on_opt(N) using_opt(U). {
    A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,S,N,U);
    sqlite3SrcListIndexedBy(pParse, A, &I);
  }
  seltablist(A) ::= stl_prefix(A) LP seltablist(F) RP
                    as(Z) indexed_opt(I) on_opt(N) using_opt(U). {
    if( A==0 && Z.n==0 && N==0 && U==0 ){
      A = F;
    }else if( F->nSrc==1 ){
      A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,0,N,U);
      if( A ){
        struct SrcList_item *pNew = &A->a[A->nSrc-1];
        struct SrcList_item *pOld = F->a;
        pNew->zName = pOld->zName;
        pNew->zDatabase = pOld->zDatabase;
        pNew->pSelect = pOld->pSelect;
        pOld->zName = pOld->zDatabase = 0;
        pOld->pSelect = 0;
      }
      sqlite3SrcListDelete(pParse->db, F);
    }else{
      Select *pSubquery;
      sqlite3SrcListShiftJoinType(F);
      pSubquery = sqlite3SelectNew(pParse,0,F,0,0,0,0,SF_NestedFrom,0);
      A = sqlite3SrcListAppendFromTerm(pParse,A,0,0,&Z,pSubquery,N,U);
    }
    sqlite3SrcListIndexedBy(pParse, A, &I);
  }
%endif  SQLITE_OMIT_SUBQUERY

%type dbnm {Token}
dbnm(A) ::= .          {A.z=0; A.n=0;}
dbnm(A) ::= DOT nm(X). {A = X;}

747
748
749
750
751
752
753

754
755
756
757
758
759
760
// normally illegal. The sqlite3SrcListIndexedBy() function 
// recognizes and interprets this as a special case.
//
%type indexed_opt {Token}
indexed_opt(A) ::= .                 {A.z=0; A.n=0;}
indexed_opt(A) ::= INDEXED BY nm(X). {A = X;}
indexed_opt(A) ::= NOT INDEXED.      {A.z=0; A.n=1;}


%type using_opt {IdList*}
%destructor using_opt {sqlite3IdListDelete(pParse->db, $$);}
using_opt(U) ::= USING LP idlist(L) RP.  {U = L;}
using_opt(U) ::= .                        {U = 0;}









>







749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
// normally illegal. The sqlite3SrcListIndexedBy() function 
// recognizes and interprets this as a special case.
//
%type indexed_opt {Token}
indexed_opt(A) ::= .                 {A.z=0; A.n=0;}
indexed_opt(A) ::= INDEXED BY nm(X). {A = X;}
indexed_opt(A) ::= NOT INDEXED.      {A.z=0; A.n=1;}
indexed_opt(A) ::= INDEXED.          {A.z=0; A.n=2;}

%type using_opt {IdList*}
%destructor using_opt {sqlite3IdListDelete(pParse->db, $$);}
using_opt(U) ::= USING LP idlist(L) RP.  {U = L;}
using_opt(U) ::= .                        {U = 0;}


Changes to src/sqliteInt.h.

2604
2605
2606
2607
2608
2609
2610

2611
2612
2613
2614
2615
2616
2617
      u8 jointype;      /* Type of join between this table and the previous */
      unsigned notIndexed :1;    /* True if there is a NOT INDEXED clause */
      unsigned isIndexedBy :1;   /* True if there is an INDEXED BY clause */
      unsigned isTabFunc :1;     /* True if table-valued-function syntax */
      unsigned isCorrelated :1;  /* True if sub-query is correlated */
      unsigned viaCoroutine :1;  /* Implemented as a co-routine */
      unsigned isRecursive :1;   /* True for recursive reference in WITH */

    } fg;
    int iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N of pTab is used */
    union {
      char *zIndexedBy;    /* Identifier from "INDEXED BY <zIndex>" clause */







>







2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
      u8 jointype;      /* Type of join between this table and the previous */
      unsigned notIndexed :1;    /* True if there is a NOT INDEXED clause */
      unsigned isIndexedBy :1;   /* True if there is an INDEXED BY clause */
      unsigned isTabFunc :1;     /* True if table-valued-function syntax */
      unsigned isCorrelated :1;  /* True if sub-query is correlated */
      unsigned viaCoroutine :1;  /* Implemented as a co-routine */
      unsigned isRecursive :1;   /* True for recursive reference in WITH */
      unsigned useAutoIdx  :1;   /* Use an automatic index if possible */
    } fg;
    int iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N of pTab is used */
    union {
      char *zIndexedBy;    /* Identifier from "INDEXED BY <zIndex>" clause */

Changes to src/where.c.

2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
        ** those objects, since there is no opportunity to add schema
        ** indexes on subqueries and views. */
        pNew->rSetup = rLogSize + rSize + 4;
        if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
          pNew->rSetup += 24;
        }
        ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
        if( pNew->rSetup<0 ) pNew->rSetup = 0;
        /* TUNING: Each index lookup yields 20 rows in the table.  This
        ** is more than the usual guess of 10 rows, since we have no way
        ** of knowing how selective the index will ultimately be.  It would
        ** not be unreasonable to make this value much larger. */
        pNew->nOut = 43;  assert( 43==sqlite3LogEst(20) );
        pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
        pNew->wsFlags = WHERE_AUTO_INDEX;







|







2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
        ** those objects, since there is no opportunity to add schema
        ** indexes on subqueries and views. */
        pNew->rSetup = rLogSize + rSize + 4;
        if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
          pNew->rSetup += 24;
        }
        ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
        if( pNew->rSetup<0 || pSrc->fg.useAutoIdx ) pNew->rSetup = 0;
        /* TUNING: Each index lookup yields 20 rows in the table.  This
        ** is more than the usual guess of 10 rows, since we have no way
        ** of knowing how selective the index will ultimately be.  It would
        ** not be unreasonable to make this value much larger. */
        pNew->nOut = 43;  assert( 43==sqlite3LogEst(20) );
        pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
        pNew->wsFlags = WHERE_AUTO_INDEX;
4001
4002
4003
4004
4005
4006
4007
4008



4009
4010
4011
4012
4013
4014
4015
4016
4017
        LogEst rUnsorted;                 /* Unsorted cost of (pFrom+pWLoop) */
        i8 isOrdered = pFrom->isOrdered;  /* isOrdered for (pFrom+pWLoop) */
        Bitmask maskNew;                  /* Mask of src visited by (..) */
        Bitmask revMask = 0;              /* Mask of rev-order loops for (..) */

        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 && pFrom->nRow<10 ){



          /* Do not use an automatic index if the this loop is expected
          ** to run less than 2 times. */
          assert( 10==sqlite3LogEst(2) );
          continue;
        }
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
        rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted);







|
>
>
>

|







4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
        LogEst rUnsorted;                 /* Unsorted cost of (pFrom+pWLoop) */
        i8 isOrdered = pFrom->isOrdered;  /* isOrdered for (pFrom+pWLoop) */
        Bitmask maskNew;                  /* Mask of src visited by (..) */
        Bitmask revMask = 0;              /* Mask of rev-order loops for (..) */

        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0
         && (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0
         && pWInfo->iLimit<10
        ){
          /* Do not use an automatic index if the this loop is expected
          ** to run less than twice due to a LIMIT clause. */
          assert( 10==sqlite3LogEst(2) );
          continue;
        }
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
        rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted);