/ Check-in [57047372]
Login

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

Overview
Comment:Add tests for incremental merge code.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts4-incr-merge
Files: files | file ages | folders
SHA1:570473729d6561d81e6e5f8884fd18487008636e
User & Date: dan 2012-03-14 20:01:52
Context
2012-03-15
17:45
Modify incremental merge code to merge nMin segments at a time. check-in: cd34bc1a user: dan tags: fts4-incr-merge
2012-03-14
20:01
Add tests for incremental merge code. check-in: 57047372 user: dan tags: fts4-incr-merge
12:17
Avoid allocating a large object on the stack in the incremental merge code. Use sqlite3_malloc() instead. check-in: 36ae510d user: dan tags: fts4-incr-merge
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3Int.h.

120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
** false.
*/
#ifdef SQLITE_COVERAGE_TEST
# define ALWAYS(x) (1)
# define NEVER(X)  (0)
#else
# define ALWAYS(x) (x)
# define NEVER(X)  (x)
#endif

/*
** Internal types used by SQLite.
*/
typedef unsigned char u8;         /* 1-byte (or larger) unsigned integer */
typedef short int i16;            /* 2-byte (or larger) signed integer */







|







120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
** false.
*/
#ifdef SQLITE_COVERAGE_TEST
# define ALWAYS(x) (1)
# define NEVER(X)  (0)
#else
# define ALWAYS(x) (x)
# define NEVER(x)  (x)
#endif

/*
** Internal types used by SQLite.
*/
typedef unsigned char u8;         /* 1-byte (or larger) unsigned integer */
typedef short int i16;            /* 2-byte (or larger) signed integer */

Changes to ext/fts3/fts3_write.c.

3268
3269
3270
3271
3272
3273
3274






3275
3276
3277
3278



3279
3280
3281
3282
3283
3284
3285
....
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
....
3561
3562
3563
3564
3565
3566
3567
3568

3569
3570


3571
3572
3573
3574
3575
3576
3577
....
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645

3646
3647
3648
3649
3650
3651
3652
3653
....
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
....
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871

3872
3873
3874
3875
3876
3877
3878
....
4006
4007
4008
4009
4010
4011
4012

4013
4014
4015
4016
4017
4018
4019
....
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035




4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
....
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
....
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
....
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
....
4191
4192
4193
4194
4195
4196
4197


4198
4199
4200
4201
4202
4203
4204
....
4226
4227
4228
4229
4230
4231
4232
4233



4234
4235
4236
4237
4238
4239
4240
....
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257

4258
4259

4260
4261
4262
4263
4264
4265
4266
....
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
}

typedef struct IncrmergeWriter IncrmergeWriter;
typedef struct LayerWriter LayerWriter;
typedef struct Blob Blob;
typedef struct NodeReader NodeReader;







struct Blob {
  char *a;
  int n;
  int nAlloc;



};

struct LayerWriter {
  sqlite3_int64 iBlock;           /* Current block id */
  Blob key;                       /* Last key written to the current block */
  Blob block;                     /* Current block image */
};
................................................................................
  const char *zTerm,              /* Term to write to internal node */
  int nTerm                       /* Bytes at zTerm */
){
  sqlite3_int64 iPtr = pWriter->aLayer[0].iBlock;
  int iLayer;

  assert( nTerm>0 );
  for(iLayer=1; iLayer<FTS_MAX_APPENDABLE_HEIGHT; iLayer++){
    sqlite3_int64 iNextPtr = 0;
    LayerWriter *pLayer = &pWriter->aLayer[iLayer];
    int rc = SQLITE_OK;
    int nPrefix;
    int nSuffix;
    int nSpace;

................................................................................
  int i;                          /* Used to iterate through non-root layers */
  int iRoot;
  LayerWriter *pRoot;
  int rc = *pRc;

  /* Find the root node */
  for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){
    if( pWriter->aLayer[iRoot].block.n>0 ) break;

    assert( pWriter->aLayer[iRoot].block.nAlloc==0 );
    assert( pWriter->aLayer[iRoot].key.nAlloc==0 );


  }

  /* Empty output segment. This is a no-op. */
  if( iRoot<0 ) return;

  /* The entire output segment fits on the root node. This is not allowed. */
  if( iRoot==0 ){
................................................................................
  res = memcmp(zLhs, zRhs, nCmp);
  if( res==0 ) res = nLhs - nRhs;

  return res;
}


static int fts3IsAppendable(Fts3Table *p, sqlite3_int64 iEnd, int *pRc){
  int bRes = 0;
  if( *pRc==SQLITE_OK ){
    sqlite3_stmt *pCheck = 0;
    int rc;

    rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0);
    if( rc==SQLITE_OK ){
      sqlite3_bind_int64(pCheck, 1, iEnd);
      if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1;
      rc = sqlite3_reset(pCheck);
    }
    *pRc = rc;
  }
  

  return bRes;
}

/*
**
*/
static int fts3IncrmergeLoad(
  Fts3Table *p,                   /* Fts3 table handle */
................................................................................
      nRoot = sqlite3_column_bytes(pSelect, 4);
      aRoot = sqlite3_column_blob(pSelect, 4);
    }else{
      return sqlite3_reset(pSelect);
    }

    /* Check for the zero-length marker in the %_segments table */
    bAppendable = fts3IsAppendable(p, iEnd, &rc);

    /* Check that zKey/nKey is larger than the largest key the candidate */
    if( rc==SQLITE_OK && bAppendable ){
      char *aLeaf = (char *)aRoot;
      int nLeaf = nRoot;

      if( aRoot[0] ){
        rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0);
      }
      if( rc==SQLITE_OK ){
        NodeReader reader;
        for(rc = nodeReaderInit(&reader, aLeaf, nLeaf);
            rc==SQLITE_OK && reader.aNode;
            rc = nodeReaderNext(&reader)
        ){
          assert( reader.aNode );
        }
        if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){
          bAppendable = 0;
        }
        nodeReaderRelease(&reader);
      }
      if( aLeaf!=aRoot ) sqlite3_free(aLeaf);
    }

    if( rc==SQLITE_OK && bAppendable ){
      /* It is possible to append to this segment. Set up the IncrmergeWriter
      ** object to do so.  */
      int i;
      int nHeight = (int)aRoot[0];
................................................................................
    rc = sqlite3_reset(pFirstBlock);
  }
  if( rc!=SQLITE_OK ) return rc;

  /* Insert the marker in the %_segments table to make sure nobody tries
  ** to steal the space just allocated. This is also used to identify 
  ** appendable segments.  */
  if( rc==SQLITE_OK ){
    rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0);
  }


  pWriter->iAbsLevel = iAbsLevel;
  pWriter->nLeafEst = nLeafEst;
  pWriter->iIdx = iIdx;

  /* Set up the array of LayerWriter objects */
  for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
................................................................................
      *piBlock = reader.iChild;
      bStarted = 1;
    }
    rc = fts3AppendToNode(
        pNew, &prev, reader.term.a, reader.term.n,
        reader.aDoclist, reader.nDoclist
    );

  }
  if( bStarted==0 ){
    fts3StartNode(pNew, (int)aNode[0], reader.iChild);
    *piBlock = reader.iChild;
  }
  assert( pNew->n<=pNew->nAlloc );

................................................................................
static int fts3TruncateSegment(
  Fts3Table *p,                   /* FTS3 table handle */
  sqlite3_int64 iAbsLevel,        /* Absolute level of segment to modify */
  int iIdx,                       /* Index within level of segment to modify */
  const char *zTerm,              /* Remove terms smaller than this */
  int nTerm                       /* Number of bytes in buffer zTerm */
){
  int rc;                         /* Return code */
  Blob root = {0,0,0};            /* New root page image */
  Blob block = {0,0,0};           /* Buffer used for any other block */





  sqlite3_stmt *pFetch = 0;       /* Statement used to fetch segdir */

  rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0);
  if( rc==SQLITE_OK ){
    sqlite3_int64 iBlock = 0;     /* Block id */
    sqlite3_int64 iNewStart = 0;
    sqlite3_int64 iOldStart = 0;
    int rc2;                      /* sqlite3_reset() return code */

    sqlite3_bind_int64(pFetch, 1, iAbsLevel);
    sqlite3_bind_int(pFetch, 2, iIdx);
    if( SQLITE_ROW==sqlite3_step(pFetch) ){
      const char *aRoot = sqlite3_column_blob(pFetch, 4);
      int nRoot = sqlite3_column_bytes(pFetch, 4);
      iOldStart = sqlite3_column_int64(pFetch, 1);
      rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
    }
    rc2 = sqlite3_reset(pFetch);
    if( rc==SQLITE_OK ) rc = rc2;

    while( rc==SQLITE_OK && iBlock ){
      char *aBlock = 0;
      int nBlock = 0;
      iNewStart = iBlock;

      rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);
      if( rc==SQLITE_OK ){
        rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock);
      }
      if( rc==SQLITE_OK ){
        rc = fts3WriteSegment(p, iNewStart, block.a, block.n);
      }
      sqlite3_free(aBlock);
    }

    /* Variable iNewStart now contains the first valid leaf node. */
    if( rc==SQLITE_OK && iNewStart ){
      sqlite3_stmt *pDel = 0;
      rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0);
      if( rc==SQLITE_OK ){
        sqlite3_bind_int64(pDel, 1, iOldStart);
        sqlite3_bind_int64(pDel, 2, iNewStart-1);
        sqlite3_step(pDel);
        rc = sqlite3_reset(pDel);
      }
    }

    if( rc==SQLITE_OK ){
      sqlite3_stmt *pChomp = 0;
      rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0);
      if( rc==SQLITE_OK ){
        sqlite3_bind_int64(pChomp, 1, iNewStart);
        sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC);
        sqlite3_bind_int64(pChomp, 3, iAbsLevel);
        sqlite3_bind_int(pChomp, 4, iIdx);
        sqlite3_step(pChomp);
        rc = sqlite3_reset(pChomp);
      }
    }
  }

  sqlite3_free(root.a);
  sqlite3_free(block.a);
  return rc;
}
................................................................................
  int rc = SQLITE_OK;

  assert( pCsr->nSegment==2 );
  assert( (pCsr->apSegment[0]->iIdx==0 && pCsr->apSegment[1]->iIdx==1)
       || (pCsr->apSegment[1]->iIdx==0 && pCsr->apSegment[0]->iIdx==1) 
  );

  for(i=1; i>=0; i--){
    Fts3SegReader *pSeg = pCsr->apSegment[0];
    if( pSeg->iIdx!=i ) pSeg = pCsr->apSegment[1];
    assert( pSeg->iIdx==i );

    if( pSeg->aNode==0 ){
      /* Seg-reader is at EOF. Remove the entire input segment. */
      rc = fts3DeleteSegment(p, pSeg);
................................................................................

  return rc;
}

/*
** Attempt an incremental merge that writes nMerge leaf pages.
**
** Incremental merges happen two segments at a time.  The two
** segments to be merged are the two oldest segments (the ones with
** the smallest index) in the highest level that has at least
** nMin segments.  Multiple segment pair merges might occur in
** an attempt to write the quota of nMerge leaf pages.
*/
static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){
  int rc = SQLITE_OK;             /* Return code */
  int nRem = nMerge;              /* Number of leaf pages yet to  be written */

  assert( nMin>=2 );
................................................................................
    ** is set to the absolute level number of the level to merge from.  */
    rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
    sqlite3_bind_int(pFindLevel, 1, nMin);
    if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){
      return sqlite3_reset(pFindLevel);
    }
    iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
    rc = sqlite3_reset(pFindLevel);
    if( rc!=SQLITE_OK ) return rc;

    /* Allocate space for the cursor, filter and writer objects */
    pWriter = (IncrmergeWriter *)sqlite3_malloc(nAlloc);
    if( !pWriter ) return SQLITE_NOMEM;
    memset(pWriter, 0, nAlloc);
    pFilter = (Fts3SegFilter *)&pWriter[1];
    pCsr = (Fts3MultiSegReader *)&pFilter[1];
................................................................................
    /* Open a cursor to iterate through the contents of indexes 0 and 1 of
    ** the selected absolute level. */
    pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;
    rc = fts3IncrmergeCsr(p, iAbsLevel, pCsr);

    if( rc==SQLITE_OK ){
      rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter);


      if( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr)) ){
        rc = fts3IncrmergeWriter(p, iAbsLevel, pCsr->zTerm,pCsr->nTerm,pWriter);
        if( rc==SQLITE_OK ){
          do {
            rc = fts3IncrmergeAppend(p, pWriter, pCsr);
            if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
            if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
................................................................................
**
**    INSERT INTO table(table) VALUES('merge=A,B');
**
** A and B are integers that decode to be the number of leaf pages
** written for the merge, and the minimum number of segments on a level
** before it will be selected for a merge, respectively.
*/
static int fts3DoIncrmerge(Fts3Table *p, const char *zParam){



  int rc;
  int nMin = (FTS3_MERGE_COUNT / 2);
  int nMerge = 0;
  const char *z = zParam;

  /* Read the first integer value */
  for(z=zParam; z[0]>='0' && z[0]<='9'; z++){
................................................................................
    nMin = 0;
    while( z[0]>='0' && z[0]<='9' ){
      nMin = nMin * 10 + (z[0] - '0');
      z++;
    }
  }

  if( z[0]!='\0' ) return SQLITE_ERROR;
  if( nMin<2 ) nMin = 2;


  rc = fts3Incrmerge(p, nMerge, nMin);
  sqlite3Fts3SegmentsClose(p);

  return rc;
}

/*
** Handle a 'special' INSERT of the form:
**
**   "INSERT INTO tbl(tbl) VALUES(<expr>)"
................................................................................
}

/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables. The schema of the virtual table being:
**
**     CREATE TABLE <table name>( 
**       <user COLUMns>,
**       <table name> HIDDEN, 
**       docid HIDDEN, 
**       <langid> HIDDEN
**     );
**
** 
*/







>
>
>
>
>
>

<
<
<
>
>
>







 







|







 







|
>
|
|
>
>







 







|

<
|
|

|
|
|
|
|
|
<
|
<
>
|







 







|



|
|

<
|
<













|







 







<
|
<
>







 







>







 







|


<
>
>
>
>


|
<
<
<
|
<

|
|
|
|
|
|
|
|
|
|

|
|
|
|

|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
<







 







|







 







|


|







 







|
<







 







>
>







 







|
>
>
>







 







|
|
<
>
|
|
>







 







|







3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281



3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
....
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
....
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
....
3633
3634
3635
3636
3637
3638
3639
3640
3641

3642
3643
3644
3645
3646
3647
3648
3649
3650

3651

3652
3653
3654
3655
3656
3657
3658
3659
3660
....
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698

3699

3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
....
3867
3868
3869
3870
3871
3872
3873

3874

3875
3876
3877
3878
3879
3880
3881
3882
....
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
....
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039

4040
4041
4042
4043
4044
4045
4046



4047

4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096

4097
4098
4099
4100
4101
4102
4103
....
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
....
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
....
4177
4178
4179
4180
4181
4182
4183
4184

4185
4186
4187
4188
4189
4190
4191
....
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
....
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
....
4255
4256
4257
4258
4259
4260
4261
4262
4263

4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
....
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
}

typedef struct IncrmergeWriter IncrmergeWriter;
typedef struct LayerWriter LayerWriter;
typedef struct Blob Blob;
typedef struct NodeReader NodeReader;

/*
** An instance of the following structure is used as a dynamic buffer
** to build up nodes or other blobs of data in.
**
** The function blobGrowBuffer() is used to extend the allocation.
*/
struct Blob {



  char *a;                        /* Pointer to allocation */
  int n;                          /* Number of valid bytes of data in a[] */
  int nAlloc;                     /* Allocated size of a[] (nAlloc>=n) */
};

struct LayerWriter {
  sqlite3_int64 iBlock;           /* Current block id */
  Blob key;                       /* Last key written to the current block */
  Blob block;                     /* Current block image */
};
................................................................................
  const char *zTerm,              /* Term to write to internal node */
  int nTerm                       /* Bytes at zTerm */
){
  sqlite3_int64 iPtr = pWriter->aLayer[0].iBlock;
  int iLayer;

  assert( nTerm>0 );
  for(iLayer=1; ALWAYS(iLayer<FTS_MAX_APPENDABLE_HEIGHT); iLayer++){
    sqlite3_int64 iNextPtr = 0;
    LayerWriter *pLayer = &pWriter->aLayer[iLayer];
    int rc = SQLITE_OK;
    int nPrefix;
    int nSuffix;
    int nSpace;

................................................................................
  int i;                          /* Used to iterate through non-root layers */
  int iRoot;
  LayerWriter *pRoot;
  int rc = *pRc;

  /* Find the root node */
  for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){
    LayerWriter *pLayer = &pWriter->aLayer[iRoot];
    if( pLayer->block.n>0 ) break;
    assert( *pRc || pLayer->block.nAlloc==0 );
    assert( *pRc || pLayer->key.nAlloc==0 );
    sqlite3_free(pLayer->block.a);
    sqlite3_free(pLayer->key.a);
  }

  /* Empty output segment. This is a no-op. */
  if( iRoot<0 ) return;

  /* The entire output segment fits on the root node. This is not allowed. */
  if( iRoot==0 ){
................................................................................
  res = memcmp(zLhs, zRhs, nCmp);
  if( res==0 ) res = nLhs - nRhs;

  return res;
}


static int fts3IsAppendable(Fts3Table *p, sqlite3_int64 iEnd, int *pbRes){
  int bRes = 0;

  sqlite3_stmt *pCheck = 0;
  int rc;

  rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0);
  if( rc==SQLITE_OK ){
    sqlite3_bind_int64(pCheck, 1, iEnd);
    if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1;
    rc = sqlite3_reset(pCheck);
  }

  

  *pbRes = bRes;
  return rc;
}

/*
**
*/
static int fts3IncrmergeLoad(
  Fts3Table *p,                   /* Fts3 table handle */
................................................................................
      nRoot = sqlite3_column_bytes(pSelect, 4);
      aRoot = sqlite3_column_blob(pSelect, 4);
    }else{
      return sqlite3_reset(pSelect);
    }

    /* Check for the zero-length marker in the %_segments table */
    rc = fts3IsAppendable(p, iEnd, &bAppendable);

    /* Check that zKey/nKey is larger than the largest key the candidate */
    if( rc==SQLITE_OK && bAppendable ){
      char *aLeaf = 0;
      int nLeaf = 0;


      rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0);

      if( rc==SQLITE_OK ){
        NodeReader reader;
        for(rc = nodeReaderInit(&reader, aLeaf, nLeaf);
            rc==SQLITE_OK && reader.aNode;
            rc = nodeReaderNext(&reader)
        ){
          assert( reader.aNode );
        }
        if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){
          bAppendable = 0;
        }
        nodeReaderRelease(&reader);
      }
      sqlite3_free(aLeaf);
    }

    if( rc==SQLITE_OK && bAppendable ){
      /* It is possible to append to this segment. Set up the IncrmergeWriter
      ** object to do so.  */
      int i;
      int nHeight = (int)aRoot[0];
................................................................................
    rc = sqlite3_reset(pFirstBlock);
  }
  if( rc!=SQLITE_OK ) return rc;

  /* Insert the marker in the %_segments table to make sure nobody tries
  ** to steal the space just allocated. This is also used to identify 
  ** appendable segments.  */

  rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0);

  if( rc!=SQLITE_OK ) return rc;

  pWriter->iAbsLevel = iAbsLevel;
  pWriter->nLeafEst = nLeafEst;
  pWriter->iIdx = iIdx;

  /* Set up the array of LayerWriter objects */
  for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
................................................................................
      *piBlock = reader.iChild;
      bStarted = 1;
    }
    rc = fts3AppendToNode(
        pNew, &prev, reader.term.a, reader.term.n,
        reader.aDoclist, reader.nDoclist
    );
    if( rc!=SQLITE_OK ) break;
  }
  if( bStarted==0 ){
    fts3StartNode(pNew, (int)aNode[0], reader.iChild);
    *piBlock = reader.iChild;
  }
  assert( pNew->n<=pNew->nAlloc );

................................................................................
static int fts3TruncateSegment(
  Fts3Table *p,                   /* FTS3 table handle */
  sqlite3_int64 iAbsLevel,        /* Absolute level of segment to modify */
  int iIdx,                       /* Index within level of segment to modify */
  const char *zTerm,              /* Remove terms smaller than this */
  int nTerm                       /* Number of bytes in buffer zTerm */
){
  int rc = SQLITE_OK;             /* Return code */
  Blob root = {0,0,0};            /* New root page image */
  Blob block = {0,0,0};           /* Buffer used for any other block */

  sqlite3_int64 iBlock = 0;       /* Block id */
  sqlite3_int64 iNewStart = 0;    /* New value for iStartBlock */
  sqlite3_int64 iOldStart = 0;    /* Old value for iStartBlock */
  int rc2;                        /* sqlite3_reset() return code */
  sqlite3_stmt *pFetch = 0;       /* Statement used to fetch segdir */

  assert( p->aStmt[SQL_SELECT_SEGDIR] );



  pFetch = p->aStmt[SQL_SELECT_SEGDIR];


  sqlite3_bind_int64(pFetch, 1, iAbsLevel);
  sqlite3_bind_int(pFetch, 2, iIdx);
  if( SQLITE_ROW==sqlite3_step(pFetch) ){
    const char *aRoot = sqlite3_column_blob(pFetch, 4);
    int nRoot = sqlite3_column_bytes(pFetch, 4);
    iOldStart = sqlite3_column_int64(pFetch, 1);
    rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
  }
  rc2 = sqlite3_reset(pFetch);
  if( rc==SQLITE_OK ) rc = rc2;

  while( rc==SQLITE_OK && iBlock ){
    char *aBlock = 0;
    int nBlock = 0;
    iNewStart = iBlock;

    rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);
    if( rc==SQLITE_OK ){
      rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock);
    }
    if( rc==SQLITE_OK ){
      rc = fts3WriteSegment(p, iNewStart, block.a, block.n);
    }
    sqlite3_free(aBlock);
  }

  /* Variable iNewStart now contains the first valid leaf node. */
  if( rc==SQLITE_OK && iNewStart ){
    sqlite3_stmt *pDel = 0;
    rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0);
    if( rc==SQLITE_OK ){
      sqlite3_bind_int64(pDel, 1, iOldStart);
      sqlite3_bind_int64(pDel, 2, iNewStart-1);
      sqlite3_step(pDel);
      rc = sqlite3_reset(pDel);
    }
  }

  if( rc==SQLITE_OK ){
    sqlite3_stmt *pChomp = 0;
    rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0);
    if( rc==SQLITE_OK ){
      sqlite3_bind_int64(pChomp, 1, iNewStart);
      sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC);
      sqlite3_bind_int64(pChomp, 3, iAbsLevel);
      sqlite3_bind_int(pChomp, 4, iIdx);
      sqlite3_step(pChomp);
      rc = sqlite3_reset(pChomp);

    }
  }

  sqlite3_free(root.a);
  sqlite3_free(block.a);
  return rc;
}
................................................................................
  int rc = SQLITE_OK;

  assert( pCsr->nSegment==2 );
  assert( (pCsr->apSegment[0]->iIdx==0 && pCsr->apSegment[1]->iIdx==1)
       || (pCsr->apSegment[1]->iIdx==0 && pCsr->apSegment[0]->iIdx==1) 
  );

  for(i=1; i>=0 && rc==SQLITE_OK; i--){
    Fts3SegReader *pSeg = pCsr->apSegment[0];
    if( pSeg->iIdx!=i ) pSeg = pCsr->apSegment[1];
    assert( pSeg->iIdx==i );

    if( pSeg->aNode==0 ){
      /* Seg-reader is at EOF. Remove the entire input segment. */
      rc = fts3DeleteSegment(p, pSeg);
................................................................................

  return rc;
}

/*
** Attempt an incremental merge that writes nMerge leaf pages.
**
** Incremental merges happen two segments at a time. The two
** segments to be merged are the two oldest segments (the ones with
** the smallest index) in the highest level that has at least
** nMin segments. Multiple segment pair merges might occur in
** an attempt to write the quota of nMerge leaf pages.
*/
static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){
  int rc = SQLITE_OK;             /* Return code */
  int nRem = nMerge;              /* Number of leaf pages yet to  be written */

  assert( nMin>=2 );
................................................................................
    ** is set to the absolute level number of the level to merge from.  */
    rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
    sqlite3_bind_int(pFindLevel, 1, nMin);
    if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){
      return sqlite3_reset(pFindLevel);
    }
    iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
    sqlite3_reset(pFindLevel);


    /* Allocate space for the cursor, filter and writer objects */
    pWriter = (IncrmergeWriter *)sqlite3_malloc(nAlloc);
    if( !pWriter ) return SQLITE_NOMEM;
    memset(pWriter, 0, nAlloc);
    pFilter = (Fts3SegFilter *)&pWriter[1];
    pCsr = (Fts3MultiSegReader *)&pFilter[1];
................................................................................
    /* Open a cursor to iterate through the contents of indexes 0 and 1 of
    ** the selected absolute level. */
    pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;
    rc = fts3IncrmergeCsr(p, iAbsLevel, pCsr);

    if( rc==SQLITE_OK ){
      rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter);
    }
    if( rc==SQLITE_OK ){
      if( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr)) ){
        rc = fts3IncrmergeWriter(p, iAbsLevel, pCsr->zTerm,pCsr->nTerm,pWriter);
        if( rc==SQLITE_OK ){
          do {
            rc = fts3IncrmergeAppend(p, pWriter, pCsr);
            if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
            if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
................................................................................
**
**    INSERT INTO table(table) VALUES('merge=A,B');
**
** A and B are integers that decode to be the number of leaf pages
** written for the merge, and the minimum number of segments on a level
** before it will be selected for a merge, respectively.
*/
static int fts3DoIncrmerge(
  Fts3Table *p,                   /* FTS3 table handle */
  const char *zParam              /* Nul-terminated string containing "A,B" */
){
  int rc;
  int nMin = (FTS3_MERGE_COUNT / 2);
  int nMerge = 0;
  const char *z = zParam;

  /* Read the first integer value */
  for(z=zParam; z[0]>='0' && z[0]<='9'; z++){
................................................................................
    nMin = 0;
    while( z[0]>='0' && z[0]<='9' ){
      nMin = nMin * 10 + (z[0] - '0');
      z++;
    }
  }

  if( z[0]!='\0' || nMin<2 ){
    rc = SQLITE_ERROR;

  }else{
    rc = fts3Incrmerge(p, nMerge, nMin);
    sqlite3Fts3SegmentsClose(p);
  }
  return rc;
}

/*
** Handle a 'special' INSERT of the form:
**
**   "INSERT INTO tbl(tbl) VALUES(<expr>)"
................................................................................
}

/*
** This function does the work for the xUpdate method of FTS3 virtual
** tables. The schema of the virtual table being:
**
**     CREATE TABLE <table name>( 
**       <user columns>,
**       <table name> HIDDEN, 
**       docid HIDDEN, 
**       <langid> HIDDEN
**     );
**
** 
*/

Changes to test/fts3_common.tcl.

10
11
12
13
14
15
16





























































17
18
19
20
21
22
23
..
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#***********************************************************************
#
# This file contains common code used the fts3 tests. At one point
# equivalent functionality was implemented in C code. But it is easier
# to use Tcl.
#






























































#-------------------------------------------------------------------------
# USAGE: fts3_integrity_check TBL
#
# This proc is used to verify that the full-text index is consistent with
# the contents of the fts3 table. In other words, it checks that the
# data in the %_contents table matches that in the %_segdir and %_segments 
# tables.
................................................................................
      set sql {SELECT fts3_tokenizer_test('simple', $c)}

      foreach {pos term dummy} [db one $sql] {
        if {![info exists C($iDoc,$iCol,$pos)]} {
          set es "Error at docid=$iDoc col=$iCol pos=$pos. Index is missing"
          lappend errors $es
        } else {
          if {$C($iDoc,$iCol,$pos) != "$term"} {
            set    es "Error at docid=$iDoc col=$iCol pos=$pos. Index "
            append es "has \"$C($iDoc,$iCol,$pos)\", document has \"$term\""
            lappend errors $es
          }
          unset C($iDoc,$iCol,$pos)
        }
      }







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







 







|







10
11
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
...
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#***********************************************************************
#
# This file contains common code used the fts3 tests. At one point
# equivalent functionality was implemented in C code. But it is easier
# to use Tcl.
#


#-------------------------------------------------------------------------
# USAGE: fts3_build_db_1 N
#
# Build a sample FTS table in the database opened by database connection 
# [db]. The name of the new table is "t1".
#
proc fts3_build_db_1 {n} {

  if {$n > 10000} {error "n must be <= 10000"}

  db eval { CREATE VIRTUAL TABLE t1 USING fts4(x, y) }

  set xwords [list zero one two three four five six seven eight nine ten]
  set ywords [list alpha beta gamma delta epsilon zeta eta theta iota kappa]

  for {set i 0} {$i < $n} {incr i} {
    set x ""
    set y ""

    set x [list]
    lappend x [lindex $xwords [expr ($i / 1000) % 10]]
    lappend x [lindex $xwords [expr ($i / 100)  % 10]]
    lappend x [lindex $xwords [expr ($i / 10)   % 10]]
    lappend x [lindex $xwords [expr ($i / 1)   % 10]]

    set y [list]
    lappend y [lindex $ywords [expr ($i / 1000) % 10]]
    lappend y [lindex $ywords [expr ($i / 100)  % 10]]
    lappend y [lindex $ywords [expr ($i / 10)   % 10]]
    lappend y [lindex $ywords [expr ($i / 1)   % 10]]

    db eval { INSERT INTO t1(docid, x, y) VALUES($i, $x, $y) }
  }
}

#-------------------------------------------------------------------------
# USAGE: fts3_build_db_2 N
#
# Build a sample FTS table in the database opened by database connection 
# [db]. The name of the new table is "t2".
#
proc fts3_build_db_2 {n} {

  if {$n > 100000} {error "n must be <= 100000"}

  db eval { CREATE VIRTUAL TABLE t2 USING fts4 }

  set chars [list a b c d e f g h  i j k l m n o p  q r s t u v w x  y z ""]

  for {set i 0} {$i < $n} {incr i} {
    set word ""
    set n [llength $chars]
    append word [lindex $chars [expr {($i / 1)   % $n}]]
    append word [lindex $chars [expr {($i / $n)  % $n}]]
    append word [lindex $chars [expr {($i / ($n*$n)) % $n}]]

    db eval { INSERT INTO t2(docid, content) VALUES($i, $word) }
  }
}

#-------------------------------------------------------------------------
# USAGE: fts3_integrity_check TBL
#
# This proc is used to verify that the full-text index is consistent with
# the contents of the fts3 table. In other words, it checks that the
# data in the %_contents table matches that in the %_segdir and %_segments 
# tables.
................................................................................
      set sql {SELECT fts3_tokenizer_test('simple', $c)}

      foreach {pos term dummy} [db one $sql] {
        if {![info exists C($iDoc,$iCol,$pos)]} {
          set es "Error at docid=$iDoc col=$iCol pos=$pos. Index is missing"
          lappend errors $es
        } else {
          if {[string compare $C($iDoc,$iCol,$pos) $term]} {
            set    es "Error at docid=$iDoc col=$iCol pos=$pos. Index "
            append es "has \"$C($iDoc,$iCol,$pos)\", document has \"$term\""
            lappend errors $es
          }
          unset C($iDoc,$iCol,$pos)
        }
      }

Changes to test/fts4merge.test.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
..
94
95
96
97
98
99
100



101
















































102
103

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}

proc fts3_build_db_1 {n} {

  if {$n > 10000} {error "n must be <= 10000"}

  db eval { CREATE VIRTUAL TABLE t1 USING fts4(x, y) }

  set xwords [list zero one two three four five six seven eight nine ten]
  set ywords [list alpha beta gamma delta epsilon zeta eta theta iota kappa]

  for {set i 0} {$i < $n} {incr i} {
    set x ""
    set y ""

    set x [list]
    lappend x [lindex $xwords [expr ($i / 1000) % 10]]
    lappend x [lindex $xwords [expr ($i / 100)  % 10]]
    lappend x [lindex $xwords [expr ($i / 10)   % 10]]
    lappend x [lindex $xwords [expr ($i / 1)   % 10]]

    set y [list]
    lappend y [lindex $ywords [expr ($i / 1000) % 10]]
    lappend y [lindex $ywords [expr ($i / 100)  % 10]]
    lappend y [lindex $ywords [expr ($i / 10)   % 10]]
    lappend y [lindex $ywords [expr ($i / 1)   % 10]]

    db eval { INSERT INTO t1(docid, x, y) VALUES($i, $x, $y) }
  }
}

#-------------------------------------------------------------------------
# Test cases 1.*
#
do_test 1.0 { fts3_build_db_1 1004 } {}
do_test 1.1 { fts3_integrity_check t1 } {ok}
do_execsql_test 1.1 { 
  SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
................................................................................
} {
  0 {0 1 2 3} 
  1 {0 1 2 3} 
  2 {0 1 2 3} 
  3 {0 1 2}
}





















































finish_test








<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







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


19
20
21
22
23
24
25





























26
27
28
29
30
31
32
..
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}






























#-------------------------------------------------------------------------
# Test cases 1.*
#
do_test 1.0 { fts3_build_db_1 1004 } {}
do_test 1.1 { fts3_integrity_check t1 } {ok}
do_execsql_test 1.1 { 
  SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
................................................................................
} {
  0 {0 1 2 3} 
  1 {0 1 2 3} 
  2 {0 1 2 3} 
  3 {0 1 2}
}

#-------------------------------------------------------------------------
# Test cases 2.* test that errors in the xxx part of the 'merge=xxx' are
# handled correctly.
#
do_execsql_test 2.0 { CREATE VIRTUAL TABLE t2 USING fts4 }

foreach {tn arg} {
  1   {merge=abc}
  2   {merge=%%%}
  3   {merge=,}
  4   {merge=5,}
  5   {merge=6,%}
  6   {merge=6,six}
  7   {merge=6,1}
  8   {merge=6,0}
} {
  do_catchsql_test 2.$tn { 
    INSERT INTO t2(t2) VALUES($arg);
  } {1 {SQL logic error or missing database}}
}

#-------------------------------------------------------------------------
# Test cases 3.*
#
do_test 3.0 { 
  reset_db
  execsql { PRAGMA page_size = 512 }
  fts3_build_db_2 30040 
} {}
do_test 3.1 { fts3_integrity_check t2 } {ok}

do_execsql_test 3.2 { 
  SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level 
} {
  0 {0 1 2 3 4 5 6 7} 
  1 {0 1 2 3 4} 
  2 {0 1 2 3 4} 
  3 {0 1 2 3 4 5 6}
}

do_execsql_test 3.3 { 
  INSERT INTO t2(t2) VALUES('merge=1000000,2');
  SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level 
} {
  0 {0 1} 
  1 {0 1} 
  2 0 
  3 {0 1}  
  4 {0 1} 
  5 0
}

finish_test

Added test/fts4merge2.test.













































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
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


set testdir [file dirname $argv0]
source $testdir/tester.tcl
source $testdir/fts3_common.tcl
source $testdir/malloc_common.tcl
set ::testprefix fts4merge2

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}

do_test 1.0 {
  fts3_build_db_1 1000
  faultsim_save_and_close
} {}

do_faultsim_test 1.1 -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  execsql { INSERT INTO t1(t1) VALUES('merge=32,4') }
} -test {
  faultsim_test_result {0 {}} 
}

do_faultsim_test 1.2 -faults oom-t* -prep {
  if {$iFail<100} {set iFail 803}
  faultsim_restore_and_reopen
} -body {
  execsql { INSERT INTO t1(t1) VALUES('merge=1,2') }
  execsql { INSERT INTO t1(t1) VALUES('merge=1,2') }
} -test {
  faultsim_test_result {0 {}} 
}

finish_test

Changes to test/permutations.test.

180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
  fts3defer.test fts3defer2.test fts3e.test fts3expr.test fts3expr2.test 
  fts3near.test fts3query.test fts3shared.test fts3snippet.test 
  fts3sort.test
  fts3fault.test fts3malloc.test fts3matchinfo.test
  fts3aux1.test fts3comp1.test fts3auto.test
  fts4aa.test fts4content.test
  fts3conf.test fts3prefix.test fts3fault2.test fts3corrupt.test
  fts3corrupt2.test fts3first.test fts4langid.test
}


lappend ::testsuitelist xxx
#-------------------------------------------------------------------------
# Define the coverage related test suites:
#







|







180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
  fts3defer.test fts3defer2.test fts3e.test fts3expr.test fts3expr2.test 
  fts3near.test fts3query.test fts3shared.test fts3snippet.test 
  fts3sort.test
  fts3fault.test fts3malloc.test fts3matchinfo.test
  fts3aux1.test fts3comp1.test fts3auto.test
  fts4aa.test fts4content.test
  fts3conf.test fts3prefix.test fts3fault2.test fts3corrupt.test
  fts3corrupt2.test fts3first.test fts4langid.test fts4merge.test
}


lappend ::testsuitelist xxx
#-------------------------------------------------------------------------
# Define the coverage related test suites:
#