SQLite: Check-in [50fae1f0]

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

Overview

Comment:	Logically store updates as (insert+delete) within the FTS tree. This allows keys to be annihilated more quickly under some circumstances.
Downloads:	Tarball \| ZIP archive \| SQL archive
Timelines:	family \| ancestors \| descendants \| both \| fts5
Files:	files \| file ages \| folders
SHA1:	50fae1f0006c0e946b5214e73eedf2687a0016f9
User & Date:	dan 2015-04-15 18:49:20

Context

2015-04-20
18:48		Fix some fts5 problems with very large position lists. (check-in: 2ea8f9cb user: dan tags: fts5)
2015-04-15
18:49		Logically store updates as (insert+delete) within the FTS tree. This allows keys to be annihilated more quickly under some circumstances. (check-in: 50fae1f0 user: dan tags: fts5)
16:01		Fix a problem preventing doclist indexes from being loaded. (check-in: b29109a0 user: dan tags: fts5)

Changes

Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

}

/*
** Return true if the iterator passed as the second argument currently
** points to a delete marker. A delete marker is an entry with a 0 byte
** position-list.
*/
static int fts5SegIterIsDelete(
  Fts5Index *p,                   /* FTS5 backend object */
  Fts5SegIter *pIter              /* Iterator to advance */
){
  int bRet = 0;
  Fts5Data *pLeaf = pIter->pLeaf;
  if( p->rc==SQLITE_OK && pLeaf ){
    bRet = pIter->nPos==0;
    /* bRet = pIter->bDel; */
#if 0
    if( pIter->iLeafOffset<pLeaf->n ){
      bRet = ((pLeaf->p[pIter->iLeafOffset] & 0xFE)==0x00);
    }else{
      Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID(
            pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno+1
      ));
      if( pNew ){
        bRet = ((pNew->p[4] & 0xFE)==0x00);
        fts5DataRelease(pNew);
      }
    }
#endif
  }
  return bRet;
}

/*
** Advance iterator pIter to the next entry. 
**
** If an error occurs, Fts5Index.rc is set to an appropriate error code. It 
** is not considered an error if the iterator reaches EOF. If an error has 
................................................................................
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      pRes->bTermEq = 1;
      if( p1->iRowid==p2->iRowid ) return i2;



      res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
................................................................................
       || fts5MultiIterAdvanceRowid(p, pIter, iFirst)
      ){
        fts5MultiIterAdvanced(p, pIter, iFirst, 1);
      }
      fts5AssertMultiIterSetup(p, pIter);

      bUseFrom = 0;
    }while( pIter->bSkipEmpty 
         && fts5SegIterIsDelete(p, &pIter->aSeg[pIter->aFirst[1].iFirst])
    );
  }
}

/*
** Allocate a new Fts5MultiSegIter object.
**
** The new object will be used to iterate through data in structure pStruct.
................................................................................
      if( (iEq = fts5MultiIterDoCompare(pNew, iIter)) ){
        fts5SegIterNext(p, &pNew->aSeg[iEq], 0);
        fts5MultiIterAdvanced(p, pNew, iEq, iIter);
      }
    }
    fts5AssertMultiIterSetup(p, pNew);

    if( pNew->bSkipEmpty 
     && fts5SegIterIsDelete(p, &pNew->aSeg[pNew->aFirst[1].iFirst]) 
    ){
      fts5MultiIterNext(p, pNew, 0, 0);
    }
  }else{
    fts5MultiIterFree(p, pNew);
    *ppOut = 0;
  }
}
................................................................................
  assert( iLvl>=0 );
  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
    Fts5ChunkIter sPos;           /* Used to iterate through position list */




    /* If the segment being written is the oldest in the entire index and
    ** the position list is empty (i.e. the entry is a delete marker), no
    ** entry need be written to the output.  */



    fts5ChunkIterInit(p, pSeg, &sPos);
    if( bOldest==0 || sPos.nRem>0 ){
      int nTerm;

      const u8 *pTerm = fts5MultiIterTerm(pIter, &nTerm);
      if( nTerm!=term.n || memcmp(pTerm, term.p, nTerm) ){
        if( pnRem && writer.nLeafWritten>nRem ){
          fts5ChunkIterRelease(&sPos);
          break;
        }

        /* This is a new term. Append a term to the output segment. */
        if( bRequireDoclistTerm ){
          fts5WriteAppendZerobyte(p, &writer);
        }
        fts5WriteAppendTerm(p, &writer, nTerm, pTerm);
        fts5BufferSet(&p->rc, &term, nTerm, pTerm);
        bRequireDoclistTerm = 1;
      }

      /* Append the rowid to the output */
      /* WRITEPOSLISTSIZE */

      fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter), sPos.nRem*2);

      for(/* noop */; !fts5ChunkIterEof(p, &sPos); fts5ChunkIterNext(p, &sPos)){
        fts5WriteAppendPoslistData(p, &writer, sPos.p, sPos.n);
      }
    }

    fts5ChunkIterRelease(&sPos);
  }

  /* Flush the last leaf page to disk. Set the output segment b-tree height
  ** and last leaf page number at the same time.  */
................................................................................
  Fts5StructureSegment *pSeg, 
  Fts5BtreeIter *pIter
){
  int nByte;
  int i;
  nByte = sizeof(pIter->aLvl[0]) * (pSeg->nHeight-1);
  memset(pIter, 0, sizeof(*pIter));




  pIter->nLvl = pSeg->nHeight-1;
  pIter->iIdx = iIdx;
  pIter->p = p;
  pIter->pSeg = pSeg;
  if( nByte && p->rc==SQLITE_OK ){
    pIter->aLvl = (Fts5BtreeIterLevel*)fts5IdxMalloc(p, nByte);
  }
  for(i=0; p->rc==SQLITE_OK && i<pIter->nLvl; i++){
    i64 iRowid = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, i+1, 1);
    Fts5Data *pData;
    pIter->aLvl[i].pData = pData = fts5DataRead(p, iRowid);
    if( pData ){
      fts5NodeIterInit(pData->p, pData->n, &pIter->aLvl[i].s);








|
|
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|
>
>
>







 







|
<
<







 







|
<
<







 







>
>
>

<
<
<
>
>
>

<
<
>
|
|
|
|
|
|

|
|
|
|
|
|
|
|

|
|
>
|

|
|
<







 







>
>
>
>
|
|
|
|
<
<

}

/*
** Return true if the iterator passed as the second argument currently
** points to a delete marker. A delete marker is an entry with a 0 byte
** position-list.
*/
static int fts5MultiIterIsEmpty(Fts5Index *p, Fts5MultiSegIter *pIter){
  Fts5SegIter *pSeg = &pIter->aSeg[pIter->aFirst[1].iFirst];




  return (p->rc==SQLITE_OK && pSeg->pLeaf && pSeg->nPos==0);

















}

/*
** Advance iterator pIter to the next entry. 
**
** If an error occurs, Fts5Index.rc is set to an appropriate error code. It 
** is not considered an error if the iterator reaches EOF. If an error has 
................................................................................
    iRes = i1;
  }else{
    int res = fts5BufferCompare(&p1->term, &p2->term);
    if( res==0 ){
      assert( i2>i1 );
      assert( i2!=0 );
      pRes->bTermEq = 1;
      if( p1->iRowid==p2->iRowid ){
        p1->bDel = p2->bDel;
        return i2;
      }
      res = ((p1->iRowid > p2->iRowid)==pIter->bRev) ? -1 : +1;
    }
    assert( res!=0 );
    if( res<0 ){
      iRes = i1;
    }else{
      iRes = i2;
................................................................................
       || fts5MultiIterAdvanceRowid(p, pIter, iFirst)
      ){
        fts5MultiIterAdvanced(p, pIter, iFirst, 1);
      }
      fts5AssertMultiIterSetup(p, pIter);

      bUseFrom = 0;
    }while( pIter->bSkipEmpty && fts5MultiIterIsEmpty(p, pIter) );


  }
}

/*
** Allocate a new Fts5MultiSegIter object.
**
** The new object will be used to iterate through data in structure pStruct.
................................................................................
      if( (iEq = fts5MultiIterDoCompare(pNew, iIter)) ){
        fts5SegIterNext(p, &pNew->aSeg[iEq], 0);
        fts5MultiIterAdvanced(p, pNew, iEq, iIter);
      }
    }
    fts5AssertMultiIterSetup(p, pNew);

    if( pNew->bSkipEmpty && fts5MultiIterIsEmpty(p, pNew) ){


      fts5MultiIterNext(p, pNew, 0, 0);
    }
  }else{
    fts5MultiIterFree(p, pNew);
    *ppOut = 0;
  }
}
................................................................................
  assert( iLvl>=0 );
  for(fts5MultiIterNew(p, pStruct, iIdx, 0, 0, 0, 0, iLvl, nInput, &pIter);
      fts5MultiIterEof(p, pIter)==0;
      fts5MultiIterNext(p, pIter, 0, 0)
  ){
    Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ];
    Fts5ChunkIter sPos;           /* Used to iterate through position list */
    int nPos;                     /* position-list size field value */
    int nTerm;
    const u8 *pTerm;




    /* Check for key annihilation. */
    if( pSeg->nPos==0 && (bOldest || pSeg->bDel==0) ) continue;

    fts5ChunkIterInit(p, pSeg, &sPos);



    pTerm = fts5MultiIterTerm(pIter, &nTerm);
    if( nTerm!=term.n || memcmp(pTerm, term.p, nTerm) ){
      if( pnRem && writer.nLeafWritten>nRem ){
        fts5ChunkIterRelease(&sPos);
        break;
      }

      /* This is a new term. Append a term to the output segment. */
      if( bRequireDoclistTerm ){
        fts5WriteAppendZerobyte(p, &writer);
      }
      fts5WriteAppendTerm(p, &writer, nTerm, pTerm);
      fts5BufferSet(&p->rc, &term, nTerm, pTerm);
      bRequireDoclistTerm = 1;
    }

    /* Append the rowid to the output */
    /* WRITEPOSLISTSIZE */
    nPos = pSeg->nPos*2 + pSeg->bDel;
    fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter), nPos);

    for(/* noop */; !fts5ChunkIterEof(p, &sPos); fts5ChunkIterNext(p, &sPos)){
      fts5WriteAppendPoslistData(p, &writer, sPos.p, sPos.n);

    }

    fts5ChunkIterRelease(&sPos);
  }

  /* Flush the last leaf page to disk. Set the output segment b-tree height
  ** and last leaf page number at the same time.  */
................................................................................
  Fts5StructureSegment *pSeg, 
  Fts5BtreeIter *pIter
){
  int nByte;
  int i;
  nByte = sizeof(pIter->aLvl[0]) * (pSeg->nHeight-1);
  memset(pIter, 0, sizeof(*pIter));
  if( nByte ){
    pIter->aLvl = (Fts5BtreeIterLevel*)fts5IdxMalloc(p, nByte);
  }
  if( p->rc==SQLITE_OK ){
    pIter->nLvl = pSeg->nHeight-1;
    pIter->iIdx = iIdx;
    pIter->p = p;
    pIter->pSeg = pSeg;


  }
  for(i=0; p->rc==SQLITE_OK && i<pIter->nLvl; i++){
    i64 iRowid = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, i+1, 1);
    Fts5Data *pData;
    pIter->aLvl[i].pData = pData = fts5DataRead(p, iRowid);
    if( pData ){
      fts5NodeIterInit(pData->p, pData->n, &pIter->aLvl[i].s);

Changes to ext/fts5/test/fts5corrupt.test.

  CREATE VIRTUAL TABLE t2 USING fts5(x);
  INSERT INTO t2(t2, rank) VALUES('pgsz', 64);
}
db func rnddoc fts5_rnddoc
do_test 2.1 {
  for {set i 0} {$i < 500} {incr i} {
    execsql { INSERT INTO t2 VALUES(rnddoc(50)) }
    execsql { INSERT INTO t2(t2) VALUES('integrity-check') }
  }

} {}

#--------------------------------------------------------------------
#

finish_test








<

>

  CREATE VIRTUAL TABLE t2 USING fts5(x);
  INSERT INTO t2(t2, rank) VALUES('pgsz', 64);
}
db func rnddoc fts5_rnddoc
do_test 2.1 {
  for {set i 0} {$i < 500} {incr i} {
    execsql { INSERT INTO t2 VALUES(rnddoc(50)) }

  }
  execsql { INSERT INTO t2(t2) VALUES('integrity-check') }
} {}

#--------------------------------------------------------------------
#

finish_test