« back to all changes in this revision
Viewing changes to storage/myisam/ft_boolean_search.c
- browse files at revision 51.1.7
- compare with another revision
- download diff
- download tarball
- view history from revision 51.1.7
- Committer: Jay Pipes
- Date: 2008-07-06 18:59:55 UTC
- mfrom: (78 monty)
- mto: (77.3.26 glibclient) (51.3.4 remove-dbug)
- mto: This revision was merged to the branch mainline in revision 98.
- Revision ID: jay@mysql.com-20080706185955-orgp5jcktd2r7631
Merging trunk changes from over weekend.
- files removed:
- include/my_alarm.h
- files renamed:
- mysys/mf_keycache.c => storage/myisam/mf_keycache.c
- mysys/mf_keycaches.c => storage/myisam/mf_keycaches.c
- mysys/my_lock.c => storage/myisam/my_lock.c
- files modified:
- Makefile.am
added
removed
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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1