<commit_before>/*-------------------------------------------------------------------------
 *
 * ts_typanalyze.c
 *	  functions for gathering statistics from tsvector columns
 *
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/tsearch/ts_typanalyze.c,v 1.4 2008/12/13 19:13:44 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/hash.h"
#include "catalog/pg_operator.h"
#include "commands/vacuum.h"
#include "tsearch/ts_type.h"
#include "utils/builtins.h"
#include "utils/hsearch.h"


/* A hash key for lexemes */
typedef struct
{
	char	   *lexeme;			/* lexeme (not NULL terminated!) */
	int			length;			/* its length in bytes */
} LexemeHashKey;

/* A hash table entry for the Lossy Counting algorithm */
typedef struct
{
	LexemeHashKey	key;		/* This is 'e' from the LC algorithm. */
	int				frequency;	/* This is 'f'. */
	int				delta;		/* And this is 'delta'. */
} TrackItem;

static void compute_tsvector_stats(VacAttrStats *stats,
								   AnalyzeAttrFetchFunc fetchfunc,
								   int samplerows,
								   double totalrows);
static void prune_lexemes_hashtable(HTAB *lexemes_tab, int b_current);
static uint32 lexeme_hash(const void *key, Size keysize);
static int lexeme_match(const void *key1, const void *key2, Size keysize);
static int lexeme_compare(const void *key1, const void *key2);
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
static int trackitem_compare_lexemes(const void *e1, const void *e2);


/*
 *	ts_typanalyze -- a custom typanalyze function for tsvector columns
 */
Datum
ts_typanalyze(PG_FUNCTION_ARGS)
{
	VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
	Form_pg_attribute attr = stats->attr;

	/* If the attstattarget column is negative, use the default value */
	/* NB: it is okay to scribble on stats->attr since it's a copy */
	if (attr->attstattarget < 0)
		attr->attstattarget = default_statistics_target;

	stats->compute_stats = compute_tsvector_stats;
	/* see comment about the choice of minrows in commands/analyze.c */
	stats->minrows = 300 * attr->attstattarget;

	PG_RETURN_BOOL(true);
}

/*
 *	compute_tsvector_stats() -- compute statistics for a tsvector column
 *
 *	This functions computes statistics that are useful for determining @@
 *	operations' selectivity, along with the fraction of non-null rows and
 *	average width.
 *
 *	Instead of finding the most common values, as we do for most datatypes,
 *	we're looking for the most common lexemes. This is more useful, because
 *	there most probably won't be any two rows with the same tsvector and thus
 *	the notion of a MCV is a bit bogus with this datatype. With a list of the
 *	most common lexemes we can do a better job at figuring out @@ selectivity.
 *
 *	For the same reasons we assume that tsvector columns are unique when
 *	determining the number of distinct values.
 *
 *	The algorithm used is Lossy Counting, as proposed in the paper "Approximate
 *	frequency counts over data streams" by <NAME> and <NAME>, in
 *	Proceedings of the 28th International Conference on Very Large Data Bases,
 *	Hong Kong, China, August 2002, section 4.2. The paper is available at
 *	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 * 100, where 100 is an arbitrarily chosen constant,
 *	meant to approximate the number of lexemes in a single tsvector.
 */
static void
compute_tsvector_stats(VacAttrStats *stats,
					   AnalyzeAttrFetchFunc fetchfunc,
					   int samplerows,
					   double totalrows)
{
	int				num_mcelem;
	int				null_cnt = 0;
	double			total_width = 0;
	/* This is D from the LC algorithm. */
	HTAB			*lexemes_tab;
	HASHCTL			hash_ctl;
	HASH_SEQ_STATUS	scan_status;
	/* This is the current bucket number from the LC algorithm */
	int				b_current;
	/* This is 'w' from the LC algorithm */
	int				bucket_width;
	int vector_no,
		lexeme_no;
	LexemeHashKey 	hash_key;
	TrackItem		*item;

	/* We want statistics_target * 100 lexemes in the MCELEM array */
	num_mcelem = stats->attr->attstattarget * 100;

	/*
	 * 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
	 * worry about initial size too much. Also we don't need to pay any
	 * attention to locking and memory management.
	 */
	MemSet(&hash_ctl, 0, sizeof(hash_ctl));
	hash_ctl.keysize = sizeof(LexemeHashKey);
	hash_ctl.entrysize = sizeof(TrackItem);
	hash_ctl.hash = lexeme_hash;
	hash_ctl.match = lexeme_match;
	hash_ctl.hcxt = CurrentMemoryContext;
	lexemes_tab = hash_create("Analyzed lexemes table",
							  bucket_width * 4,
							  &hash_ctl,
							  HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

	/* Initialize counters. */<commit_msg>Reduce the scaling factor for attstattarget to number-of-lexemes from 100 to 10, to compensate for the recent change in default statistics target. The original number was pulled out of the air anyway :-(, but it was picked in the context of the old default, so holding the default size of the MCELEM array constant seems the best thing.  Per discussion.<commit_after>/*-------------------------------------------------------------------------
 *
 * ts_typanalyze.c
 *	  functions for gathering statistics from tsvector columns
 *
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/tsearch/ts_typanalyze.c,v 1.5 2008/12/15 15:06:31 tgl Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/hash.h"
#include "catalog/pg_operator.h"
#include "commands/vacuum.h"
#include "tsearch/ts_type.h"
#include "utils/builtins.h"
#include "utils/hsearch.h"


/* A hash key for lexemes */
typedef struct
{
	char	   *lexeme;			/* lexeme (not NULL terminated!) */
	int			length;			/* its length in bytes */
} LexemeHashKey;

/* A hash table entry for the Lossy Counting algorithm */
typedef struct
{
	LexemeHashKey	key;		/* This is 'e' from the LC algorithm. */
	int				frequency;	/* This is 'f'. */
	int				delta;		/* And this is 'delta'. */
} TrackItem;

static void compute_tsvector_stats(VacAttrStats *stats,
								   AnalyzeAttrFetchFunc fetchfunc,
								   int samplerows,
								   double totalrows);
static void prune_lexemes_hashtable(HTAB *lexemes_tab, int b_current);
static uint32 lexeme_hash(const void *key, Size keysize);
static int lexeme_match(const void *key1, const void *key2, Size keysize);
static int lexeme_compare(const void *key1, const void *key2);
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
static int trackitem_compare_lexemes(const void *e1, const void *e2);


/*
 *	ts_typanalyze -- a custom typanalyze function for tsvector columns
 */
Datum
ts_typanalyze(PG_FUNCTION_ARGS)
{
	VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
	Form_pg_attribute attr = stats->attr;

	/* If the attstattarget column is negative, use the default value */
	/* NB: it is okay to scribble on stats->attr since it's a copy */
	if (attr->attstattarget < 0)
		attr->attstattarget = default_statistics_target;

	stats->compute_stats = compute_tsvector_stats;
	/* see comment about the choice of minrows in commands/analyze.c */
	stats->minrows = 300 * attr->attstattarget;

	PG_RETURN_BOOL(true);
}

/*
 *	compute_tsvector_stats() -- compute statistics for a tsvector column
 *
 *	This functions computes statistics that are useful for determining @@
 *	operations' selectivity, along with the fraction of non-null rows and
 *	average width.
 *
 *	Instead of finding the most common values, as we do for most datatypes,
 *	we're looking for the most common lexemes. This is more useful, because
 *	there most probably won't be any two rows with the same tsvector and thus
 *	the notion of a MCV is a bit bogus with this datatype. With a list of the
 *	most common lexemes we can do a better job at figuring out @@ selectivity.
 *
 *	For the same reasons we assume that tsvector columns are unique when
 *	determining the number of distinct values.
 *
 *	The algorithm used is Lossy Counting, as proposed in the paper "Approximate
 *	frequency counts over data streams" by <NAME> and <NAME>, in
 *	Proceedings of the 28th International Conference on Very Large Data Bases,
 *	Hong Kong, China, August 2002, section 4.2. The paper is available at
 *	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,
					   AnalyzeAttrFetchFunc fetchfunc,
					   int samplerows,
					   double totalrows)
{
	int				num_mcelem;
	int				null_cnt = 0;
	double			total_width = 0;
	/* This is D from the LC algorithm. */
	HTAB			*lexemes_tab;
	HASHCTL			hash_ctl;
	HASH_SEQ_STATUS	scan_status;
	/* This is the current bucket number from the LC algorithm */
	int				b_current;
	/* This is 'w' from the LC algorithm */
	int				bucket_width;
	int vector_no,
		lexeme_no;
	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
	 * worry about initial size too much. Also we don't need to pay any
	 * attention to locking and memory management.
	 */
	MemSet(&hash_ctl, 0, sizeof(hash_ctl));
	hash_ctl.keysize = sizeof(LexemeHashKey);
	hash_ctl.entrysize = sizeof(TrackItem);
	hash_ctl.hash = lexeme_hash;
	hash_ctl.match = lexeme_match;
	hash_ctl.hcxt = CurrentMemoryContext;
	lexemes_tab = hash_create("Analyzed lexemes table",
							  bucket_width * 4,
							  &hash_ctl,
							  HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

	/* Initialize counters. */
{'fraction_non_alphanumeric': 0.10398083911463495, 'fraction_numerical': 0.012305913445655764, 'mean_word_length': 3.320014270424545, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1669595', 'n_tokens_mistral': 4154, 'n_tokens_neox': 3735, 'n_words': 1490}