chunk.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * chunk.c
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/utils/adt/chunk.c,v 1.20.2.1 1999/08/02 05:24:50 scrappy Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <ctype.h>
#include <sys/types.h>
#include <fcntl.h>

#include "postgres.h"

#include "catalog/pg_type.h"
#include "fmgr.h"
#include "libpq/be-fsstubs.h"
#include "libpq/libpq-fs.h"
#include "optimizer/internal.h"
#include "utils/array.h"
#include "utils/memutils.h"

#define INFTY 500000000
#define MANY  10000
#define MAXPAT 20
#define quot_ceil(x,y)	(((x)+(y)-1)/(y))
#define min(x,y)		(((x) < (y))? (x) : (y))
#define max(x,y)		(((x) > (y))? (x) : (y))

static CHUNK_INFO cInfo;

/* non-export function prototypes */
static int _FindBestChunk(int size, int *dmax, int *dbest, int dim,
			   int A[MAXPAT][MAXDIM + 1], int N);
static int	get_next(int *d, int k, int C, int *dmax);
static void initialize_info(CHUNK_INFO *A, int ndim, int *dim, int *chunk);

#ifdef LOARRAY
static void _ConvertToChunkFile(int n, int baseSize, int *dim, int *C,
					int srcfd, int destfd);
static void read_chunk(int *chunk_no, int *C, char *a_chunk, int srcfd,
		   int n, int baseSize, int *PX, int *dist);
static int	write_chunk(struct varlena * a_chunk, int ofile);
static int	seek_and_read(int pos, int size, char *buff, int fp, int from);

#endif
static int GetChunkSize(FILE *fd, int ndim, int dim[MAXDIM], int baseSize,
			 int d[MAXDIM]);

/*------------------------------------------------------------------------
 * _ChunkArray ---
 *	   converts an input array to chunked format using the information
 *	   provided by the access pattern.
 * Results:
 *	   creates a new file that stores the chunked array and returns
 *	   information about the chunked file
 *-----------------------------------------------------------------------
 */
char *
_ChunkArray(int fd,
			FILE *afd,
			int ndim,
			int *dim,
			int baseSize,
			int *nbytes,
			char *chunkfile)
{
#ifdef LOARRAY
	int			cfd = 0;

#endif
	int			chunk[MAXDIM],
				csize;
	bool		reorgFlag;

	if (chunkfile == NULL)
		reorgFlag = true;
	else
		reorgFlag = false;

#ifdef LOARRAY
	if (reorgFlag)
		/* create new LO for chunked file */
		chunkfile = _array_newLO(&cfd, fileFlag);
	else
		cfd = LOopen(chunkfile, O_RDONLY);
	if (cfd < 0)
		elog(ERROR, "Unable to open chunk file");
#endif

	strcpy(cInfo.lo_name, chunkfile);

	/* find chunk size */
	csize = GetChunkSize(afd, ndim, dim, baseSize, chunk);

#ifdef LOARRAY
	if (reorgFlag)
		/* copy data from input file to chunked file */
		_ConvertToChunkFile(ndim, baseSize, dim, chunk, fd, cfd);
#endif

	initialize_info(&cInfo, ndim, dim, chunk);
	*nbytes = sizeof(CHUNK_INFO);
	return (char *) &cInfo;
}

/*--------------------------------------------------------------------------
 * GetChunkSize
 *		  given an access pattern and array dimensionality etc, this program
 *		returns the dimensions of the chunk in "d"
 *-----------------------------------------------------------------------
 */
static int
GetChunkSize(FILE *fd,
			 int ndim,
			 int dim[MAXDIM],
			 int baseSize,
			 int d[MAXDIM])
{
	int			N,
				i,
				j,
				csize;
	int			A[MAXPAT][MAXDIM + 1],
				dmax[MAXDIM];

	/*
	 * ----------- read input ------------
	 */
	fscanf(fd, "%d", &N);
	if (N > MAXPAT)
		elog(ERROR, "array_in: too many access pattern elements");
	for (i = 0; i < N; i++)
		for (j = 0; j < ndim + 1; j++)
			if (fscanf(fd, "%d ", &(A[i][j])) == EOF)
				elog(ERROR, "array_in: bad access pattern input");

	/*
	 * estimate chunk size
	 */
	for (i = 0; i < ndim; i++)
		for (j = 0, dmax[i] = 1; j < N; j++)
			if (dmax[i] < A[j][i])
				dmax[i] = A[j][i];
	csize = BLCKSZ / baseSize;

	_FindBestChunk(csize, dmax, d, ndim, A, N);

	return csize;
}

/*-------------------------------------------------------------------------
 * _FindBestChunk
 *		  This routine does most of the number crunching to compute the
 *		  optimal chunk shape.
 * Called by GetChunkSize
 *------------------------------------------------------------------------
 */
static int
_FindBestChunk(int size,
			   int *dmax,
			   int *dbest,
			   int dim,
			   int A[MAXPAT][MAXDIM + 1],
			   int N)
{
	int			d[MAXDIM];
	int			tc,
				mintc = INFTY;

	d[0] = 0;
	mintc = INFTY;
	while (get_next(d, dim, size, dmax))
	{

		/*
		 * compute the number of page fetches for a given chunk size (*d)
		 * and access pattern (**A)
		 */
		int			i,
					j,
					nc;

		for (i = 0, tc = 0; i < N; i++)
		{
			for (j = 0, nc = 1; j < dim; j++)
				nc *= quot_ceil(A[i][j], d[j]);
			nc *= A[i][dim];
			tc += nc;
		}

		/*
		 * tc holds the total number of page fetches
		 */
		if (mintc >= tc)
		{
			mintc = tc;
			for (j = 0; j < dim; dbest[j] = d[j], j++)
				;
		}
	}
	return mintc;
}

/*----------------------------------------------------------------------
 * get_next
 *	 Called by _GetBestChunk to get the next tuple in the lexicographic order
 *---------------------------------------------------------------------
 */
static int
get_next(int *d, int k, int C, int *dmax)
{
	int			i,
				j,
				temp;

	if (!d[0])
	{
		temp = C;
		for (j = k - 1; j >= 0; j--)
		{
			d[j] = min(temp, dmax[j]);
			temp = max(1, temp / d[j]);
		}
		return 1;
	}

	for (j = 0, temp = 1; j < k; j++)
		temp *= d[j];

	for (i = k - 1; i >= 0; i--)
	{
		temp = temp / d[i];
		if (((temp * (d[i] + 1)) < C) && (d[i] + 1 <= dmax[i]))
			break;
	}
	if (i < 0)
		return 0;

	d[i]++;
	j = C / temp;
	d[i] = min(dmax[i], j / (j / d[i]));
	temp = temp * d[i];
	temp = C / temp;

	for (j = k - 1; j > i; j--)
	{
		d[j] = min(temp, dmax[j]);
		temp = max(1, temp / d[j]);
	}
	return 1;
}

#ifdef LOARRAY
static char a_chunk[BLCKSZ + VARHDRSZ]; /* VARHDRSZ since a_chunk is in
										 * varlena format */

#endif

static void
initialize_info(CHUNK_INFO *A, int ndim, int *dim, int *chunk)
{
	int			i;

	for (i = 0; i < ndim; i++)
		A->C[i] = chunk[i];
}

/*--------------------------------------------------------------------------
 * Procedure reorganize_data():
 *	  This procedure reads the input multidimensional array that is organised
 *	  in the order specified by array "X" and breaks it up into chunks of
 *	  dimensions specified in "C".
 *
 *	  This is a very slow process, since reading and writing of LARGE files
 *	  may be involved.
 *
 *-------------------------------------------------------------------------
 */
#ifdef LOARRAY
static void
_ConvertToChunkFile(int n,
					int baseSize,
					int *dim,
					int *C,
					int srcfd,
					int destfd)
{
	int			max_chunks[MAXDIM],
				chunk_no[MAXDIM];
	int			PX[MAXDIM],
				dist[MAXDIM];
	int			csize = 1,
				i,
				temp;

	for (i = 0; i < n; chunk_no[i++] = 0)
	{
		max_chunks[i] = dim[i] / C[i];
		csize *= C[i];
	}
	csize *= baseSize;
	temp = csize + VARHDRSZ;
	memmove(a_chunk, &temp, VARHDRSZ);

	mda_get_prod(n, dim, PX);
	mda_get_offset_values(n, dist, PX, C);
	for (i = 0; i < n; dist[i] *= baseSize, i++)
		;
	do
	{
		read_chunk(chunk_no, C, &(a_chunk[VARHDRSZ]), srcfd, n, baseSize, PX, dist);
		write_chunk((struct varlena *) a_chunk, destfd);
	} while (next_tuple(n, chunk_no, max_chunks) != -1);
}

/*--------------------------------------------------------------------------
 * read_chunk
 *	  reads a chunk from the input files into a_chunk, the position of the
 *	  chunk is specified by chunk_no
 *--------------------------------------------------------------------------
 */
static void
read_chunk(int *chunk_no,
		   int *C,
		   char *a_chunk,
		   int srcfd,
		   int n,
		   int baseSize,
		   int *PX,
		   int *dist)
{
	int			i,
				j,
				cp,
				unit_transfer;