analyze.c

来自「PostgreSQL7.4.6 for Linux」· C语言 代码 · 共 1,819 行 · 第 1/4 页

		/* Seems to be a scalar datatype */
		stats->algcode = ALG_SCALAR;
		/*--------------------
		 * The following choice of minrows is based on the paper
		 * "Random sampling for histogram construction: how much is enough?"
		 * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
		 * Proceedings of ACM SIGMOD International Conference on Management
		 * of Data, 1998, Pages 436-447.  Their Corollary 1 to Theorem 5
		 * says that for table size n, histogram size k, maximum relative
		 * error in bin size f, and error probability gamma, the minimum
		 * random sample size is
		 *		r = 4 * k * ln(2*n/gamma) / f^2
		 * Taking f = 0.5, gamma = 0.01, n = 1 million rows, we obtain
		 *		r = 305.82 * k
		 * Note that because of the log function, the dependence on n is
		 * quite weak; even at n = 1 billion, a 300*k sample gives <= 0.59
		 * bin size error with probability 0.99.  So there's no real need to
		 * scale for n, which is a good thing because we don't necessarily
		 * know it at this point.
		 *--------------------
		 */
		stats->minrows = 300 * stats->attr->attstattarget;
	}
	else
	{
		/* Can't do much but the minimal stuff */
		stats->algcode = ALG_MINIMAL;
		/* Might as well use the same minrows as above */
		stats->minrows = 300 * stats->attr->attstattarget;
	}

	return stats;
}

/*
 * acquire_sample_rows -- acquire a random sample of rows from the table
 *
 * Up to targrows rows are collected (if there are fewer than that many
 * rows in the table, all rows are collected).	When the table is larger
 * than targrows, a truly random sample is collected: every row has an
 * equal chance of ending up in the final sample.
 *
 * We also estimate the total number of rows in the table, and return that
 * into *totalrows.
 *
 * The returned list of tuples is in order by physical position in the table.
 * (We will rely on this later to derive correlation estimates.)
 */
static int
acquire_sample_rows(Relation onerel, HeapTuple *rows, int targrows,
					double *totalrows)
{
	int			numrows = 0;
	HeapScanDesc scan;
	HeapTuple	tuple;
	ItemPointer lasttuple;
	BlockNumber lastblock,
				estblock;
	OffsetNumber lastoffset;
	int			numest;
	double		tuplesperpage;
	double		t;
	double		rstate;

	Assert(targrows > 1);

	/*
	 * Do a simple linear scan until we reach the target number of rows.
	 */
	scan = heap_beginscan(onerel, SnapshotNow, 0, NULL);
	while ((tuple = heap_getnext(scan, ForwardScanDirection)) != NULL)
	{
		rows[numrows++] = heap_copytuple(tuple);
		if (numrows >= targrows)
			break;
		CHECK_FOR_INTERRUPTS();
	}
	heap_endscan(scan);

	/*
	 * If we ran out of tuples then we're done, no matter how few we
	 * collected.  No sort is needed, since they're already in order.
	 */
	if (!HeapTupleIsValid(tuple))
	{
		*totalrows = (double) numrows;

		ereport(elevel,
				(errmsg("\"%s\": %u pages, %d rows sampled, %.0f estimated total rows",
						RelationGetRelationName(onerel),
						onerel->rd_nblocks, numrows, *totalrows)));

		return numrows;
	}

	/*
	 * Otherwise, start replacing tuples in the sample until we reach the
	 * end of the relation.  This algorithm is from Jeff Vitter's paper
	 * (see full citation below).  It works by repeatedly computing the
	 * number of the next tuple we want to fetch, which will replace a
	 * randomly chosen element of the reservoir (current set of tuples).
	 * At all times the reservoir is a true random sample of the tuples
	 * we've passed over so far, so when we fall off the end of the
	 * relation we're done.
	 *
	 * A slight difficulty is that since we don't want to fetch tuples or
	 * even pages that we skip over, it's not possible to fetch *exactly*
	 * the N'th tuple at each step --- we don't know how many valid tuples
	 * are on the skipped pages.  We handle this by assuming that the
	 * average number of valid tuples/page on the pages already scanned
	 * over holds good for the rest of the relation as well; this lets us
	 * estimate which page the next tuple should be on and its position in
	 * the page.  Then we fetch the first valid tuple at or after that
	 * position, being careful not to use the same tuple twice.  This
	 * approach should still give a good random sample, although it's not
	 * perfect.
	 */
	lasttuple = &(rows[numrows - 1]->t_self);
	lastblock = ItemPointerGetBlockNumber(lasttuple);
	lastoffset = ItemPointerGetOffsetNumber(lasttuple);

	/*
	 * If possible, estimate tuples/page using only completely-scanned
	 * pages.
	 */
	for (numest = numrows; numest > 0; numest--)
	{
		if (ItemPointerGetBlockNumber(&(rows[numest - 1]->t_self)) != lastblock)
			break;
	}
	if (numest == 0)
	{
		numest = numrows;		/* don't have a full page? */
		estblock = lastblock + 1;
	}
	else
		estblock = lastblock;
	tuplesperpage = (double) numest / (double) estblock;

	t = (double) numrows;		/* t is the # of records processed so far */
	rstate = init_selection_state(targrows);
	for (;;)
	{
		double		targpos;
		BlockNumber targblock;
		Buffer		targbuffer;
		Page		targpage;
		OffsetNumber targoffset,
					maxoffset;

		CHECK_FOR_INTERRUPTS();

		t = select_next_random_record(t, targrows, &rstate);
		/* Try to read the t'th record in the table */
		targpos = t / tuplesperpage;
		targblock = (BlockNumber) targpos;
		targoffset = ((int) ((targpos - targblock) * tuplesperpage)) +
			FirstOffsetNumber;
		/* Make sure we are past the last selected record */
		if (targblock <= lastblock)
		{
			targblock = lastblock;
			if (targoffset <= lastoffset)
				targoffset = lastoffset + 1;
		}
		/* Loop to find first valid record at or after given position */
pageloop:;

		/*
		 * Have we fallen off the end of the relation?	(We rely on
		 * heap_beginscan to have updated rd_nblocks.)
		 */
		if (targblock >= onerel->rd_nblocks)
			break;

		/*
		 * We must maintain a pin on the target page's buffer to ensure
		 * that the maxoffset value stays good (else concurrent VACUUM
		 * might delete tuples out from under us).	Hence, pin the page
		 * until we are done looking at it.  We don't maintain a lock on
		 * the page, so tuples could get added to it, but we ignore such
		 * tuples.
		 */
		targbuffer = ReadBuffer(onerel, targblock);
		if (!BufferIsValid(targbuffer))
			elog(ERROR, "ReadBuffer failed");
		LockBuffer(targbuffer, BUFFER_LOCK_SHARE);
		targpage = BufferGetPage(targbuffer);
		maxoffset = PageGetMaxOffsetNumber(targpage);
		LockBuffer(targbuffer, BUFFER_LOCK_UNLOCK);

		for (;;)
		{
			HeapTupleData targtuple;
			Buffer		tupbuffer;

			if (targoffset > maxoffset)
			{
				/* Fell off end of this page, try next */
				ReleaseBuffer(targbuffer);
				targblock++;
				targoffset = FirstOffsetNumber;
				goto pageloop;
			}
			ItemPointerSet(&targtuple.t_self, targblock, targoffset);
			if (heap_fetch(onerel, SnapshotNow, &targtuple, &tupbuffer,
						   false, NULL))
			{
				/*
				 * Found a suitable tuple, so save it, replacing one old
				 * tuple at random
				 */
				int			k = (int) (targrows * random_fract());

				Assert(k >= 0 && k < targrows);
				heap_freetuple(rows[k]);
				rows[k] = heap_copytuple(&targtuple);
				/* this releases the second pin acquired by heap_fetch: */
				ReleaseBuffer(tupbuffer);
				/* this releases the initial pin: */
				ReleaseBuffer(targbuffer);
				lastblock = targblock;
				lastoffset = targoffset;
				break;
			}
			/* this tuple is dead, so advance to next one on same page */
			targoffset++;
		}
	}

	/*
	 * Now we need to sort the collected tuples by position (itempointer).
	 */
	qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);

	/*
	 * Estimate total number of valid rows in relation.
	 */
	*totalrows = floor((double) onerel->rd_nblocks * tuplesperpage + 0.5);

	/*
	 * Emit some interesting relation info 
	 */
	ereport(elevel,
			(errmsg("\"%s\": %u pages, %d rows sampled, %.0f estimated total rows",
					RelationGetRelationName(onerel),
					onerel->rd_nblocks, numrows, *totalrows)));

	return numrows;
}

/* Select a random value R uniformly distributed in 0 < R < 1 */
static double
random_fract(void)
{
	long		z;

	/* random() can produce endpoint values, try again if so */
	do
	{
		z = random();
	} while (z <= 0 || z >= MAX_RANDOM_VALUE);
	return (double) z / (double) MAX_RANDOM_VALUE;
}

/*
 * These two routines embody Algorithm Z from "Random sampling with a
 * reservoir" by Jeffrey S. Vitter, in ACM Trans. Math. Softw. 11, 1
 * (Mar. 1985), Pages 37-57.  While Vitter describes his algorithm in terms
 * of the count S of records to skip before processing another record,
 * it is convenient to work primarily with t, the index (counting from 1)
 * of the last record processed and next record to process.  The only extra
 * state needed between calls is W, a random state variable.
 *
 * Note: the original algorithm defines t, S, numer, and denom as integers.
 * Here we express them as doubles to avoid overflow if the number of rows
 * in the table exceeds INT_MAX.  The algorithm should work as long as the
 * row count does not become so large that it is not represented accurately
 * in a double (on IEEE-math machines this would be around 2^52 rows).
 *
 * init_selection_state computes the initial W value.
 *
 * Given that we've already processed t records (t >= n),
 * select_next_random_record determines the number of the next record to
 * process.
 */
static double
init_selection_state(int n)
{
	/* Initial value of W (for use when Algorithm Z is first applied) */
	return exp(-log(random_fract()) / n);
}

static double
select_next_random_record(double t, int n, double *stateptr)
{
	/* The magic constant here is T from Vitter's paper */
	if (t <= (22.0 * n))
	{
		/* Process records using Algorithm X until t is large enough */
		double		V,
					quot;

		V = random_fract();		/* Generate V */
		t += 1;
		quot = (t - (double) n) / t;
		/* Find min S satisfying (4.1) */
		while (quot > V)
		{
			t += 1;
			quot *= (t - (double) n) / t;
		}
	}
	else
	{
		/* Now apply Algorithm Z */
		double		W = *stateptr;
		double		term = t - (double) n + 1;
		double		S;

		for (;;)
		{
			double		numer,
						numer_lim,
						denom;
			double		U,
						X,
						lhs,
						rhs,
						y,
						tmp;

			/* Generate U and X */
			U = random_fract();
			X = t * (W - 1.0);
			S = floor(X);		/* S is tentatively set to floor(X) */
			/* Test if U <= h(S)/cg(X) in the manner of (6.3) */
			tmp = (t + 1) / term;
			lhs = exp(log(((U * tmp * tmp) * (term + S)) / (t + X)) / n);
			rhs = (((t + X) / (term + S)) * term) / t;
			if (lhs <= rhs)
			{
				W = rhs / lhs;
				break;
			}
			/* Test if U <= f(S)/cg(X) */
			y = (((U * (t + 1)) / term) * (t + S + 1)) / (t + X);
			if ((double) n < S)
			{
				denom = t;
				numer_lim = term + S;
			}
			else
			{
				denom = t - (double) n + S;
				numer_lim = t + 1;
			}
			for (numer = t + S; numer >= numer_lim; numer -= 1)
			{
				y *= numer / denom;
				denom -= 1;
			}
			W = exp(-log(random_fract()) / n);	/* Generate W in advance */
			if (exp(log(y) / n) <= (t + X) / t)
				break;
		}
		t += S + 1;
		*stateptr = W;
	}
	return t;
}

/*
 * qsort comparator for sorting rows[] array
 */
static int
compare_rows(const void *a, const void *b)
{
	HeapTuple	ha = *(HeapTuple *) a;
	HeapTuple	hb = *(HeapTuple *) b;
	BlockNumber ba = ItemPointerGetBlockNumber(&ha->t_self);
	OffsetNumber oa = ItemPointerGetOffsetNumber(&ha->t_self);
	BlockNumber bb = ItemPointerGetBlockNumber(&hb->t_self);
	OffsetNumber ob = ItemPointerGetOffsetNumber(&hb->t_self);

	if (ba < bb)
		return -1;
	if (ba > bb)
		return 1;
	if (oa < ob)
		return -1;
	if (oa > ob)
		return 1;
	return 0;
}


/*
 *	compute_minimal_stats() -- compute minimal column statistics
 *
 *	We use this when we can find only an "=" operator for the datatype.
 *
 *	We determine the fraction of non-null rows, the average width, the
 *	most common values, and the (estimated) number of distinct values.
 *
 *	The most common values are determined by brute force: we keep a list
 *	of previously seen values, ordered by number of times seen, as we scan
 *	the samples.  A newly seen value is inserted just after the last
 *	multiply-seen value, causing the bottommost (oldest) singly-seen value
 *	to drop off the list.  The accuracy of this method, and also its cost,
 *	depend mainly on the length of the list we are willing to keep.
 */
static void
compute_minimal_stats(VacAttrStats *stats,
					  TupleDesc tupDesc, double totalrows,
					  HeapTuple *rows, int numrows)
{
	int			i;
	int			null_cnt = 0;
	int			nonnull_cnt = 0;
	int			toowide_cnt = 0;
	double		total_width = 0;
	bool		is_varlena = (!stats->attr->attbyval &&
							  stats->attr->attlen == -1);
	bool		is_varwidth = (!stats->attr->attbyval &&
							   stats->attr->attlen < 0);
	FmgrInfo	f_cmpeq;
	typedef struct
	{
		Datum		value;
		int			count;
	} TrackItem;
	TrackItem  *track;
	int			track_cnt,
				track_max;
	int			num_mcv = stats->attr->attstattarget;

	/*
	 * We track up to 2*n values for an n-element MCV list; but at least
	 * 10
	 */
	track_max = 2 * num_mcv;
	if (track_max < 10)
		track_max = 10;
	track = (TrackItem *) palloc(track_max * sizeof(TrackItem));
	track_cnt = 0;

	fmgr_info(stats->eqfunc, &f_cmpeq);

	for (i = 0; i < numrows; i++)
	{
		HeapTuple	tuple = rows[i];
		Datum		value;
		bool		isnull;
		bool		match;