SQLite

Check-in [ac6d0fba78]
Login

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

Overview
Comment:Progress toward getting automatic indices to work. Still failing in corner cases.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1: ac6d0fba78eb9dcd69372e128d4a039aaff4b417
User & Date: drh 2010-04-06 18:28:21.000
Context
2010-04-06
18:51
Runs quicktest without hitting an assert now. Some tests get unexpected results still and there is a memory leak. (check-in: a8224448cc user: drh tags: experimental)
18:28
Progress toward getting automatic indices to work. Still failing in corner cases. (check-in: ac6d0fba78 user: drh tags: experimental)
15:57
Automatically generate transient indices for tables in joins that would otherwise have to use a full table scan. (check-in: 1b2a04125f user: drh tags: experimental)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
1653
1654
1655
1656
1657
1658
1659

1660
1661
1662
1663
1664
1665
1666
  WhereCost *pCost            /* Lowest cost query plan */
){
  double nTableRow;           /* Rows in the input table */
  double logN;                /* log(nTableRow) */
  double costTempIdx;         /* per-query cost of the transient index */
  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  WhereTerm *pWCEnd;          /* End of pWC->a[] */


  if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
    /* We already have some kind of index in use for this query. */
    return;
  }
  if( pSrc->notIndexed ){
    /* The NOT INDEXED clause appears in the SQL. */







>







1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
  WhereCost *pCost            /* Lowest cost query plan */
){
  double nTableRow;           /* Rows in the input table */
  double logN;                /* log(nTableRow) */
  double costTempIdx;         /* per-query cost of the transient index */
  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  WhereTerm *pWCEnd;          /* End of pWC->a[] */
  Table *pTable;              /* Table tht might be indexed */

  if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
    /* We already have some kind of index in use for this query. */
    return;
  }
  if( pSrc->notIndexed ){
    /* The NOT INDEXED clause appears in the SQL. */
1674
1675
1676
1677
1678
1679
1680

1681
1682
1683
1684
1685


1686
1687
1688
1689
1690
1691
1692
  if( costTempIdx>=pCost->rCost ){
    /* The cost of creating the transient table would be greater than
    ** doing the full table scan */
    return;
  }

  /* Search for any equality comparison term */

  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0


    ){
      WHERETRACE(("auto-index reduces cost from %.2f to %.2f\n",
                    pCost->rCost, costTempIdx));
      pCost->rCost = costTempIdx;
      pCost->nRow = logN + 1;
      pCost->plan.wsFlags = WHERE_TEMP_INDEX;
      pCost->used = pTerm->prereqRight;







>





>
>







1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
  if( costTempIdx>=pCost->rCost ){
    /* The cost of creating the transient table would be greater than
    ** doing the full table scan */
    return;
  }

  /* Search for any equality comparison term */
  pTable = pSrc->pTab;
  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0
       && sqlite3IndexAffinityOk(pTerm->pExpr,
                                 pTable->aCol[pTerm->u.leftColumn].affinity)
    ){
      WHERETRACE(("auto-index reduces cost from %.2f to %.2f\n",
                    pCost->rCost, costTempIdx));
      pCost->rCost = costTempIdx;
      pCost->nRow = logN + 1;
      pCost->plan.wsFlags = WHERE_TEMP_INDEX;
      pCost->used = pTerm->prereqRight;
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
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762


1763
1764

1765


1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777

1778
1779
1780
1781
1782
1783
1784
  int regIsInit;              /* Register set by initialization */
  int addrInit;               /* Address of the initialization bypass jump */
  Table *pTable;              /* The table being indexed */
  KeyInfo *pKeyinfo;          /* Key information for the index */   
  int addrTop;                /* Top of the index fill loop */
  int regRecord;              /* Register holding an index record */
  int n;                      /* Column counter */


  /* Generate code to skip over the creation and initialization of the
  ** transient index on 2nd and subsequent iterations of the loop. */
  v = pParse->pVdbe;
  assert( v!=0 );
  regIsInit = ++pParse->nMem;
  addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit);
  sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit);

  /* Count the number of columns that will be added to the index */
  nColumn = 0;

  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0


    ){
      nColumn++;
    }
  }
  assert( nColumn>0 );



  /* Construct the Index object to describe this index */
  nByte = sizeof(Index);
  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  nByte += nColumn*sizeof(char*);   /* Index.azColl */
  nByte += nColumn;                 /* Index.aSortOrder */
  pIdx = sqlite3DbMallocZero(pParse->db, nByte);
  if( pIdx==0 ) return;
  pLevel->plan.u.pIdx = pIdx;
  pIdx->azColl = (char**)&pIdx[1];
  pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
  pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
  pIdx->zName = "auto-index";
  pIdx->nColumn = nColumn;
  pIdx->pTable = pTable = pSrc->pTab;
  n = 0;
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0


    ){
      int iCol = pTerm->u.leftColumn;

      pIdx->aiColumn[n] = iCol;


      pIdx->azColl[n] = pTable->aCol[iCol].zColl;
      if( pIdx->azColl[n]==0 ) pIdx->azColl[n] = "BINARY";
      n++;
    }
  }
  assert( n==pIdx->nColumn );

  /* Create the transient index */
  pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
  assert( pLevel->iIdxCur>=0 );
  sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pLevel->iIdxCur, nColumn+1, 0,
                    (char*)pKeyinfo, P4_KEYINFO_HANDOFF);


  /* Fill the transient index with content */
  addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
  regRecord = sqlite3GetTempReg(pParse);
  sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
  sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);







>











>





>
>





>
>














|





>
>


>

>
>
|
<










>







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
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781

1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
  int regIsInit;              /* Register set by initialization */
  int addrInit;               /* Address of the initialization bypass jump */
  Table *pTable;              /* The table being indexed */
  KeyInfo *pKeyinfo;          /* Key information for the index */   
  int addrTop;                /* Top of the index fill loop */
  int regRecord;              /* Register holding an index record */
  int n;                      /* Column counter */
  CollSeq *pColl;             /* Collating sequence to on a column */

  /* Generate code to skip over the creation and initialization of the
  ** transient index on 2nd and subsequent iterations of the loop. */
  v = pParse->pVdbe;
  assert( v!=0 );
  regIsInit = ++pParse->nMem;
  addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit);
  sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit);

  /* Count the number of columns that will be added to the index */
  nColumn = 0;
  pTable = pSrc->pTab;
  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0
       && sqlite3IndexAffinityOk(pTerm->pExpr,
                                 pTable->aCol[pTerm->u.leftColumn].affinity)
    ){
      nColumn++;
    }
  }
  assert( nColumn>0 );
  pLevel->plan.nEq = nColumn;
  pLevel->plan.wsFlags = WHERE_COLUMN_EQ | WO_EQ;

  /* Construct the Index object to describe this index */
  nByte = sizeof(Index);
  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  nByte += nColumn*sizeof(char*);   /* Index.azColl */
  nByte += nColumn;                 /* Index.aSortOrder */
  pIdx = sqlite3DbMallocZero(pParse->db, nByte);
  if( pIdx==0 ) return;
  pLevel->plan.u.pIdx = pIdx;
  pIdx->azColl = (char**)&pIdx[1];
  pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
  pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
  pIdx->zName = "auto-index";
  pIdx->nColumn = nColumn;
  pIdx->pTable = pTable;
  n = 0;
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->leftCursor==pSrc->iCursor
       && (pTerm->prereqRight & notReady)==0
       && (pTerm->eOperator & WO_EQ)!=0
       && sqlite3IndexAffinityOk(pTerm->pExpr,
                                 pTable->aCol[pTerm->u.leftColumn].affinity)
    ){
      int iCol = pTerm->u.leftColumn;
      Expr *pX;
      pIdx->aiColumn[n] = iCol;
      pX = pTerm->pExpr;
      pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
      pIdx->azColl[n] = pColl->zName;

      n++;
    }
  }
  assert( n==pIdx->nColumn );

  /* Create the transient index */
  pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
  assert( pLevel->iIdxCur>=0 );
  sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pLevel->iIdxCur, nColumn+1, 0,
                    (char*)pKeyinfo, P4_KEYINFO_HANDOFF);
  VdbeComment((v, "auto-idx for %s", pTable->zName));

  /* Fill the transient index with content */
  addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
  regRecord = sqlite3GetTempReg(pParse);
  sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
  sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
4056
4057
4058
4059
4060
4061
4062

4063
4064





4065
4066
4067
4068
4069
4070
4071
        zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
      }
      sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;

    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;





#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
      const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
    }else
#endif







>

|
>
>
>
>
>







4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
        zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
      }
      sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    pLevel->iTabCur = pTabItem->iCursor;
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
      if( pLevel->plan.wsFlags & WHERE_TEMP_INDEX ){
        constructTransientIndex(pParse, pWC, pTabItem, notReady, pLevel);
      }
      continue;
    }
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
      const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
      int iCur = pTabItem->iCursor;
      sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
    }else
#endif
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
        sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, 
                            SQLITE_INT_TO_PTR(n), P4_INT32);
        assert( n<=pTab->nCol );
      }
    }else{
      sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
    }
    pLevel->iTabCur = pTabItem->iCursor;
    if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
      constructTransientIndex(pParse, pWC, pTabItem, notReady, pLevel);
    }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
      Index *pIx = pLevel->plan.u.pIdx;
      KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
      int iIdxCur = pLevel->iIdxCur;
      assert( pIx->pSchema==pTab->pSchema );







<







4101
4102
4103
4104
4105
4106
4107

4108
4109
4110
4111
4112
4113
4114
        sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, 
                            SQLITE_INT_TO_PTR(n), P4_INT32);
        assert( n<=pTab->nCol );
      }
    }else{
      sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
    }

    if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
      constructTransientIndex(pParse, pWC, pTabItem, notReady, pLevel);
    }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
      Index *pIx = pLevel->plan.u.pIdx;
      KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
      int iIdxCur = pLevel->iIdxCur;
      assert( pIx->pSchema==pTab->pSchema );