ft_boolean_search.c 17.5 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 */

21
#define FT_CORE
22
#include "ftdefs.h"
23
#include <queues.h>
24 25 26

/* search with boolean queries */

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

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

57 58 59 60
#define FTB_FLAG_TRUNC 1                  /* MUST be 1                  */
#define FTB_FLAG_YES   2                  /* These two - YES and NO     */
#define FTB_FLAG_NO    4                  /*  should NEVER be set both  */

61
typedef struct st_ftb_expr FTB_EXPR;
62 63
struct st_ftb_expr
{
64
  FTB_EXPR *up;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
65
  byte     *quot, *qend;
66
  float     weight;
67 68
  uint      flags;
  my_off_t  docid[2];             /* for index search and for scan */
69 70 71 72
  float     cur_weight;
  int       yesses;               /* number of "yes" words matched */
  int       nos;                  /* number of "no"  words matched */
  int       ythresh;              /* number of "yes" words in expr */
73
  int       yweaks;               /* number of "yes" words for scan only */
74 75
};

76 77
typedef struct st_ftb_word
{
78 79
  FTB_EXPR *up;
  float     weight;
80 81
  uint      flags;
  my_off_t  docid[2];             /* for index search and for scan */
82 83
  uint      ndepth;
  int       len;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
84
  /* ... docid cache can be added here. SerG */
85 86 87
  byte      word[1];
} FTB_WORD;

88 89
typedef struct st_ft_info
{
90
  struct _ft_vft *please;
91
  MI_INFO   *info;
92
  uint       keynr;
93
  CHARSET_INFO *charset;
94
  enum { UNINITIALIZED, READY, INDEX_SEARCH, INDEX_DONE /*, SCAN*/ } state;
95
  uint       with_scan;
96
  my_off_t   lastpos;
97 98
  FTB_EXPR  *root;
  QUEUE      queue;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
99
  TREE       no_dupes;
100
  FTB_WORD **list;
101 102 103
  MEM_ROOT   mem_root;
} FTB;

104
static int FTB_WORD_cmp(my_off_t *v, FTB_WORD *a, FTB_WORD *b)
105
{
106 107 108 109 110 111
  int i;

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

112
  /* ORDER BY docid, ndepth DESC */
113
  i=CMP_NUM(a->docid[0], b->docid[0]);
114
  if (!i)
115
    i=CMP_NUM(b->ndepth,a->ndepth);
116 117 118
  return i;
}

119
static int FTB_WORD_cmp_list(CHARSET_INFO *cs, FTB_WORD **a, FTB_WORD **b)
120 121
{
  /* ORDER BY word DESC, ndepth DESC */
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
122
  int i= mi_compare_text(cs, (*b)->word+1,(*b)->len-1,
123
                             (*a)->word+1,(*a)->len-1,0);
124
  if (!i)
125
    i=CMP_NUM((*b)->ndepth,(*a)->ndepth);
126
  return i;
127
}
128

129
static void _ftb_parse_query(FTB *ftb, byte **start, byte *end,
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
130
                      FTB_EXPR *up, uint depth)
131 132 133 134 135 136
{
  byte        res;
  FTB_PARAM   param;
  FT_WORD     w;
  FTB_WORD   *ftbw;
  FTB_EXPR   *ftbe;
137
  uint  extra=HA_FT_WLEN+ftb->info->s->rec_reflength; /* just a shortcut */
138

139
  if (ftb->state != UNINITIALIZED)
140 141
    return;

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

191 192
static int _ftb_no_dupes_cmp(void* not_used __attribute__((unused)),
			     const void *a,const void *b)
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
193 194 195 196
{
  return CMP_NUM((*((my_off_t*)a)), (*((my_off_t*)b)));
}

197
static void _ftb_init_index_search(FT_INFO *ftb)
198 199
{
  int i, r;
200
  FTB_WORD   *ftbw;
201
  MI_INFO    *info=ftb->info;
202 203
  MI_KEYDEF  *keyinfo;
  my_off_t    keyroot;
204

205 206
  if ((ftb->state != READY && ftb->state !=INDEX_DONE) ||
      ftb->keynr == NO_SUCH_KEY)
207 208 209
    return;
  ftb->state=INDEX_SEARCH;

210 211 212
  keyinfo=info->s->keyinfo+ftb->keynr;
  keyroot=info->s->state.key_root[ftb->keynr];

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

217 218 219 220 221
    if (ftbw->flags & FTB_FLAG_TRUNC)
    {
      /*
	special treatment for truncation operator :((
        1. +trunc* and there're other (not +trunc*) words
222 223
           | 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
224
        2. -trunc*
225
           | same as 1.
226
        3. trunc*
227 228 229 230 231 232
           | 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...
233
      */
234 235 236
      if ( test(ftbw->flags&FTB_FLAG_NO) ||                 /* 2 */
          (test(ftbw->flags&FTB_FLAG_YES) &&                /* 1 */
           ftbw->up->ythresh - ftbw->up->yweaks >1))        /* 1 */
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
237 238 239 240 241
      {
        ftbw->docid[0]=HA_POS_ERROR;
        ftbw->up->yweaks++;
        continue;
      }
242
      else /* 3 */
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
243 244 245
      {
        if (!is_tree_inited(& ftb->no_dupes))
        {
246 247
          init_tree(&ftb->no_dupes,0,0,sizeof(my_off_t),
		    _ftb_no_dupes_cmp, 0, NULL, NULL);
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
248 249
        }
      }
250
    }
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
251
    r=_mi_search(info, keyinfo, (uchar*) ftbw->word, ftbw->len,
252
                              SEARCH_FIND | SEARCH_BIGGER, keyroot);
253 254
    if (!r)
    {
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
255
      r= mi_compare_text(ftb->charset,
256 257 258 259
                         info->lastkey + (ftbw->flags&FTB_FLAG_TRUNC),
                         ftbw->len     - (ftbw->flags&FTB_FLAG_TRUNC),
                         ftbw->word    + (ftbw->flags&FTB_FLAG_TRUNC),
                         ftbw->len     - (ftbw->flags&FTB_FLAG_TRUNC),
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
260
                         0);
261 262 263
    }
    if (r) /* not found */
    {
264
      if (ftbw->flags&FTB_FLAG_YES && ftbw->up->up==0)
265 266 267 268 269
      {
	/*
	  This word MUST BE present in every document returned,
	  so we can abort the search right now
	*/
270 271 272 273 274 275 276
        ftb->state=INDEX_DONE;
        return;
      }
    }
    else
    {
      memcpy(ftbw->word, info->lastkey, info->lastkey_length);
277
      ftbw->docid[0]=info->lastpos;
278 279 280 281 282
    }
  }
  queue_fix(& ftb->queue);
}

283

284
FT_INFO * ft_init_boolean_search(MI_INFO *info, uint keynr, byte *query,
285 286
				 uint query_len,
				 my_bool presort __attribute__((unused)))
287
{
288 289 290
  FTB       *ftb;
  FTB_EXPR  *ftbe;
  uint       res;
291

292 293
  if (!(ftb=(FTB *)my_malloc(sizeof(FTB), MYF(MY_WME))))
    return 0;
294
  ftb->please= (struct _ft_vft *) & _ft_vft_boolean;
295
  ftb->state=UNINITIALIZED;
296 297
  ftb->info=info;
  ftb->keynr=keynr;
298 299 300
  ftb->charset= ((keynr==NO_SUCH_KEY) ?
    default_charset_info              :
    info->s->keyinfo[keynr].seg->charset);
301
  ftb->with_scan=0;
302
  ftb->lastpos=0;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
303
  bzero(& ftb->no_dupes, sizeof(TREE));
304

305
  init_alloc_root(&ftb->mem_root, 1024, 1024);
306

307 308 309 310
  /*
    Hack: instead of init_queue, we'll use reinit queue to be able
    to alloc queue with alloc_root()
  */
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
311
  res=ftb->queue.max_elements=1+query_len/(ft_min_word_len+1);
312
  ftb->queue.root=(byte **)alloc_root(&ftb->mem_root, (res+1)*sizeof(void*));
313
  reinit_queue(& ftb->queue, res, 0, 0,
314
                         (int (*)(void*,byte*,byte*))FTB_WORD_cmp, 0);
315
  ftbe=(FTB_EXPR *)alloc_root(&ftb->mem_root, sizeof(FTB_EXPR));
316
  ftbe->weight=1;
317 318
  ftbe->flags=FTB_FLAG_YES;
  ftbe->nos=1;
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
319 320
  ftbe->quot=0;
  ftbe->up=0;
321 322
  ftbe->ythresh=ftbe->yweaks=0;
  ftbe->docid[0]=ftbe->docid[1]=HA_POS_ERROR;
323
  ftb->root=ftbe;
324
  _ftb_parse_query(ftb, &query, query+query_len, ftbe, 0);
325 326
  ftb->list=(FTB_WORD **)alloc_root(&ftb->mem_root,
                                     sizeof(FTB_WORD *)*ftb->queue.elements);
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
327
  memcpy(ftb->list, ftb->queue.root+1, sizeof(FTB_WORD *)*ftb->queue.elements);
328
  qsort2(ftb->list, ftb->queue.elements, sizeof(FTB_WORD *),
329
                              (qsort2_cmp)FTB_WORD_cmp_list, ftb->charset);
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
330
  if (ftb->queue.elements<2) ftb->with_scan &= ~FTB_FLAG_TRUNC;
331
  ftb->state=READY;
332 333
  return ftb;
}
334

335

serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
336
/* returns 1 if str0 contain str1 */
337
static int _ftb_strstr(const byte *s0, const byte *e0,
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
338 339
                const byte *s1, const byte *e1,
                CHARSET_INFO *cs)
340
{
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
341 342 343 344
  const byte *p;

  while (s0 < e0)
  {
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
345 346
    while (s0 < e0 && cs->to_upper[(uint) (uchar) *s0++] !=
	   cs->to_upper[(uint) (uchar) *s1])
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
347 348 349 350
      /* no-op */;
    if (s0 >= e0)
      return 0;
    p=s1+1;
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
351 352
    while (s0 < e0 && p < e1 && cs->to_upper[(uint) (uchar) *s0++] ==
	   cs->to_upper[(uint) (uchar) *p++])
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
353 354 355 356 357 358 359
      /* no-op */;
    if (p >= e1)
      return 1;
  }
  return 0;
}

360

361
static void _ftb_climb_the_tree(FTB *ftb, FTB_WORD *ftbw, FT_SEG_ITERATOR *ftsi_orig)
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
362 363
{
  FT_SEG_ITERATOR ftsi;
364 365
  FTB_EXPR *ftbe;
  float weight=ftbw->weight;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
366
  int  yn=ftbw->flags, ythresh, mode=(ftsi_orig != 0);
367
  my_off_t curdoc=ftbw->docid[mode];
368 369 370

  for (ftbe=ftbw->up; ftbe; ftbe=ftbe->up)
  {
371 372
    ythresh = ftbe->ythresh - (mode ? 0 : ftbe->yweaks);
    if (ftbe->docid[mode] != curdoc)
373
    {
374 375
      ftbe->cur_weight=0;
      ftbe->yesses=ftbe->nos=0;
376
      ftbe->docid[mode]=curdoc;
377
    }
378 379
    if (ftbe->nos)
      break;
380
    if (yn & FTB_FLAG_YES)
381
    {
382 383
      weight /= ftbe->ythresh;
      ftbe->cur_weight += weight;
384
      if (++ftbe->yesses == ythresh)
385
      {
386
        yn=ftbe->flags;
387
        weight=ftbe->cur_weight*ftbe->weight;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
388 389 390 391 392 393 394 395 396 397 398 399 400 401
        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 */
402 403 404 405 406
      }
      else
        break;
    }
    else
407
    if (yn & FTB_FLAG_NO)
408
    {
409 410 411 412 413 414 415
      /*
	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.
416 417 418 419 420 421
      */
      ++ftbe->nos;
      break;
    }
    else
    {
422 423
      if (ftbe->ythresh)
	weight/=3;
424
      ftbe->cur_weight +=  weight;
425
      if (ftbe->yesses < ythresh)
426
        break;
427
      yn= (ftbe->yesses++ == ythresh) ? ftbe->flags : 0 ;
428
      weight*= ftbe->weight;
429 430 431 432
    }
  }
}

433

434
int ft_boolean_read_next(FT_INFO *ftb, char *record)
435
{
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
436
  FTB_EXPR  *ftbe;
437 438 439 440 441 442 443
  FTB_WORD  *ftbw;
  MI_INFO   *info=ftb->info;
  MI_KEYDEF *keyinfo=info->s->keyinfo+ftb->keynr;
  my_off_t   keyroot=info->s->state.key_root[ftb->keynr];
  my_off_t   curdoc;
  int        r;

444 445
  if (ftb->state != INDEX_SEARCH && ftb->state != INDEX_DONE)
    return -1;
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
446

447 448 449 450 451 452 453
  /* 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 */

454 455
  if (!ftb->queue.elements)
    return my_errno=HA_ERR_END_OF_FILE;
456

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

460 461 462
  while (ftb->state == INDEX_SEARCH &&
	 (curdoc=((FTB_WORD *)queue_top(& ftb->queue))->docid[0]) !=
	 HA_POS_ERROR)
463
  {
464
    while (curdoc == (ftbw=(FTB_WORD *)queue_top(& ftb->queue))->docid[0])
465
    {
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
466
      _ftb_climb_the_tree(ftb, ftbw, 0);
467

468
      /* update queue */
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
469
      r=_mi_search(info, keyinfo, (uchar*) ftbw->word, USE_WHOLE_KEY,
470
                   SEARCH_BIGGER , keyroot);
471 472
      if (!r)
      {
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
473
        r= mi_compare_text(ftb->charset,
474 475 476
                           info->lastkey + (ftbw->flags&FTB_FLAG_TRUNC),
                           ftbw->len     - (ftbw->flags&FTB_FLAG_TRUNC),
                           ftbw->word    + (ftbw->flags&FTB_FLAG_TRUNC),
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
477
                           ftbw->len     - (ftbw->flags&FTB_FLAG_TRUNC),
478
                           0);
479 480 481
      }
      if (r) /* not found */
      {
482 483
        ftbw->docid[0]=HA_POS_ERROR;
        if (ftbw->flags&FTB_FLAG_YES && ftbw->up->up==0)
484 485 486 487 488
        {
	  /*
	    This word MUST BE present in every document returned,
	    so we can stop the search right now
	  */
489
          ftb->state=INDEX_DONE;
490
        }
491 492 493 494
      }
      else
      {
        memcpy(ftbw->word, info->lastkey, info->lastkey_length);
495
        ftbw->docid[0]=info->lastpos;
496
      }
497
      queue_replaced(& ftb->queue);
498
    }
499

500
    ftbe=ftb->root;
501 502
    if (ftbe->docid[0]==curdoc && ftbe->cur_weight>0 &&
        ftbe->yesses>=(ftbe->ythresh-ftbe->yweaks) && !ftbe->nos)
503 504
    {
      /* curdoc matched ! */
505 506 507
      if (is_tree_inited(&ftb->no_dupes) &&
          tree_insert(&ftb->no_dupes, &curdoc, 0, 
		      ftb->no_dupes.custom_arg)->count >1)
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
508 509 510
        /* but it managed to get past this line once */
        continue;

511
      info->lastpos=curdoc;
512
      /* Clear all states, except that the table was updated */
513
      info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
514

515 516
      if (!(*info->read_record)(info,curdoc,record))
      {
517
        info->update|= HA_STATE_AKTIV;          /* Record is read */
518 519
        if (ftb->with_scan && ft_boolean_find_relevance(ftb,record,0)==0)
            continue; /* no match */
520 521
        my_errno=0;
        goto err;
522
      }
523
      goto err;
524 525
    }
  }
526
  ftb->state=INDEX_DONE;
527 528 529 530
  my_errno=HA_ERR_END_OF_FILE;
err:
  ftb->queue.first_cmp_arg=(void *)0;
  return my_errno;
531 532
}

533

534
float ft_boolean_find_relevance(FT_INFO *ftb, byte *record, uint length)
535
{
536
  FT_WORD word;
537 538
  FTB_WORD *ftbw;
  FTB_EXPR *ftbe;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
539
  FT_SEG_ITERATOR ftsi, ftsi2;
540
  const byte *end;
541
  my_off_t  docid=ftb->info->lastpos;
542

543 544
  if (docid == HA_POS_ERROR)
    return -2.0;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
545 546
  if (!ftb->queue.elements)
    return 0;
547

548 549 550 551 552 553 554 555 556 557 558 559 560 561 562
  if (ftb->state != INDEX_SEARCH && docid < ftb->lastpos)
  {
    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;

563 564 565 566
  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);
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
567
  memcpy(&ftsi2, &ftsi, sizeof(ftsi));
568

569
  while (_mi_ft_segiterator(&ftsi))
570
  {
571 572 573 574
    if (!ftsi.pos)
      continue;

    end=ftsi.pos+ftsi.len;
575
    while (ft_simple_get_word((byte **) &ftsi.pos,(byte *) end, &word))
576
    {
577 578
      int a, b, c;
      for (a=0, b=ftb->queue.elements, c=(a+b)/2; b-a>1; c=(a+b)/2)
579
      {
580
        ftbw=ftb->list[c];
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
581 582 583
        if (mi_compare_text(ftb->charset, word.pos, word.len,
                            (uchar*) ftbw->word+1, ftbw->len-1,
                            (my_bool) (ftbw->flags&FTB_FLAG_TRUNC)) >0)
584 585 586 587
          b=c;
        else
          a=c;
      }
588
      for (; c>=0; c--)
589
      {
590
        ftbw=ftb->list[c];
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
591 592 593
        if (mi_compare_text(ftb->charset, word.pos,word.len,
                            (uchar*) ftbw->word+1,ftbw->len-1,
                            (my_bool) (ftbw->flags&FTB_FLAG_TRUNC)))
594
          break;
595
        if (ftbw->docid[1] == docid)
596
          continue;
597
        ftbw->docid[1]=docid;
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
598
        _ftb_climb_the_tree(ftb, ftbw, &ftsi2);
599 600 601
      }
    }
  }
602

603
  ftbe=ftb->root;
604
  if (ftbe->docid[1]==docid && ftbe->cur_weight>0 &&
605 606 607 608 609 610 611 612
      ftbe->yesses>=ftbe->ythresh && !ftbe->nos)
  { /* row matched ! */
    return ftbe->cur_weight;
  }
  else
  { /* match failed ! */
    return 0.0;
  }
613 614
}

615

616 617
void ft_boolean_close_search(FT_INFO *ftb)
{
serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
618 619 620 621
  if (is_tree_inited(& ftb->no_dupes))
  {
    delete_tree(& ftb->no_dupes);
  }
622 623 624 625
  free_root(& ftb->mem_root, MYF(0));
  my_free((gptr)ftb,MYF(0));
}

626

627 628 629 630 631
float ft_boolean_get_relevance(FT_INFO *ftb)
{
  return ftb->root->cur_weight;
}

632

633 634
void ft_boolean_reinit_search(FT_INFO *ftb)
{
635
  _ftb_init_index_search(ftb);
636
}
637