Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tsrank.c
4 : * rank tsvector by tsquery
5 : *
6 : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 : *
8 : *
9 : * IDENTIFICATION
10 : * src/backend/utils/adt/tsrank.c
11 : *
12 : *-------------------------------------------------------------------------
13 : */
14 : #include "postgres.h"
15 :
16 : #include <limits.h>
17 : #include <math.h>
18 :
19 : #include "miscadmin.h"
20 : #include "tsearch/ts_utils.h"
21 : #include "utils/array.h"
22 : #include "utils/fmgrprotos.h"
23 :
24 : #define NUM_WEIGHTS 4
25 : static const float default_weights[NUM_WEIGHTS] = {0.1f, 0.2f, 0.4f, 1.0f};
26 :
27 : #define wpos(wep) ( w[ WEP_GETWEIGHT(wep) ] )
28 :
29 : #define RANK_NO_NORM 0x00
30 : #define RANK_NORM_LOGLENGTH 0x01
31 : #define RANK_NORM_LENGTH 0x02
32 : #define RANK_NORM_EXTDIST 0x04
33 : #define RANK_NORM_UNIQ 0x08
34 : #define RANK_NORM_LOGUNIQ 0x10
35 : #define RANK_NORM_RDIVRPLUS1 0x20
36 : #define DEF_NORM_METHOD RANK_NO_NORM
37 :
38 : static float calc_rank_or(const float *w, TSVector t, TSQuery q);
39 : static float calc_rank_and(const float *w, TSVector t, TSQuery q);
40 :
41 : /*
42 : * Returns a weight of a word collocation
43 : */
44 : static float4
45 18 : word_distance(int32 w)
46 : {
47 18 : if (w > 100)
48 0 : return 1e-30f;
49 :
50 18 : return 1.0 / (1.005 + 0.05 * exp(((float4) w) / 1.5 - 2));
51 : }
52 :
53 : static int
54 0 : cnt_length(TSVector t)
55 : {
56 0 : WordEntry *ptr = ARRPTR(t),
57 0 : *end = (WordEntry *) STRPTR(t);
58 0 : int len = 0;
59 :
60 0 : while (ptr < end)
61 : {
62 0 : int clen = POSDATALEN(t, ptr);
63 :
64 0 : if (clen == 0)
65 0 : len += 1;
66 : else
67 0 : len += clen;
68 :
69 0 : ptr++;
70 : }
71 :
72 0 : return len;
73 : }
74 :
75 :
76 : #define WordECompareQueryItem(e,q,p,i,m) \
77 : tsCompareString((q) + (i)->distance, (i)->length, \
78 : (e) + (p)->pos, (p)->len, (m))
79 :
80 :
81 : /*
82 : * Returns a pointer to a WordEntry's array corresponding to 'item' from
83 : * tsvector 't'. 'q' is the TSQuery containing 'item'.
84 : * Returns NULL if not found.
85 : */
86 : static WordEntry *
87 426 : find_wordentry(TSVector t, TSQuery q, QueryOperand *item, int32 *nitem)
88 : {
89 426 : WordEntry *StopLow = ARRPTR(t);
90 426 : WordEntry *StopHigh = (WordEntry *) STRPTR(t);
91 426 : WordEntry *StopMiddle = StopHigh;
92 : int difference;
93 :
94 426 : *nitem = 0;
95 :
96 : /* Loop invariant: StopLow <= item < StopHigh */
97 1146 : while (StopLow < StopHigh)
98 : {
99 1098 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
100 1098 : difference = WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, false);
101 1098 : if (difference == 0)
102 : {
103 378 : StopHigh = StopMiddle;
104 378 : *nitem = 1;
105 378 : break;
106 : }
107 720 : else if (difference > 0)
108 252 : StopLow = StopMiddle + 1;
109 : else
110 468 : StopHigh = StopMiddle;
111 : }
112 :
113 426 : if (item->prefix)
114 : {
115 54 : if (StopLow >= StopHigh)
116 54 : StopMiddle = StopHigh;
117 :
118 54 : *nitem = 0;
119 :
120 222 : while (StopMiddle < (WordEntry *) STRPTR(t) &&
121 84 : WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, true) == 0)
122 : {
123 84 : (*nitem)++;
124 84 : StopMiddle++;
125 : }
126 : }
127 :
128 426 : return (*nitem > 0) ? StopHigh : NULL;
129 : }
130 :
131 :
132 : /*
133 : * sort QueryOperands by (length, word)
134 : */
135 : static int
136 108 : compareQueryOperand(const void *a, const void *b, void *arg)
137 : {
138 108 : char *operand = (char *) arg;
139 108 : QueryOperand *qa = (*(QueryOperand *const *) a);
140 108 : QueryOperand *qb = (*(QueryOperand *const *) b);
141 :
142 216 : return tsCompareString(operand + qa->distance, qa->length,
143 108 : operand + qb->distance, qb->length,
144 : false);
145 : }
146 :
147 : /*
148 : * Returns a sorted, de-duplicated array of QueryOperands in a query.
149 : * The returned QueryOperands are pointers to the original QueryOperands
150 : * in the query.
151 : *
152 : * Length of the returned array is stored in *size
153 : */
154 : static QueryOperand **
155 54 : SortAndUniqItems(TSQuery q, int *size)
156 : {
157 54 : char *operand = GETOPERAND(q);
158 54 : QueryItem *item = GETQUERY(q);
159 : QueryOperand **res,
160 : **ptr,
161 : **prevptr;
162 :
163 54 : ptr = res = (QueryOperand **) palloc(sizeof(QueryOperand *) * *size);
164 :
165 : /* Collect all operands from the tree to res */
166 216 : while ((*size)--)
167 : {
168 162 : if (item->type == QI_VAL)
169 : {
170 108 : *ptr = (QueryOperand *) item;
171 108 : ptr++;
172 : }
173 162 : item++;
174 : }
175 :
176 54 : *size = ptr - res;
177 54 : if (*size < 2)
178 0 : return res;
179 :
180 54 : qsort_arg(res, *size, sizeof(QueryOperand *), compareQueryOperand, operand);
181 :
182 54 : ptr = res + 1;
183 54 : prevptr = res;
184 :
185 : /* remove duplicates */
186 108 : while (ptr - res < *size)
187 : {
188 54 : if (compareQueryOperand(ptr, prevptr, operand) != 0)
189 : {
190 54 : prevptr++;
191 54 : *prevptr = *ptr;
192 : }
193 54 : ptr++;
194 : }
195 :
196 54 : *size = prevptr + 1 - res;
197 54 : return res;
198 : }
199 :
200 : static float
201 18 : calc_rank_and(const float *w, TSVector t, TSQuery q)
202 : {
203 : WordEntryPosVector **pos;
204 : WordEntryPosVector1 posnull;
205 : WordEntryPosVector *POSNULL;
206 : int i,
207 : k,
208 : l,
209 : p;
210 : WordEntry *entry,
211 : *firstentry;
212 : WordEntryPos *post,
213 : *ct;
214 : int32 dimt,
215 : lenct,
216 : dist,
217 : nitem;
218 18 : float res = -1.0;
219 : QueryOperand **item;
220 18 : int size = q->size;
221 :
222 18 : item = SortAndUniqItems(q, &size);
223 18 : if (size < 2)
224 : {
225 0 : pfree(item);
226 0 : return calc_rank_or(w, t, q);
227 : }
228 18 : pos = (WordEntryPosVector **) palloc0(sizeof(WordEntryPosVector *) * q->size);
229 :
230 : /* A dummy WordEntryPos array to use when haspos is false */
231 18 : posnull.npos = 1;
232 18 : posnull.pos[0] = 0;
233 18 : WEP_SETPOS(posnull.pos[0], MAXENTRYPOS - 1);
234 18 : POSNULL = (WordEntryPosVector *) &posnull;
235 :
236 54 : for (i = 0; i < size; i++)
237 : {
238 36 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
239 36 : if (!entry)
240 0 : continue;
241 :
242 72 : while (entry - firstentry < nitem)
243 : {
244 36 : if (entry->haspos)
245 36 : pos[i] = _POSVECPTR(t, entry);
246 : else
247 0 : pos[i] = POSNULL;
248 :
249 36 : dimt = pos[i]->npos;
250 36 : post = pos[i]->pos;
251 54 : for (k = 0; k < i; k++)
252 : {
253 18 : if (!pos[k])
254 0 : continue;
255 18 : lenct = pos[k]->npos;
256 18 : ct = pos[k]->pos;
257 36 : for (l = 0; l < dimt; l++)
258 : {
259 36 : for (p = 0; p < lenct; p++)
260 : {
261 18 : dist = abs((int) WEP_GETPOS(post[l]) - (int) WEP_GETPOS(ct[p]));
262 18 : if (dist || (dist == 0 && (pos[i] == POSNULL || pos[k] == POSNULL)))
263 : {
264 : float curw;
265 :
266 18 : if (!dist)
267 0 : dist = MAXENTRYPOS;
268 18 : curw = sqrt(wpos(post[l]) * wpos(ct[p]) * word_distance(dist));
269 18 : res = (res < 0) ? curw : 1.0 - (1.0 - res) * (1.0 - curw);
270 : }
271 : }
272 : }
273 : }
274 :
275 36 : entry++;
276 : }
277 : }
278 18 : pfree(pos);
279 18 : pfree(item);
280 18 : return res;
281 : }
282 :
283 : static float
284 36 : calc_rank_or(const float *w, TSVector t, TSQuery q)
285 : {
286 : WordEntry *entry,
287 : *firstentry;
288 : WordEntryPosVector1 posnull;
289 : WordEntryPos *post;
290 : int32 dimt,
291 : j,
292 : i,
293 : nitem;
294 36 : float res = 0.0;
295 : QueryOperand **item;
296 36 : int size = q->size;
297 :
298 : /* A dummy WordEntryPos array to use when haspos is false */
299 36 : posnull.npos = 1;
300 36 : posnull.pos[0] = 0;
301 :
302 36 : item = SortAndUniqItems(q, &size);
303 :
304 108 : for (i = 0; i < size; i++)
305 : {
306 : float resj,
307 : wjm;
308 : int32 jm;
309 :
310 72 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
311 72 : if (!entry)
312 6 : continue;
313 :
314 132 : while (entry - firstentry < nitem)
315 : {
316 66 : if (entry->haspos)
317 : {
318 66 : dimt = POSDATALEN(t, entry);
319 66 : post = POSDATAPTR(t, entry);
320 : }
321 : else
322 : {
323 0 : dimt = posnull.npos;
324 0 : post = posnull.pos;
325 : }
326 :
327 66 : resj = 0.0;
328 66 : wjm = -1.0;
329 66 : jm = 0;
330 132 : for (j = 0; j < dimt; j++)
331 : {
332 66 : resj = resj + wpos(post[j]) / ((j + 1) * (j + 1));
333 66 : if (wpos(post[j]) > wjm)
334 : {
335 66 : wjm = wpos(post[j]);
336 66 : jm = j;
337 : }
338 : }
339 : /*
340 : limit (sum(1/i^2),i=1,inf) = pi^2/6
341 : resj = sum(wi/i^2),i=1,noccurrence,
342 : wi - should be sorted desc,
343 : don't sort for now, just choose maximum weight. This should be corrected
344 : Oleg Bartunov
345 : */
346 66 : res = res + (wjm + resj - wjm / ((jm + 1) * (jm + 1))) / 1.64493406685;
347 :
348 66 : entry++;
349 : }
350 : }
351 36 : if (size > 0)
352 36 : res = res / size;
353 36 : pfree(item);
354 36 : return res;
355 : }
356 :
357 : static float
358 54 : calc_rank(const float *w, TSVector t, TSQuery q, int32 method)
359 : {
360 54 : QueryItem *item = GETQUERY(q);
361 54 : float res = 0.0;
362 : int len;
363 :
364 54 : if (!t->size || !q->size)
365 0 : return 0.0;
366 :
367 : /* XXX: What about NOT? */
368 54 : res = (item->type == QI_OPR && (item->qoperator.oper == OP_AND ||
369 36 : item->qoperator.oper == OP_PHRASE)) ?
370 72 : calc_rank_and(w, t, q) :
371 36 : calc_rank_or(w, t, q);
372 :
373 54 : if (res < 0)
374 0 : res = 1e-20f;
375 :
376 54 : if ((method & RANK_NORM_LOGLENGTH) && t->size > 0)
377 0 : res /= log((double) (cnt_length(t) + 1)) / log(2.0);
378 :
379 54 : if (method & RANK_NORM_LENGTH)
380 : {
381 0 : len = cnt_length(t);
382 0 : if (len > 0)
383 0 : res /= (float) len;
384 : }
385 :
386 : /* RANK_NORM_EXTDIST not applicable */
387 :
388 54 : if ((method & RANK_NORM_UNIQ) && t->size > 0)
389 0 : res /= (float) (t->size);
390 :
391 54 : if ((method & RANK_NORM_LOGUNIQ) && t->size > 0)
392 0 : res /= log((double) (t->size + 1)) / log(2.0);
393 :
394 54 : if (method & RANK_NORM_RDIVRPLUS1)
395 0 : res /= (res + 1);
396 :
397 54 : return res;
398 : }
399 :
400 : /*
401 : * Extract weights from an array. The weights are stored in *ws, which must
402 : * have space for NUM_WEIGHTS elements.
403 : */
404 : static void
405 0 : getWeights(ArrayType *win, float *ws)
406 : {
407 : int i;
408 : float4 *arrdata;
409 :
410 : Assert(win != NULL);
411 :
412 0 : if (ARR_NDIM(win) != 1)
413 0 : ereport(ERROR,
414 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
415 : errmsg("array of weight must be one-dimensional")));
416 :
417 0 : if (ArrayGetNItems(ARR_NDIM(win), ARR_DIMS(win)) < NUM_WEIGHTS)
418 0 : ereport(ERROR,
419 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
420 : errmsg("array of weight is too short")));
421 :
422 0 : if (array_contains_nulls(win))
423 0 : ereport(ERROR,
424 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
425 : errmsg("array of weight must not contain nulls")));
426 :
427 0 : arrdata = (float4 *) ARR_DATA_PTR(win);
428 0 : for (i = 0; i < NUM_WEIGHTS; i++)
429 : {
430 0 : ws[i] = (arrdata[i] >= 0) ? arrdata[i] : default_weights[i];
431 0 : if (ws[i] > 1.0)
432 0 : ereport(ERROR,
433 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
434 : errmsg("weight out of range")));
435 : }
436 0 : }
437 :
438 : Datum
439 0 : ts_rank_wttf(PG_FUNCTION_ARGS)
440 : {
441 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
442 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
443 0 : TSQuery query = PG_GETARG_TSQUERY(2);
444 0 : int method = PG_GETARG_INT32(3);
445 : float weights[NUM_WEIGHTS];
446 : float res;
447 :
448 0 : getWeights(win, weights);
449 0 : res = calc_rank(weights, txt, query, method);
450 :
451 0 : PG_FREE_IF_COPY(win, 0);
452 0 : PG_FREE_IF_COPY(txt, 1);
453 0 : PG_FREE_IF_COPY(query, 2);
454 0 : PG_RETURN_FLOAT4(res);
455 : }
456 :
457 : Datum
458 0 : ts_rank_wtt(PG_FUNCTION_ARGS)
459 : {
460 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
461 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
462 0 : TSQuery query = PG_GETARG_TSQUERY(2);
463 : float weights[NUM_WEIGHTS];
464 : float res;
465 :
466 0 : getWeights(win, weights);
467 0 : res = calc_rank(weights, txt, query, DEF_NORM_METHOD);
468 :
469 0 : PG_FREE_IF_COPY(win, 0);
470 0 : PG_FREE_IF_COPY(txt, 1);
471 0 : PG_FREE_IF_COPY(query, 2);
472 0 : PG_RETURN_FLOAT4(res);
473 : }
474 :
475 : Datum
476 0 : ts_rank_ttf(PG_FUNCTION_ARGS)
477 : {
478 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
479 0 : TSQuery query = PG_GETARG_TSQUERY(1);
480 0 : int method = PG_GETARG_INT32(2);
481 : float res;
482 :
483 0 : res = calc_rank(default_weights, txt, query, method);
484 :
485 0 : PG_FREE_IF_COPY(txt, 0);
486 0 : PG_FREE_IF_COPY(query, 1);
487 0 : PG_RETURN_FLOAT4(res);
488 : }
489 :
490 : Datum
491 54 : ts_rank_tt(PG_FUNCTION_ARGS)
492 : {
493 54 : TSVector txt = PG_GETARG_TSVECTOR(0);
494 54 : TSQuery query = PG_GETARG_TSQUERY(1);
495 : float res;
496 :
497 54 : res = calc_rank(default_weights, txt, query, DEF_NORM_METHOD);
498 :
499 54 : PG_FREE_IF_COPY(txt, 0);
500 54 : PG_FREE_IF_COPY(query, 1);
501 54 : PG_RETURN_FLOAT4(res);
502 : }
503 :
504 : typedef struct
505 : {
506 : union
507 : {
508 : struct
509 : { /* compiled doc representation */
510 : QueryItem **items;
511 : int16 nitem;
512 : } query;
513 : struct
514 : { /* struct is used for preparing doc
515 : * representation */
516 : QueryItem *item;
517 : WordEntry *entry;
518 : } map;
519 : } data;
520 : WordEntryPos pos;
521 : } DocRepresentation;
522 :
523 : static int
524 348 : compareDocR(const void *va, const void *vb)
525 : {
526 348 : const DocRepresentation *a = (const DocRepresentation *) va;
527 348 : const DocRepresentation *b = (const DocRepresentation *) vb;
528 :
529 348 : if (WEP_GETPOS(a->pos) == WEP_GETPOS(b->pos))
530 : {
531 36 : if (WEP_GETWEIGHT(a->pos) == WEP_GETWEIGHT(b->pos))
532 : {
533 6 : if (a->data.map.entry == b->data.map.entry)
534 6 : return 0;
535 :
536 0 : return (a->data.map.entry > b->data.map.entry) ? 1 : -1;
537 : }
538 :
539 30 : return (WEP_GETWEIGHT(a->pos) > WEP_GETWEIGHT(b->pos)) ? 1 : -1;
540 : }
541 :
542 312 : return (WEP_GETPOS(a->pos) > WEP_GETPOS(b->pos)) ? 1 : -1;
543 : }
544 :
545 : #define MAXQROPOS MAXENTRYPOS
546 : typedef struct
547 : {
548 : bool operandexists;
549 : bool reverseinsert; /* indicates insert order, true means
550 : * descending order */
551 : uint32 npos;
552 : WordEntryPos pos[MAXQROPOS];
553 : } QueryRepresentationOperand;
554 :
555 : typedef struct
556 : {
557 : TSQuery query;
558 : QueryRepresentationOperand *operandData;
559 : } QueryRepresentation;
560 :
561 : #define QR_GET_OPERAND_DATA(q, v) \
562 : ( (q)->operandData + (((QueryItem*)(v)) - GETQUERY((q)->query)) )
563 :
564 : /*
565 : * TS_execute callback for matching a tsquery operand to QueryRepresentation
566 : */
567 : static TSTernaryValue
568 1158 : checkcondition_QueryOperand(void *checkval, QueryOperand *val,
569 : ExecPhraseData *data)
570 : {
571 1158 : QueryRepresentation *qr = (QueryRepresentation *) checkval;
572 1158 : QueryRepresentationOperand *opData = QR_GET_OPERAND_DATA(qr, val);
573 :
574 1158 : if (!opData->operandexists)
575 444 : return TS_NO;
576 :
577 714 : if (data)
578 : {
579 348 : data->npos = opData->npos;
580 348 : data->pos = opData->pos;
581 348 : if (opData->reverseinsert)
582 108 : data->pos += MAXQROPOS - opData->npos;
583 : }
584 :
585 714 : return TS_YES;
586 : }
587 :
588 : typedef struct
589 : {
590 : int pos;
591 : int p;
592 : int q;
593 : DocRepresentation *begin;
594 : DocRepresentation *end;
595 : } CoverExt;
596 :
597 : static void
598 498 : resetQueryRepresentation(QueryRepresentation *qr, bool reverseinsert)
599 : {
600 : int i;
601 :
602 2016 : for (i = 0; i < qr->query->size; i++)
603 : {
604 1518 : qr->operandData[i].operandexists = false;
605 1518 : qr->operandData[i].reverseinsert = reverseinsert;
606 1518 : qr->operandData[i].npos = 0;
607 : }
608 498 : }
609 :
610 : static void
611 720 : fillQueryRepresentationData(QueryRepresentation *qr, DocRepresentation *entry)
612 : {
613 : int i;
614 : int lastPos;
615 : QueryRepresentationOperand *opData;
616 :
617 1446 : for (i = 0; i < entry->data.query.nitem; i++)
618 : {
619 726 : if (entry->data.query.items[i]->type != QI_VAL)
620 0 : continue;
621 :
622 726 : opData = QR_GET_OPERAND_DATA(qr, entry->data.query.items[i]);
623 :
624 726 : opData->operandexists = true;
625 :
626 726 : if (opData->npos == 0)
627 : {
628 660 : lastPos = (opData->reverseinsert) ? (MAXQROPOS - 1) : 0;
629 660 : opData->pos[lastPos] = entry->pos;
630 660 : opData->npos++;
631 660 : continue;
632 : }
633 :
634 132 : lastPos = opData->reverseinsert ?
635 66 : (MAXQROPOS - opData->npos) :
636 66 : (opData->npos - 1);
637 :
638 66 : if (WEP_GETPOS(opData->pos[lastPos]) != WEP_GETPOS(entry->pos))
639 : {
640 84 : lastPos = opData->reverseinsert ?
641 42 : (MAXQROPOS - 1 - opData->npos) :
642 42 : (opData->npos);
643 :
644 42 : opData->pos[lastPos] = entry->pos;
645 42 : opData->npos++;
646 : }
647 : }
648 720 : }
649 :
650 : static bool
651 324 : Cover(DocRepresentation *doc, int len, QueryRepresentation *qr, CoverExt *ext)
652 : {
653 : DocRepresentation *ptr;
654 324 : int lastpos = ext->pos;
655 324 : bool found = false;
656 :
657 : /*
658 : * since this function recurses, it could be driven to stack overflow.
659 : * (though any decent compiler will optimize away the tail-recursion.
660 : */
661 324 : check_stack_depth();
662 :
663 324 : resetQueryRepresentation(qr, false);
664 :
665 324 : ext->p = INT_MAX;
666 324 : ext->q = 0;
667 324 : ptr = doc + ext->pos;
668 :
669 : /* find upper bound of cover from current position, move up */
670 606 : while (ptr - doc < len)
671 : {
672 456 : fillQueryRepresentationData(qr, ptr);
673 :
674 456 : if (TS_execute(GETQUERY(qr->query), qr,
675 : TS_EXEC_EMPTY, checkcondition_QueryOperand))
676 : {
677 174 : if (WEP_GETPOS(ptr->pos) > ext->q)
678 : {
679 174 : ext->q = WEP_GETPOS(ptr->pos);
680 174 : ext->end = ptr;
681 174 : lastpos = ptr - doc;
682 174 : found = true;
683 : }
684 174 : break;
685 : }
686 282 : ptr++;
687 : }
688 :
689 324 : if (!found)
690 150 : return false;
691 :
692 174 : resetQueryRepresentation(qr, true);
693 :
694 174 : ptr = doc + lastpos;
695 :
696 : /* find lower bound of cover from found upper bound, move down */
697 264 : while (ptr >= doc + ext->pos)
698 : {
699 : /*
700 : * we scan doc from right to left, so pos info in reverse order!
701 : */
702 264 : fillQueryRepresentationData(qr, ptr);
703 :
704 264 : if (TS_execute(GETQUERY(qr->query), qr,
705 : TS_EXEC_EMPTY, checkcondition_QueryOperand))
706 : {
707 174 : if (WEP_GETPOS(ptr->pos) < ext->p)
708 : {
709 174 : ext->begin = ptr;
710 174 : ext->p = WEP_GETPOS(ptr->pos);
711 : }
712 174 : break;
713 : }
714 90 : ptr--;
715 : }
716 :
717 174 : if (ext->p <= ext->q)
718 : {
719 : /*
720 : * set position for next try to next lexeme after beginning of found
721 : * cover
722 : */
723 174 : ext->pos = (ptr - doc) + 1;
724 174 : return true;
725 : }
726 :
727 0 : ext->pos++;
728 0 : return Cover(doc, len, qr, ext);
729 : }
730 :
731 : static DocRepresentation *
732 156 : get_docrep(TSVector txt, QueryRepresentation *qr, int *doclen)
733 : {
734 156 : QueryItem *item = GETQUERY(qr->query);
735 : WordEntry *entry,
736 : *firstentry;
737 : WordEntryPos *post;
738 : int32 dimt, /* number of 'post' items */
739 : j,
740 : i,
741 : nitem;
742 156 : int len = qr->query->size * 4,
743 156 : cur = 0;
744 : DocRepresentation *doc;
745 :
746 156 : doc = (DocRepresentation *) palloc(sizeof(DocRepresentation) * len);
747 :
748 : /*
749 : * Iterate through query to make DocRepresentation for words and it's
750 : * entries satisfied by query
751 : */
752 636 : for (i = 0; i < qr->query->size; i++)
753 : {
754 : QueryOperand *curoperand;
755 :
756 480 : if (item[i].type != QI_VAL)
757 162 : continue;
758 :
759 318 : curoperand = &item[i].qoperand;
760 :
761 318 : firstentry = entry = find_wordentry(txt, qr->query, curoperand, &nitem);
762 318 : if (!entry)
763 6 : continue;
764 :
765 : /* iterations over entries in tsvector */
766 654 : while (entry - firstentry < nitem)
767 : {
768 342 : if (entry->haspos)
769 : {
770 330 : dimt = POSDATALEN(txt, entry);
771 330 : post = POSDATAPTR(txt, entry);
772 : }
773 : else
774 : {
775 : /* ignore words without positions */
776 12 : entry++;
777 12 : continue;
778 : }
779 :
780 330 : while (cur + dimt >= len)
781 : {
782 0 : len *= 2;
783 0 : doc = (DocRepresentation *) repalloc(doc, sizeof(DocRepresentation) * len);
784 : }
785 :
786 : /* iterations over entry's positions */
787 714 : for (j = 0; j < dimt; j++)
788 : {
789 384 : if (curoperand->weight == 0 ||
790 30 : curoperand->weight & (1 << WEP_GETWEIGHT(post[j])))
791 : {
792 372 : doc[cur].pos = post[j];
793 372 : doc[cur].data.map.entry = entry;
794 372 : doc[cur].data.map.item = (QueryItem *) curoperand;
795 372 : cur++;
796 : }
797 : }
798 :
799 330 : entry++;
800 : }
801 : }
802 :
803 156 : if (cur > 0)
804 : {
805 150 : DocRepresentation *rptr = doc + 1,
806 150 : *wptr = doc,
807 : storage;
808 :
809 : /*
810 : * Sort representation in ascending order by pos and entry
811 : */
812 150 : qsort(doc, cur, sizeof(DocRepresentation), compareDocR);
813 :
814 : /*
815 : * Join QueryItem per WordEntry and its position
816 : */
817 150 : storage.pos = doc->pos;
818 150 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
819 150 : storage.data.query.items[0] = doc->data.map.item;
820 150 : storage.data.query.nitem = 1;
821 :
822 372 : while (rptr - doc < cur)
823 : {
824 222 : if (rptr->pos == (rptr - 1)->pos &&
825 6 : rptr->data.map.entry == (rptr - 1)->data.map.entry)
826 : {
827 6 : storage.data.query.items[storage.data.query.nitem] = rptr->data.map.item;
828 6 : storage.data.query.nitem++;
829 : }
830 : else
831 : {
832 216 : *wptr = storage;
833 216 : wptr++;
834 216 : storage.pos = rptr->pos;
835 216 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
836 216 : storage.data.query.items[0] = rptr->data.map.item;
837 216 : storage.data.query.nitem = 1;
838 : }
839 :
840 222 : rptr++;
841 : }
842 :
843 150 : *wptr = storage;
844 150 : wptr++;
845 :
846 150 : *doclen = wptr - doc;
847 150 : return doc;
848 : }
849 :
850 6 : pfree(doc);
851 6 : return NULL;
852 : }
853 :
854 : static float4
855 156 : calc_rank_cd(const float4 *arrdata, TSVector txt, TSQuery query, int method)
856 : {
857 : DocRepresentation *doc;
858 : int len,
859 : i,
860 156 : doclen = 0;
861 : CoverExt ext;
862 156 : double Wdoc = 0.0;
863 : double invws[NUM_WEIGHTS];
864 156 : double SumDist = 0.0,
865 156 : PrevExtPos = 0.0;
866 156 : int NExtent = 0;
867 : QueryRepresentation qr;
868 :
869 :
870 780 : for (i = 0; i < NUM_WEIGHTS; i++)
871 : {
872 624 : invws[i] = ((double) ((arrdata[i] >= 0) ? arrdata[i] : default_weights[i]));
873 624 : if (invws[i] > 1.0)
874 0 : ereport(ERROR,
875 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
876 : errmsg("weight out of range")));
877 624 : invws[i] = 1.0 / invws[i];
878 : }
879 :
880 156 : qr.query = query;
881 156 : qr.operandData = (QueryRepresentationOperand *)
882 156 : palloc0(sizeof(QueryRepresentationOperand) * query->size);
883 :
884 156 : doc = get_docrep(txt, &qr, &doclen);
885 156 : if (!doc)
886 : {
887 6 : pfree(qr.operandData);
888 6 : return 0.0;
889 : }
890 :
891 750 : MemSet(&ext, 0, sizeof(CoverExt));
892 324 : while (Cover(doc, doclen, &qr, &ext))
893 : {
894 174 : double Cpos = 0.0;
895 174 : double InvSum = 0.0;
896 : double CurExtPos;
897 : int nNoise;
898 174 : DocRepresentation *ptr = ext.begin;
899 :
900 438 : while (ptr <= ext.end)
901 : {
902 264 : InvSum += invws[WEP_GETWEIGHT(ptr->pos)];
903 264 : ptr++;
904 : }
905 :
906 174 : Cpos = ((double) (ext.end - ext.begin + 1)) / InvSum;
907 :
908 : /*
909 : * if doc are big enough then ext.q may be equal to ext.p due to limit
910 : * of positional information. In this case we approximate number of
911 : * noise word as half cover's length
912 : */
913 174 : nNoise = (ext.q - ext.p) - (ext.end - ext.begin);
914 174 : if (nNoise < 0)
915 0 : nNoise = (ext.end - ext.begin) / 2;
916 174 : Wdoc += Cpos / ((double) (1 + nNoise));
917 :
918 174 : CurExtPos = ((double) (ext.q + ext.p)) / 2.0;
919 174 : if (NExtent > 0 && CurExtPos > PrevExtPos /* prevent division by
920 : * zero in a case of
921 : * multiple lexize */ )
922 42 : SumDist += 1.0 / (CurExtPos - PrevExtPos);
923 :
924 174 : PrevExtPos = CurExtPos;
925 174 : NExtent++;
926 : }
927 :
928 150 : if ((method & RANK_NORM_LOGLENGTH) && txt->size > 0)
929 0 : Wdoc /= log((double) (cnt_length(txt) + 1));
930 :
931 150 : if (method & RANK_NORM_LENGTH)
932 : {
933 0 : len = cnt_length(txt);
934 0 : if (len > 0)
935 0 : Wdoc /= (double) len;
936 : }
937 :
938 150 : if ((method & RANK_NORM_EXTDIST) && NExtent > 0 && SumDist > 0)
939 0 : Wdoc /= ((double) NExtent) / SumDist;
940 :
941 150 : if ((method & RANK_NORM_UNIQ) && txt->size > 0)
942 0 : Wdoc /= (double) (txt->size);
943 :
944 150 : if ((method & RANK_NORM_LOGUNIQ) && txt->size > 0)
945 0 : Wdoc /= log((double) (txt->size + 1)) / log(2.0);
946 :
947 150 : if (method & RANK_NORM_RDIVRPLUS1)
948 0 : Wdoc /= (Wdoc + 1);
949 :
950 150 : pfree(doc);
951 :
952 150 : pfree(qr.operandData);
953 :
954 150 : return (float4) Wdoc;
955 : }
956 :
957 : Datum
958 0 : ts_rankcd_wttf(PG_FUNCTION_ARGS)
959 : {
960 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
961 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
962 0 : TSQuery query = PG_GETARG_TSQUERY(2);
963 0 : int method = PG_GETARG_INT32(3);
964 : float weights[NUM_WEIGHTS];
965 : float res;
966 :
967 0 : getWeights(win, weights);
968 0 : res = calc_rank_cd(weights, txt, query, method);
969 :
970 0 : PG_FREE_IF_COPY(win, 0);
971 0 : PG_FREE_IF_COPY(txt, 1);
972 0 : PG_FREE_IF_COPY(query, 2);
973 0 : PG_RETURN_FLOAT4(res);
974 : }
975 :
976 : Datum
977 0 : ts_rankcd_wtt(PG_FUNCTION_ARGS)
978 : {
979 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
980 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
981 0 : TSQuery query = PG_GETARG_TSQUERY(2);
982 : float weights[NUM_WEIGHTS];
983 : float res;
984 :
985 0 : getWeights(win, weights);
986 0 : res = calc_rank_cd(weights, txt, query, DEF_NORM_METHOD);
987 :
988 0 : PG_FREE_IF_COPY(win, 0);
989 0 : PG_FREE_IF_COPY(txt, 1);
990 0 : PG_FREE_IF_COPY(query, 2);
991 0 : PG_RETURN_FLOAT4(res);
992 : }
993 :
994 : Datum
995 0 : ts_rankcd_ttf(PG_FUNCTION_ARGS)
996 : {
997 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
998 0 : TSQuery query = PG_GETARG_TSQUERY(1);
999 0 : int method = PG_GETARG_INT32(2);
1000 : float res;
1001 :
1002 0 : res = calc_rank_cd(default_weights, txt, query, method);
1003 :
1004 0 : PG_FREE_IF_COPY(txt, 0);
1005 0 : PG_FREE_IF_COPY(query, 1);
1006 0 : PG_RETURN_FLOAT4(res);
1007 : }
1008 :
1009 : Datum
1010 156 : ts_rankcd_tt(PG_FUNCTION_ARGS)
1011 : {
1012 156 : TSVector txt = PG_GETARG_TSVECTOR(0);
1013 156 : TSQuery query = PG_GETARG_TSQUERY(1);
1014 : float res;
1015 :
1016 156 : res = calc_rank_cd(default_weights, txt, query, DEF_NORM_METHOD);
1017 :
1018 156 : PG_FREE_IF_COPY(txt, 0);
1019 156 : PG_FREE_IF_COPY(query, 1);
1020 156 : PG_RETURN_FLOAT4(res);
1021 : }
|
