SQLite4
Check-in [6f06ebee56]
Not logged in

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

Overview
Comment:Fix a bug preventing the planner from finding sorting indexes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-planner
Files: files | file ages | folders
SHA1: 6f06ebee5687f20f55a6228af99bbdb87a72964e
User & Date: dan 2013-07-17 20:03:57
Context
2013-07-18
19:53
Fix some problems with the LIKE optimization. check-in: 8330a46831 user: dan tags: nextgen-query-planner
2013-07-17
20:03
Fix a bug preventing the planner from finding sorting indexes. check-in: 6f06ebee56 user: dan tags: nextgen-query-planner
18:49
Further updates to ngqp code. check-in: 9844269b3d user: dan tags: nextgen-query-planner
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658

4659
4660
4661
4662
4663
4664
4665
4666


4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739

4740
4741
4742
4743
4744
4745
4746
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }
#endif /* ifndef SQLITE4_OMIT_AUTOMATIC_INDEX */

  /* If this table has no primary key, then it is either a materialized
  ** view or ephemeral table. Either way, add an entry for a full-scan 
  ** of it.  */
  if( pPk==0 ){
    assert( pSrc->pTab->pSelect || (pSrc->pTab->tabFlags & TF_Ephemeral) );
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = 0;
    pNew->iSortIdx = 0;
    pNew->wsFlags = 0;
    pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
    rc = whereLoopInsert(pBuilder, pNew);
  }

  /* Loop through the set of indices being considered. */
  for(; rc==SQLITE4_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){

    if( pProbe->eIndexType==SQLITE4_INDEX_FTS5 ) continue;


    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = pProbe;


    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );

    assert( pProbe->tnum>0 );
#if 0
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else
    {
      Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
#if 0
      pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
#endif
      pNew->wsFlags = WHERE_INDEXED;

      /* Full scan via index */
      if( b
       || ( m==0
         && pProbe->bUnordered==0
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
#if 0
         && sqlite4GlobalConfig.bUseCis
#endif
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE4_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
          **  +  The extra 2 factor is to encourage the use of indexed lookups
          **     over index scans.  A table scan uses a factor of 3 so that
          **     index scans are favored over table scans.
          **  +  If this covering index might also help satisfy the ORDER BY
          **     clause, then the cost is fudged down slightly so that this
          **     index is favored above other indices that have no hope of
          **     helping with the ORDER BY. */
          pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b;
        }else{
          assert( b!=0 ); 
          /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
          ** which we will simplify to just N*log2(N) */
          pNew->rRun = rSize + rLogSize;
        }
        rc = whereLoopInsert(pBuilder, pNew);
        if( rc ) break;
      }
    }
#endif

    pNew->wsFlags = WHERE_INDEXED;

    if( pProbe==pPk ){
      /* Add a WhereLoop for full-scan via primary key index. */
      pNew->iSortIdx = b ? iSortIdx : 0;

      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */

      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);








|










<









>



<




>
>



<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|

<






>







4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648

4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661

4662
4663
4664
4665
4666
4667
4668
4669
4670








4671









4672










































4673
4674

4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }
#endif /* ifndef SQLITE4_OMIT_AUTOMATIC_INDEX */

  /* If this table has no primary key, then it is either a materialized
  ** view or ephemeral table. Either way, add a WhereLoop for a full-scan 
  ** of it.  */
  if( pPk==0 ){
    assert( pSrc->pTab->pSelect || (pSrc->pTab->tabFlags & TF_Ephemeral) );
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = 0;

    pNew->wsFlags = 0;
    pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
    rc = whereLoopInsert(pBuilder, pNew);
  }

  /* Loop through the set of indices being considered. */
  for(; rc==SQLITE4_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){

    if( pProbe->eIndexType==SQLITE4_INDEX_FTS5 ) continue;
    assert( pProbe->tnum>0 );

    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;

    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = pProbe;
    pNew->wsFlags = WHERE_INDEXED;

    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );








    pNew->iSortIdx = b ? iSortIdx : 0;




















































    if( pProbe==pPk || b ){
      /* Add a WhereLoop for full-scan via primary key index. */


      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      /* TODO: Fix tuning for src4 as described in comment immediately above. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);

Changes to test/permutations.test.

127
128
129
130
131
132
133

134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#   src4
#   veryquick
#   quick
#   full
#
lappend ::testsuitelist xxx


test_suite "src4" -prefix "" -description {
} -files {
  simple.test simple2.test
  lsm1.test lsm2.test lsm3.test lsm4.test lsm5.test
  csr1.test
  ckpt1.test
  mc1.test
  fts5expr1.test fts5query1.test fts5rnd1.test fts5create.test
  fts5snippet.test

  alter.test alter3.test alter4.test
  analyze.test analyze3.test analyze4.test analyze5.test 
  analyze6.test analyze7.test analyze8.test
  auth.test auth2.test auth3.test auth4.test
  aggerror.test
  attach.test attach3.test attach4.test







>







<
<







127
128
129
130
131
132
133
134
135
136
137
138
139
140
141


142
143
144
145
146
147
148
#   src4
#   veryquick
#   quick
#   full
#
lappend ::testsuitelist xxx

# fts5expr1.test fts5query1.test fts5rnd1.test fts5create.test fts5snippet.test
test_suite "src4" -prefix "" -description {
} -files {
  simple.test simple2.test
  lsm1.test lsm2.test lsm3.test lsm4.test lsm5.test
  csr1.test
  ckpt1.test
  mc1.test



  alter.test alter3.test alter4.test
  analyze.test analyze3.test analyze4.test analyze5.test 
  analyze6.test analyze7.test analyze8.test
  auth.test auth2.test auth3.test auth4.test
  aggerror.test
  attach.test attach3.test attach4.test