ft_nlq_search.c 9.45 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* Written by Sergei A. Golubchik, who has a shared copyright to this code */

unknown's avatar
unknown committed
19
#define FT_CORE
20 21 22 23
#include "ftdefs.h"

/* search with natural language queries */

24 25
typedef struct ft_doc_rec
{
unknown's avatar
unknown committed
26 27 28 29
  my_off_t  dpos;
  double    weight;
} FT_DOC;

30 31
struct st_ft_info
{
unknown's avatar
unknown committed
32 33 34 35 36 37 38
  struct _ft_vft *please;
  MI_INFO  *info;
  int       ndocs;
  int       curdoc;
  FT_DOC    doc[1];
};

39 40
typedef struct st_all_in_one
{
41 42
  MI_INFO    *info;
  uint	      keynr;
43
  CHARSET_INFO *charset;
44 45 46 47
  uchar      *keybuff;
  TREE	      dtree;
} ALL_IN_ONE;

48 49
typedef struct st_ft_superdoc
{
50 51 52 53 54
    FT_DOC   doc;
    FT_WORD *word_ptr;
    double   tmp_weight;
} FT_SUPERDOC;

55 56
static int FT_SUPERDOC_cmp(void* cmp_arg __attribute__((unused)),
			   FT_SUPERDOC *p1, FT_SUPERDOC *p2)
57 58 59 60 61 62 63 64 65 66
{
  if (p1->doc.dpos < p2->doc.dpos)
    return -1;
  if (p1->doc.dpos == p2->doc.dpos)
    return 0;
  return 1;
}

static int walk_and_match(FT_WORD *word, uint32 count, ALL_IN_ONE *aio)
{
67 68
  int	       subkeys, r;
  uint	       keylen, doc_cnt;
69 70
  FT_SUPERDOC  sdoc, *sptr;
  TREE_ELEMENT *selem;
unknown's avatar
unknown committed
71
  double       gweight=1;
72 73 74 75
  MI_INFO      *info=aio->info;
  uchar        *keybuff=aio->keybuff;
  MI_KEYDEF    *keyinfo=info->s->keyinfo+aio->keynr;
  my_off_t     key_root=info->s->state.key_root[aio->keynr];
76
  uint         extra=HA_FT_WLEN+info->s->base.rec_reflength;
77 78 79 80 81 82
#if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
  float tmp_weight;
#else
#error
#endif

unknown's avatar
unknown committed
83 84
  DBUG_ENTER("walk_and_match");

85 86
  word->weight=LWS_FOR_QUERY;

87
  keylen=_ft_make_key(info,aio->keynr,(char*) keybuff,word,0);
88 89 90
  keylen-=HA_FT_WLEN;
  doc_cnt=0;

unknown's avatar
unknown committed
91
  /* Skip rows inserted by current inserted */
unknown's avatar
unknown committed
92
  for (r=_mi_search(info, keyinfo, keybuff, keylen, SEARCH_FIND, key_root) ;
unknown's avatar
unknown committed
93 94 95
       !r &&
         (subkeys=ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
         info->lastpos >= info->state->data_file_length ;
unknown's avatar
unknown committed
96 97 98 99
       r= _mi_search_next(info, keyinfo, info->lastkey,
                          info->lastkey_length, SEARCH_BIGGER, key_root))
    ;

100
  info->update|= HA_STATE_AKTIV;              /* for _mi_test_if_changed() */
101

102
  /* The following should be safe, even if we compare doubles */
103
  while (!r && gweight)
104
  {
105 106

    if (keylen &&
107
        mi_compare_text(aio->charset,info->lastkey+1,
108
                        info->lastkey_length-extra-1, keybuff+1,keylen-1,0,0))
unknown's avatar
unknown committed
109
     break;
110

111 112 113 114 115 116 117 118 119 120 121 122 123
    if (subkeys<0)
    {
      if (doc_cnt)
        DBUG_RETURN(1); /* index is corrupted */
      /*
        TODO here: unsafe optimization, should this word
        be skipped (based on subkeys) ?
      */
      keybuff+=keylen;
      keyinfo=& info->s->ft2_keyinfo;
      key_root=info->lastpos;
      keylen=0;
      r=_mi_search_first(info, keyinfo, key_root);
124
      goto do_skip;
125
    }
126
#if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
127
    tmp_weight=*(float*)&subkeys;
128 129 130
#else
#error
#endif
131
  /* The following should be safe, even if we compare doubles */
132 133
    if (tmp_weight==0)
      DBUG_RETURN(doc_cnt); /* stopword, doc_cnt should be 0 */
134

135
    sdoc.doc.dpos=info->lastpos;
136 137

    /* saving document matched into dtree */
unknown's avatar
unknown committed
138
    if (!(selem=tree_insert(&aio->dtree, &sdoc, 0, aio->dtree.custom_arg)))
unknown's avatar
unknown committed
139
      DBUG_RETURN(1);
140 141 142

    sptr=(FT_SUPERDOC *)ELEMENT_KEY((&aio->dtree), selem);

143
    if (selem->count==1) /* document's first match */
144 145 146 147 148 149 150 151
      sptr->doc.weight=0;
    else
      sptr->doc.weight+=sptr->tmp_weight*sptr->word_ptr->weight;

    sptr->word_ptr=word;
    sptr->tmp_weight=tmp_weight;

    doc_cnt++;
152

153 154 155
    gweight=word->weight*GWS_IN_USE;
    if (gweight < 0 || doc_cnt > 2000000)
      gweight=0;
156

157 158 159
    if (_mi_test_if_changed(info) == 0)
	r=_mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
                          SEARCH_BIGGER, key_root);
160
    else
161 162
	r=_mi_search(info, keyinfo, info->lastkey, info->lastkey_length,
                     SEARCH_BIGGER, key_root);
163 164 165
do_skip:
    while ((subkeys=ft_sintXkorr(info->lastkey+info->lastkey_length-extra)) > 0 &&
           !r && info->lastpos >= info->state->data_file_length)
unknown's avatar
unknown committed
166 167
      r= _mi_search_next(info, keyinfo, info->lastkey, info->lastkey_length,
                         SEARCH_BIGGER, key_root);
unknown's avatar
unknown committed
168

169
  }
170
  word->weight=gweight;
unknown's avatar
unknown committed
171 172

  DBUG_RETURN(0);
173 174
}

175

176 177 178
static int walk_and_copy(FT_SUPERDOC *from,
			 uint32 count __attribute__((unused)), FT_DOC **to)
{
unknown's avatar
unknown committed
179
  DBUG_ENTER("walk_and_copy");
180 181 182 183
  from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
  (*to)->dpos=from->doc.dpos;
  (*to)->weight=from->doc.weight;
  (*to)++;
unknown's avatar
unknown committed
184
  DBUG_RETURN(0);
185 186
}

187 188 189 190 191
static int walk_and_push(FT_SUPERDOC *from,
			 uint32 count __attribute__((unused)), QUEUE *best)
{
  DBUG_ENTER("walk_and_copy");
  from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
unknown's avatar
unknown committed
192
  set_if_smaller(best->elements, ft_query_expansion_limit-1);
193 194 195
  queue_insert(best, (byte *)& from->doc);
  DBUG_RETURN(0);
}
196

197 198 199

static int FT_DOC_cmp(void *unused __attribute__((unused)),
                      FT_DOC *a, FT_DOC *b)
200
{
201
  return sgn(b->weight - a->weight);
202 203
}

204

unknown's avatar
unknown committed
205
FT_INFO *ft_init_nlq_search(MI_INFO *info, uint keynr, byte *query,
206
			    uint query_len, uint flags, byte *record)
207
{
208
  TREE	      wtree;
209
  ALL_IN_ONE  aio;
210
  FT_DOC     *dptr;
unknown's avatar
unknown committed
211 212
  FT_INFO    *dlist=NULL;
  my_off_t    saved_lastpos=info->lastpos;
213 214
  struct st_mysql_ftparser *parser;
  MYSQL_FTPARSER_PARAM *ftparser_param;
unknown's avatar
unknown committed
215
  DBUG_ENTER("ft_init_nlq_search");
216

217
/* black magic ON */
unknown's avatar
unknown committed
218
  if ((int) (keynr = _mi_check_index(info,keynr)) < 0)
unknown's avatar
unknown committed
219
    DBUG_RETURN(NULL);
unknown's avatar
unknown committed
220
  if (_mi_readinfo(info,F_RDLCK,1))
unknown's avatar
unknown committed
221
    DBUG_RETURN(NULL);
222 223
/* black magic OFF */

unknown's avatar
unknown committed
224
  aio.info=info;
225
  aio.keynr=keynr;
226
  aio.charset=info->s->keyinfo[keynr].seg->charset;
227
  aio.keybuff=info->lastkey+info->s->base.max_key_length;
228
  parser= info->s->keyinfo[keynr].parser;
229
  if (! (ftparser_param= ftparser_call_initializer(info, keynr, 0)))
230
    goto err;
231

232
  bzero(&wtree,sizeof(wtree));
233

unknown's avatar
unknown committed
234 235
  init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
            NULL, NULL);
236

237
  ft_parse_init(&wtree, aio.charset);
238
  if (ft_parse(&wtree, query, query_len, 0, parser, ftparser_param))
239
    goto err;
240

241
  if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
242
		left_root_right))
243 244 245 246 247
    goto err;

  if (flags & FT_EXPAND && ft_query_expansion_limit)
  {
    QUEUE best;
248 249
    init_queue(&best,ft_query_expansion_limit,0,0, (queue_compare) &FT_DOC_cmp,
	       0);
250 251 252 253 254 255 256 257
    tree_walk(&aio.dtree, (tree_walk_action) &walk_and_push,
              &best, left_root_right);
    while (best.elements)
    {
      my_off_t docid=((FT_DOC *)queue_remove(& best, 0))->dpos;
      if (!(*info->read_record)(info,docid,record))
      {
        info->update|= HA_STATE_AKTIV;
258
        _mi_ft_parse(&wtree, info, keynr, record, 1, ftparser_param);
259 260 261 262 263 264 265 266 267
      }
    }
    delete_queue(&best);
    reset_tree(&aio.dtree);
    if (tree_walk(&wtree, (tree_walk_action)&walk_and_match, &aio,
                  left_root_right))
      goto err;

  }
268

unknown's avatar
unknown committed
269 270 271 272
  /*
    If ndocs == 0, this will not allocate RAM for FT_INFO.doc[],
    so if ndocs == 0, FT_INFO.doc[] must not be accessed.
   */
unknown's avatar
unknown committed
273
  dlist=(FT_INFO *)my_malloc(sizeof(FT_INFO)+
274 275
			     sizeof(FT_DOC)*
			     (int)(aio.dtree.elements_in_tree-1),
276
			     MYF(0));
277 278
  if (!dlist)
    goto err;
279

280
  dlist->please= (struct _ft_vft *) & _ft_vft_nlq;
281 282 283 284 285
  dlist->ndocs=aio.dtree.elements_in_tree;
  dlist->curdoc=-1;
  dlist->info=aio.info;
  dptr=dlist->doc;

286 287
  tree_walk(&aio.dtree, (tree_walk_action) &walk_and_copy,
	    &dptr, left_root_right);
288

289
  if (flags & FT_SORTED)
290
    qsort2(dlist->doc, dlist->ndocs, sizeof(FT_DOC), (qsort2_cmp)&FT_DOC_cmp, 0);
291 292

err:
293 294
  delete_tree(&aio.dtree);
  delete_tree(&wtree);
unknown's avatar
unknown committed
295
  info->lastpos=saved_lastpos;
unknown's avatar
unknown committed
296
  DBUG_RETURN(dlist);
297 298
}

299

unknown's avatar
unknown committed
300
int ft_nlq_read_next(FT_INFO *handler, char *record)
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
{
  MI_INFO *info= (MI_INFO *) handler->info;

  if (++handler->curdoc >= handler->ndocs)
  {
    --handler->curdoc;
    return HA_ERR_END_OF_FILE;
  }

  info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);

  info->lastpos=handler->doc[handler->curdoc].dpos;
  if (!(*info->read_record)(info,info->lastpos,record))
  {
    info->update|= HA_STATE_AKTIV;		/* Record is read */
    return 0;
  }
  return my_errno;
}

321

322
float ft_nlq_find_relevance(FT_INFO *handler,
unknown's avatar
unknown committed
323 324
			    byte *record __attribute__((unused)),
			    uint length __attribute__((unused)))
unknown's avatar
unknown committed
325 326 327
{
  int a,b,c;
  FT_DOC  *docs=handler->doc;
328 329 330 331
  my_off_t docid=handler->info->lastpos;

  if (docid == HA_POS_ERROR)
    return -5.0;
unknown's avatar
unknown committed
332

unknown's avatar
unknown committed
333
  /* Assuming docs[] is sorted by dpos... */
unknown's avatar
unknown committed
334 335 336 337 338 339 340 341

  for (a=0, b=handler->ndocs, c=(a+b)/2; b-a>1; c=(a+b)/2)
  {
    if (docs[c].dpos > docid)
      b=c;
    else
      a=c;
  }
unknown's avatar
unknown committed
342 343
  /* bounds check to avoid accessing unallocated handler->doc  */
  if (a < handler->ndocs && docs[a].dpos == docid)
unknown's avatar
unknown committed
344
    return (float) docs[a].weight;
unknown's avatar
unknown committed
345 346 347 348
  else
    return 0.0;
}

349

unknown's avatar
unknown committed
350 351 352 353 354
void ft_nlq_close_search(FT_INFO *handler)
{
  my_free((gptr)handler,MYF(0));
}

355

unknown's avatar
unknown committed
356 357
float ft_nlq_get_relevance(FT_INFO *handler)
{
unknown's avatar
unknown committed
358
  return (float) handler->doc[handler->curdoc].weight;
unknown's avatar
unknown committed
359 360
}

361

unknown's avatar
unknown committed
362 363 364 365 366
void ft_nlq_reinit_search(FT_INFO *handler)
{
  handler->curdoc=-1;
}