/ Check-in [8682b87e]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Add support for AND, OR and NOT to fts5.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: 8682b87e794767cefcaa080fd53c8973c24c556a
User & Date: dan 2014-07-05 15:15:41
Context
2014-07-08
16:27
Add support for prefix queries to fts5. check-in: 75ebd3cd user: dan tags: fts5
2014-07-05
15:15
Add support for AND, OR and NOT to fts5. check-in: 8682b87e user: dan tags: fts5
07:54
Add support for the "colname : <nearset>" syntax to fts5. check-in: 00466710 user: dan tags: fts5
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_expr.c.

313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
...
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
...
646
647
648
649
650
651
652

653
654














655
656





657






























658
















659

660









































661
662
663








664
665
666
667
668
669
670
...
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
void sqlite3Fts5ExprFree(Fts5Expr *p){
  if( p ){
    sqlite3Fts5ParseNodeFree(p->pRoot);
    sqlite3_free(p);
  }
}

/*
**
*/
static int fts5ExprNodeTest(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  assert( 0 );
  return SQLITE_OK;
}

/*
** All individual term iterators in pPhrase are guaranteed to be valid and
** pointing to the same rowid when this function is called. This function 
** checks if the current rowid really is a match, and if so populates
** the pPhrase->poslist buffer accordingly. Output parameter *pbMatch
** is set to true if this is really a match, or false otherwise.
**
................................................................................
 ismatch_out:
  *pbMatch = bMatch;
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

/*
** Advance each phrase iterator in phrase pNear. If any reach EOF, set
** output variable *pbEof to true before returning.
*/
static int fts5ExprNearAdvanceAll(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNearset *pNear,         /* Near object to advance iterators of */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int rc = SQLITE_OK;             /* Return code */
................................................................................
      }
    }
  }

  return SQLITE_OK;
}


static int fts5ExprNearNext(
  Fts5Expr *pExpr,                /* Expression that pNear is a part of */














  Fts5ExprNode *pNode
){





  int rc = fts5ExprNearAdvanceAll(pExpr, pNode->pNear, &pNode->bEof);






























  if( rc==SQLITE_OK && pNode->bEof==0 ){
















    rc = fts5ExprNearNextMatch(pExpr, pNode);

  }









































  return rc;
}
 








static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  pNode->bEof = 0;

  if( pNode->eType==FTS5_STRING ){

    /* Initialize all term iterators in the NEAR object. */
................................................................................

  }else{
    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
    }
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeTest(pExpr, pNode);
    }
  }
  return rc;
}

static int fts5ExprNodeNext(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;

  if( pNode->eType==FTS5_STRING ){
    rc = fts5ExprNearNext(pExpr, pNode);
  }else{
    assert( 0 );
  }
  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by







<
<
<
<
<
<
<
<







 







|
|







 







>
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
<
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


|
>
>
>
>
>
>
>
>







 







|


<
<
<
<
<
<
<
<
<
<
<







313
314
315
316
317
318
319








320
321
322
323
324
325
326
...
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
...
638
639
640
641
642
643
644
645
646

647
648
649
650
651
652
653
654
655
656
657
658
659
660
661

662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
...
783
784
785
786
787
788
789
790
791
792











793
794
795
796
797
798
799
void sqlite3Fts5ExprFree(Fts5Expr *p){
  if( p ){
    sqlite3Fts5ParseNodeFree(p->pRoot);
    sqlite3_free(p);
  }
}









/*
** All individual term iterators in pPhrase are guaranteed to be valid and
** pointing to the same rowid when this function is called. This function 
** checks if the current rowid really is a match, and if so populates
** the pPhrase->poslist buffer accordingly. Output parameter *pbMatch
** is set to true if this is really a match, or false otherwise.
**
................................................................................
 ismatch_out:
  *pbMatch = bMatch;
  if( aIter!=aStatic ) sqlite3_free(aIter);
  return rc;
}

/*
** Advance each term iterator in each phrase in pNear. If any reach EOF, 
** set output variable *pbEof to true before returning.
*/
static int fts5ExprNearAdvanceAll(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNearset *pNear,         /* Near object to advance iterators of */
  int *pbEof                      /* OUT: Set to true if phrase at EOF */
){
  int rc = SQLITE_OK;             /* Return code */
................................................................................
      }
    }
  }

  return SQLITE_OK;
}

/* fts3ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */
static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*);


/*
** Nodes at EOF are considered larger than all other nodes. A node that
** points to a *smaller* rowid is considered larger.
** 
**    res = (*p1) - (*p2)
*/
static int fts5NodeCompare(Fts5ExprNode *p1, Fts5ExprNode *p2){
  if( p2->bEof ) return -1;
  if( p1->bEof ) return +1;
  if( p1->iRowid>p2->iRowid ) return -1;
  return (p1->iRowid < p2->iRowid);
}

static int fts5ExprNodeNext(Fts5Expr *pExpr, Fts5ExprNode *pNode){

  int rc = SQLITE_OK;

  if( pNode->bEof==0 ){
    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceAll(pExpr, pNode->pNear, &pNode->bEof);
        break;
      };

      case FTS5_AND: {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft);
        if( rc==SQLITE_OK ) rc = fts5ExprNodeNext(pExpr, pNode->pRight);
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        int cmp = fts5NodeCompare(p1, p2);

        if( cmp==0 ){
          rc = fts5ExprNodeNext(pExpr, p1);
          if( rc==SQLITE_OK ) rc = fts5ExprNodeNext(pExpr, p2);
        }else{
          rc = fts5ExprNodeNext(pExpr, (cmp < 0) ? p1 : p2);
        }

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        rc = fts5ExprNodeNext(pExpr, pNode->pLeft);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }

  return rc;
}

/*
**
*/
static int fts5ExprNodeNextMatch(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  if( pNode->bEof==0 ){
    switch( pNode->eType ){

      case FTS5_STRING: {
        rc = fts5ExprNearNextMatch(pExpr, pNode);
        break;
      }

      case FTS5_AND: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;

        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv = (p1->iRowid > p2->iRowid) ? p1 : p2;
          rc = fts5ExprNodeNext(pExpr, pAdv);
          if( rc!=SQLITE_OK ) break;
        }
        pNode->bEof = p1->bEof || p2->bEof;
        pNode->iRowid = p1->iRowid;
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        Fts5ExprNode *pNext = (fts5NodeCompare(p1, p2) > 0 ? p2 : p1);
        pNode->bEof = pNext->bEof;
        pNode->iRowid = pNext->iRowid;
        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        while( rc==SQLITE_OK ){
          int cmp;
          while( rc==SQLITE_OK && (cmp = fts5NodeCompare(p1, p2))>0 ){
            rc = fts5ExprNodeNext(pExpr, p2);
          }
          if( rc || cmp ) break;
          rc = fts5ExprNodeNext(pExpr, p1);
        }
        pNode->bEof = p1->bEof;
        pNode->iRowid = p1->iRowid;
        break;
      }
    }
  }
  return rc;
}

 
/*
** Set node pNode, which is part of expression pExpr, to point to the first
** match. If there are no matches, set the Node.bEof flag to indicate EOF.
**
** Return an SQLite error code if an error occurs, or SQLITE_OK otherwise.
** It is not an error if there are no matches.
*/
static int fts5ExprNodeFirst(Fts5Expr *pExpr, Fts5ExprNode *pNode){
  int rc = SQLITE_OK;
  pNode->bEof = 0;

  if( pNode->eType==FTS5_STRING ){

    /* Initialize all term iterators in the NEAR object. */
................................................................................

  }else{
    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
    }
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }











  return rc;
}



/*
** Begin iterating through the set of documents in index pIdx matched by

Changes to test/fts5ac.test.

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219



220
221
222
223
224
225
226
...
268
269
270
271
272
273
274









275
276
277
278
279
280
281
282
283
284
285
286
      break
    }
  }

  return $bMatch
}

proc matchdata {expr} {
  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]
  foreach {id x y} $::data {
    set cols [list $x $y]
    if $tclexpr {
      set res [concat $id $res]
    }
  }



  return $res
}

foreach {tn phrase} {
  1 "o"
  2 "b q"
  3 "e a e"
................................................................................
  5 { NEAR(r c, 0) }
  6 { NEAR(a b c) }
  7 { NEAR(a b c, 8) }
  8  { x : NEAR(r c) }
  9  { y : NEAR(r c) }
  10 { x : "r c" }
  11 { y : "r c" }









} {

  set res [matchdata $expr]
  do_execsql_test 2.$tn.[llength $res] { 
    SELECT rowid FROM xx WHERE xx match $expr
  } $res
}



finish_test








|








>
>
>







 







>
>
>
>
>
>
>
>
>

<

|








204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
...
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

288
289
290
291
292
293
294
295
296
297
      break
    }
  }

  return $bMatch
}

proc matchdata {expr {print 0}} {
  set tclexpr [db one {SELECT fts5_expr_tcl($expr, 'nearset $cols', 'x', 'y')}]
  set res [list]
  foreach {id x y} $::data {
    set cols [list $x $y]
    if $tclexpr {
      set res [concat $id $res]
    }
  }
  if {$print} {
    puts $tclexpr
  }
  return $res
}

foreach {tn phrase} {
  1 "o"
  2 "b q"
  3 "e a e"
................................................................................
  5 { NEAR(r c, 0) }
  6 { NEAR(a b c) }
  7 { NEAR(a b c, 8) }
  8  { x : NEAR(r c) }
  9  { y : NEAR(r c) }
  10 { x : "r c" }
  11 { y : "r c" }
  12 { a AND b }
  13 { a AND b AND c }
  14a { a }
  14b { a OR b }
  15 { a OR b AND c }
  16 { c AND b OR a }
  17 { c AND (b OR a) }
  18 { c NOT (b OR a) }
  19 { c NOT b OR a AND d }
} {

  set res [matchdata $expr]
  do_execsql_test 4.$tn.[llength $res] { 
    SELECT rowid FROM xx WHERE xx match $expr
  } $res
}



finish_test