ft_boolean_search.c 19.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* Written by Sergei A. Golubchik, who has a shared copyright to this code */

19 20
/*  TODO: add caching - pre-read several index entries at once */

unknown's avatar
unknown committed
21
#define FT_CORE
22 23 24 25
#include "ftdefs.h"

/* search with boolean queries */

26 27
static double _wghts[11]=
{
28 29 30 31 32 33 34 35 36 37 38
  0.131687242798354,
  0.197530864197531,
  0.296296296296296,
  0.444444444444444,
  0.666666666666667,
  1.000000000000000,
  1.500000000000000,
  2.250000000000000,
  3.375000000000000,
  5.062500000000000,
  7.593750000000000};
unknown's avatar
unknown committed
39
static double *wghts=_wghts+5; /* wghts[i] = 1.5**i */
40

41 42
static double _nwghts[11]=
{
43 44 45 46 47 48 49 50 51 52 53
 -0.065843621399177,
 -0.098765432098766,
 -0.148148148148148,
 -0.222222222222222,
 -0.333333333333334,
 -0.500000000000000,
 -0.750000000000000,
 -1.125000000000000,
 -1.687500000000000,
 -2.531250000000000,
 -3.796875000000000};
unknown's avatar
unknown committed
54
static double *nwghts=_nwghts+5; /* nwghts[i] = -0.5*1.5**i */
55

56
#define FTB_FLAG_TRUNC 1                  /* MUST be 1                  */
unknown's avatar
unknown committed
57 58 59
#define FTB_FLAG_YES   2                  /*  no two from these three   */
#define FTB_FLAG_NO    4                  /*   YES, NO, WONLY           */
#define FTB_FLAG_WONLY 8                  /*  should be ever set both   */
60

61
typedef struct st_ftb_expr FTB_EXPR;
62 63
struct st_ftb_expr
{
64
  FTB_EXPR *up;
unknown's avatar
unknown committed
65
  uint      flags;
unknown's avatar
unknown committed
66
/* ^^^^^^^^^^^^^^^^^^ FTB_{EXPR,WORD} common section */
unknown's avatar
unknown committed
67
  my_off_t  docid[2];
68
  float     weight;
69
  float     cur_weight;
unknown's avatar
unknown committed
70
  byte     *quot, *qend;
71 72 73 74
  uint      yesses;               /* number of "yes" words matched */
  uint      nos;                  /* number of "no"  words matched */
  uint      ythresh;              /* number of "yes" words in expr */
  uint      yweaks;               /* number of "yes" words for scan only */
75 76
};

77 78
typedef struct st_ftb_word
{
79
  FTB_EXPR  *up;
unknown's avatar
unknown committed
80
  uint       flags;
unknown's avatar
unknown committed
81
/* ^^^^^^^^^^^^^^^^^^ FTB_{EXPR,WORD} common section */
unknown's avatar
unknown committed
82
  my_off_t   docid[2];             /* for index search and for scan */
83
  my_off_t   key_root;
unknown's avatar
unknown committed
84
  MI_KEYDEF *keyinfo;
85 86 87 88 89
  float      weight;
  uint       ndepth;
  uint       len;
  uchar      off;
  byte       word[1];
90 91
} FTB_WORD;

92 93
typedef struct st_ft_info
{
unknown's avatar
unknown committed
94
  struct _ft_vft *please;
95
  MI_INFO   *info;
96
  CHARSET_INFO *charset;
97
  FTB_EXPR  *root;
98
  FTB_WORD **list;
99
  MEM_ROOT   mem_root;
100 101 102 103 104 105
  QUEUE      queue;
  TREE       no_dupes;
  my_off_t   lastpos;
  uint       keynr;
  uchar      with_scan;
  enum { UNINITIALIZED, READY, INDEX_SEARCH, INDEX_DONE } state;
106 107
} FTB;

108
static int FTB_WORD_cmp(my_off_t *v, FTB_WORD *a, FTB_WORD *b)
109
{
110 111 112 113 114 115
  int i;

  /* if a==curdoc, take it as  a < b */
  if (v && a->docid[0] == *v)
    return -1;

116
  /* ORDER BY docid, ndepth DESC */
117
  i=CMP_NUM(a->docid[0], b->docid[0]);
118
  if (!i)
119
    i=CMP_NUM(b->ndepth,a->ndepth);
120 121 122
  return i;
}

123
static int FTB_WORD_cmp_list(CHARSET_INFO *cs, FTB_WORD **a, FTB_WORD **b)
124 125
{
  /* ORDER BY word DESC, ndepth DESC */
unknown's avatar
unknown committed
126
  int i= mi_compare_text(cs, (uchar*) (*b)->word+1,(*b)->len-1,
127
                             (uchar*) (*a)->word+1,(*a)->len-1,0,0);
128
  if (!i)
129
    i=CMP_NUM((*b)->ndepth,(*a)->ndepth);
unknown's avatar
unknown committed
130
  return i;
131
}
132

133
static void _ftb_parse_query(FTB *ftb, byte **start, byte *end,
unknown's avatar
unknown committed
134
                      FTB_EXPR *up, uint depth)
135 136 137 138 139 140
{
  byte        res;
  FTB_PARAM   param;
  FT_WORD     w;
  FTB_WORD   *ftbw;
  FTB_EXPR   *ftbe;
141
  uint  extra=HA_FT_WLEN+ftb->info->s->rec_reflength; /* just a shortcut */
142

143
  if (ftb->state != UNINITIALIZED)
144 145
    return;

unknown's avatar
unknown committed
146
  param.prev=' ';
unknown's avatar
unknown committed
147
  param.quot=up->quot;
148
  while ((res=ft_get_word(ftb->charset,start,end,&w,&param)))
149
  {
unknown's avatar
unknown committed
150
    int   r=param.plusminus;
unknown's avatar
unknown committed
151
    float weight= (float) (param.pmsign ? nwghts : wghts)[(r>5)?5:((r<-5)?-5:r)];
152
    switch (res) {
unknown's avatar
unknown committed
153
      case 1: /* word found */
unknown's avatar
unknown committed
154
        ftbw=(FTB_WORD *)alloc_root(&ftb->mem_root,
unknown's avatar
unknown committed
155 156 157
                                    sizeof(FTB_WORD) +
                                    (param.trunc ? MI_MAX_KEY_BUFF :
                                     w.len+extra));
158
        ftbw->len=w.len+1;
159 160 161 162
        ftbw->flags=0;
        if (param.yesno>0) ftbw->flags|=FTB_FLAG_YES;
        if (param.yesno<0) ftbw->flags|=FTB_FLAG_NO;
        if (param.trunc)   ftbw->flags|=FTB_FLAG_TRUNC;
unknown's avatar
unknown committed
163 164
        ftbw->weight=weight;
        ftbw->up=up;
165
        ftbw->docid[0]=ftbw->docid[1]=HA_POS_ERROR;
166
        ftbw->ndepth= (param.yesno<0) + depth;
167
        ftbw->key_root=HA_POS_ERROR;
168 169
        memcpy(ftbw->word+1, w.pos, w.len);
        ftbw->word[0]=w.len;
170
        if (param.yesno > 0) up->ythresh++;
171
        queue_insert(& ftb->queue, (byte *)ftbw);
unknown's avatar
unknown committed
172
        ftb->with_scan|=(param.trunc & FTB_FLAG_TRUNC);
173
        break;
unknown's avatar
unknown committed
174 175
      case 2: /* left bracket */
        ftbe=(FTB_EXPR *)alloc_root(&ftb->mem_root, sizeof(FTB_EXPR));
176 177 178
        ftbe->flags=0;
        if (param.yesno>0) ftbe->flags|=FTB_FLAG_YES;
        if (param.yesno<0) ftbe->flags|=FTB_FLAG_NO;
unknown's avatar
unknown committed
179 180
        ftbe->weight=weight;
        ftbe->up=up;
181 182
        ftbe->ythresh=ftbe->yweaks=0;
        ftbe->docid[0]=ftbe->docid[1]=HA_POS_ERROR;
unknown's avatar
unknown committed
183
        if ((ftbe->quot=param.quot)) ftb->with_scan|=2;
184
        if (param.yesno > 0) up->ythresh++;
185
        _ftb_parse_query(ftb, start, end, ftbe, depth+1);
unknown's avatar
unknown committed
186
        param.quot=0;
unknown's avatar
unknown committed
187 188
        break;
      case 3: /* right bracket */
unknown's avatar
unknown committed
189
        if (up->quot) up->qend=param.quot;
unknown's avatar
unknown committed
190
        return;
191 192
    }
  }
193
  return;
194 195
}

196
static int _ftb_no_dupes_cmp(void* not_used __attribute__((unused)),
unknown's avatar
unknown committed
197
                             const void *a,const void *b)
unknown's avatar
unknown committed
198 199 200 201
{
  return CMP_NUM((*((my_off_t*)a)), (*((my_off_t*)b)));
}

202 203 204 205 206 207
/* returns 1 if the search was finished (must-word wasn't found) */
static int _ft2_search(FTB *ftb, FTB_WORD *ftbw, my_bool init_search)
{
  int r;
  uint off;
  int subkeys;
208
  my_bool can_go_down;
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
  MI_INFO *info=ftb->info;

  if (init_search)
  {
    ftbw->key_root=info->s->state.key_root[ftb->keynr];
    ftbw->keyinfo=info->s->keyinfo+ftb->keynr;
    ftbw->off=0;

    r=_mi_search(info, ftbw->keyinfo, (uchar*) ftbw->word, ftbw->len,
                 SEARCH_FIND | SEARCH_BIGGER, ftbw->key_root);
  }
  else
  {
    r=_mi_search(info, ftbw->keyinfo, (uchar*) ftbw->word+ftbw->off,
                   USE_WHOLE_KEY, SEARCH_BIGGER, ftbw->key_root);
  }
unknown's avatar
unknown committed
225

226
  can_go_down=(!ftbw->off && (init_search || (ftbw->flags & FTB_FLAG_TRUNC)));
unknown's avatar
unknown committed
227
  /* Skip rows inserted by concurrent insert */
228 229 230 231 232 233 234 235 236 237
  while (!r)
  {
    if (can_go_down)
    {
      /* going down ? */
      off=info->lastkey_length-HA_FT_WLEN-info->s->base.rec_reflength;
      subkeys=ft_sintXkorr(info->lastkey+off);
    }
    if (subkeys<0 || info->lastpos < info->state->data_file_length)
      break;
unknown's avatar
unknown committed
238 239 240
    r= _mi_search_next(info, ftbw->keyinfo, info->lastkey,
                       info->lastkey_length,
		       SEARCH_BIGGER, ftbw->key_root);
241
  }
unknown's avatar
unknown committed
242

243 244 245 246 247 248 249
  if (!r && !ftbw->off)
  {
    r= mi_compare_text(ftb->charset,
                       info->lastkey + (ftbw->flags & FTB_FLAG_TRUNC),
                       ftbw->len     - (ftbw->flags & FTB_FLAG_TRUNC),
              (uchar*) ftbw->word    + (ftbw->flags & FTB_FLAG_TRUNC),
                       ftbw->len     - (ftbw->flags & FTB_FLAG_TRUNC),
250
                       0,0);
251 252 253 254 255 256 257 258 259 260
  }

  if (r) /* not found */
  {
    if (!ftbw->off || !(ftbw->flags & FTB_FLAG_TRUNC))
    {
      ftbw->docid[0]=HA_POS_ERROR;
      if ((ftbw->flags & FTB_FLAG_YES) && ftbw->up->up==0)
      {
        /*
unknown's avatar
unknown committed
261 262 263
          This word MUST BE present in every document returned,
          so we can stop the search right now
        */
264 265 266 267 268 269 270 271
        ftb->state=INDEX_DONE;
        return 1; /* search is done */
      }
      else
        return 0;
    }

    /* going up to the first-level tree to continue search there */
unknown's avatar
unknown committed
272
    _mi_dpointer(info, (uchar*) (ftbw->word+ftbw->off+HA_FT_WLEN),
unknown's avatar
unknown committed
273
                 ftbw->key_root);
274 275 276 277 278 279 280 281 282 283 284 285 286
    ftbw->key_root=info->s->state.key_root[ftb->keynr];
    ftbw->keyinfo=info->s->keyinfo+ftb->keynr;
    ftbw->off=0;
    return _ft2_search(ftb, ftbw, 0);
  }

  /* matching key found */
  memcpy(ftbw->word+ftbw->off, info->lastkey, info->lastkey_length);
  if (!ftbw->off && (init_search || (ftbw->flags & FTB_FLAG_TRUNC)))
  {
    /* going down ? */
    if (subkeys<0)
    {
unknown's avatar
unknown committed
287 288 289 290
      /*
	yep, going down, to the second-level tree
	TODO here: subkey-based optimization
      */
291 292 293 294 295 296 297 298 299 300 301 302
      ftbw->off=off;
      ftbw->key_root=info->lastpos;
      ftbw->keyinfo=& info->s->ft2_keyinfo;
      r=_mi_search_first(info, ftbw->keyinfo, ftbw->key_root);
      DBUG_ASSERT(r==0);  /* found something */
      memcpy(ftbw->word+off, info->lastkey, info->lastkey_length);
    }
  }
  ftbw->docid[0]=info->lastpos;
  return 0;
}

303
static void _ftb_init_index_search(FT_INFO *ftb)
304
{
305
  int i;
306
  FTB_WORD   *ftbw;
307

308 309
  if ((ftb->state != READY && ftb->state !=INDEX_DONE) ||
      ftb->keynr == NO_SUCH_KEY)
310 311 312 313 314 315 316
    return;
  ftb->state=INDEX_SEARCH;

  for (i=ftb->queue.elements; i; i--)
  {
    ftbw=(FTB_WORD *)(ftb->queue.root[i]);

317 318 319
    if (ftbw->flags & FTB_FLAG_TRUNC)
    {
      /*
unknown's avatar
unknown committed
320
        special treatment for truncation operator
unknown's avatar
unknown committed
321
        1. there are some (besides this) +words
unknown's avatar
unknown committed
322 323
           | no need to search in the index, it can never ADD new rows
           | to the result, and to remove half-matched rows we do scan anyway
324
        2. -trunc*
unknown's avatar
unknown committed
325
           | same as 1.
unknown's avatar
unknown committed
326 327 328
        3. in 1 and 2, +/- need not be on the same expr. level,
           but can be on any upper level, as in +word +(trunc1* trunc2*)
        4. otherwise
unknown's avatar
unknown committed
329 330 331 332 333 334
           | We have to index-search for this prefix.
           | It may cause duplicates, as in the index (sorted by <word,docid>)
           |   <aaaa,row1>
           |   <aabb,row2>
           |   <aacc,row1>
           | Searching for "aa*" will find row1 twice...
335
      */
unknown's avatar
unknown committed
336 337 338 339
      FTB_EXPR *ftbe;
      for (ftbe=(FTB_EXPR*)ftbw;
           ftbe->up && !(ftbe->up->flags & FTB_FLAG_TRUNC);
           ftbe->up->flags|= FTB_FLAG_TRUNC, ftbe=ftbe->up)
unknown's avatar
unknown committed
340
      {
unknown's avatar
unknown committed
341 342 343 344 345 346 347 348 349 350 351
        if (ftbe->flags & FTB_FLAG_NO ||                     /* 2 */
             ftbe->up->ythresh - ftbe->up->yweaks >1)        /* 1 */
        {
          FTB_EXPR *top_ftbe=ftbe->up->up;
          ftbw->docid[0]=HA_POS_ERROR;
          for (ftbe=ftbw->up; ftbe != top_ftbe; ftbe=ftbe->up)
            if (ftbe->flags & FTB_FLAG_YES)
              ftbe->yweaks++;
          ftbe=0;
          break;
        }
unknown's avatar
unknown committed
352
      }
unknown's avatar
unknown committed
353 354 355 356 357 358 359 360
      if (!ftbe)
        continue;
      /* 3 */
      if (!is_tree_inited(& ftb->no_dupes))
        init_tree(& ftb->no_dupes,0,0,sizeof(my_off_t),
            _ftb_no_dupes_cmp,0,0,0);
      else
        reset_tree(& ftb->no_dupes);
361
    }
362 363 364

    if (_ft2_search(ftb, ftbw, 1))
      return;
365 366 367 368
  }
  queue_fix(& ftb->queue);
}

369

unknown's avatar
unknown committed
370
FT_INFO * ft_init_boolean_search(MI_INFO *info, uint keynr, byte *query,
unknown's avatar
unknown committed
371
                                 uint query_len)
372
{
373 374 375
  FTB       *ftb;
  FTB_EXPR  *ftbe;
  uint       res;
376

377 378
  if (!(ftb=(FTB *)my_malloc(sizeof(FTB), MYF(MY_WME))))
    return 0;
379
  ftb->please= (struct _ft_vft *) & _ft_vft_boolean;
380
  ftb->state=UNINITIALIZED;
381 382
  ftb->info=info;
  ftb->keynr=keynr;
383
  ftb->charset= ((keynr==NO_SUCH_KEY) ?
384
           default_charset_info : info->s->keyinfo[keynr].seg->charset);
385
  ftb->with_scan=0;
386
  ftb->lastpos=HA_POS_ERROR;
unknown's avatar
unknown committed
387
  bzero(& ftb->no_dupes, sizeof(TREE));
388

unknown's avatar
unknown committed
389
  init_alloc_root(&ftb->mem_root, 1024, 1024);
390

391 392 393 394
  /*
    Hack: instead of init_queue, we'll use reinit queue to be able
    to alloc queue with alloc_root()
  */
395
  res=ftb->queue.max_elements=1+query_len/(min(ft_min_word_len,2)+1);
unknown's avatar
unknown committed
396 397 398
  if (!(ftb->queue.root=
        (byte **)alloc_root(&ftb->mem_root, (res+1)*sizeof(void*))))
    goto err;
399
  reinit_queue(& ftb->queue, res, 0, 0,
400
                         (int (*)(void*,byte*,byte*))FTB_WORD_cmp, 0);
unknown's avatar
unknown committed
401 402
  if (!(ftbe=(FTB_EXPR *)alloc_root(&ftb->mem_root, sizeof(FTB_EXPR))))
    goto err;
unknown's avatar
unknown committed
403
  ftbe->weight=1;
404 405
  ftbe->flags=FTB_FLAG_YES;
  ftbe->nos=1;
unknown's avatar
unknown committed
406 407
  ftbe->quot=0;
  ftbe->up=0;
408 409
  ftbe->ythresh=ftbe->yweaks=0;
  ftbe->docid[0]=ftbe->docid[1]=HA_POS_ERROR;
410
  ftb->root=ftbe;
411
  _ftb_parse_query(ftb, &query, query+query_len, ftbe, 0);
412 413
  ftb->list=(FTB_WORD **)alloc_root(&ftb->mem_root,
                                     sizeof(FTB_WORD *)*ftb->queue.elements);
unknown's avatar
unknown committed
414
  memcpy(ftb->list, ftb->queue.root+1, sizeof(FTB_WORD *)*ftb->queue.elements);
415
  qsort2(ftb->list, ftb->queue.elements, sizeof(FTB_WORD *),
416
                              (qsort2_cmp)FTB_WORD_cmp_list, ftb->charset);
unknown's avatar
unknown committed
417
  if (ftb->queue.elements<2) ftb->with_scan &= ~FTB_FLAG_TRUNC;
418
  ftb->state=READY;
419
  return ftb;
unknown's avatar
unknown committed
420 421 422 423
err:
  free_root(& ftb->mem_root, MYF(0));
  my_free((gptr)ftb,MYF(0));
  return 0;
424
}
425

426

427
/* returns 1 if str0 ~= /\<str1\>/ */
428
static int _ftb_strstr(const byte *s0, const byte *e0,
unknown's avatar
unknown committed
429 430
                const byte *s1, const byte *e1,
                CHARSET_INFO *cs)
431
{
432 433
  const byte *p0, *p1;
  my_bool s_after, e_before;
unknown's avatar
unknown committed
434

435 436 437 438 439
  s_after=true_word_char(cs, s1[0]);
  e_before=true_word_char(cs, e1[-1]);
  p0=s0;

  while (p0 < e0)
unknown's avatar
unknown committed
440
  {
441
    while (p0 < e0 && cs->to_upper[(uint) (uchar) *p0++] !=
unknown's avatar
unknown committed
442
           cs->to_upper[(uint) (uchar) *s1])
unknown's avatar
unknown committed
443
      /* no-op */;
444
    if (p0 >= e0)
unknown's avatar
unknown committed
445
      return 0;
446 447 448 449 450 451

    if (s_after && p0-1 > s0 && true_word_char(cs, p0[-2]))
      continue;

    p1=s1+1;
    while (p0 < e0 && p1 < e1 && cs->to_upper[(uint) (uchar) *p0] ==
unknown's avatar
unknown committed
452
           cs->to_upper[(uint) (uchar) *p1])
453 454
      p0++, p1++;
    if (p1 == e1 && (!e_before || p0 == e0 || !true_word_char(cs, p0[0])))
unknown's avatar
unknown committed
455 456 457 458 459
      return 1;
  }
  return 0;
}

460

461
static void _ftb_climb_the_tree(FTB *ftb, FTB_WORD *ftbw, FT_SEG_ITERATOR *ftsi_orig)
unknown's avatar
unknown committed
462 463
{
  FT_SEG_ITERATOR ftsi;
464 465
  FTB_EXPR *ftbe;
  float weight=ftbw->weight;
unknown's avatar
unknown committed
466
  int  yn=ftbw->flags, ythresh, mode=(ftsi_orig != 0);
467
  my_off_t curdoc=ftbw->docid[mode];
468 469 470

  for (ftbe=ftbw->up; ftbe; ftbe=ftbe->up)
  {
471 472
    ythresh = ftbe->ythresh - (mode ? 0 : ftbe->yweaks);
    if (ftbe->docid[mode] != curdoc)
473
    {
unknown's avatar
unknown committed
474 475
      ftbe->cur_weight=0;
      ftbe->yesses=ftbe->nos=0;
476
      ftbe->docid[mode]=curdoc;
477
    }
478 479
    if (ftbe->nos)
      break;
480
    if (yn & FTB_FLAG_YES)
481
    {
482 483
      weight /= ftbe->ythresh;
      ftbe->cur_weight += weight;
484
      if ((int) ++ftbe->yesses == ythresh)
485
      {
486
        yn=ftbe->flags;
487
        weight=ftbe->cur_weight*ftbe->weight;
unknown's avatar
unknown committed
488 489 490 491 492 493 494 495 496 497 498 499 500 501
        if (mode && ftbe->quot)
        {
          int not_found=1;

          memcpy(&ftsi, ftsi_orig, sizeof(ftsi));
          while (_mi_ft_segiterator(&ftsi) && not_found)
          {
            if (!ftsi.pos)
              continue;
            not_found = ! _ftb_strstr(ftsi.pos, ftsi.pos+ftsi.len,
                                      ftbe->quot, ftbe->qend, ftb->charset);
          }
          if (not_found) break;
        } /* ftbe->quot */
502 503 504 505 506
      }
      else
        break;
    }
    else
507
    if (yn & FTB_FLAG_NO)
508
    {
509
      /*
unknown's avatar
unknown committed
510 511 512 513 514 515
        NOTE: special sort function of queue assures that all
        (yn & FTB_FLAG_NO) != 0
        events for every particular subexpression will
        "auto-magically" happen BEFORE all the
        (yn & FTB_FLAG_YES) != 0 events. So no
        already matched expression can become not-matched again.
516 517 518 519 520 521
      */
      ++ftbe->nos;
      break;
    }
    else
    {
522
      if (ftbe->ythresh)
unknown's avatar
unknown committed
523
        weight/=3;
524
      ftbe->cur_weight +=  weight;
525
      if ((int) ftbe->yesses < ythresh)
526
        break;
unknown's avatar
unknown committed
527
      if (!(yn & FTB_FLAG_WONLY))
unknown's avatar
unknown committed
528
        yn= ((int) ftbe->yesses++ == ythresh) ? ftbe->flags : FTB_FLAG_WONLY ;
529
      weight*= ftbe->weight;
530 531 532 533
    }
  }
}

534

unknown's avatar
unknown committed
535
int ft_boolean_read_next(FT_INFO *ftb, char *record)
536
{
unknown's avatar
unknown committed
537
  FTB_EXPR  *ftbe;
538 539 540 541
  FTB_WORD  *ftbw;
  MI_INFO   *info=ftb->info;
  my_off_t   curdoc;

542 543
  if (ftb->state != INDEX_SEARCH && ftb->state != INDEX_DONE)
    return -1;
unknown's avatar
unknown committed
544

545 546 547 548 549 550 551
  /* black magic ON */
  if ((int) _mi_check_index(info, ftb->keynr) < 0)
    return my_errno;
  if (_mi_readinfo(info, F_RDLCK, 1))
    return my_errno;
  /* black magic OFF */

unknown's avatar
unknown committed
552 553
  if (!ftb->queue.elements)
    return my_errno=HA_ERR_END_OF_FILE;
554

555 556 557
  /* Attention!!! Address of a local variable is used here! See err: label */
  ftb->queue.first_cmp_arg=(void *)&curdoc;

558
  while (ftb->state == INDEX_SEARCH &&
unknown's avatar
unknown committed
559 560
         (curdoc=((FTB_WORD *)queue_top(& ftb->queue))->docid[0]) !=
         HA_POS_ERROR)
unknown's avatar
unknown committed
561
  {
unknown's avatar
unknown committed
562
    while (curdoc == (ftbw=(FTB_WORD *)queue_top(& ftb->queue))->docid[0])
563
    {
unknown's avatar
unknown committed
564
      _ftb_climb_the_tree(ftb, ftbw, 0);
565

566
      /* update queue */
567
      _ft2_search(ftb, ftbw, 0);
unknown's avatar
unknown committed
568
      queue_replaced(& ftb->queue);
569
    }
570

571
    ftbe=ftb->root;
572 573
    if (ftbe->docid[0]==curdoc && ftbe->cur_weight>0 &&
        ftbe->yesses>=(ftbe->ythresh-ftbe->yweaks) && !ftbe->nos)
574 575
    {
      /* curdoc matched ! */
unknown's avatar
unknown committed
576
      if (is_tree_inited(&ftb->no_dupes) &&
577
          tree_insert(&ftb->no_dupes, &curdoc, 0,
unknown's avatar
unknown committed
578
                      ftb->no_dupes.custom_arg)->count >1)
579
        /* but it managed already to get past this line once */
unknown's avatar
unknown committed
580 581
        continue;

582
      info->lastpos=curdoc;
unknown's avatar
unknown committed
583
      /* Clear all states, except that the table was updated */
584
      info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
585

586 587
      if (!(*info->read_record)(info,curdoc,record))
      {
unknown's avatar
unknown committed
588
        info->update|= HA_STATE_AKTIV;          /* Record is read */
589 590
        if (ftb->with_scan && ft_boolean_find_relevance(ftb,record,0)==0)
            continue; /* no match */
591 592
        my_errno=0;
        goto err;
593
      }
594
      goto err;
595 596
    }
  }
597
  ftb->state=INDEX_DONE;
598 599 600 601
  my_errno=HA_ERR_END_OF_FILE;
err:
  ftb->queue.first_cmp_arg=(void *)0;
  return my_errno;
602 603
}

604

605
float ft_boolean_find_relevance(FT_INFO *ftb, byte *record, uint length)
unknown's avatar
unknown committed
606
{
607
  FT_WORD word;
608 609
  FTB_WORD *ftbw;
  FTB_EXPR *ftbe;
unknown's avatar
unknown committed
610
  FT_SEG_ITERATOR ftsi, ftsi2;
611
  const byte *end;
612
  my_off_t  docid=ftb->info->lastpos;
613

614 615
  if (docid == HA_POS_ERROR)
    return -2.0;
unknown's avatar
unknown committed
616 617
  if (!ftb->queue.elements)
    return 0;
618

619
  if (ftb->state != INDEX_SEARCH && docid <= ftb->lastpos)
620 621 622 623 624 625 626 627 628 629 630 631 632 633
  {
    FTB_EXPR *x;
    uint i;

    for (i=0; i < ftb->queue.elements; i++)
    {
      ftb->list[i]->docid[1]=HA_POS_ERROR;
      for (x=ftb->list[i]->up; x; x=x->up)
        x->docid[1]=HA_POS_ERROR;
    }
  }

  ftb->lastpos=docid;

634 635 636 637
  if (ftb->keynr==NO_SUCH_KEY)
    _mi_ft_segiterator_dummy_init(record, length, &ftsi);
  else
    _mi_ft_segiterator_init(ftb->info, ftb->keynr, record, &ftsi);
unknown's avatar
unknown committed
638
  memcpy(&ftsi2, &ftsi, sizeof(ftsi));
639

640
  while (_mi_ft_segiterator(&ftsi))
641
  {
642 643 644 645
    if (!ftsi.pos)
      continue;

    end=ftsi.pos+ftsi.len;
646 647
    while (ft_simple_get_word(ftb->charset,
                              (byte **) &ftsi.pos, (byte *) end, &word))
648
    {
649 650
      int a, b, c;
      for (a=0, b=ftb->queue.elements, c=(a+b)/2; b-a>1; c=(a+b)/2)
651
      {
652
        ftbw=ftb->list[c];
unknown's avatar
unknown committed
653
        if (mi_compare_text(ftb->charset, (uchar*) word.pos, word.len,
unknown's avatar
unknown committed
654
                            (uchar*) ftbw->word+1, ftbw->len-1,
655
                            (my_bool) (ftbw->flags&FTB_FLAG_TRUNC),0) >0)
656 657 658 659
          b=c;
        else
          a=c;
      }
660
      for (; c>=0; c--)
661
      {
662
        ftbw=ftb->list[c];
unknown's avatar
unknown committed
663
        if (mi_compare_text(ftb->charset, (uchar*) word.pos, word.len,
unknown's avatar
unknown committed
664
                            (uchar*) ftbw->word+1,ftbw->len-1,
665
                            (my_bool) (ftbw->flags&FTB_FLAG_TRUNC),0))
666
          break;
667
        if (ftbw->docid[1] == docid)
668
          continue;
669
        ftbw->docid[1]=docid;
unknown's avatar
unknown committed
670
        _ftb_climb_the_tree(ftb, ftbw, &ftsi2);
671 672 673
      }
    }
  }
674

675
  ftbe=ftb->root;
676
  if (ftbe->docid[1]==docid && ftbe->cur_weight>0 &&
677 678 679 680 681 682 683 684
      ftbe->yesses>=ftbe->ythresh && !ftbe->nos)
  { /* row matched ! */
    return ftbe->cur_weight;
  }
  else
  { /* match failed ! */
    return 0.0;
  }
unknown's avatar
unknown committed
685 686
}

687

unknown's avatar
unknown committed
688 689
void ft_boolean_close_search(FT_INFO *ftb)
{
unknown's avatar
unknown committed
690 691 692 693
  if (is_tree_inited(& ftb->no_dupes))
  {
    delete_tree(& ftb->no_dupes);
  }
unknown's avatar
unknown committed
694 695 696 697
  free_root(& ftb->mem_root, MYF(0));
  my_free((gptr)ftb,MYF(0));
}

698

unknown's avatar
unknown committed
699 700 701 702 703
float ft_boolean_get_relevance(FT_INFO *ftb)
{
  return ftb->root->cur_weight;
}

704

unknown's avatar
unknown committed
705 706
void ft_boolean_reinit_search(FT_INFO *ftb)
{
707
  _ftb_init_index_search(ftb);
unknown's avatar
unknown committed
708
}
709