SQLite

Check-in [c05c3fd20d]
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
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: c05c3fd20d93f430140d762ead23bacd337ffb4d
User & Date: dan 2012-01-25 16:29:45.749
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: 2a7170f03c 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: 11f68d997d 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: c05c3fd20d 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: 7036886e83 user: dan tags: trunk)
Changes
Unified Diff 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
**
**   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) */







>







106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
**
**   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) */
1083
1084
1085
1086
1087
1088
1089












1090
1091
1092
1093
1094
1095
1096
  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(







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







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
  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(
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
        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;
    }







|
<
<
<
<
<







1136
1137
1138
1139
1140
1141
1142
1143





1144
1145
1146
1147
1148
1149
1150
        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;
    }
1375
1376
1377
1378
1379
1380
1381

1382
1383
1384
1385
1386
1387
1388
}

/*
** 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 */
){







>







1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
}

/*
** 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 */
){
1396
1397
1398
1399
1400
1401
1402

1403
1404
1405
1406
1407
1408
1409

  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];







>







1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419

  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];
2398
2399
2400
2401
2402
2403
2404

2405
2406
2407
2408
2409




2410
2411
2412
2413
2414
2415
2416
  /* 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(







>




|
>
>
>
>







2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
  /* 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(
2523
2524
2525
2526
2527
2528
2529




2530

2531
2532
2533
2534
2535
2536
2537
    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 );







>
>
>
>
|
>







2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
    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