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