The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/storage/myisam/ft_nlq_search.c Source File
mysql/src/5.1-dbg/storage/myisam/ft_nlq_search.c

00001 /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; either version 2 of the License, or
00006    (at your option) any later version.
00007 
00008    This program is distributed in the hope that it will be useful,
00009    but WITHOUT ANY WARRANTY; without even the implied warranty of
00010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011    GNU General Public License for more details.
00012 
00013    You should have received a copy of the GNU General Public License
00014    along with this program; if not, write to the Free Software
00015    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
00016 
00017 /* Written by Sergei A. Golubchik, who has a shared copyright to this code */
00018 
00019 #define FT_CORE
00020 #include "ftdefs.h"
00021 
00022 /* search with natural language queries */
00023 
00024 typedef struct ft_doc_rec
00025 {
00026   my_off_t  dpos;
00027   double    weight;
00028 } FT_DOC;
00029 
00030 struct st_ft_info
00031 {
00032   struct _ft_vft *please;
00033   MI_INFO  *info;
00034   int       ndocs;
00035   int       curdoc;
00036   FT_DOC    doc[1];
00037 };
00038 
00039 typedef struct st_all_in_one
00040 {
00041   MI_INFO    *info;
00042   uint        keynr;
00043   CHARSET_INFO *charset;
00044   uchar      *keybuff;
00045   TREE        dtree;
00046 } ALL_IN_ONE;
00047 
00048 typedef struct st_ft_superdoc
00049 {
00050     FT_DOC   doc;
00051     FT_WORD *word_ptr;
00052     double   tmp_weight;
00053 } FT_SUPERDOC;
00054 
00055 static int FT_SUPERDOC_cmp(void* cmp_arg __attribute__((unused)),
00056                            FT_SUPERDOC *p1, FT_SUPERDOC *p2)
00057 {
00058   if (p1->doc.dpos < p2->doc.dpos)
00059     return -1;
00060   if (p1->doc.dpos == p2->doc.dpos)
00061     return 0;
00062   return 1;
00063 }
00064 
00065 static int walk_and_match(FT_WORD *word, uint32 count, ALL_IN_ONE *aio)
00066 {
00067   int          subkeys, r;
00068   uint         keylen, doc_cnt;
00069   FT_SUPERDOC  sdoc, *sptr;
00070   TREE_ELEMENT *selem;
00071   double       gweight=1;
00072   MI_INFO      *info=aio->info;
00073   uchar        *keybuff=aio->keybuff;
00074   MI_KEYDEF    *keyinfo=info->s->keyinfo+aio->keynr;
00075   my_off_t     key_root=info->s->state.key_root[aio->keynr];
00076   uint         extra=HA_FT_WLEN+info->s->base.rec_reflength;
00077 #if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
00078   float tmp_weight;
00079 #else
00080 #error
00081 #endif
00082 
00083   DBUG_ENTER("walk_and_match");
00084 
00085   word->weight=LWS_FOR_QUERY;
00086 
00087   keylen=_ft_make_key(info,aio->keynr,(char*) keybuff,word,0);
00088   keylen-=HA_FT_WLEN;
00089   doc_cnt=0;
00090 
00091   /* Skip rows inserted by current inserted */
00092   for (r=_mi_search(info, keyinfo, keybuff, keylen, SEARCH_FIND, key_root) ;
00093        !r &&
00094          (subkeys=ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
00095          info->lastpos >= info->state->data_file_length ;
00096        r= _mi_search_next(info, keyinfo, info->lastkey,
00097                           info->lastkey_length, SEARCH_BIGGER, key_root))
00098     ;
00099 
00100   info->update|= HA_STATE_AKTIV;              /* for _mi_test_if_changed() */
00101 
00102   /* The following should be safe, even if we compare doubles */
00103   while (!r && gweight)
00104   {
00105 
00106     if (keylen &&
00107         mi_compare_text(aio->charset,info->lastkey+1,
00108                         info->lastkey_length-extra-1, keybuff+1,keylen-1,0,0))
00109      break;
00110 
00111     if (subkeys<0)
00112     {
00113       if (doc_cnt)
00114         DBUG_RETURN(1); /* index is corrupted */
00115       /*
00116         TODO here: unsafe optimization, should this word
00117         be skipped (based on subkeys) ?
00118       */
00119       keybuff+=keylen;
00120       keyinfo=& info->s->ft2_keyinfo;
00121       key_root=info->lastpos;
00122       keylen=0;
00123       r=_mi_search_first(info, keyinfo, key_root);
00124       goto do_skip;
00125     }
00126 #if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
00127     tmp_weight=*(float*)&subkeys;
00128 #else
00129 #error
00130 #endif
00131   /* The following should be safe, even if we compare doubles */
00132     if (tmp_weight==0)
00133       DBUG_RETURN(doc_cnt); /* stopword, doc_cnt should be 0 */
00134 
00135     sdoc.doc.dpos=info->lastpos;
00136 
00137     /* saving document matched into dtree */
00138     if (!(selem=tree_insert(&aio->dtree, &sdoc, 0, aio->dtree.custom_arg)))
00139       DBUG_RETURN(1);
00140 
00141     sptr=(FT_SUPERDOC *)ELEMENT_KEY((&aio->dtree), selem);
00142 
00143     if (selem->count==1) /* document's first match */
00144       sptr->doc.weight=0;
00145     else
00146       sptr->doc.weight+=sptr->tmp_weight*sptr->word_ptr->weight;
00147 
00148     sptr->word_ptr=word;
00149     sptr->tmp_weight=tmp_weight;
00150 
00151     doc_cnt++;
00152 
00153     gweight=word->weight*GWS_IN_USE;
00154     if (gweight < 0 || doc_cnt > 2000000)
00155       gweight=0;
00156 
00157     if (_mi_test_if_changed(info) == 0)
00158         r=_mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
00159                           SEARCH_BIGGER, key_root);
00160     else
00161         r=_mi_search(info, keyinfo, info->lastkey, info->lastkey_length,
00162                      SEARCH_BIGGER, key_root);
00163 do_skip:
00164     while ((subkeys=ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
00165            !r && info->lastpos >= info->state->data_file_length)
00166       r= _mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
00167                          SEARCH_BIGGER, key_root);
00168 
00169   }
00170   word->weight=gweight;
00171 
00172   DBUG_RETURN(0);
00173 }
00174 
00175 
00176 static int walk_and_copy(FT_SUPERDOC *from,
00177                          uint32 count __attribute__((unused)), FT_DOC **to)
00178 {
00179   DBUG_ENTER("walk_and_copy");
00180   from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
00181   (*to)->dpos=from->doc.dpos;
00182   (*to)->weight=from->doc.weight;
00183   (*to)++;
00184   DBUG_RETURN(0);
00185 }
00186 
00187 static int walk_and_push(FT_SUPERDOC *from,
00188                          uint32 count __attribute__((unused)), QUEUE *best)
00189 {
00190   DBUG_ENTER("walk_and_copy");
00191   from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
00192   set_if_smaller(best->elements, ft_query_expansion_limit-1);
00193   queue_insert(best, (byte *)& from->doc);
00194   DBUG_RETURN(0);
00195 }
00196 
00197 
00198 static int FT_DOC_cmp(void *unused __attribute__((unused)),
00199                       FT_DOC *a, FT_DOC *b)
00200 {
00201   return sgn(b->weight - a->weight);
00202 }
00203 
00204 
00205 FT_INFO *ft_init_nlq_search(MI_INFO *info, uint keynr, byte *query,
00206                             uint query_len, uint flags, byte *record)
00207 {
00208   TREE        wtree;
00209   ALL_IN_ONE  aio;
00210   FT_DOC     *dptr;
00211   FT_INFO    *dlist=NULL;
00212   my_off_t    saved_lastpos=info->lastpos;
00213   struct st_mysql_ftparser *parser;
00214   MYSQL_FTPARSER_PARAM *ftparser_param;
00215   DBUG_ENTER("ft_init_nlq_search");
00216 
00217 /* black magic ON */
00218   if ((int) (keynr = _mi_check_index(info,keynr)) < 0)
00219     DBUG_RETURN(NULL);
00220   if (_mi_readinfo(info,F_RDLCK,1))
00221     DBUG_RETURN(NULL);
00222 /* black magic OFF */
00223 
00224   aio.info=info;
00225   aio.keynr=keynr;
00226   aio.charset=info->s->keyinfo[keynr].seg->charset;
00227   aio.keybuff=info->lastkey+info->s->base.max_key_length;
00228   parser= info->s->keyinfo[keynr].parser;
00229   if (! (ftparser_param= ftparser_call_initializer(info, keynr, 0)))
00230     goto err;
00231 
00232   bzero(&wtree,sizeof(wtree));
00233 
00234   init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
00235             NULL, NULL);
00236 
00237   ft_parse_init(&wtree, aio.charset);
00238   ftparser_param->flags= 0;
00239   if (ft_parse(&wtree, query, query_len, parser, ftparser_param,
00240                &wtree.mem_root))
00241     goto err;
00242 
00243   if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
00244                 left_root_right))
00245     goto err;
00246 
00247   if (flags & FT_EXPAND && ft_query_expansion_limit)
00248   {
00249     QUEUE best;
00250     init_queue(&best,ft_query_expansion_limit,0,0, (queue_compare) &FT_DOC_cmp,
00251                0);
00252     tree_walk(&aio.dtree, (tree_walk_action) &walk_and_push,
00253               &best, left_root_right);
00254     while (best.elements)
00255     {
00256       my_off_t docid=((FT_DOC *)queue_remove(& best, 0))->dpos;
00257       if (!(*info->read_record)(info,docid,record))
00258       {
00259         info->update|= HA_STATE_AKTIV;
00260         ftparser_param->flags= MYSQL_FTFLAGS_NEED_COPY;
00261         _mi_ft_parse(&wtree, info, keynr, record, ftparser_param,
00262                      &wtree.mem_root);
00263       }
00264     }
00265     delete_queue(&best);
00266     reset_tree(&aio.dtree);
00267     if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
00268                   left_root_right))
00269       goto err;
00270 
00271   }
00272 
00273   /*
00274     If ndocs == 0, this will not allocate RAM for FT_INFO.doc[],
00275     so if ndocs == 0, FT_INFO.doc[] must not be accessed.
00276    */
00277   dlist=(FT_INFO *)my_malloc(sizeof(FT_INFO)+
00278                              sizeof(FT_DOC)*
00279                              (int)(aio.dtree.elements_in_tree-1),
00280                              MYF(0));
00281   if (!dlist)
00282     goto err;
00283 
00284   dlist->please= (struct _ft_vft *) & _ft_vft_nlq;
00285   dlist->ndocs=aio.dtree.elements_in_tree;
00286   dlist->curdoc=-1;
00287   dlist->info=aio.info;
00288   dptr=dlist->doc;
00289 
00290   tree_walk(&aio.dtree, (tree_walk_action) &walk_and_copy,
00291             &dptr, left_root_right);
00292 
00293   if (flags & FT_SORTED)
00294     qsort2(dlist->doc, dlist->ndocs, sizeof(FT_DOC), (qsort2_cmp)&FT_DOC_cmp, 0);
00295 
00296 err:
00297   delete_tree(&aio.dtree);
00298   delete_tree(&wtree);
00299   info->lastpos=saved_lastpos;
00300   DBUG_RETURN(dlist);
00301 }
00302 
00303 
00304 int ft_nlq_read_next(FT_INFO *handler, char *record)
00305 {
00306   MI_INFO *info= (MI_INFO *) handler->info;
00307 
00308   if (++handler->curdoc >= handler->ndocs)
00309   {
00310     --handler->curdoc;
00311     return HA_ERR_END_OF_FILE;
00312   }
00313 
00314   info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
00315 
00316   info->lastpos=handler->doc[handler->curdoc].dpos;
00317   if (!(*info->read_record)(info,info->lastpos,record))
00318   {
00319     info->update|= HA_STATE_AKTIV;              /* Record is read */
00320     return 0;
00321   }
00322   return my_errno;
00323 }
00324 
00325 
00326 float ft_nlq_find_relevance(FT_INFO *handler,
00327                             byte *record __attribute__((unused)),
00328                             uint length __attribute__((unused)))
00329 {
00330   int a,b,c;
00331   FT_DOC  *docs=handler->doc;
00332   my_off_t docid=handler->info->lastpos;
00333 
00334   if (docid == HA_POS_ERROR)
00335     return -5.0;
00336 
00337   /* Assuming docs[] is sorted by dpos... */
00338 
00339   for (a=0, b=handler->ndocs, c=(a+b)/2; b-a>1; c=(a+b)/2)
00340   {
00341     if (docs[c].dpos > docid)
00342       b=c;
00343     else
00344       a=c;
00345   }
00346   /* bounds check to avoid accessing unallocated handler->doc  */
00347   if (a < handler->ndocs && docs[a].dpos == docid)
00348     return (float) docs[a].weight;
00349   else
00350     return 0.0;
00351 }
00352 
00353 
00354 void ft_nlq_close_search(FT_INFO *handler)
00355 {
00356   my_free((gptr)handler,MYF(0));
00357 }
00358 
00359 
00360 float ft_nlq_get_relevance(FT_INFO *handler)
00361 {
00362   return (float) handler->doc[handler->curdoc].weight;
00363 }
00364 
00365 
00366 void ft_nlq_reinit_search(FT_INFO *handler)
00367 {
00368   handler->curdoc=-1;
00369 }
00370
Generated on Sat Sep 9 00:50:30 2006 for MySQL 5.1 by
1.4.7