1 /* Copyright (c) 2001, 2011, Oracle and/or its affiliates.
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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
15
16 /* Written by Sergei A. Golubchik, who has a shared copyright to this code */
17
18 #define FT_CORE
19 #include "ftdefs.h"
20
21 /* search with natural language queries */
22
23 typedef struct ft_doc_rec
24 {
25 my_off_t dpos;
26 double weight;
27 } FT_DOC;
28
29 struct st_ft_info
30 {
31 struct _ft_vft *please;
32 MI_INFO *info;
33 int ndocs;
34 int curdoc;
35 FT_DOC doc[1];
36 };
37
38 typedef struct st_all_in_one
39 {
40 MI_INFO *info;
41 uint keynr;
42 CHARSET_INFO *charset;
43 uchar *keybuff;
44 TREE dtree;
45 } ALL_IN_ONE;
46
47 typedef struct st_ft_superdoc
48 {
49 FT_DOC doc;
50 FT_WORD *word_ptr;
51 double tmp_weight;
52 } FT_SUPERDOC;
53
FT_SUPERDOC_cmp(void * cmp_arg,FT_SUPERDOC * p1,FT_SUPERDOC * p2)54 static int FT_SUPERDOC_cmp(void* cmp_arg __attribute__((unused)),
55 FT_SUPERDOC *p1, FT_SUPERDOC *p2)
56 {
57 if (p1->doc.dpos < p2->doc.dpos)
58 return -1;
59 if (p1->doc.dpos == p2->doc.dpos)
60 return 0;
61 return 1;
62 }
63
walk_and_match(FT_WORD * word,uint32 count,ALL_IN_ONE * aio)64 static int walk_and_match(FT_WORD *word, uint32 count, ALL_IN_ONE *aio)
65 {
66 FT_WEIGTH subkeys;
67 int r;
68 uint keylen, doc_cnt;
69 FT_SUPERDOC sdoc, *sptr;
70 TREE_ELEMENT *selem;
71 double gweight=1;
72 MI_INFO *info=aio->info;
73 MYISAM_SHARE *share= info->s;
74 uchar *keybuff=aio->keybuff;
75 MI_KEYDEF *keyinfo=info->s->keyinfo+aio->keynr;
76 my_off_t key_root;
77 uint extra= HA_FT_WLEN + info->s->rec_reflength;
78 float tmp_weight;
79 DBUG_ENTER("walk_and_match");
80
81 word->weight=LWS_FOR_QUERY;
82
83 keylen=_ft_make_key(info,aio->keynr,keybuff,word,0);
84 keylen-=HA_FT_WLEN;
85 doc_cnt=0;
86 subkeys.i= 0;
87
88 if (share->concurrent_insert)
89 mysql_rwlock_rdlock(&share->key_root_lock[aio->keynr]);
90
91 key_root= share->state.key_root[aio->keynr];
92
93 /* Skip rows inserted by current inserted */
94 for (r=_mi_search(info, keyinfo, keybuff, keylen, SEARCH_FIND, key_root) ;
95 !r &&
96 (subkeys.i= ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
97 info->lastpos >= info->state->data_file_length ;
98 r= _mi_search_next(info, keyinfo, info->lastkey,
99 info->lastkey_length, SEARCH_BIGGER, key_root))
100 ;
101
102 if (share->concurrent_insert)
103 mysql_rwlock_unlock(&share->key_root_lock[aio->keynr]);
104
105 info->update|= HA_STATE_AKTIV; /* for _mi_test_if_changed() */
106
107 /* The following should be safe, even if we compare doubles */
108 while (!r && gweight)
109 {
110
111 if (keylen &&
112 ha_compare_text(aio->charset,info->lastkey+1,
113 info->lastkey_length-extra-1, keybuff+1,keylen-1,0))
114 break;
115
116 if (subkeys.i < 0)
117 {
118 if (doc_cnt)
119 DBUG_RETURN(1); /* index is corrupted */
120 /*
121 TODO here: unsafe optimization, should this word
122 be skipped (based on subkeys) ?
123 */
124 keybuff+=keylen;
125 keyinfo=& info->s->ft2_keyinfo;
126 key_root=info->lastpos;
127 keylen=0;
128 if (share->concurrent_insert)
129 mysql_rwlock_rdlock(&share->key_root_lock[aio->keynr]);
130 r=_mi_search_first(info, keyinfo, key_root);
131 goto do_skip;
132 }
133 /* The weight we read was actually a float */
134 tmp_weight= subkeys.f;
135 /* The following should be safe, even if we compare doubles */
136 if (tmp_weight==0)
137 DBUG_RETURN(doc_cnt); /* stopword, doc_cnt should be 0 */
138
139 sdoc.doc.dpos=info->lastpos;
140
141 /* saving document matched into dtree */
142 if (!(selem=tree_insert(&aio->dtree, &sdoc, 0, aio->dtree.custom_arg)))
143 DBUG_RETURN(1);
144
145 sptr=(FT_SUPERDOC *)ELEMENT_KEY((&aio->dtree), selem);
146
147 if (selem->count==1) /* document's first match */
148 sptr->doc.weight=0;
149 else
150 sptr->doc.weight+=sptr->tmp_weight*sptr->word_ptr->weight;
151
152 sptr->word_ptr=word;
153 sptr->tmp_weight=tmp_weight;
154
155 doc_cnt++;
156
157 gweight=word->weight*GWS_IN_USE;
158 if (gweight < 0 || doc_cnt > 2000000)
159 gweight=0;
160
161 if (share->concurrent_insert)
162 mysql_rwlock_rdlock(&share->key_root_lock[aio->keynr]);
163
164 if (_mi_test_if_changed(info) == 0)
165 r=_mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
166 SEARCH_BIGGER, key_root);
167 else
168 r=_mi_search(info, keyinfo, info->lastkey, info->lastkey_length,
169 SEARCH_BIGGER, key_root);
170 do_skip:
171 while ((subkeys.i= ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
172 !r && info->lastpos >= info->state->data_file_length)
173 r= _mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
174 SEARCH_BIGGER, key_root);
175
176 if (share->concurrent_insert)
177 mysql_rwlock_unlock(&share->key_root_lock[aio->keynr]);
178 }
179 word->weight=gweight;
180
181 DBUG_RETURN(0);
182 }
183
184
walk_and_copy(FT_SUPERDOC * from,uint32 count,FT_DOC ** to)185 static int walk_and_copy(FT_SUPERDOC *from,
186 uint32 count __attribute__((unused)), FT_DOC **to)
187 {
188 DBUG_ENTER("walk_and_copy");
189 from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
190 (*to)->dpos=from->doc.dpos;
191 (*to)->weight=from->doc.weight;
192 (*to)++;
193 DBUG_RETURN(0);
194 }
195
walk_and_push(FT_SUPERDOC * from,uint32 count,QUEUE * best)196 static int walk_and_push(FT_SUPERDOC *from,
197 uint32 count __attribute__((unused)), QUEUE *best)
198 {
199 DBUG_ENTER("walk_and_copy");
200 from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
201 set_if_smaller(best->elements, ft_query_expansion_limit-1);
202 queue_insert(best, (uchar *)& from->doc);
203 DBUG_RETURN(0);
204 }
205
206
FT_DOC_cmp(void * unused,FT_DOC * a,FT_DOC * b)207 static int FT_DOC_cmp(void *unused __attribute__((unused)),
208 FT_DOC *a, FT_DOC *b)
209 {
210 return CMP_NUM(b->weight, a->weight);
211 }
212
213
ft_init_nlq_search(MI_INFO * info,uint keynr,uchar * query,uint query_len,uint flags,uchar * record)214 FT_INFO *ft_init_nlq_search(MI_INFO *info, uint keynr, uchar *query,
215 uint query_len, uint flags, uchar *record)
216 {
217 TREE wtree;
218 ALL_IN_ONE aio;
219 FT_DOC *dptr;
220 FT_INFO *dlist=NULL;
221 my_off_t saved_lastpos=info->lastpos;
222 struct st_mysql_ftparser *parser;
223 MYSQL_FTPARSER_PARAM *ftparser_param;
224 DBUG_ENTER("ft_init_nlq_search");
225
226 /* black magic ON */
227 if ((int) (keynr = _mi_check_index(info,keynr)) < 0)
228 DBUG_RETURN(NULL);
229 if (_mi_readinfo(info,F_RDLCK,1))
230 DBUG_RETURN(NULL);
231 /* black magic OFF */
232
233 aio.info=info;
234 aio.keynr=keynr;
235 aio.charset=info->s->keyinfo[keynr].seg->charset;
236 aio.keybuff=info->lastkey+info->s->base.max_key_length;
237 parser= info->s->keyinfo[keynr].parser;
238 if (! (ftparser_param= ftparser_call_initializer(info, keynr, 0)))
239 goto err;
240
241 bzero(&wtree,sizeof(wtree));
242
243 init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,
244 NULL, NULL, MYF(0));
245
246 ft_parse_init(&wtree, aio.charset);
247 ftparser_param->flags= 0;
248 if (ft_parse(&wtree, query, query_len, parser, ftparser_param,
249 &wtree.mem_root))
250 goto err;
251
252 if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
253 left_root_right))
254 goto err;
255
256 if (flags & FT_EXPAND && ft_query_expansion_limit)
257 {
258 QUEUE best;
259 init_queue(&best,ft_query_expansion_limit,0,0, (queue_compare) &FT_DOC_cmp,
260 0, 0, 0);
261 tree_walk(&aio.dtree, (tree_walk_action) &walk_and_push,
262 &best, left_root_right);
263 while (best.elements)
264 {
265 my_off_t docid= ((FT_DOC *)queue_remove_top(&best))->dpos;
266 if (!(*info->read_record)(info,docid,record))
267 {
268 info->update|= HA_STATE_AKTIV;
269 ftparser_param->flags= MYSQL_FTFLAGS_NEED_COPY;
270 if (unlikely(_mi_ft_parse(&wtree, info, keynr, record, ftparser_param,
271 &wtree.mem_root)))
272 {
273 delete_queue(&best);
274 goto err;
275 }
276 }
277 }
278 delete_queue(&best);
279 reset_tree(&aio.dtree);
280 if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
281 left_root_right))
282 goto err;
283
284 }
285
286 /*
287 If ndocs == 0, this will not allocate RAM for FT_INFO.doc[],
288 so if ndocs == 0, FT_INFO.doc[] must not be accessed.
289 */
290 dlist=(FT_INFO *)my_malloc(mi_key_memory_FT_INFO, sizeof(FT_INFO)+
291 sizeof(FT_DOC)*
292 (int)(aio.dtree.elements_in_tree-1),
293 MYF(0));
294 if (!dlist)
295 goto err;
296
297 dlist->please= (struct _ft_vft *) & _ft_vft_nlq;
298 dlist->ndocs=aio.dtree.elements_in_tree;
299 dlist->curdoc=-1;
300 dlist->info=aio.info;
301 dptr=dlist->doc;
302
303 tree_walk(&aio.dtree, (tree_walk_action) &walk_and_copy,
304 &dptr, left_root_right);
305
306 if (flags & FT_SORTED)
307 my_qsort2(dlist->doc, dlist->ndocs, sizeof(FT_DOC), (qsort2_cmp)&FT_DOC_cmp,
308 0);
309
310 err:
311 delete_tree(&aio.dtree, 0);
312 delete_tree(&wtree, 0);
313 info->lastpos=saved_lastpos;
314 DBUG_RETURN(dlist);
315 }
316
317
ft_nlq_read_next(FT_INFO * handler,char * record)318 int ft_nlq_read_next(FT_INFO *handler, char *record)
319 {
320 MI_INFO *info= (MI_INFO *) handler->info;
321
322 if (++handler->curdoc >= handler->ndocs)
323 {
324 --handler->curdoc;
325 return HA_ERR_END_OF_FILE;
326 }
327
328 info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
329
330 info->lastpos=handler->doc[handler->curdoc].dpos;
331 if (!(*info->read_record)(info,info->lastpos,(uchar*) record))
332 {
333 info->update|= HA_STATE_AKTIV; /* Record is read */
334 return 0;
335 }
336 return my_errno;
337 }
338
339
ft_nlq_find_relevance(FT_INFO * handler,uchar * record,uint length)340 float ft_nlq_find_relevance(FT_INFO *handler,
341 uchar *record __attribute__((unused)),
342 uint length __attribute__((unused)))
343 {
344 int a,b,c;
345 FT_DOC *docs=handler->doc;
346 my_off_t docid=handler->info->lastpos;
347
348 if (docid == HA_POS_ERROR)
349 return -5.0;
350
351 /* Assuming docs[] is sorted by dpos... */
352
353 for (a=0, b=handler->ndocs, c=(a+b)/2; b-a>1; c=(a+b)/2)
354 {
355 if (docs[c].dpos > docid)
356 b=c;
357 else
358 a=c;
359 }
360 /* bounds check to avoid accessing unallocated handler->doc */
361 if (a < handler->ndocs && docs[a].dpos == docid)
362 return (float) docs[a].weight;
363 else
364 return 0.0;
365 }
366
367
ft_nlq_close_search(FT_INFO * handler)368 void ft_nlq_close_search(FT_INFO *handler)
369 {
370 my_free(handler);
371 }
372
373
ft_nlq_get_relevance(FT_INFO * handler)374 float ft_nlq_get_relevance(FT_INFO *handler)
375 {
376 return (float) handler->doc[handler->curdoc].weight;
377 }
378
379
ft_nlq_reinit_search(FT_INFO * handler)380 void ft_nlq_reinit_search(FT_INFO *handler)
381 {
382 handler->curdoc=-1;
383 }
384
385