/ Check-in [c05c3fd2]
Login

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

Overview
Comment:Fix an FTS problem triggered by querying for an N character prefix using an N+1 character prefix index after rows have been deleted from the FTS table. Fix for [edb497982c].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: c05c3fd20d93f430140d762ead23bacd337ffb4d
User & Date: dan 2012-01-25 16:29:45
Original Comment: Fix an FTS problem triggered by querying for an N character prefix using an N+1 character prefix index after rows have been deleted from the FTS table.
References
2012-01-25
22:08
Cherrypick the FTS fix in [c05c3fd20d9] into the nx-devkit branch. Ticket [edb497982c]. check-in: 2a7170f0 user: drh tags: nx-devkit
Context
2012-01-25
20:43
Only invalidate the schema when the OP_ParseSchema opcode fails, not on any general failure of a vdbe program. check-in: 11f68d99 user: drh tags: trunk
16:29
Fix an FTS problem triggered by querying for an N character prefix using an N+1 character prefix index after rows have been deleted from the FTS table. Fix for [edb497982c]. check-in: c05c3fd2 user: dan tags: trunk
2012-01-24
10:08
Changes to the async-io module so that the xFileControl method returns SQLITE_NOTFOUND when a file-control is not recognized and so that it adds the second nul-terminator byte to filenames passed to the xOpen method of the underlying VFS. check-in: 7036886e user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

2596
2597
2598
2599
2600
2601
2602


2603
2604
2605
2606
2607
2608
2609
2610
        sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
        rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
        if( rc!=SQLITE_OK ) goto finished;
        if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
      }
 
      rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1, 


          iStartBlock, iLeavesEndBlock, iEndBlock, zRoot, nRoot, &pSeg
      );
      if( rc!=SQLITE_OK ) goto finished;
      rc = fts3SegReaderCursorAppend(pCsr, pSeg);
    }
  }

 finished:







>
>
|







2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
        sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
        rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
        if( rc!=SQLITE_OK ) goto finished;
        if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
      }
 
      rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1, 
          (isPrefix==0 && isScan==0),
          iStartBlock, iLeavesEndBlock, 
          iEndBlock, zRoot, nRoot, &pSeg
      );
      if( rc!=SQLITE_OK ) goto finished;
      rc = fts3SegReaderCursorAppend(pCsr, pSeg);
    }
  }

 finished:

Changes to ext/fts3/fts3Int.h.

397
398
399
400
401
402
403
404
405
406
407
408
409
410
411


/* fts3_write.c */
int sqlite3Fts3UpdateMethod(sqlite3_vtab*,int,sqlite3_value**,sqlite3_int64*);
int sqlite3Fts3PendingTermsFlush(Fts3Table *);
void sqlite3Fts3PendingTermsClear(Fts3Table *);
int sqlite3Fts3Optimize(Fts3Table *);
int sqlite3Fts3SegReaderNew(int, sqlite3_int64,
  sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
int sqlite3Fts3SegReaderPending(
  Fts3Table*,int,const char*,int,int,Fts3SegReader**);
void sqlite3Fts3SegReaderFree(Fts3SegReader *);
int sqlite3Fts3AllSegdirs(Fts3Table*, int, int, sqlite3_stmt **);
int sqlite3Fts3ReadLock(Fts3Table *);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*, int*);







|







397
398
399
400
401
402
403
404
405
406
407
408
409
410
411


/* fts3_write.c */
int sqlite3Fts3UpdateMethod(sqlite3_vtab*,int,sqlite3_value**,sqlite3_int64*);
int sqlite3Fts3PendingTermsFlush(Fts3Table *);
void sqlite3Fts3PendingTermsClear(Fts3Table *);
int sqlite3Fts3Optimize(Fts3Table *);
int sqlite3Fts3SegReaderNew(int, int, sqlite3_int64,
  sqlite3_int64, sqlite3_int64, const char *, int, Fts3SegReader**);
int sqlite3Fts3SegReaderPending(
  Fts3Table*,int,const char*,int,int,Fts3SegReader**);
void sqlite3Fts3SegReaderFree(Fts3SegReader *);
int sqlite3Fts3AllSegdirs(Fts3Table*, int, int, sqlite3_stmt **);
int sqlite3Fts3ReadLock(Fts3Table *);
int sqlite3Fts3ReadBlock(Fts3Table*, sqlite3_int64, char **, int*, int*);

Changes to ext/fts3/fts3_write.c.

106
107
108
109
110
111
112

113
114
115
116
117
118
119
....
1083
1084
1085
1086
1087
1088
1089












1090
1091
1092
1093
1094
1095
1096
....
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
....
1375
1376
1377
1378
1379
1380
1381

1382
1383
1384
1385
1386
1387
1388
....
1396
1397
1398
1399
1400
1401
1402

1403
1404
1405
1406
1407
1408
1409
....
2398
2399
2400
2401
2402
2403
2404

2405
2406
2407
2408
2409




2410
2411
2412
2413
2414
2415
2416
....
2523
2524
2525
2526
2527
2528
2529




2530

2531
2532
2533
2534
2535
2536
2537
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
*/
struct Fts3SegReader {
  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */


  sqlite3_int64 iStartBlock;      /* Rowid of first leaf block to traverse */
  sqlite3_int64 iLeafEndBlock;    /* Rowid of final leaf block to traverse */
  sqlite3_int64 iEndBlock;        /* Rowid of final block in segment (or 0) */
  sqlite3_int64 iCurrentBlock;    /* Current leaf block (or 0) */

  char *aNode;                    /* Pointer to node data (or NULL) */
................................................................................
  while( pReader->pBlob && rc==SQLITE_OK 
     &&  (pFrom - pReader->aNode + nByte)>pReader->nPopulate
  ){
    rc = fts3SegReaderIncrRead(pReader);
  }
  return rc;
}













/*
** Move the iterator passed as the first argument to the next term in the
** segment. If successful, SQLITE_OK is returned. If there is no next term,
** SQLITE_DONE. Otherwise, an SQLite error code.
*/
static int fts3SegReaderNext(
................................................................................
        pReader->aNode = pReader->aDoclist = pList->aData;
        pReader->ppNextElem++;
        assert( pReader->aNode );
      }
      return SQLITE_OK;
    }

    if( !fts3SegReaderIsRootOnly(pReader) ){
      sqlite3_free(pReader->aNode);
      sqlite3_blob_close(pReader->pBlob);
      pReader->pBlob = 0;
    }
    pReader->aNode = 0;

    /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf 
    ** blocks have already been traversed.  */
    assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock );
    if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
      return SQLITE_OK;
    }
................................................................................
}

/*
** Allocate a new SegReader object.
*/
int sqlite3Fts3SegReaderNew(
  int iAge,                       /* Segment "age". */

  sqlite3_int64 iStartLeaf,       /* First leaf to traverse */
  sqlite3_int64 iEndLeaf,         /* Final leaf to traverse */
  sqlite3_int64 iEndBlock,        /* Final block of segment */
  const char *zRoot,              /* Buffer containing root node */
  int nRoot,                      /* Size of buffer containing root node */
  Fts3SegReader **ppReader        /* OUT: Allocated Fts3SegReader */
){
................................................................................

  pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
  if( !pReader ){
    return SQLITE_NOMEM;
  }
  memset(pReader, 0, sizeof(Fts3SegReader));
  pReader->iIdx = iAge;

  pReader->iStartBlock = iStartLeaf;
  pReader->iLeafEndBlock = iEndLeaf;
  pReader->iEndBlock = iEndBlock;

  if( nExtra ){
    /* The entire segment is stored in the root node. */
    pReader->aNode = (char *)&pReader[1];
................................................................................
  /* If the Fts3SegFilter defines a specific term (or term prefix) to search 
  ** for, then advance each segment iterator until it points to a term of
  ** equal or greater value than the specified term. This prevents many
  ** unnecessary merge/sort operations for the case where single segment
  ** b-tree leaf nodes contain more than one term.
  */
  for(i=0; pCsr->bRestart==0 && i<pCsr->nSegment; i++){

    Fts3SegReader *pSeg = pCsr->apSegment[i];
    do {
      int rc = fts3SegReaderNext(p, pSeg, 0);
      if( rc!=SQLITE_OK ) return rc;
    }while( zTerm && fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 );




  }
  fts3SegReaderSort(pCsr->apSegment, nSeg, nSeg, fts3SegReaderCmp);

  return SQLITE_OK;
}

int sqlite3Fts3SegReaderStart(
................................................................................
    int nMerge;
    int i;
  
    /* Advance the first pCsr->nAdvance entries in the apSegment[] array
    ** forward. Then sort the list in order of current term again.  
    */
    for(i=0; i<pCsr->nAdvance; i++){




      rc = fts3SegReaderNext(p, apSegment[i], 0);

      if( rc!=SQLITE_OK ) return rc;
    }
    fts3SegReaderSort(apSegment, nSegment, pCsr->nAdvance, fts3SegReaderCmp);
    pCsr->nAdvance = 0;

    /* If all the seg-readers are at EOF, we're finished. return SQLITE_OK. */
    assert( rc==SQLITE_OK );







>







 







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







 







|
<
<
<
<
<







 







>







 







>







 







>




|
>
>
>
>







 







>
>
>
>
|
>







106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
....
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
....
1136
1137
1138
1139
1140
1141
1142
1143





1144
1145
1146
1147
1148
1149
1150
....
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
....
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
....
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
....
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
**
**   fts3SegReaderNext()
**   fts3SegReaderFirstDocid()
**   fts3SegReaderNextDocid()
*/
struct Fts3SegReader {
  int iIdx;                       /* Index within level, or 0x7FFFFFFF for PT */
  int bLookup;                    /* True for a lookup only */

  sqlite3_int64 iStartBlock;      /* Rowid of first leaf block to traverse */
  sqlite3_int64 iLeafEndBlock;    /* Rowid of final leaf block to traverse */
  sqlite3_int64 iEndBlock;        /* Rowid of final block in segment (or 0) */
  sqlite3_int64 iCurrentBlock;    /* Current leaf block (or 0) */

  char *aNode;                    /* Pointer to node data (or NULL) */
................................................................................
  while( pReader->pBlob && rc==SQLITE_OK 
     &&  (pFrom - pReader->aNode + nByte)>pReader->nPopulate
  ){
    rc = fts3SegReaderIncrRead(pReader);
  }
  return rc;
}

/*
** Set an Fts3SegReader cursor to point at EOF.
*/
static void fts3SegReaderSetEof(Fts3SegReader *pSeg){
  if( !fts3SegReaderIsRootOnly(pSeg) ){
    sqlite3_free(pSeg->aNode);
    sqlite3_blob_close(pSeg->pBlob);
    pSeg->pBlob = 0;
  }
  pSeg->aNode = 0;
}

/*
** Move the iterator passed as the first argument to the next term in the
** segment. If successful, SQLITE_OK is returned. If there is no next term,
** SQLITE_DONE. Otherwise, an SQLite error code.
*/
static int fts3SegReaderNext(
................................................................................
        pReader->aNode = pReader->aDoclist = pList->aData;
        pReader->ppNextElem++;
        assert( pReader->aNode );
      }
      return SQLITE_OK;
    }

    fts3SegReaderSetEof(pReader);






    /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf 
    ** blocks have already been traversed.  */
    assert( pReader->iCurrentBlock<=pReader->iLeafEndBlock );
    if( pReader->iCurrentBlock>=pReader->iLeafEndBlock ){
      return SQLITE_OK;
    }
................................................................................
}

/*
** Allocate a new SegReader object.
*/
int sqlite3Fts3SegReaderNew(
  int iAge,                       /* Segment "age". */
  int bLookup,                    /* True for a lookup only */
  sqlite3_int64 iStartLeaf,       /* First leaf to traverse */
  sqlite3_int64 iEndLeaf,         /* Final leaf to traverse */
  sqlite3_int64 iEndBlock,        /* Final block of segment */
  const char *zRoot,              /* Buffer containing root node */
  int nRoot,                      /* Size of buffer containing root node */
  Fts3SegReader **ppReader        /* OUT: Allocated Fts3SegReader */
){
................................................................................

  pReader = (Fts3SegReader *)sqlite3_malloc(sizeof(Fts3SegReader) + nExtra);
  if( !pReader ){
    return SQLITE_NOMEM;
  }
  memset(pReader, 0, sizeof(Fts3SegReader));
  pReader->iIdx = iAge;
  pReader->bLookup = bLookup;
  pReader->iStartBlock = iStartLeaf;
  pReader->iLeafEndBlock = iEndLeaf;
  pReader->iEndBlock = iEndBlock;

  if( nExtra ){
    /* The entire segment is stored in the root node. */
    pReader->aNode = (char *)&pReader[1];
................................................................................
  /* If the Fts3SegFilter defines a specific term (or term prefix) to search 
  ** for, then advance each segment iterator until it points to a term of
  ** equal or greater value than the specified term. This prevents many
  ** unnecessary merge/sort operations for the case where single segment
  ** b-tree leaf nodes contain more than one term.
  */
  for(i=0; pCsr->bRestart==0 && i<pCsr->nSegment; i++){
    int res;
    Fts3SegReader *pSeg = pCsr->apSegment[i];
    do {
      int rc = fts3SegReaderNext(p, pSeg, 0);
      if( rc!=SQLITE_OK ) return rc;
    }while( zTerm && (res = fts3SegReaderTermCmp(pSeg, zTerm, nTerm))<0 );

    if( pSeg->bLookup && res!=0 ){
      fts3SegReaderSetEof(pSeg);
    }
  }
  fts3SegReaderSort(pCsr->apSegment, nSeg, nSeg, fts3SegReaderCmp);

  return SQLITE_OK;
}

int sqlite3Fts3SegReaderStart(
................................................................................
    int nMerge;
    int i;
  
    /* Advance the first pCsr->nAdvance entries in the apSegment[] array
    ** forward. Then sort the list in order of current term again.  
    */
    for(i=0; i<pCsr->nAdvance; i++){
      Fts3SegReader *pSeg = apSegment[i];
      if( pSeg->bLookup ){
        fts3SegReaderSetEof(pSeg);
      }else{
        rc = fts3SegReaderNext(p, pSeg, 0);
      }
      if( rc!=SQLITE_OK ) return rc;
    }
    fts3SegReaderSort(apSegment, nSegment, pCsr->nAdvance, fts3SegReaderCmp);
    pCsr->nAdvance = 0;

    /* If all the seg-readers are at EOF, we're finished. return SQLITE_OK. */
    assert( rc==SQLITE_OK );

Changes to test/fts3auto.test.

569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
#--------------------------------------------------------------------------
# The following test cases - fts3auto-5.* - focus on using prefix indexes.
#
set chunkconfig [fts3_configure_incr_load 1 1]
foreach {tn create pending} {
  1    "fts4(a, b)"                                  1
  2    "fts4(a, b, order=ASC, prefix=1)"             1
  3    "fts4(a, b, order=ASC,  prefix=1,3)"          0
  4    "fts4(a, b, order=DESC, prefix=2,4)"          0
  5    "fts4(a, b, order=DESC, prefix=1)"            0
  6    "fts4(a, b, order=ASC,  prefix=1,3)"          0
} {

  execsql [subst {
    DROP TABLE IF EXISTS t1;
    CREATE VIRTUAL TABLE t1 USING $create;
  }]








|
|
|
|







569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
#--------------------------------------------------------------------------
# The following test cases - fts3auto-5.* - focus on using prefix indexes.
#
set chunkconfig [fts3_configure_incr_load 1 1]
foreach {tn create pending} {
  1    "fts4(a, b)"                                  1
  2    "fts4(a, b, order=ASC, prefix=1)"             1
  3    "fts4(a, b, order=ASC,  prefix=\"1,3\")"      0
  4    "fts4(a, b, order=DESC, prefix=\"2,4\")"      0
  5    "fts4(a, b, order=DESC, prefix=\"1\")"        0
  6    "fts4(a, b, order=ASC,  prefix=\"1,3\")"      0
} {

  execsql [subst {
    DROP TABLE IF EXISTS t1;
    CREATE VIRTUAL TABLE t1 USING $create;
  }]

Added test/fts3prefix2.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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 2012 January 25
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    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 FTS3 module.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix fts3prefix2

ifcapable !fts3 {
  finish_test
  return
}

do_execsql_test 1.0 { PRAGMA page_size = 512 }
do_execsql_test 1.1 { 
  CREATE VIRTUAL TABLE t1 USING fts4(x, prefix="2,3");

  BEGIN;
    INSERT INTO t1 VALUES('T TX T TX T TX T TX T TX');
    INSERT INTO t1 SELECT * FROM t1;                       -- 2
    INSERT INTO t1 SELECT * FROM t1;                       -- 4
    INSERT INTO t1 SELECT * FROM t1;                       -- 8
    INSERT INTO t1 SELECT * FROM t1;                       -- 16
    INSERT INTO t1 SELECT * FROM t1;                       -- 32
    INSERT INTO t1 SELECT * FROM t1;                       -- 64
    INSERT INTO t1 SELECT * FROM t1;                       -- 128
    INSERT INTO t1 SELECT * FROM t1;                       -- 256
    INSERT INTO t1 SELECT * FROM t1;                       -- 512
    INSERT INTO t1 SELECT * FROM t1;                       -- 1024
    INSERT INTO t1 SELECT * FROM t1;                       -- 2048
  COMMIT;
}

do_execsql_test 1.2 {
  INSERT INTO t1 SELECT * FROM t1 LIMIT 10;
  INSERT INTO t1 SELECT * FROM t1 LIMIT 10;
  INSERT INTO t1 SELECT * FROM t1 LIMIT 10;
  DELETE FROM t1 WHERE docid > 5;
}

do_execsql_test 1.3 {
  SELECT * FROM t1 WHERE t1 MATCH 'T*';
} {
  {T TX T TX T TX T TX T TX}
  {T TX T TX T TX T TX T TX}
  {T TX T TX T TX T TX T TX}
  {T TX T TX T TX T TX T TX}
  {T TX T TX T TX T TX T TX}
}

finish_test