/ Check-in [0778825d]
Login

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

Overview
Comment:Rework the Fts5MultiSegIter structure a bit to make it more efficient.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 0778825d0ec9315c70659fae8d0640b209049dd8
User & Date: dan 2015-07-03 20:47:18
Context
2015-07-03
21:38
Add static mutexes for use by the built-in / third-party VFSs and use the built-in VFS mutex where appropriate. check-in: b202e2a1 user: mistachkin tags: trunk
20:47
Rework the Fts5MultiSegIter structure a bit to make it more efficient. check-in: 0778825d user: dan tags: trunk
19:13
Speed up eof checks on fts5 cursors. check-in: 3df4af5d user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
...
514
515
516
517
518
519
520










521
522
523
524
525
526
527
....
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
....
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537

typedef struct Fts5CResult Fts5CResult;
struct Fts5CResult {
  u16 iFirst;                     /* aSeg[] index of firstest iterator */
  u8 bTermEq;                     /* True if the terms are equal */
};

struct Fts5MultiSegIter {
  int nSeg;                       /* Size of aSeg[] array */
  int bRev;                       /* True to iterate in reverse order */
  int bSkipEmpty;                 /* True to skip deleted entries */
  int bEof;                       /* True at EOF */
  Fts5SegIter *aSeg;              /* Array of segment iterators */
  Fts5CResult *aFirst;            /* Current merge state (see above) */
};

/*
** Object for iterating through a single segment, visiting each term/docid
** pair in the segment.
**
** pSeg:
**   The segment to iterate through.
**
................................................................................
  int nPos;                       /* Number of bytes in current position list */
  int bDel;                       /* True if the delete flag is set */
};

#define FTS5_SEGITER_ONETERM 0x01
#define FTS5_SEGITER_REVERSE 0x02












/*
** Object for iterating through the conents of a single internal node in 
** memory.
*/
struct Fts5NodeIter {
  /* Internal. Set and managed by fts5NodeIterXXX() functions. Except, 
................................................................................
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged                    /* Index of sub-iterator just advanced */
){
  int i;
  Fts5SegIter *pNew = &pIter->aSeg[iChanged];
  Fts5SegIter *pOther = &pIter->aSeg[iChanged ^ 0x0001];

  for(i=(pIter->nSeg+iChanged)/2; p->rc==SQLITE_OK; i=i/2){
    Fts5CResult *pRes = &pIter->aFirst[i];

    assert( pNew->pLeaf );
    assert( pRes->bTermEq==0 || pOther->pLeaf );
    
    if( pRes->bTermEq ){
      if( pNew->iRowid==pOther->iRowid ){
................................................................................
){
  Fts5MultiSegIter *pNew;
  int nSlot;                      /* Power of two >= nSeg */

  for(nSlot=2; nSlot<nSeg; nSlot=nSlot*2);
  pNew = fts5IdxMalloc(p, 
      sizeof(Fts5MultiSegIter) +          /* pNew */
      sizeof(Fts5SegIter) * nSlot +       /* pNew->aSeg[] */
      sizeof(Fts5CResult) * nSlot         /* pNew->aFirst[] */
  );
  if( pNew ){
    pNew->nSeg = nSlot;
    pNew->aSeg = (Fts5SegIter*)&pNew[1];
    pNew->aFirst = (Fts5CResult*)&pNew->aSeg[nSlot];
  }
  return pNew;
}

/*
** Allocate a new Fts5MultiSegIter object.







<
<
<
<
<
<
<
<
<







 







>
>
>
>
>
>
>
>
>
>







 







|







 







|




<







432
433
434
435
436
437
438









439
440
441
442
443
444
445
...
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
....
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
....
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530

2531
2532
2533
2534
2535
2536
2537

typedef struct Fts5CResult Fts5CResult;
struct Fts5CResult {
  u16 iFirst;                     /* aSeg[] index of firstest iterator */
  u8 bTermEq;                     /* True if the terms are equal */
};










/*
** Object for iterating through a single segment, visiting each term/docid
** pair in the segment.
**
** pSeg:
**   The segment to iterate through.
**
................................................................................
  int nPos;                       /* Number of bytes in current position list */
  int bDel;                       /* True if the delete flag is set */
};

#define FTS5_SEGITER_ONETERM 0x01
#define FTS5_SEGITER_REVERSE 0x02


struct Fts5MultiSegIter {
  int nSeg;                       /* Size of aSeg[] array */
  int bRev;                       /* True to iterate in reverse order */
  int bSkipEmpty;                 /* True to skip deleted entries */
  int bEof;                       /* True at EOF */
  Fts5CResult *aFirst;            /* Current merge state (see above) */
  Fts5SegIter aSeg[1];            /* Array of segment iterators */
};


/*
** Object for iterating through the conents of a single internal node in 
** memory.
*/
struct Fts5NodeIter {
  /* Internal. Set and managed by fts5NodeIterXXX() functions. Except, 
................................................................................
  Fts5MultiSegIter *pIter,        /* Iterator to update aFirst[] array for */
  int iChanged                    /* Index of sub-iterator just advanced */
){
  int i;
  Fts5SegIter *pNew = &pIter->aSeg[iChanged];
  Fts5SegIter *pOther = &pIter->aSeg[iChanged ^ 0x0001];

  for(i=(pIter->nSeg+iChanged)/2; 1; i=i/2){
    Fts5CResult *pRes = &pIter->aFirst[i];

    assert( pNew->pLeaf );
    assert( pRes->bTermEq==0 || pOther->pLeaf );
    
    if( pRes->bTermEq ){
      if( pNew->iRowid==pOther->iRowid ){
................................................................................
){
  Fts5MultiSegIter *pNew;
  int nSlot;                      /* Power of two >= nSeg */

  for(nSlot=2; nSlot<nSeg; nSlot=nSlot*2);
  pNew = fts5IdxMalloc(p, 
      sizeof(Fts5MultiSegIter) +          /* pNew */
      sizeof(Fts5SegIter) * (nSlot-1) +   /* pNew->aSeg[] */
      sizeof(Fts5CResult) * nSlot         /* pNew->aFirst[] */
  );
  if( pNew ){
    pNew->nSeg = nSlot;

    pNew->aFirst = (Fts5CResult*)&pNew->aSeg[nSlot];
  }
  return pNew;
}

/*
** Allocate a new Fts5MultiSegIter object.