ft_nlq_search.c 7.14 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 */

19
#define FT_CORE
20 21 22 23
#include "ftdefs.h"

/* search with natural language queries */

24 25
typedef struct ft_doc_rec
{
26 27 28 29
  my_off_t  dpos;
  double    weight;
} FT_DOC;

30 31
struct st_ft_info
{
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 48 49
  uchar      *keybuff;
  MI_KEYDEF  *keyinfo;
  my_off_t    key_root;
  TREE	      dtree;
} ALL_IN_ONE;

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

57 58
static int FT_SUPERDOC_cmp(void* cmp_arg __attribute__((unused)),
			   FT_SUPERDOC *p1, FT_SUPERDOC *p2)
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
{
  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)
{
  uint	       keylen, r, doc_cnt;
#ifdef EVAL_RUN
  uint	       cnt;
  double       sum, sum2, suml;
#endif /* EVAL_RUN */
  FT_SUPERDOC  sdoc, *sptr;
  TREE_ELEMENT *selem;
#if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
  float tmp_weight;
#else
#error
#endif

82 83
  DBUG_ENTER("walk_and_match");

84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  word->weight=LWS_FOR_QUERY;

  keylen=_ft_make_key(aio->info,aio->keynr,(char*) aio->keybuff,word,0);
#ifdef EVAL_RUN
  keylen-=1+HA_FT_WLEN;
#else /* EVAL_RUN */
  keylen-=HA_FT_WLEN;
#endif /* EVAL_RUN */

#ifdef EVAL_RUN
  sum=sum2=suml=
#endif /* EVAL_RUN */
  doc_cnt=0;

  r=_mi_search(aio->info, aio->keyinfo, aio->keybuff, keylen,
	       SEARCH_FIND | SEARCH_PREFIX, aio->key_root);

101
  while (!r)
102
  {
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
103
    if (mi_compare_text(aio->charset,
104
			aio->info->lastkey,keylen,
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
105 106
			aio->keybuff,keylen,0))
     break;
107 108 109 110 111 112 113 114 115 116

#if HA_FT_WTYPE == HA_KEYTYPE_FLOAT
#ifdef EVAL_RUN
    mi_float4get(tmp_weight,aio->info->lastkey+keylen+1);
#else /* EVAL_RUN */
    mi_float4get(tmp_weight,aio->info->lastkey+keylen);
#endif /* EVAL_RUN */
#else
#error
#endif
117
    if(tmp_weight==0) DBUG_RETURN(doc_cnt); /* stopword, doc_cnt should be 0 */
118 119 120 121 122 123 124 125

#ifdef EVAL_RUN
    cnt=*(byte *)(aio->info->lastkey+keylen);
#endif /* EVAL_RUN */

    sdoc.doc.dpos=aio->info->lastpos;

    /* saving document matched into dtree */
monty@narttu.mysql.fi's avatar
monty@narttu.mysql.fi committed
126
    if (!(selem=tree_insert(&aio->dtree, &sdoc, 0, aio->dtree.custom_arg)))
127
      DBUG_RETURN(1);
128 129 130

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

131
    if (selem->count==1) /* document's first match */
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
      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++;
#ifdef EVAL_RUN
    sum +=cnt;
    sum2+=cnt*cnt;
    suml+=cnt*log(cnt);
#endif /* EVAL_RUN */

    if (_mi_test_if_changed(aio->info) == 0)
	r=_mi_search_next(aio->info, aio->keyinfo, aio->info->lastkey,
			  aio->info->lastkey_length, SEARCH_BIGGER,
			  aio->key_root);
    else
	r=_mi_search(aio->info, aio->keyinfo, aio->info->lastkey,
		     aio->info->lastkey_length, SEARCH_BIGGER,
		     aio->key_root);
  }
155 156
  if (doc_cnt)
  {
157
    word->weight*=GWS_IN_USE;
serg@sergbook.mysql.com's avatar
serg@sergbook.mysql.com committed
158 159
    if (word->weight < 0)
      word->weight=0;
160

161
  }
162
  DBUG_RETURN(0);
163 164
}

165

166 167 168
static int walk_and_copy(FT_SUPERDOC *from,
			 uint32 count __attribute__((unused)), FT_DOC **to)
{
169
  DBUG_ENTER("walk_and_copy");
170 171 172 173
  from->doc.weight+=from->tmp_weight*from->word_ptr->weight;
  (*to)->dpos=from->doc.dpos;
  (*to)->weight=from->doc.weight;
  (*to)++;
174
  DBUG_RETURN(0);
175 176
}

177

178 179
static int FT_DOC_cmp(FT_DOC *a, FT_DOC *b)
{
180
  return sgn(b->weight - a->weight);
181 182
}

183

184
FT_INFO *ft_init_nlq_search(MI_INFO *info, uint keynr, byte *query,
185
			    uint query_len, my_bool presort)
186
{
187
  TREE	     allocated_wtree, *wtree=&allocated_wtree;
188
  ALL_IN_ONE  aio;
189
  FT_DOC     *dptr;
190 191
  FT_INFO    *dlist=NULL;
  my_off_t    saved_lastpos=info->lastpos;
192
  DBUG_ENTER("ft_init_nlq_search");
193

194
/* black magic ON */
195
  if ((int) (keynr = _mi_check_index(info,keynr)) < 0)
196
    DBUG_RETURN(NULL);
197
  if (_mi_readinfo(info,F_RDLCK,1))
198
    DBUG_RETURN(NULL);
199 200
/* black magic OFF */

201
  aio.info=info;
202
  aio.keynr=keynr;
203
  aio.keyinfo=info->s->keyinfo+keynr;
204 205
  aio.charset=aio.keyinfo->seg->charset;
  aio.keybuff=info->lastkey+info->s->base.max_key_length;
206
  aio.key_root=info->s->state.key_root[keynr];
207 208 209

  bzero(&allocated_wtree,sizeof(allocated_wtree));

serg@serg.mysql.com's avatar
serg@serg.mysql.com committed
210 211
  init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
            NULL, NULL);
212

213
  ft_parse_init(&allocated_wtree, aio.charset);
214
  if (ft_parse(&allocated_wtree,query,query_len))
215
    goto err;
216

217 218
  if (tree_walk(wtree, (tree_walk_action)&walk_and_match, &aio,
		left_root_right))
219
    goto err2;
220

221
  dlist=(FT_INFO *)my_malloc(sizeof(FT_INFO)+
222 223
			     sizeof(FT_DOC)*(aio.dtree.elements_in_tree-1),
			     MYF(0));
224
  if(!dlist)
225
    goto err2;
226

227
  dlist->please= (struct _ft_vft *) & _ft_vft_nlq;
228 229 230 231 232
  dlist->ndocs=aio.dtree.elements_in_tree;
  dlist->curdoc=-1;
  dlist->info=aio.info;
  dptr=dlist->doc;

233 234
  tree_walk(&aio.dtree, (tree_walk_action) &walk_and_copy,
	    &dptr, left_root_right);
235

236
  if (presort)
237 238 239
    qsort(dlist->doc, dlist->ndocs, sizeof(FT_DOC), (qsort_cmp)&FT_DOC_cmp);

err2:
240 241
  delete_tree(wtree);
  delete_tree(&aio.dtree);
242 243

err:
244
  info->lastpos=saved_lastpos;
245
  DBUG_RETURN(dlist);
246 247
}

248

249
int ft_nlq_read_next(FT_INFO *handler, char *record)
250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
{
  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;
}

270

271
float ft_nlq_find_relevance(FT_INFO *handler,
272 273
			    byte *record __attribute__((unused)),
			    uint length __attribute__((unused)))
274 275 276
{
  int a,b,c;
  FT_DOC  *docs=handler->doc;
277 278 279 280
  my_off_t docid=handler->info->lastpos;

  if (docid == HA_POS_ERROR)
    return -5.0;
281

282
  /* Assuming docs[] is sorted by dpos... */
283 284 285 286 287 288 289 290 291

  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;
  }
  if (docs[a].dpos == docid)
292
    return (float) docs[a].weight;
293 294 295 296
  else
    return 0.0;
}

297

298 299 300 301 302
void ft_nlq_close_search(FT_INFO *handler)
{
  my_free((gptr)handler,MYF(0));
}

303

304 305
float ft_nlq_get_relevance(FT_INFO *handler)
{
306
  return (float) handler->doc[handler->curdoc].weight;
307 308
}

309

310 311 312 313 314
void ft_nlq_reinit_search(FT_INFO *handler)
{
  handler->curdoc=-1;
}