← Back to branch summary

~stewart/drizzle/embedded-innodb-create-select-transaction-arrgh

« back to all changes in this revision

Viewing changes to storage/myisam/ft_boolean_search.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/myisam/ft_boolean_search.c
 
1
/* Copyright (C) 2001-2005 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
/* Written by Sergei A. Golubchik, who has a shared copyright to this code */
 
17
 
 
18
/*  TODO: add caching - pre-read several index entries at once */
 
19
 
 
20
/*
 
21
  Added optimization for full-text queries with plus-words. It was
 
22
  implemented by sharing maximal document id (max_docid) variable
 
23
  inside plus subtree. max_docid could be used by any word in plus
 
24
  subtree, but it could be updated by plus-word only.
 
25
 
 
26
  Fulltext "smarter index merge" optimization assumes that rows
 
27
  it gets are ordered by doc_id. That is not the case when we
 
28
  search for a word with truncation operator. It may return
 
29
  rows in random order. Thus we may not use "smarter index merge"
 
30
  optimization with "trunc-words".
 
31
 
 
32
  The idea is: there is no need to search for docid smaller than
 
33
  biggest docid inside current plus subtree or any upper plus subtree.
 
34
 
 
35
  Examples:
 
36
  +word1 word2
 
37
    share same max_docid
 
38
    max_docid updated by word1
 
39
  +word1 +(word2 word3)
 
40
    share same max_docid
 
41
    max_docid updated by word1
 
42
  +(word1 -word2) +(+word3 word4)
 
43
    share same max_docid
 
44
    max_docid updated by word3
 
45
   +word1 word2 (+word3 word4 (+word5 word6))
 
46
    three subexpressions (including the top-level one),
 
47
    every one has its own max_docid, updated by its plus word.
 
48
    but for the search word6 uses
 
49
    max(word1.max_docid, word3.max_docid, word5.max_docid),
 
50
    while word4 uses, accordingly,
 
51
    max(word1.max_docid, word3.max_docid).
 
52
*/
 
53
 
 
54
#define FT_CORE
 
55
#include "ftdefs.h"
 
56
 
 
57
/* search with boolean queries */
 
58
 
 
59
static double _wghts[11]=
 
60
{
 
61
  0.131687242798354,
 
62
  0.197530864197531,
 
63
  0.296296296296296,
 
64
  0.444444444444444,
 
65
  0.666666666666667,
 
66
  1.000000000000000,
 
67
  1.500000000000000,
 
68
  2.250000000000000,
 
69
  3.375000000000000,
 
70
  5.062500000000000,
 
71
  7.593750000000000};
 
72
static double *wghts=_wghts+5; /* wghts[i] = 1.5**i */
 
73
 
 
74
static double _nwghts[11]=
 
75
{
 
76
 -0.065843621399177,
 
77
 -0.098765432098766,
 
78
 -0.148148148148148,
 
79
 -0.222222222222222,
 
80
 -0.333333333333334,
 
81
 -0.500000000000000,
 
82
 -0.750000000000000,
 
83
 -1.125000000000000,
 
84
 -1.687500000000000,
 
85
 -2.531250000000000,
 
86
 -3.796875000000000};
 
87
static double *nwghts=_nwghts+5; /* nwghts[i] = -0.5*1.5**i */
 
88
 
 
89
#define FTB_FLAG_TRUNC 1
 
90
/* At most one of the following flags can be set */
 
91
#define FTB_FLAG_YES   2
 
92
#define FTB_FLAG_NO    4
 
93
#define FTB_FLAG_WONLY 8
 
94
 
 
95
typedef struct st_ftb_expr FTB_EXPR;
 
96
struct st_ftb_expr
 
97
{
 
98
  FTB_EXPR *up;
 
99
  uint      flags;
 
100
/* ^^^^^^^^^^^^^^^^^^ FTB_{EXPR,WORD} common section */
 
101
  my_off_t  docid[2];
 
102
  my_off_t  max_docid;
 
103
  float     weight;
 
104
  float     cur_weight;
 
105
  LIST     *phrase;               /* phrase words */
 
106
  LIST     *document;             /* for phrase search */
 
107
  uint      yesses;               /* number of "yes" words matched */
 
108
  uint      nos;                  /* number of "no"  words matched */
 
109
  uint      ythresh;              /* number of "yes" words in expr */
 
110
  uint      yweaks;               /* number of "yes" words for scan only */
 
111
};
 
112
 
 
113
typedef struct st_ftb_word
 
114
{
 
115
  FTB_EXPR  *up;
 
116
  uint       flags;
 
117
/* ^^^^^^^^^^^^^^^^^^ FTB_{EXPR,WORD} common section */
 
118
  my_off_t   docid[2];             /* for index search and for scan */
 
119
  my_off_t   key_root;
 
120
  FTB_EXPR  *max_docid_expr;
 
121
  MI_KEYDEF *keyinfo;
 
122
  struct st_ftb_word *prev;
 
123
  float      weight;
 
124
  uint       ndepth;
 
125
  uint       len;
 
126
  uchar      off;
 
127
  uchar      word[1];
 
128
} FTB_WORD;
 
129
 
 
130
typedef struct st_ft_info
 
131
{
 
132
  struct _ft_vft *please;
 
133
  MI_INFO   *info;
 
134
  CHARSET_INFO *charset;
 
135
  FTB_EXPR  *root;
 
136
  FTB_WORD **list;
 
137
  FTB_WORD  *last_word;
 
138
  MEM_ROOT   mem_root;
 
139
  QUEUE      queue;
 
140
  TREE       no_dupes;
 
141
  my_off_t   lastpos;
 
142
  uint       keynr;
 
143
  uchar      with_scan;
 
144
  enum { UNINITIALIZED, READY, INDEX_SEARCH, INDEX_DONE } state;
 
145
} FTB;
 
146
 
 
147
static int FTB_WORD_cmp(my_off_t *v, FTB_WORD *a, FTB_WORD *b)
 
148
{
 
149
  int i;
 
150
 
 
151
  /* if a==curdoc, take it as  a < b */
 
152
  if (v && a->docid[0] == *v)
 
153
    return -1;
 
154
 
 
155
  /* ORDER BY docid, ndepth DESC */
 
156
  i=CMP_NUM(a->docid[0], b->docid[0]);
 
157
  if (!i)
 
158
    i=CMP_NUM(b->ndepth,a->ndepth);
 
159
  return i;
 
160
}
 
161
 
 
162
static int FTB_WORD_cmp_list(CHARSET_INFO *cs, FTB_WORD **a, FTB_WORD **b)
 
163
{
 
164
  /* ORDER BY word DESC, ndepth DESC */
 
165
  int i= ha_compare_text(cs, (uchar*) (*b)->word+1,(*b)->len-1,
 
166
                             (uchar*) (*a)->word+1,(*a)->len-1,0,0);
 
167
  if (!i)
 
168
    i=CMP_NUM((*b)->ndepth,(*a)->ndepth);
 
169
  return i;
 
170
}
 
171
 
 
172
 
 
173
typedef struct st_my_ftb_param
 
174
{
 
175
  FTB *ftb;
 
176
  FTB_EXPR *ftbe;
 
177
  uchar *up_quot;
 
178
  uint depth;
 
179
} MY_FTB_PARAM;
 
180
 
 
181
 
 
182
static int ftb_query_add_word(MYSQL_FTPARSER_PARAM *param,
 
183
                              char *word, int word_len,
 
184
                              MYSQL_FTPARSER_BOOLEAN_INFO *info)
 
185
{
 
186
  MY_FTB_PARAM *ftb_param= param->mysql_ftparam;
 
187
  FTB_WORD *ftbw;
 
188
  FTB_EXPR *ftbe, *tmp_expr;
 
189
  FT_WORD *phrase_word;
 
190
  LIST *tmp_element;
 
191
  int r= info->weight_adjust;
 
192
  float weight= (float)
 
193
        (info->wasign ? nwghts : wghts)[(r>5)?5:((r<-5)?-5:r)];
 
194
 
 
195
  switch (info->type) {
 
196
    case FT_TOKEN_WORD:
 
197
      ftbw= (FTB_WORD *)alloc_root(&ftb_param->ftb->mem_root,
 
198
                                   sizeof(FTB_WORD) +
 
199
                                   (info->trunc ? MI_MAX_KEY_BUFF :
 
200
                                    word_len * ftb_param->ftb->charset->mbmaxlen +
 
201
                                    HA_FT_WLEN +
 
202
                                    ftb_param->ftb->info->s->rec_reflength));
 
203
      ftbw->len= word_len + 1;
 
204
      ftbw->flags= 0;
 
205
      ftbw->off= 0;
 
206
      if (info->yesno > 0) ftbw->flags|= FTB_FLAG_YES;
 
207
      if (info->yesno < 0) ftbw->flags|= FTB_FLAG_NO;
 
208
      if (info->trunc) ftbw->flags|= FTB_FLAG_TRUNC;
 
209
      ftbw->weight= weight;
 
210
      ftbw->up= ftb_param->ftbe;
 
211
      ftbw->docid[0]= ftbw->docid[1]= HA_OFFSET_ERROR;
 
212
      ftbw->ndepth= (info->yesno < 0) + ftb_param->depth;
 
213
      ftbw->key_root= HA_OFFSET_ERROR;
 
214
      memcpy(ftbw->word + 1, word, word_len);
 
215
      ftbw->word[0]= word_len;
 
216
      if (info->yesno > 0) ftbw->up->ythresh++;
 
217
      ftb_param->ftb->queue.max_elements++;
 
218
      ftbw->prev= ftb_param->ftb->last_word;
 
219
      ftb_param->ftb->last_word= ftbw;
 
220
      ftb_param->ftb->with_scan|= (info->trunc & FTB_FLAG_TRUNC);
 
221
      for (tmp_expr= ftb_param->ftbe; tmp_expr->up; tmp_expr= tmp_expr->up)
 
222
        if (! (tmp_expr->flags & FTB_FLAG_YES))
 
223
          break;
 
224
      ftbw->max_docid_expr= tmp_expr;
 
225
      /* fall through */
 
226
    case FT_TOKEN_STOPWORD:
 
227
      if (! ftb_param->up_quot) break;
 
228
      phrase_word= (FT_WORD *)alloc_root(&ftb_param->ftb->mem_root, sizeof(FT_WORD));
 
229
      tmp_element= (LIST *)alloc_root(&ftb_param->ftb->mem_root, sizeof(LIST));
 
230
      phrase_word->pos= (uchar*) word;
 
231
      phrase_word->len= word_len;
 
232
      tmp_element->data= (void *)phrase_word;
 
233
      ftb_param->ftbe->phrase= list_add(ftb_param->ftbe->phrase, tmp_element);
 
234
      /* Allocate document list at this point.
 
235
         It allows to avoid huge amount of allocs/frees for each row.*/
 
236
      tmp_element= (LIST *)alloc_root(&ftb_param->ftb->mem_root, sizeof(LIST));
 
237
      tmp_element->data= alloc_root(&ftb_param->ftb->mem_root, sizeof(FT_WORD));
 
238
      ftb_param->ftbe->document=
 
239
        list_add(ftb_param->ftbe->document, tmp_element);
 
240
      break;
 
241
    case FT_TOKEN_LEFT_PAREN:
 
242
      ftbe=(FTB_EXPR *)alloc_root(&ftb_param->ftb->mem_root, sizeof(FTB_EXPR));
 
243
      ftbe->flags= 0;
 
244
      if (info->yesno > 0) ftbe->flags|= FTB_FLAG_YES;
 
245
      if (info->yesno < 0) ftbe->flags|= FTB_FLAG_NO;
 
246
      ftbe->weight= weight;
 
247
      ftbe->up= ftb_param->ftbe;
 
248
      ftbe->max_docid= ftbe->ythresh= ftbe->yweaks= 0;
 
249
      ftbe->docid[0]= ftbe->docid[1]= HA_OFFSET_ERROR;
 
250
      ftbe->phrase= NULL;
 
251
      ftbe->document= 0;
 
252
      if (info->quot) ftb_param->ftb->with_scan|= 2;
 
253
      if (info->yesno > 0) ftbe->up->ythresh++;
 
254
      ftb_param->ftbe= ftbe;
 
255
      ftb_param->depth++;
 
256
      ftb_param->up_quot= (uchar*) info->quot;
 
257
      break;
 
258
    case FT_TOKEN_RIGHT_PAREN:
 
259
      if (ftb_param->ftbe->document)
 
260
      {
 
261
        /* Circuit document list */
 
262
        for (tmp_element= ftb_param->ftbe->document;
 
263
             tmp_element->next; tmp_element= tmp_element->next) /* no-op */;
 
264
        tmp_element->next= ftb_param->ftbe->document;
 
265
        ftb_param->ftbe->document->prev= tmp_element;
 
266
      }
 
267
      info->quot= 0;
 
268
      if (ftb_param->ftbe->up)
 
269
      {
 
270
        DBUG_ASSERT(ftb_param->depth);
 
271
        ftb_param->ftbe= ftb_param->ftbe->up;
 
272
        ftb_param->depth--;
 
273
        ftb_param->up_quot= 0;
 
274
      }
 
275
      break;
 
276
    case FT_TOKEN_EOF:
 
277
    default:
 
278
      break;
 
279
  }
 
280
  return(0);
 
281
}
 
282
 
 
283
 
 
284
static int ftb_parse_query_internal(MYSQL_FTPARSER_PARAM *param,
 
285
                                    char *query, int len)
 
286
{
 
287
  MY_FTB_PARAM *ftb_param= param->mysql_ftparam;
 
288
  MYSQL_FTPARSER_BOOLEAN_INFO info;
 
289
  CHARSET_INFO *cs= ftb_param->ftb->charset;
 
290
  uchar **start= (uchar**) &query;
 
291
  uchar *end= (uchar*) query + len;
 
292
  FT_WORD w;
 
293
 
 
294
  info.prev= ' ';
 
295
  info.quot= 0;
 
296
  while (ft_get_word(cs, start, end, &w, &info))
 
297
    param->mysql_add_word(param, (char*) w.pos, w.len, &info);
 
298
  return(0);
 
299
}
 
300
 
 
301
 
 
302
static int _ftb_parse_query(FTB *ftb, uchar *query, uint len,
 
303
                            struct st_mysql_ftparser *parser)
 
304
{
 
305
  MYSQL_FTPARSER_PARAM *param;
 
306
  MY_FTB_PARAM ftb_param;
 
307
  DBUG_ENTER("_ftb_parse_query");
 
308
  DBUG_ASSERT(parser);
 
309
 
 
310
  if (ftb->state != UNINITIALIZED)
 
311
    DBUG_RETURN(0);
 
312
  if (! (param= ftparser_call_initializer(ftb->info, ftb->keynr, 0)))
 
313
    DBUG_RETURN(1);
 
314
 
 
315
  ftb_param.ftb= ftb;
 
316
  ftb_param.depth= 0;
 
317
  ftb_param.ftbe= ftb->root;
 
318
  ftb_param.up_quot= 0;
 
319
 
 
320
  param->mysql_parse= ftb_parse_query_internal;
 
321
  param->mysql_add_word= ftb_query_add_word;
 
322
  param->mysql_ftparam= (void *)&ftb_param;
 
323
  param->cs= ftb->charset;
 
324
  param->doc= (char*) query;
 
325
  param->length= len;
 
326
  param->flags= 0;
 
327
  param->mode= MYSQL_FTPARSER_FULL_BOOLEAN_INFO;
 
328
  DBUG_RETURN(parser->parse(param));
 
329
}
 
330
 
 
331
 
 
332
static int _ftb_no_dupes_cmp(void* not_used __attribute__((unused)),
 
333
                             const void *a,const void *b)
 
334
{
 
335
  return CMP_NUM((*((my_off_t*)a)), (*((my_off_t*)b)));
 
336
}
 
337
 
 
338
/* returns 1 if the search was finished (must-word wasn't found) */
 
339
static int _ft2_search(FTB *ftb, FTB_WORD *ftbw, my_bool init_search)
 
340
{
 
341
  int r;
 
342
  int subkeys=1;
 
343
  my_bool can_go_down;
 
344
  MI_INFO *info=ftb->info;
 
345
  uint off= 0, extra= HA_FT_WLEN+info->s->base.rec_reflength;
 
346
  uchar *lastkey_buf=ftbw->word+ftbw->off;
 
347
 
 
348
  if (ftbw->flags & FTB_FLAG_TRUNC)
 
349
    lastkey_buf+=ftbw->len;
 
350
 
 
351
  if (init_search)
 
352
  {
 
353
    ftbw->key_root=info->s->state.key_root[ftb->keynr];
 
354
    ftbw->keyinfo=info->s->keyinfo+ftb->keynr;
 
355
 
 
356
    r=_mi_search(info, ftbw->keyinfo, (uchar*) ftbw->word, ftbw->len,
 
357
                 SEARCH_FIND | SEARCH_BIGGER, ftbw->key_root);
 
358
  }
 
359
  else
 
360
  {
 
361
    uint sflag= SEARCH_BIGGER;
 
362
    my_off_t max_docid=0;
 
363
    FTB_EXPR *tmp;
 
364
 
 
365
    for (tmp= ftbw->max_docid_expr; tmp; tmp= tmp->up)
 
366
      set_if_bigger(max_docid, tmp->max_docid);
 
367
 
 
368
    if (ftbw->docid[0] < max_docid)
 
369
    {
 
370
      sflag|= SEARCH_SAME;
 
371
      _mi_dpointer(info, (uchar *)(ftbw->word + ftbw->len + HA_FT_WLEN),
 
372
                   max_docid);
 
373
    }
 
374
    r=_mi_search(info, ftbw->keyinfo, (uchar*) lastkey_buf,
 
375
                   USE_WHOLE_KEY, sflag, ftbw->key_root);
 
376
  }
 
377
 
 
378
  can_go_down=(!ftbw->off && (init_search || (ftbw->flags & FTB_FLAG_TRUNC)));
 
379
  /* Skip rows inserted by concurrent insert */
 
380
  while (!r)
 
381
  {
 
382
    if (can_go_down)
 
383
    {
 
384
      /* going down ? */
 
385
      off=info->lastkey_length-extra;
 
386
      subkeys=ft_sintXkorr(info->lastkey+off);
 
387
    }
 
388
    if (subkeys<0 || info->lastpos < info->state->data_file_length)
 
389
      break;
 
390
    r= _mi_search_next(info, ftbw->keyinfo, info->lastkey,
 
391
                       info->lastkey_length,
 
392
                       SEARCH_BIGGER, ftbw->key_root);
 
393
  }
 
394
 
 
395
  if (!r && !ftbw->off)
 
396
  {
 
397
    r= ha_compare_text(ftb->charset,
 
398
                       info->lastkey+1,
 
399
                       info->lastkey_length-extra-1,
 
400
              (uchar*) ftbw->word+1,
 
401
                       ftbw->len-1,
 
402
             (my_bool) (ftbw->flags & FTB_FLAG_TRUNC),0);
 
403
  }
 
404
 
 
405
  if (r) /* not found */
 
406
  {
 
407
    if (!ftbw->off || !(ftbw->flags & FTB_FLAG_TRUNC))
 
408
    {
 
409
      ftbw->docid[0]=HA_OFFSET_ERROR;
 
410
      if ((ftbw->flags & FTB_FLAG_YES) && ftbw->up->up==0)
 
411
      {
 
412
        /*
 
413
          This word MUST BE present in every document returned,
 
414
          so we can stop the search right now
 
415
        */
 
416
        ftb->state=INDEX_DONE;
 
417
        return 1; /* search is done */
 
418
      }
 
419
      else
 
420
        return 0;
 
421
    }
 
422
 
 
423
    /* going up to the first-level tree to continue search there */
 
424
    _mi_dpointer(info, (uchar*) (lastkey_buf+HA_FT_WLEN), ftbw->key_root);
 
425
    ftbw->key_root=info->s->state.key_root[ftb->keynr];
 
426
    ftbw->keyinfo=info->s->keyinfo+ftb->keynr;
 
427
    ftbw->off=0;
 
428
    return _ft2_search(ftb, ftbw, 0);
 
429
  }
 
430
 
 
431
  /* matching key found */
 
432
  memcpy(lastkey_buf, info->lastkey, info->lastkey_length);
 
433
  if (lastkey_buf == ftbw->word)
 
434
    ftbw->len=info->lastkey_length-extra;
 
435
 
 
436
  /* going down ? */
 
437
  if (subkeys<0)
 
438
  {
 
439
    /*
 
440
      yep, going down, to the second-level tree
 
441
      TODO here: subkey-based optimization
 
442
    */
 
443
    ftbw->off=off;
 
444
    ftbw->key_root=info->lastpos;
 
445
    ftbw->keyinfo=& info->s->ft2_keyinfo;
 
446
    r=_mi_search_first(info, ftbw->keyinfo, ftbw->key_root);
 
447
    DBUG_ASSERT(r==0);  /* found something */
 
448
    memcpy(lastkey_buf+off, info->lastkey, info->lastkey_length);
 
449
  }
 
450
  ftbw->docid[0]=info->lastpos;
 
451
  if (ftbw->flags & FTB_FLAG_YES && !(ftbw->flags & FTB_FLAG_TRUNC))
 
452
    ftbw->max_docid_expr->max_docid= info->lastpos;
 
453
  return 0;
 
454
}
 
455
 
 
456
static void _ftb_init_index_search(FT_INFO *ftb)
 
457
{
 
458
  int i;
 
459
  FTB_WORD   *ftbw;
 
460
 
 
461
  if ((ftb->state != READY && ftb->state !=INDEX_DONE) ||
 
462
      ftb->keynr == NO_SUCH_KEY)
 
463
    return;
 
464
  ftb->state=INDEX_SEARCH;
 
465
 
 
466
  for (i=ftb->queue.elements; i; i--)
 
467
  {
 
468
    ftbw=(FTB_WORD *)(ftb->queue.root[i]);
 
469
 
 
470
    if (ftbw->flags & FTB_FLAG_TRUNC)
 
471
    {
 
472
      /*
 
473
        special treatment for truncation operator
 
474
        1. there are some (besides this) +words
 
475
           | no need to search in the index, it can never ADD new rows
 
476
           | to the result, and to remove half-matched rows we do scan anyway
 
477
        2. -trunc*
 
478
           | same as 1.
 
479
        3. in 1 and 2, +/- need not be on the same expr. level,
 
480
           but can be on any upper level, as in +word +(trunc1* trunc2*)
 
481
        4. otherwise
 
482
           | We have to index-search for this prefix.
 
483
           | It may cause duplicates, as in the index (sorted by <word,docid>)
 
484
           |   <aaaa,row1>
 
485
           |   <aabb,row2>
 
486
           |   <aacc,row1>
 
487
           | Searching for "aa*" will find row1 twice...
 
488
      */
 
489
      FTB_EXPR *ftbe;
 
490
      for (ftbe=(FTB_EXPR*)ftbw;
 
491
           ftbe->up && !(ftbe->up->flags & FTB_FLAG_TRUNC);
 
492
           ftbe->up->flags|= FTB_FLAG_TRUNC, ftbe=ftbe->up)
 
493
      {
 
494
        if (ftbe->flags & FTB_FLAG_NO ||                     /* 2 */
 
495
            ftbe->up->ythresh - ftbe->up->yweaks >
 
496
            (uint) test(ftbe->flags & FTB_FLAG_YES))         /* 1 */
 
497
        {
 
498
          FTB_EXPR *top_ftbe=ftbe->up;
 
499
          ftbw->docid[0]=HA_OFFSET_ERROR;
 
500
          for (ftbe=(FTB_EXPR *)ftbw;
 
501
               ftbe != top_ftbe && !(ftbe->flags & FTB_FLAG_NO);
 
502
               ftbe=ftbe->up)
 
503
              ftbe->up->yweaks++;
 
504
          ftbe=0;
 
505
          break;
 
506
        }
 
507
      }
 
508
      if (!ftbe)
 
509
        continue;
 
510
      /* 4 */
 
511
      if (!is_tree_inited(& ftb->no_dupes))
 
512
        init_tree(& ftb->no_dupes,0,0,sizeof(my_off_t),
 
513
            _ftb_no_dupes_cmp,0,0,0);
 
514
      else
 
515
        reset_tree(& ftb->no_dupes);
 
516
    }
 
517
 
 
518
    ftbw->off=0; /* in case of reinit */
 
519
    if (_ft2_search(ftb, ftbw, 1))
 
520
      return;
 
521
  }
 
522
  queue_fix(& ftb->queue);
 
523
}
 
524
 
 
525
 
 
526
FT_INFO * ft_init_boolean_search(MI_INFO *info, uint keynr, uchar *query,
 
527
                                 uint query_len, CHARSET_INFO *cs)
 
528
{
 
529
  FTB       *ftb;
 
530
  FTB_EXPR  *ftbe;
 
531
  FTB_WORD  *ftbw;
 
532
 
 
533
  if (!(ftb=(FTB *)my_malloc(sizeof(FTB), MYF(MY_WME))))
 
534
    return 0;
 
535
  ftb->please= (struct _ft_vft *) & _ft_vft_boolean;
 
536
  ftb->state=UNINITIALIZED;
 
537
  ftb->info=info;
 
538
  ftb->keynr=keynr;
 
539
  ftb->charset=cs;
 
540
  DBUG_ASSERT(keynr==NO_SUCH_KEY || cs == info->s->keyinfo[keynr].seg->charset);
 
541
  ftb->with_scan=0;
 
542
  ftb->lastpos=HA_OFFSET_ERROR;
 
543
  bzero(& ftb->no_dupes, sizeof(TREE));
 
544
  ftb->last_word= 0;
 
545
 
 
546
  init_alloc_root(&ftb->mem_root, 1024, 1024);
 
547
  ftb->queue.max_elements= 0;
 
548
  if (!(ftbe=(FTB_EXPR *)alloc_root(&ftb->mem_root, sizeof(FTB_EXPR))))
 
549
    goto err;
 
550
  ftbe->weight=1;
 
551
  ftbe->flags=FTB_FLAG_YES;
 
552
  ftbe->nos=1;
 
553
  ftbe->up=0;
 
554
  ftbe->max_docid= ftbe->ythresh= ftbe->yweaks= 0;
 
555
  ftbe->docid[0]=ftbe->docid[1]=HA_OFFSET_ERROR;
 
556
  ftbe->phrase= NULL;
 
557
  ftbe->document= 0;
 
558
  ftb->root=ftbe;
 
559
  if (unlikely(_ftb_parse_query(ftb, query, query_len,
 
560
                                keynr == NO_SUCH_KEY ? &ft_default_parser :
 
561
                                info->s->keyinfo[keynr].parser)))
 
562
    goto err;
 
563
  /*
 
564
    Hack: instead of init_queue, we'll use reinit queue to be able
 
565
    to alloc queue with alloc_root()
 
566
  */
 
567
  if (! (ftb->queue.root= (uchar **)alloc_root(&ftb->mem_root,
 
568
                                              (ftb->queue.max_elements + 1) *
 
569
                                              sizeof(void *))))
 
570
    goto err;
 
571
  reinit_queue(&ftb->queue, ftb->queue.max_elements, 0, 0,
 
572
                         (int (*)(void*, uchar*, uchar*))FTB_WORD_cmp, 0);
 
573
  for (ftbw= ftb->last_word; ftbw; ftbw= ftbw->prev)
 
574
    queue_insert(&ftb->queue, (uchar *)ftbw);
 
575
  ftb->list=(FTB_WORD **)alloc_root(&ftb->mem_root,
 
576
                                     sizeof(FTB_WORD *)*ftb->queue.elements);
 
577
  memcpy(ftb->list, ftb->queue.root+1, sizeof(FTB_WORD *)*ftb->queue.elements);
 
578
  my_qsort2(ftb->list, ftb->queue.elements, sizeof(FTB_WORD *),
 
579
            (qsort2_cmp)FTB_WORD_cmp_list, ftb->charset);
 
580
  if (ftb->queue.elements<2) ftb->with_scan &= ~FTB_FLAG_TRUNC;
 
581
  ftb->state=READY;
 
582
  return ftb;
 
583
err:
 
584
  free_root(& ftb->mem_root, MYF(0));
 
585
  my_free((uchar*)ftb,MYF(0));
 
586
  return 0;
 
587
}
 
588
 
 
589
 
 
590
typedef struct st_my_ftb_phrase_param
 
591
{
 
592
  LIST *phrase;
 
593
  LIST *document;
 
594
  CHARSET_INFO *cs;
 
595
  uint phrase_length;
 
596
  uint document_length;
 
597
  uint match;
 
598
} MY_FTB_PHRASE_PARAM;
 
599
 
 
600
 
 
601
static int ftb_phrase_add_word(MYSQL_FTPARSER_PARAM *param,
 
602
                               char *word, int word_len,
 
603
    MYSQL_FTPARSER_BOOLEAN_INFO *boolean_info __attribute__((unused)))
 
604
{
 
605
  MY_FTB_PHRASE_PARAM *phrase_param= param->mysql_ftparam;
 
606
  FT_WORD *w= (FT_WORD *)phrase_param->document->data;
 
607
  LIST *phrase, *document;
 
608
  w->pos= (uchar*) word;
 
609
  w->len= word_len;
 
610
  phrase_param->document= phrase_param->document->prev;
 
611
  if (phrase_param->phrase_length > phrase_param->document_length)
 
612
  {
 
613
    phrase_param->document_length++;
 
614
    return 0;
 
615
  }
 
616
  /* TODO: rewrite phrase search to avoid
 
617
     comparing the same word twice. */
 
618
  for (phrase= phrase_param->phrase, document= phrase_param->document->next;
 
619
       phrase; phrase= phrase->next, document= document->next)
 
620
  {
 
621
    FT_WORD *phrase_word= (FT_WORD *)phrase->data;
 
622
    FT_WORD *document_word= (FT_WORD *)document->data;
 
623
    if (my_strnncoll(phrase_param->cs, (uchar*) phrase_word->pos,
 
624
                     phrase_word->len,
 
625
                     (uchar*) document_word->pos, document_word->len))
 
626
      return 0;
 
627
  }
 
628
  phrase_param->match++;
 
629
  return 0;
 
630
}
 
631
 
 
632
 
 
633
static int ftb_check_phrase_internal(MYSQL_FTPARSER_PARAM *param,
 
634
                                     char *document, int len)
 
635
{
 
636
  FT_WORD word;
 
637
  MY_FTB_PHRASE_PARAM *phrase_param= param->mysql_ftparam;
 
638
  const uchar *docend= (uchar*) document + len;
 
639
  while (ft_simple_get_word(phrase_param->cs, (uchar**) &document, docend,
 
640
                            &word, FALSE))
 
641
  {
 
642
    param->mysql_add_word(param, (char*) word.pos, word.len, 0);
 
643
    if (phrase_param->match)
 
644
      break;
 
645
  }
 
646
  return 0;
 
647
}
 
648
 
 
649
 
 
650
/*
 
651
  Checks if given buffer matches phrase list.
 
652
 
 
653
  SYNOPSIS
 
654
    _ftb_check_phrase()
 
655
    s0     start of buffer
 
656
    e0     end of buffer
 
657
    phrase broken into list phrase
 
658
    cs     charset info
 
659
 
 
660
  RETURN VALUE
 
661
    1 is returned if phrase found, 0 else.
 
662
    -1 is returned if error occurs.
 
663
*/
 
664
 
 
665
static int _ftb_check_phrase(FTB *ftb, const uchar *document, uint len,
 
666
                FTB_EXPR *ftbe, struct st_mysql_ftparser *parser)
 
667
{
 
668
  MY_FTB_PHRASE_PARAM ftb_param;
 
669
  MYSQL_FTPARSER_PARAM *param;
 
670
  DBUG_ENTER("_ftb_check_phrase");
 
671
  DBUG_ASSERT(parser);
 
672
 
 
673
  if (! (param= ftparser_call_initializer(ftb->info, ftb->keynr, 1)))
 
674
    DBUG_RETURN(0);
 
675
 
 
676
  ftb_param.phrase= ftbe->phrase;
 
677
  ftb_param.document= ftbe->document;
 
678
  ftb_param.cs= ftb->charset;
 
679
  ftb_param.phrase_length= list_length(ftbe->phrase);
 
680
  ftb_param.document_length= 1;
 
681
  ftb_param.match= 0;
 
682
 
 
683
  param->mysql_parse= ftb_check_phrase_internal;
 
684
  param->mysql_add_word= ftb_phrase_add_word;
 
685
  param->mysql_ftparam= (void *)&ftb_param;
 
686
  param->cs= ftb->charset;
 
687
  param->doc= (char *) document;
 
688
  param->length= len;
 
689
  param->flags= 0;
 
690
  param->mode= MYSQL_FTPARSER_WITH_STOPWORDS;
 
691
  if (unlikely(parser->parse(param)))
 
692
    return -1;
 
693
  DBUG_RETURN(ftb_param.match ? 1 : 0);
 
694
}
 
695
 
 
696
 
 
697
static int _ftb_climb_the_tree(FTB *ftb, FTB_WORD *ftbw, FT_SEG_ITERATOR *ftsi_orig)
 
698
{
 
699
  FT_SEG_ITERATOR ftsi;
 
700
  FTB_EXPR *ftbe;
 
701
  float weight=ftbw->weight;
 
702
  int  yn_flag= ftbw->flags, ythresh, mode=(ftsi_orig != 0);
 
703
  my_off_t curdoc=ftbw->docid[mode];
 
704
  struct st_mysql_ftparser *parser= ftb->keynr == NO_SUCH_KEY ?
 
705
                                    &ft_default_parser :
 
706
                                    ftb->info->s->keyinfo[ftb->keynr].parser;
 
707
 
 
708
  for (ftbe=ftbw->up; ftbe; ftbe=ftbe->up)
 
709
  {
 
710
    ythresh = ftbe->ythresh - (mode ? 0 : ftbe->yweaks);
 
711
    if (ftbe->docid[mode] != curdoc)
 
712
    {
 
713
      ftbe->cur_weight=0;
 
714
      ftbe->yesses=ftbe->nos=0;
 
715
      ftbe->docid[mode]=curdoc;
 
716
    }
 
717
    if (ftbe->nos)
 
718
      break;
 
719
    if (yn_flag & FTB_FLAG_YES)
 
720
    {
 
721
      weight /= ftbe->ythresh;
 
722
      ftbe->cur_weight += weight;
 
723
      if ((int) ++ftbe->yesses == ythresh)
 
724
      {
 
725
        yn_flag=ftbe->flags;
 
726
        weight=ftbe->cur_weight*ftbe->weight;
 
727
        if (mode && ftbe->phrase)
 
728
        {
 
729
          int found= 0;
 
730
 
 
731
          memcpy(&ftsi, ftsi_orig, sizeof(ftsi));
 
732
          while (_mi_ft_segiterator(&ftsi) && !found)
 
733
          {
 
734
            if (!ftsi.pos)
 
735
              continue;
 
736
            found= _ftb_check_phrase(ftb, ftsi.pos, ftsi.len, ftbe, parser);
 
737
            if (unlikely(found < 0))
 
738
              return 1;
 
739
          }
 
740
          if (!found)
 
741
            break;
 
742
        } /* ftbe->quot */
 
743
      }
 
744
      else
 
745
        break;
 
746
    }
 
747
    else
 
748
    if (yn_flag & FTB_FLAG_NO)
 
749
    {
 
750
      /*
 
751
        NOTE: special sort function of queue assures that all
 
752
        (yn_flag & FTB_FLAG_NO) != 0
 
753
        events for every particular subexpression will
 
754
        "auto-magically" happen BEFORE all the
 
755
        (yn_flag & FTB_FLAG_YES) != 0 events. So no
 
756
        already matched expression can become not-matched again.
 
757
      */
 
758
      ++ftbe->nos;
 
759
      break;
 
760
    }
 
761
    else
 
762
    {
 
763
      if (ftbe->ythresh)
 
764
        weight/=3;
 
765
      ftbe->cur_weight +=  weight;
 
766
      if ((int) ftbe->yesses < ythresh)
 
767
        break;
 
768
      if (!(yn_flag & FTB_FLAG_WONLY))
 
769
        yn_flag= ((int) ftbe->yesses++ == ythresh) ? ftbe->flags : FTB_FLAG_WONLY ;
 
770
      weight*= ftbe->weight;
 
771
    }
 
772
  }
 
773
  return 0;
 
774
}
 
775
 
 
776
 
 
777
int ft_boolean_read_next(FT_INFO *ftb, char *record)
 
778
{
 
779
  FTB_EXPR  *ftbe;
 
780
  FTB_WORD  *ftbw;
 
781
  MI_INFO   *info=ftb->info;
 
782
  my_off_t   curdoc;
 
783
 
 
784
  if (ftb->state != INDEX_SEARCH && ftb->state != INDEX_DONE)
 
785
    return -1;
 
786
 
 
787
  /* black magic ON */
 
788
  if ((int) _mi_check_index(info, ftb->keynr) < 0)
 
789
    return my_errno;
 
790
  if (_mi_readinfo(info, F_RDLCK, 1))
 
791
    return my_errno;
 
792
  /* black magic OFF */
 
793
 
 
794
  if (!ftb->queue.elements)
 
795
    return my_errno=HA_ERR_END_OF_FILE;
 
796
 
 
797
  /* Attention!!! Address of a local variable is used here! See err: label */
 
798
  ftb->queue.first_cmp_arg=(void *)&curdoc;
 
799
 
 
800
  while (ftb->state == INDEX_SEARCH &&
 
801
         (curdoc=((FTB_WORD *)queue_top(& ftb->queue))->docid[0]) !=
 
802
         HA_OFFSET_ERROR)
 
803
  {
 
804
    while (curdoc == (ftbw=(FTB_WORD *)queue_top(& ftb->queue))->docid[0])
 
805
    {
 
806
      if (unlikely(_ftb_climb_the_tree(ftb, ftbw, 0)))
 
807
      {
 
808
        my_errno= HA_ERR_OUT_OF_MEM;
 
809
        goto err;
 
810
      }
 
811
 
 
812
      /* update queue */
 
813
      _ft2_search(ftb, ftbw, 0);
 
814
      queue_replaced(& ftb->queue);
 
815
    }
 
816
 
 
817
    ftbe=ftb->root;
 
818
    if (ftbe->docid[0]==curdoc && ftbe->cur_weight>0 &&
 
819
        ftbe->yesses>=(ftbe->ythresh-ftbe->yweaks) && !ftbe->nos)
 
820
    {
 
821
      /* curdoc matched ! */
 
822
      if (is_tree_inited(&ftb->no_dupes) &&
 
823
          tree_insert(&ftb->no_dupes, &curdoc, 0,
 
824
                      ftb->no_dupes.custom_arg)->count >1)
 
825
        /* but it managed already to get past this line once */
 
826
        continue;
 
827
 
 
828
      info->lastpos=curdoc;
 
829
      /* Clear all states, except that the table was updated */
 
830
      info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
 
831
 
 
832
      if (!(*info->read_record)(info,curdoc, (uchar*) record))
 
833
      {
 
834
        info->update|= HA_STATE_AKTIV;          /* Record is read */
 
835
        if (ftb->with_scan &&
 
836
            ft_boolean_find_relevance(ftb,(uchar*) record,0)==0)
 
837
            continue; /* no match */
 
838
        my_errno=0;
 
839
        goto err;
 
840
      }
 
841
      goto err;
 
842
    }
 
843
  }
 
844
  ftb->state=INDEX_DONE;
 
845
  my_errno=HA_ERR_END_OF_FILE;
 
846
err:
 
847
  ftb->queue.first_cmp_arg=(void *)0;
 
848
  return my_errno;
 
849
}
 
850
 
 
851
 
 
852
typedef struct st_my_ftb_find_param
 
853
{
 
854
  FT_INFO *ftb;
 
855
  FT_SEG_ITERATOR *ftsi;
 
856
} MY_FTB_FIND_PARAM;
 
857
 
 
858
 
 
859
static int ftb_find_relevance_add_word(MYSQL_FTPARSER_PARAM *param,
 
860
                                       char *word, int len,
 
861
             MYSQL_FTPARSER_BOOLEAN_INFO *boolean_info __attribute__((unused)))
 
862
{
 
863
  MY_FTB_FIND_PARAM *ftb_param= param->mysql_ftparam;
 
864
  FT_INFO *ftb= ftb_param->ftb;
 
865
  FTB_WORD *ftbw;
 
866
  int a, b, c;
 
867
  for (a= 0, b= ftb->queue.elements, c= (a+b)/2; b-a>1; c= (a+b)/2)
 
868
  {
 
869
    ftbw= ftb->list[c];
 
870
    if (ha_compare_text(ftb->charset, (uchar*)word, len,
 
871
                        (uchar*)ftbw->word+1, ftbw->len-1,
 
872
                        (my_bool)(ftbw->flags&FTB_FLAG_TRUNC), 0) > 0)
 
873
      b= c;
 
874
    else
 
875
      a= c;
 
876
  }
 
877
  for (; c >= 0; c--)
 
878
  {
 
879
    ftbw= ftb->list[c];
 
880
    if (ha_compare_text(ftb->charset, (uchar*)word, len,
 
881
                        (uchar*)ftbw->word + 1,ftbw->len - 1,
 
882
                        (my_bool)(ftbw->flags & FTB_FLAG_TRUNC), 0))
 
883
      break;
 
884
    if (ftbw->docid[1] == ftb->info->lastpos)
 
885
      continue;
 
886
    ftbw->docid[1]= ftb->info->lastpos;
 
887
    if (unlikely(_ftb_climb_the_tree(ftb, ftbw, ftb_param->ftsi)))
 
888
      return 1;
 
889
  }
 
890
  return(0);
 
891
}
 
892
 
 
893
 
 
894
static int ftb_find_relevance_parse(MYSQL_FTPARSER_PARAM *param,
 
895
                                    char *doc, int len)
 
896
{
 
897
  MY_FTB_FIND_PARAM *ftb_param= param->mysql_ftparam;
 
898
  FT_INFO *ftb= ftb_param->ftb;
 
899
  uchar *end= (uchar*) doc + len;
 
900
  FT_WORD w;
 
901
  while (ft_simple_get_word(ftb->charset, (uchar**) &doc, end, &w, TRUE))
 
902
    param->mysql_add_word(param, (char*) w.pos, w.len, 0);
 
903
  return(0);
 
904
}
 
905
 
 
906
 
 
907
float ft_boolean_find_relevance(FT_INFO *ftb, uchar *record, uint length)
 
908
{
 
909
  FTB_EXPR *ftbe;
 
910
  FT_SEG_ITERATOR ftsi, ftsi2;
 
911
  my_off_t  docid=ftb->info->lastpos;
 
912
  MY_FTB_FIND_PARAM ftb_param;
 
913
  MYSQL_FTPARSER_PARAM *param;
 
914
  struct st_mysql_ftparser *parser= ftb->keynr == NO_SUCH_KEY ?
 
915
                                    &ft_default_parser :
 
916
                                    ftb->info->s->keyinfo[ftb->keynr].parser;
 
917
 
 
918
  if (docid == HA_OFFSET_ERROR)
 
919
    return -2.0;
 
920
  if (!ftb->queue.elements)
 
921
    return 0;
 
922
  if (! (param= ftparser_call_initializer(ftb->info, ftb->keynr, 0)))
 
923
    return 0;
 
924
 
 
925
  if (ftb->state != INDEX_SEARCH && docid <= ftb->lastpos)
 
926
  {
 
927
    FTB_EXPR *x;
 
928
    uint i;
 
929
 
 
930
    for (i=0; i < ftb->queue.elements; i++)
 
931
    {
 
932
      ftb->list[i]->docid[1]=HA_OFFSET_ERROR;
 
933
      for (x=ftb->list[i]->up; x; x=x->up)
 
934
        x->docid[1]=HA_OFFSET_ERROR;
 
935
    }
 
936
  }
 
937
 
 
938
  ftb->lastpos=docid;
 
939
 
 
940
  if (ftb->keynr==NO_SUCH_KEY)
 
941
    _mi_ft_segiterator_dummy_init(record, length, &ftsi);
 
942
  else
 
943
    _mi_ft_segiterator_init(ftb->info, ftb->keynr, record, &ftsi);
 
944
  memcpy(&ftsi2, &ftsi, sizeof(ftsi));
 
945
 
 
946
  ftb_param.ftb= ftb;
 
947
  ftb_param.ftsi= &ftsi2;
 
948
  param->mysql_parse= ftb_find_relevance_parse;
 
949
  param->mysql_add_word= ftb_find_relevance_add_word;
 
950
  param->mysql_ftparam= (void *)&ftb_param;
 
951
  param->flags= 0;
 
952
  param->cs= ftb->charset;
 
953
  param->mode= MYSQL_FTPARSER_SIMPLE_MODE;
 
954
  while (_mi_ft_segiterator(&ftsi))
 
955
  {
 
956
    if (!ftsi.pos)
 
957
      continue;
 
958
    param->doc= (char *)ftsi.pos;
 
959
    param->length= ftsi.len;
 
960
    if (unlikely(parser->parse(param)))
 
961
      return 0;
 
962
  }
 
963
  ftbe=ftb->root;
 
964
  if (ftbe->docid[1]==docid && ftbe->cur_weight>0 &&
 
965
      ftbe->yesses>=ftbe->ythresh && !ftbe->nos)
 
966
  { /* row matched ! */
 
967
    return ftbe->cur_weight;
 
968
  }
 
969
  else
 
970
  { /* match failed ! */
 
971
    return 0.0;
 
972
  }
 
973
}
 
974
 
 
975
 
 
976
void ft_boolean_close_search(FT_INFO *ftb)
 
977
{
 
978
  if (is_tree_inited(& ftb->no_dupes))
 
979
  {
 
980
    delete_tree(& ftb->no_dupes);
 
981
  }
 
982
  free_root(& ftb->mem_root, MYF(0));
 
983
  my_free((uchar*)ftb,MYF(0));
 
984
}
 
985
 
 
986
 
 
987
float ft_boolean_get_relevance(FT_INFO *ftb)
 
988
{
 
989
  return ftb->root->cur_weight;
 
990
}
 
991
 
 
992
 
 
993
void ft_boolean_reinit_search(FT_INFO *ftb)
 
994
{
 
995
  _ftb_init_index_search(ftb);
 
996
}
 
997