SQLite

Check-in [c9c6457d8e]
Login

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

Overview
Comment:Further improve performance of unindexed fts5 prefix queries.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: c9c6457d8ea911f6cc63967127e58da3146fd3ef
User & Date: dan 2016-02-04 19:45:19.673
Context
2016-02-04
19:50
Temporarily back out the 0.5% performance improvement from check-in [632071bac5ff32]. Need a more elaborate solution that works with reentrant virtual tables and SQL functions. (check-in: 42736fb0ad user: drh tags: trunk)
19:45
Further improve performance of unindexed fts5 prefix queries. (check-in: c9c6457d8e user: dan tags: trunk)
17:31
Avoid running some particularly time-consuming tests as part of veryquick.test. (check-in: f465944b75 user: dan tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to ext/fts5/fts5_index.c.
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
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763

4764
4765
4766
4767
4768
4769
4770
4771

4772
4773
4774










4775
4776
4777

4778
4779
4780
4781
4782
4783
4784
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){



    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n);
    fts5DoclistIterInit(p1, &i1);
    fts5DoclistIterInit(p2, &i2);
    while( p->rc==SQLITE_OK && (i1.aPoslist!=0 || i2.aPoslist!=0) ){


      if( i2.aPoslist==0 || (i1.aPoslist && i1.iRowid<i2.iRowid) ){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
        fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist+i1.nSize);
        fts5DoclistIterNext(&i1);

      }
      else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
        /* Copy entry from i2 */
        fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
        fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist+i2.nSize);
        fts5DoclistIterNext(&i2);

      }
      else{
        i64 iPos1 = 0;
        i64 iPos2 = 0;
        int iOff1 = 0;
        int iOff2 = 0;
        u8 *a1 = &i1.aPoslist[i1.nSize];
        u8 *a2 = &i2.aPoslist[i2.nSize];

        Fts5PoslistWriter writer;
        memset(&writer, 0, sizeof(writer));

        /* Merge the two position lists. */ 
        fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
        fts5BufferZero(&tmp);

        sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
        sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);

        while( p->rc==SQLITE_OK && (iPos1>=0 || iPos2>=0) ){
          i64 iNew;
          if( iPos2<0 || (iPos1>=0 && iPos1<iPos2) ){
            iNew = iPos1;
            sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
          }else{
            iNew = iPos2;
            sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
            if( iPos1==iPos2 ){
              sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1,&iPos1);
            }
          }
          if( iNew!=writer.iPrev || tmp.n==0 ){
            p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);

          }
        }

        /* WRITEPOSLISTSIZE */
        fts5BufferSafeAppendVarint(&out, tmp.n * 2);
        fts5BufferSafeAppendBlob(&out, tmp.p, tmp.n);
        fts5DoclistIterNext(&i1);
        fts5DoclistIterNext(&i2);

      }
    }











    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);

  }
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */







>
>
>
|
|
|
|
|
<
<

|
|
|
|
>
>
|
|
|
|
|
>
|
|
|
|
|
|
>
|
|
|
|
|
|
|
|

|
|

|
|
|

|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
|
|

|
|
|
|
|
>
|
|

>
>
>
>
>
>
>
>
>
>
|
|
|
>







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
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
*/
static void fts5MergePrefixLists(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5Buffer *p1,                 /* First list to merge */
  Fts5Buffer *p2                  /* Second list to merge */
){
  if( p2->n ){
    if( p1->n==0 ){
      fts5BufferSwap(p1, p2);
    }else{
      i64 iLastRowid = 0;
      Fts5DoclistIter i1;
      Fts5DoclistIter i2;
      Fts5Buffer out = {0, 0, 0};
      Fts5Buffer tmp = {0, 0, 0};



      if( sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n) ) return;
      fts5DoclistIterInit(p1, &i1);
      fts5DoclistIterInit(p2, &i2);

      while( 1 ){

        if( i1.iRowid<i2.iRowid ){
          /* Copy entry from i1 */
          fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
          fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist+i1.nSize);
          fts5DoclistIterNext(&i1);
          if( i1.aPoslist==0 ) break;
        }
        else if( i2.iRowid!=i1.iRowid ){
          /* Copy entry from i2 */
          fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
          fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist+i2.nSize);
          fts5DoclistIterNext(&i2);
          if( i2.aPoslist==0 ) break;
        }
        else{
          i64 iPos1 = 0;
          i64 iPos2 = 0;
          int iOff1 = 0;
          int iOff2 = 0;
          u8 *a1 = &i1.aPoslist[i1.nSize];
          u8 *a2 = &i2.aPoslist[i2.nSize];

          Fts5PoslistWriter writer;
          memset(&writer, 0, sizeof(writer));

          /* Merge the two position lists. */ 
          fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
          fts5BufferZero(&tmp);

          sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
          sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);

          while( iPos1>=0 || iPos2>=0 ){
            i64 iNew;
            if( iPos2<0 || (iPos1>=0 && iPos1<iPos2) ){
              iNew = iPos1;
              sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
            }else{
              iNew = iPos2;
              sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
              if( iPos1==iPos2 ){
                sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1,&iPos1);
              }
            }
            if( iNew!=writer.iPrev || tmp.n==0 ){
              p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);
              if( p->rc ) goto error_out;
            }
          }

          /* WRITEPOSLISTSIZE */
          fts5BufferSafeAppendVarint(&out, tmp.n * 2);
          fts5BufferSafeAppendBlob(&out, tmp.p, tmp.n);
          fts5DoclistIterNext(&i1);
          fts5DoclistIterNext(&i2);
          if( i1.aPoslist==0 || i2.aPoslist==0 ) break;
        }
      }

      if( i1.aPoslist ){
        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
        fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.aEof - i1.aPoslist);
      }
      else if( i2.aPoslist ){
        fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
        fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.aEof - i2.aPoslist);
      }

     error_out:
      fts5BufferSet(&p->rc, p1, out.n, out.p);
      fts5BufferFree(&tmp);
      fts5BufferFree(&out);
    }
  }
}

static void fts5SetupPrefixIter(
  Fts5Index *p,                   /* Index to read from */
  int bDesc,                      /* True for "ORDER BY rowid DESC" */
  const u8 *pToken,               /* Buffer containing prefix to match */