ts-typanalyze-fix.patch

*** src/backend/tsearch/ts_typanalyze.c
--- src/backend/tsearch/ts_typanalyze.c	2010-05-30 19:52:28.000000000 +0200
***************
*** 92,112 ****
   *	http://www.vldb.org/conf/2002/S10P03.pdf
   *
   *	The Lossy Counting (aka LC) algorithm goes like this:
!  *	Let D be a set of triples (e, f, d), where e is an element value, f is
!  *	that element's frequency (occurrence count) and d is the maximum error in
!  *	f.	We start with D empty and process the elements in batches of size
!  *	w. (The batch size is also known as "bucket size".) Let the current batch
!  *	number be b_current, starting with 1. For each element e we either
!  *	increment its f count, if it's already in D, or insert a new triple into D
!  *	with values (e, 1, b_current - 1). After processing each batch we prune D,
!  *	by removing from it all elements with f + d <= b_current. Finally, we
!  *	gather elements with largest f.  The LC paper proves error bounds on f
!  *	dependent on the batch size w, and shows that the required table size
!  *	is no more than a few times w.
   *
!  *	We use a hashtable for the D structure and a bucket width of
!  *	statistics_target * 10, where 10 is an arbitrarily chosen constant,
!  *	meant to approximate the number of lexemes in a single tsvector.
   */
  static void
  compute_tsvector_stats(VacAttrStats *stats,
--- 92,126 ----
   *	http://www.vldb.org/conf/2002/S10P03.pdf
   *
   *	The Lossy Counting (aka LC) algorithm goes like this:
! 
!  *  Let s be a threshold frequency for an item and epsilon the error margin for
!  *  the frequency. Let D be a set of triples (e, f, d), where e is an element
!  *  value, f is that element's frequency (occurrence count) and d is the maximum
!  *  error in f. We start with D empty and process the elements in batches of
!  *  size w. (The batch size is also known as "bucket size" and is equal to
!  *  1/epsilon.) Let the current batch number be b_current, starting with 1. For
!  *  each element e we either increment its f count, if it's already in D, or
!  *  insert a new triple into D with values (e, 1, b_current - 1). After
!  *  processing each batch we prune D, by removing from it all elements with f +
!  *  d <= b_current.  After the algorithm finishes we suppress all elements from
!  *  D that do not satisfy f >= (s - e) * N, where N is the total number of
!  *  lexemes in the input.  The LC paper proves error bounds on f dependent on
!  *  the batch size w, and shows that the required table size is no more than a
!  *  few times w.
!  *
!  *  We set s to be the estimated frequency of the K'th word in a natural
!  *  language's frequency table, where K is the target number of entries in the
!  *  MCELEM array plus an arbitrary constant, meant to reflect the fact that the
!  *  top words in any language would usually be stopwords and we will not ever
!  *  see them in the input.  We assume that the distribution of word frequencies
!  *  follows Zipf's law with an exponent of 1.
   *
!  *  Assuming Zipfian distribution, thet frequency of the K'th element is equal
!  *  to 1/(K * H(W)) where H(n) is 1/2 + 1/3 + ... + 1/n and W is the number of
!  *  words in the language.  Putting one million as W, we get roughly 0.07/K,
!  *  assuming top 10 words are stopwords gives s = 0.07/(K + 10).  We set epsilon
!  *  to s/10 = 0.007/(K + 10), which gives a bucket width of (K + 10)/0.007 and
!  *  use a hashtable for the D structure.
   */
  static void
  compute_tsvector_stats(VacAttrStats *stats,
***************
*** 114,120 ****
  					   int samplerows,
  					   double totalrows)
  {
! 	int			num_mcelem;
  	int			null_cnt = 0;
  	double		total_width = 0;
  
--- 128,134 ----
  					   int samplerows,
  					   double totalrows)
  {
! 	int			num_mcelem = stats->attr->attstattarget;
  	int			null_cnt = 0;
  	double		total_width = 0;
  
***************
*** 133,147 ****
  	LexemeHashKey hash_key;
  	TrackItem  *item;
  
- 	/* We want statistics_target * 10 lexemes in the MCELEM array */
- 	num_mcelem = stats->attr->attstattarget * 10;
- 
  	/*
! 	 * We set bucket width equal to the target number of result lexemes. This
! 	 * is probably about right but perhaps might need to be scaled up or down
! 	 * a bit?
  	 */
! 	bucket_width = num_mcelem;
  
  	/*
  	 * Create the hashtable. It will be in local memory, so we don't need to
--- 147,157 ----
  	LexemeHashKey hash_key;
  	TrackItem  *item;
  
  	/*
! 	 * We set bucket width equal to (stats target + 10) / 0.007 as per the
! 	 * comment above.
  	 */
! 	bucket_width = (num_mcelem + 10) * 1000 / 7;
  
  	/*
  	 * Create the hashtable. It will be in local memory, so we don't need to
***************
*** 252,257 ****
--- 262,268 ----
  		int			i;
  		TrackItem **sort_table;
  		int			track_len;
+ 		int			cutoff_freq;
  		int			minfreq,
  					maxfreq;
  
***************
*** 282,291 ****
  		qsort(sort_table, track_len, sizeof(TrackItem *),
  			  trackitem_compare_frequencies_desc);
  
! 		/* Suppress any single-occurrence items */
  		while (track_len > 0)
  		{
! 			if (sort_table[track_len - 1]->frequency > 1)
  				break;
  			track_len--;
  		}
--- 293,307 ----
  		qsort(sort_table, track_len, sizeof(TrackItem *),
  			  trackitem_compare_frequencies_desc);
  
! 		/*
! 		 * Suppress any items will less occurrences than (s - epsilon)N. Since
! 		 * epsilon = s/10 and bucket_width = 1/epsilon, the cutoff frequency is
! 		 * 9*N / bucket_width
! 		 */
! 		cutoff_freq = 9 * lexeme_no / bucket_width;
  		while (track_len > 0)
  		{
! 			if (sort_table[track_len - 1]->frequency > cutoff_freq)
  				break;
  			track_len--;
  		}