1 /*-------------------------------------------------------------------------
4 * functions for gathering statistics from tsvector columns
6 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
12 *-------------------------------------------------------------------------
16 #include "access/hash.h"
17 #include "catalog/pg_operator.h"
18 #include "commands/vacuum.h"
19 #include "tsearch/ts_type.h"
20 #include "utils/builtins.h"
21 #include "utils/hsearch.h"
24 /* A hash key for lexemes */
27 char *lexeme
; /* lexeme (not NULL terminated!) */
28 int length
; /* its length in bytes */
31 /* A hash table entry for the Lossy Counting algorithm */
34 LexemeHashKey key
; /* This is 'e' from the LC algorithm. */
35 int frequency
; /* This is 'f'. */
36 int delta
; /* And this is 'delta'. */
39 static void compute_tsvector_stats(VacAttrStats
*stats
,
40 AnalyzeAttrFetchFunc fetchfunc
,
43 static void prune_lexemes_hashtable(HTAB
*lexemes_tab
, int b_current
);
44 static uint32
lexeme_hash(const void *key
, Size keysize
);
45 static int lexeme_match(const void *key1
, const void *key2
, Size keysize
);
46 static int trackitem_compare_desc(const void *e1
, const void *e2
);
50 * ts_typanalyze -- a custom typanalyze function for tsvector columns
53 ts_typanalyze(PG_FUNCTION_ARGS
)
55 VacAttrStats
*stats
= (VacAttrStats
*) PG_GETARG_POINTER(0);
56 Form_pg_attribute attr
= stats
->attr
;
58 /* If the attstattarget column is negative, use the default value */
59 /* NB: it is okay to scribble on stats->attr since it's a copy */
60 if (attr
->attstattarget
< 0)
61 attr
->attstattarget
= default_statistics_target
;
63 stats
->compute_stats
= compute_tsvector_stats
;
64 /* see comment about the choice of minrows from analyze.c */
65 stats
->minrows
= 300 * attr
->attstattarget
;
71 * compute_tsvector_stats() -- compute statistics for a tsvector column
73 * This functions computes statistics that are useful for determining @@
74 * operations' selectivity, along with the fraction of non-null rows and
77 * Instead of finding the most common values, as we do for most datatypes,
78 * we're looking for the most common lexemes. This is more useful, because
79 * there most probably won't be any two rows with the same tsvector and thus
80 * the notion of a MCV is a bit bogus with this datatype. With a list of the
81 * most common lexemes we can do a better job at figuring out @@ selectivity.
83 * For the same reasons we assume that tsvector columns are unique when
84 * determining the number of distinct values.
86 * The algorithm used is Lossy Counting, as proposed in the paper "Approximate
87 * frequency counts over data streams" by G. S. Manku and R. Motwani, in
88 * Proceedings of the 28th International Conference on Very Large Data Bases,
89 * Hong Kong, China, August 2002, section 4.2. The paper is available at
90 * http://www.vldb.org/conf/2002/S10P03.pdf
92 * The Lossy Counting (aka LC) algorithm goes like this:
93 * Let D be a set of triples (e, f, d), where e is an element value, f is
94 * that element's frequency (occurrence count) and d is the maximum error in
95 * f. We start with D empty and process the elements in batches of size
96 * w. (The batch size is also known as "bucket size".) Let the current batch
97 * number be b_current, starting with 1. For each element e we either
98 * increment its f count, if it's already in D, or insert a new triple into D
99 * with values (e, 1, b_current - 1). After processing each batch we prune D,
100 * by removing from it all elements with f + d <= b_current. Finally, we
101 * gather elements with largest f. The LC paper proves error bounds on f
102 * dependent on the batch size w, and shows that the required table size
103 * is no more than a few times w.
105 * We use a hashtable for the D structure and a bucket width of
106 * statistic_target * 100, where 100 is an arbitrarily chosen constant, meant
107 * to approximate the number of lexemes in a single tsvector.
110 compute_tsvector_stats(VacAttrStats
*stats
,
111 AnalyzeAttrFetchFunc fetchfunc
,
117 double total_width
= 0;
118 /* This is D from the LC algorithm. */
121 HASH_SEQ_STATUS scan_status
;
122 /* This is the current bucket number from the LC algorithm */
124 /* This is 'w' from the LC algorithm */
128 LexemeHashKey hash_key
;
131 /* We want statistic_target * 100 lexemes in the MCELEM array */
132 num_mcelem
= stats
->attr
->attstattarget
* 100;
135 * We set bucket width equal to the target number of result lexemes.
136 * This is probably about right but perhaps might need to be scaled
139 bucket_width
= num_mcelem
;
142 * Create the hashtable. It will be in local memory, so we don't need to
143 * worry about initial size too much. Also we don't need to pay any
144 * attention to locking and memory management.
146 MemSet(&hash_ctl
, 0, sizeof(hash_ctl
));
147 hash_ctl
.keysize
= sizeof(LexemeHashKey
);
148 hash_ctl
.entrysize
= sizeof(TrackItem
);
149 hash_ctl
.hash
= lexeme_hash
;
150 hash_ctl
.match
= lexeme_match
;
151 hash_ctl
.hcxt
= CurrentMemoryContext
;
152 lexemes_tab
= hash_create("Analyzed lexemes table",
155 HASH_ELEM
| HASH_FUNCTION
| HASH_COMPARE
| HASH_CONTEXT
);
157 /* Initialize counters. */
161 /* Loop over the tsvectors. */
162 for (vector_no
= 0; vector_no
< samplerows
; vector_no
++)
167 WordEntry
*curentryptr
;
171 vacuum_delay_point();
173 value
= fetchfunc(stats
, vector_no
, &isnull
);
176 * Check for null/nonnull.
185 * Add up widths for average-width calculation. Since it's a
186 * tsvector, we know it's varlena. As in the regular
187 * compute_minimal_stats function, we use the toasted width for this
190 total_width
+= VARSIZE_ANY(DatumGetPointer(value
));
193 * Now detoast the tsvector if needed.
195 vector
= DatumGetTSVector(value
);
198 * We loop through the lexemes in the tsvector and add them to our
199 * tracking hashtable. Note: the hashtable entries will point into
200 * the (detoasted) tsvector value, therefore we cannot free that
201 * storage until we're done.
203 lexemesptr
= STRPTR(vector
);
204 curentryptr
= ARRPTR(vector
);
205 for (j
= 0; j
< vector
->size
; j
++)
209 /* Construct a hash key */
210 hash_key
.lexeme
= lexemesptr
+ curentryptr
->pos
;
211 hash_key
.length
= curentryptr
->len
;
213 /* Lookup current lexeme in hashtable, adding it if new */
214 item
= (TrackItem
*) hash_search(lexemes_tab
,
215 (const void *) &hash_key
,
220 /* The lexeme is already on the tracking list */
225 /* Initialize new tracking list element */
227 item
->delta
= b_current
- 1;
230 /* We prune the D structure after processing each bucket */
231 if (lexeme_no
% bucket_width
== 0)
233 prune_lexemes_hashtable(lexemes_tab
, b_current
);
237 /* Advance to the next WordEntry in the tsvector */
243 /* We can only compute real stats if we found some non-null values. */
244 if (null_cnt
< samplerows
)
246 int nonnull_cnt
= samplerows
- null_cnt
;
248 TrackItem
**sort_table
;
251 stats
->stats_valid
= true;
252 /* Do the simple null-frac and average width stats */
253 stats
->stanullfrac
= (double) null_cnt
/ (double) samplerows
;
254 stats
->stawidth
= total_width
/ (double) nonnull_cnt
;
256 /* Assume it's a unique column (see notes above) */
257 stats
->stadistinct
= -1.0;
260 * Determine the top-N lexemes by simply copying pointers from the
261 * hashtable into an array and applying qsort()
263 track_len
= hash_get_num_entries(lexemes_tab
);
265 sort_table
= (TrackItem
**) palloc(sizeof(TrackItem
*) * track_len
);
267 hash_seq_init(&scan_status
, lexemes_tab
);
269 while ((item
= (TrackItem
*) hash_seq_search(&scan_status
)) != NULL
)
271 sort_table
[i
++] = item
;
273 Assert(i
== track_len
);
275 qsort(sort_table
, track_len
, sizeof(TrackItem
*),
276 trackitem_compare_desc
);
278 /* Suppress any single-occurrence items */
279 while (track_len
> 0)
281 if (sort_table
[track_len
-1]->frequency
> 1)
286 /* Determine the number of most common lexemes to be stored */
287 if (num_mcelem
> track_len
)
288 num_mcelem
= track_len
;
290 /* Generate MCELEM slot entry */
293 MemoryContext old_context
;
294 Datum
*mcelem_values
;
295 float4
*mcelem_freqs
;
297 /* Must copy the target values into anl_context */
298 old_context
= MemoryContextSwitchTo(stats
->anl_context
);
299 mcelem_values
= (Datum
*) palloc(num_mcelem
* sizeof(Datum
));
300 mcelem_freqs
= (float4
*) palloc(num_mcelem
* sizeof(float4
));
302 for (i
= 0; i
< num_mcelem
; i
++)
304 TrackItem
*item
= sort_table
[i
];
307 PointerGetDatum(cstring_to_text_with_len(item
->key
.lexeme
,
309 mcelem_freqs
[i
] = (double) item
->frequency
/ (double) nonnull_cnt
;
311 MemoryContextSwitchTo(old_context
);
313 stats
->stakind
[0] = STATISTIC_KIND_MCELEM
;
314 stats
->staop
[0] = TextEqualOperator
;
315 stats
->stanumbers
[0] = mcelem_freqs
;
316 stats
->numnumbers
[0] = num_mcelem
;
317 stats
->stavalues
[0] = mcelem_values
;
318 stats
->numvalues
[0] = num_mcelem
;
319 /* We are storing text values */
320 stats
->statypid
[0] = TEXTOID
;
321 stats
->statyplen
[0] = -1; /* typlen, -1 for varlena */
322 stats
->statypbyval
[0] = false;
323 stats
->statypalign
[0] = 'i';
328 /* We found only nulls; assume the column is entirely null */
329 stats
->stats_valid
= true;
330 stats
->stanullfrac
= 1.0;
331 stats
->stawidth
= 0; /* "unknown" */
332 stats
->stadistinct
= 0.0; /* "unknown" */
336 * We don't need to bother cleaning up any of our temporary palloc's.
337 * The hashtable should also go away, as it used a child memory context.
342 * A function to prune the D structure from the Lossy Counting algorithm.
343 * Consult compute_tsvector_stats() for wider explanation.
346 prune_lexemes_hashtable(HTAB
*lexemes_tab
, int b_current
)
348 HASH_SEQ_STATUS scan_status
;
351 hash_seq_init(&scan_status
, lexemes_tab
);
352 while ((item
= (TrackItem
*) hash_seq_search(&scan_status
)) != NULL
)
354 if (item
->frequency
+ item
->delta
<= b_current
)
356 if (hash_search(lexemes_tab
, (const void *) &item
->key
,
357 HASH_REMOVE
, NULL
) == NULL
)
358 elog(ERROR
, "hash table corrupted");
364 * Hash functions for lexemes. They are strings, but not NULL terminated,
365 * so we need a special hash function.
368 lexeme_hash(const void *key
, Size keysize
)
370 const LexemeHashKey
*l
= (const LexemeHashKey
*) key
;
372 return DatumGetUInt32(hash_any((const unsigned char *) l
->lexeme
,
377 * Matching function for lexemes, to be used in hashtable lookups.
380 lexeme_match(const void *key1
, const void *key2
, Size keysize
)
382 const LexemeHashKey
*d1
= (const LexemeHashKey
*) key1
;
383 const LexemeHashKey
*d2
= (const LexemeHashKey
*) key2
;
385 /* The lexemes need to have the same length, and be memcmp-equal */
386 if (d1
->length
== d2
->length
&&
387 memcmp(d1
->lexeme
, d2
->lexeme
, d1
->length
) == 0)
394 * qsort() comparator for TrackItems - LC style (descending sort)
397 trackitem_compare_desc(const void *e1
, const void *e2
)
399 const TrackItem
* const *t1
= (const TrackItem
* const *) e1
;
400 const TrackItem
* const *t2
= (const TrackItem
* const *) e2
;
402 return (*t2
)->frequency
- (*t1
)->frequency
;