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 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 } Instance()63 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 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 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 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 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(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 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 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 368 void ft_nlq_close_search(FT_INFO *handler) 369 { 370 my_free(handler); 371 } 372 373 374 float ft_nlq_get_relevance(FT_INFO *handler) 375 { 376 return (float) handler->doc[handler->curdoc].weight; 377 } 378 379 380 void ft_nlq_reinit_search(FT_INFO *handler) 381 { 382 handler->curdoc=-1; 383 } 384 385