/ Check-in [ca91bd8a]
Login

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

Overview
Comment:Further streamlining of fts5 prefix query code.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ca91bd8ac70a5b3fef127364f73ec675e58bb92c
User & Date: dan 2016-02-05 19:18:02
Context
2016-02-05
21:09
Add tests for and remove unreachable branches from fts5 in order to restore test coverage. check-in: 22589018 user: dan tags: trunk
19:40
More work on Windows 10 SDK integration. Closed-Leaf check-in: ebace2c9 user: mistachkin tags: win10sdk
19:18
Further streamlining of fts5 prefix query code. check-in: ca91bd8a user: dan tags: trunk
17:49
Make sure the "bak.db" database file does not actually exist before starting the "quota.test" testing. check-in: 1cac6c45 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5Int.h.

278
279
280
281
282
283
284

285
286
287
288
289
290
291
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  i64 iPrev;
};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);


int sqlite3Fts5PoslistNext64(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
);








>







278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
int sqlite3Fts5PoslistReaderNext(Fts5PoslistReader*);

typedef struct Fts5PoslistWriter Fts5PoslistWriter;
struct Fts5PoslistWriter {
  i64 iPrev;
};
int sqlite3Fts5PoslistWriterAppend(Fts5Buffer*, Fts5PoslistWriter*, i64);
void sqlite3Fts5PoslistSafeAppend(Fts5Buffer*, i64*, i64);

int sqlite3Fts5PoslistNext64(
  const u8 *a, int n,             /* Buffer containing poslist */
  int *pi,                        /* IN/OUT: Offset within a[] */
  i64 *piOff                      /* IN/OUT: Current offset */
);

Changes to ext/fts5/fts5_buffer.c.

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
...
203
204
205
206
207
208
209





















210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
*/



#include "fts5Int.h"

int sqlite3Fts5BufferSize(int *pRc, Fts5Buffer *pBuf, u32 nByte){

  u32 nNew = pBuf->nSpace ? pBuf->nSpace*2 : 64;
  u8 *pNew;
  while( nNew<nByte ){
    nNew = nNew * 2;
  }
  pNew = sqlite3_realloc(pBuf->p, nNew);
  if( pNew==0 ){
    *pRc = SQLITE_NOMEM;
    return 1;
  }else{
    pBuf->nSpace = nNew;
    pBuf->p = pNew;

  }
  return 0;
}


/*
** Encode value iVal as an SQLite varint and append it to the buffer object
................................................................................
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = a;
  pIter->n = n;
  sqlite3Fts5PoslistReaderNext(pIter);
  return pIter->bEof;
}






















int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  int rc = SQLITE_OK;
  if( 0==fts5BufferGrow(&rc, pBuf, 5+5+5) ){
    if( (iPos & colmask) != (pWriter->iPrev & colmask) ){
      pBuf->p[pBuf->n++] = 1;
      pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32));
      pWriter->iPrev = (iPos & colmask);
    }
    pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-pWriter->iPrev)+2);
    pWriter->iPrev = iPos;
  }
  return rc;
}

void *sqlite3Fts5MallocZero(int *pRc, int nByte){
  void *pRet = 0;
  if( *pRc==SQLITE_OK ){
    pRet = sqlite3_malloc(nByte);
    if( pRet==0 && nByte>0 ){







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







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







|
|
|
<
<
<
<
<
<
<
|







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
...
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242







243
244
245
246
247
248
249
250
*/



#include "fts5Int.h"

int sqlite3Fts5BufferSize(int *pRc, Fts5Buffer *pBuf, u32 nByte){
  if( pBuf->nSpace<nByte ){
    u32 nNew = pBuf->nSpace ? pBuf->nSpace : 64;
    u8 *pNew;
    while( nNew<nByte ){
      nNew = nNew * 2;
    }
    pNew = sqlite3_realloc(pBuf->p, nNew);
    if( pNew==0 ){
      *pRc = SQLITE_NOMEM;
      return 1;
    }else{
      pBuf->nSpace = nNew;
      pBuf->p = pNew;
    }
  }
  return 0;
}


/*
** Encode value iVal as an SQLite varint and append it to the buffer object
................................................................................
){
  memset(pIter, 0, sizeof(*pIter));
  pIter->a = a;
  pIter->n = n;
  sqlite3Fts5PoslistReaderNext(pIter);
  return pIter->bEof;
}

/*
** Append position iPos to the position list being accumulated in buffer
** pBuf, which must be already be large enough to hold the new data.
** The previous position written to this list is *piPrev. *piPrev is set
** to iPos before returning.
*/
void sqlite3Fts5PoslistSafeAppend(
  Fts5Buffer *pBuf, 
  i64 *piPrev, 
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  if( (iPos & colmask) != (*piPrev & colmask) ){
    pBuf->p[pBuf->n++] = 1;
    pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32));
    *piPrev = (iPos & colmask);
  }
  pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-*piPrev)+2);
  *piPrev = iPos;
}

int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  int rc;
  if( fts5BufferGrow(&rc, pBuf, 5+5+5) ) return rc;
  sqlite3Fts5PoslistSafeAppend(pBuf, &pWriter->iPrev, iPos);







  return SQLITE_OK;
}

void *sqlite3Fts5MallocZero(int *pRc, int nByte){
  void *pRet = 0;
  if( *pRc==SQLITE_OK ){
    pRet = sqlite3_malloc(nByte);
    if( pRet==0 && nByte>0 ){

Changes to ext/fts5/fts5_index.c.

4700
4701
4702
4703
4704
4705
4706

4707
4708
4709
4710
4711
4712
4713
....
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
....
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
....
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
** already occurred, this function is a no-op.
*/
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 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;
        }
................................................................................
          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);
................................................................................
** to the database. Additionally, assume that the contents of the %_data
** table may have changed on disk. So any in-memory caches of %_data 
** records must be invalidated.
*/
int sqlite3Fts5IndexRollback(Fts5Index *p){
  fts5CloseReader(p);
  fts5IndexDiscardData(p);
  assert( p->rc==SQLITE_OK );
  return SQLITE_OK;
}

/*
** The %_data table is completely empty when this function is called. This
** function populates it with the initial structure objects for each index,
** and the initial version of the "averages" record (a zero-byte blob).







>







 







<







 







>






>
>



>

>
>
>
>
>
>
>
>
|
<
>
|
|
>
>
|
>
|
|
>
>
|
>
>
>
>
>
|
<
>
>
|
>
|
<
<
<
>
>
>

>







 







|







4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
....
4716
4717
4718
4719
4720
4721
4722

4723
4724
4725
4726
4727
4728
4729
....
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
....
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
** already occurred, this function is a no-op.
*/
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 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;
        }
................................................................................
          i64 iPos1 = 0;
          i64 iPos2 = 0;
          int iOff1 = 0;
          int iOff2 = 0;
          u8 *a1 = &i1.aPoslist[i1.nSize];
          u8 *a2 = &i2.aPoslist[i2.nSize];

          i64 iPrev = 0;
          Fts5PoslistWriter writer;
          memset(&writer, 0, sizeof(writer));

          /* Merge the two position lists. */ 
          fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
          fts5BufferZero(&tmp);
          sqlite3Fts5BufferSize(&p->rc, &tmp, i1.nPoslist + i2.nPoslist);
          if( p->rc ) break;

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

          if( iPos1<iPos2 ){
            sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1);
            sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
          }else{
            sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2);
            sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
          }

          if( iPos1>=0 && iPos2>=0 ){

            while( 1 ){
              if( iPos1<iPos2 ){
                if( iPos1!=iPrev ){
                  sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1);
                }
                sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
                if( iPos1<0 ) break;
              }else{
                if( iPos2!=iPrev ){
                  sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2);
                }
                sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
                if( iPos2<0 ) break;
              }
            }
          }

          if( iPos1>=0 ){

            if( iPos1!=iPrev ){
              sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos1);
            }
            fts5BufferSafeAppendBlob(&tmp, &a1[iOff1], i1.nPoslist-iOff1);
          }



          else if( iPos2>=0 ){
            if( iPos2!=iPrev ){
              sqlite3Fts5PoslistSafeAppend(&tmp, &iPrev, iPos2);
            }
            fts5BufferSafeAppendBlob(&tmp, &a2[iOff2], i2.nPoslist-iOff2);
          }

          /* WRITEPOSLISTSIZE */
          fts5BufferSafeAppendVarint(&out, tmp.n * 2);
          fts5BufferSafeAppendBlob(&out, tmp.p, tmp.n);
          fts5DoclistIterNext(&i1);
          fts5DoclistIterNext(&i2);
................................................................................
** to the database. Additionally, assume that the contents of the %_data
** table may have changed on disk. So any in-memory caches of %_data 
** records must be invalidated.
*/
int sqlite3Fts5IndexRollback(Fts5Index *p){
  fts5CloseReader(p);
  fts5IndexDiscardData(p);
  /* assert( p->rc==SQLITE_OK ); */
  return SQLITE_OK;
}

/*
** The %_data table is completely empty when this function is called. This
** function populates it with the initial structure objects for each index,
** and the initial version of the "averages" record (a zero-byte blob).

Changes to ext/fts5/fts5_main.c.

799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
...
816
817
818
819
820
821
822

823
824
825
826
827
828
829
**
** Return SQLITE_OK if nothing goes wrong.  SQLITE_OK is returned
** even if we reach end-of-file.  The fts5EofMethod() will be called
** subsequently to determine whether or not an EOF was hit.
*/
static int fts5NextMethod(sqlite3_vtab_cursor *pCursor){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int rc = SQLITE_OK;

  assert( (pCsr->ePlan<3)==
          (pCsr->ePlan==FTS5_PLAN_MATCH || pCsr->ePlan==FTS5_PLAN_SOURCE) 
  );
  assert( !CsrFlagTest(pCsr, FTS5CSR_EOF) );

  if( pCsr->ePlan<3 ){
................................................................................
    rc = sqlite3Fts5ExprNext(pCsr->pExpr, pCsr->iLastRowid);
    CsrFlagSet(pCsr, sqlite3Fts5ExprEof(pCsr->pExpr));
    fts5CsrNewrow(pCsr);
  }else{
    switch( pCsr->ePlan ){
      case FTS5_PLAN_SPECIAL: {
        CsrFlagSet(pCsr, FTS5CSR_EOF);

        break;
      }
  
      case FTS5_PLAN_SORTED_MATCH: {
        rc = fts5SorterNext(pCsr);
        break;
      }







|







 







>







799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
...
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
**
** Return SQLITE_OK if nothing goes wrong.  SQLITE_OK is returned
** even if we reach end-of-file.  The fts5EofMethod() will be called
** subsequently to determine whether or not an EOF was hit.
*/
static int fts5NextMethod(sqlite3_vtab_cursor *pCursor){
  Fts5Cursor *pCsr = (Fts5Cursor*)pCursor;
  int rc;

  assert( (pCsr->ePlan<3)==
          (pCsr->ePlan==FTS5_PLAN_MATCH || pCsr->ePlan==FTS5_PLAN_SOURCE) 
  );
  assert( !CsrFlagTest(pCsr, FTS5CSR_EOF) );

  if( pCsr->ePlan<3 ){
................................................................................
    rc = sqlite3Fts5ExprNext(pCsr->pExpr, pCsr->iLastRowid);
    CsrFlagSet(pCsr, sqlite3Fts5ExprEof(pCsr->pExpr));
    fts5CsrNewrow(pCsr);
  }else{
    switch( pCsr->ePlan ){
      case FTS5_PLAN_SPECIAL: {
        CsrFlagSet(pCsr, FTS5CSR_EOF);
        rc = SQLITE_OK;
        break;
      }
  
      case FTS5_PLAN_SORTED_MATCH: {
        rc = fts5SorterNext(pCsr);
        break;
      }

Changes to ext/fts5/test/fts5ad.test.

7
8
9
10
11
12
13


14
15
16
17
18
19
20
#    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 the FTS5 module.
#


#

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5ad

# If SQLITE_ENABLE_FTS5 is defined, omit this file.
ifcapable !fts5 {







>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#    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 the FTS5 module.
#
# More specifically, the focus is on testing prefix queries, both with and
# without prefix indexes.
#

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5ad

# If SQLITE_ENABLE_FTS5 is defined, omit this file.
ifcapable !fts5 {

Changes to ext/fts5/test/fts5detail.test.

80
81
82
83
84
85
86




87
88
89
90
91
92
93
do_execsql_test 2.1 {
  INSERT INTO t2(t2) VALUES('integrity-check');
}

do_execsql_test 2.2 {
  SELECT fts5_test_poslist(t2) FROM t2('aa');
} {0.0.0}





set ::pc 0
#puts [nearset {{ax bx cx}} -pc ::pc -near 10 -- b*]
#exit

#-------------------------------------------------------------------------
# Check that the xInstCount, xInst, xPhraseFirst and xPhraseNext APIs







>
>
>
>







80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
do_execsql_test 2.1 {
  INSERT INTO t2(t2) VALUES('integrity-check');
}

do_execsql_test 2.2 {
  SELECT fts5_test_poslist(t2) FROM t2('aa');
} {0.0.0}

do_execsql_test 2.3 {
  SELECT fts5_test_collist(t2) FROM t2('aa');
} {0.0}

set ::pc 0
#puts [nearset {{ax bx cx}} -pc ::pc -near 10 -- b*]
#exit

#-------------------------------------------------------------------------
# Check that the xInstCount, xInst, xPhraseFirst and xPhraseNext APIs