geqo_params.c 7.66 KB
Newer Older
Marc G. Fournier's avatar
Marc G. Fournier committed
1 2
/*------------------------------------------------------------------------
*
3
* geqo_params.c
4
*	 routines for determining necessary genetic optimization parameters
Marc G. Fournier's avatar
Marc G. Fournier committed
5 6 7
*
* Copyright (c) 1994, Regents of the University of California
*
8
* $Id: geqo_params.c,v 1.14 1999/02/15 03:22:01 momjian Exp $
Marc G. Fournier's avatar
Marc G. Fournier committed
9 10 11 12 13 14
*
*-------------------------------------------------------------------------
*/

/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
15 16 17
   *  Martin Utesch				 * Institute of Automatic Control	   *
   =							 = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
Marc G. Fournier's avatar
Marc G. Fournier committed
18 19 20 21 22 23
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

#include <stdio.h>
#include <time.h>
#include <math.h>
24
#include <ctype.h>
25
#include <string.h>
Marc G. Fournier's avatar
Marc G. Fournier committed
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include "postgres.h"
#include "miscadmin.h"

#include "nodes/pg_list.h"
#include "nodes/relation.h"
#include "nodes/primnodes.h"

#include "utils/palloc.h"
#include "utils/elog.h"

#include "optimizer/internal.h"
#include "optimizer/paths.h"
#include "optimizer/pathnode.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"

#include "optimizer/geqo_gene.h"
#include "optimizer/geqo.h"

46 47
#include "storage/fd.h"

48 49 50 51
#define POOL_TAG		"Pool_Size"
#define TRIAL_TAG		"Generations"
#define RAND_TAG		"Random_Seed"
#define BIAS_TAG		"Selection_Bias"
Marc G. Fournier's avatar
Marc G. Fournier committed
52

53 54 55 56
#define EFFORT_TAG		"Effort"/* optimization effort and */
#define LOW				 "low"	/* corresponding tags */
#define MEDIUM		  "medium"
#define HIGH		  "high"
Marc G. Fournier's avatar
Marc G. Fournier committed
57

58 59
#define MAX_TOKEN 80			/* Maximum size of one token in the  *
								 * configuration file				 */
Marc G. Fournier's avatar
Marc G. Fournier committed
60

61 62 63
static int	gimme_pool_size(int string_length);
static int	gimme_number_generations(int pool_size, int effort);
static int	next_token(FILE *, char *, int);
64
static double geqo_log(double x, double b);
Marc G. Fournier's avatar
Marc G. Fournier committed
65 66

/*
67
 * geqo_param
68
 *		 get ga parameters out of "$PGDATA/pg_geqo" file.
Marc G. Fournier's avatar
Marc G. Fournier committed
69 70 71 72
 */
void
geqo_params(int string_length)
{
73
	int			i;
Marc G. Fournier's avatar
Marc G. Fournier committed
74

75 76
	char		buf[MAX_TOKEN];
	FILE	   *file;
Marc G. Fournier's avatar
Marc G. Fournier committed
77

78
	char	   *conf_file;
Marc G. Fournier's avatar
Marc G. Fournier committed
79 80

/* these static variables are used to signal that a value has been set */
81 82 83 84 85
	int			pool_size = 0;
	int			number_trials = 0;
	int			random_seed = 0;
	int			selection_bias = 0;
	int			effort = 0;
Marc G. Fournier's avatar
Marc G. Fournier committed
86 87 88


	/* put together the full pathname to the config file */
89
	conf_file = (char *) palloc((strlen(DataDir) + strlen(GEQO_FILE) + 2) * sizeof(char));
Marc G. Fournier's avatar
Marc G. Fournier committed
90 91 92 93

	sprintf(conf_file, "%s/%s", DataDir, GEQO_FILE);

	/* open the config file */
94
#ifndef __CYGWIN32__
95
	file = AllocateFile(conf_file, "r");
96 97 98
#else
	file = AllocateFile(conf_file, "rb");
#endif
Marc G. Fournier's avatar
Marc G. Fournier committed
99 100
	if (file)
	{
101

Marc G. Fournier's avatar
Marc G. Fournier committed
102 103 104 105 106
		/*
		 * empty and comment line stuff
		 */
		while ((i = next_token(file, buf, sizeof(buf))) != EOF)
		{
107 108 109 110 111 112 113 114 115 116
			/* If only token on the line, ignore */
			if (i == '\n')
				continue;

			/* Comment -- read until end of line then next line */
			if (buf[0] == '#')
			{
				while (next_token(file, buf, sizeof(buf)) == 0);
				continue;
			}
Marc G. Fournier's avatar
Marc G. Fournier committed
117 118 119 120

			/*
			 * get ga parameters by parsing
			 */
121

Marc G. Fournier's avatar
Marc G. Fournier committed
122
			/*------------------------------------------------- pool size */
123
			if (strcmp(buf, POOL_TAG) == 0)
Marc G. Fournier's avatar
Marc G. Fournier committed
124 125
			{
				i = next_token(file, buf, sizeof(buf)); /* get next token */
126 127

				if (i != EOF)	/* only ignore if we got no text at all */
Marc G. Fournier's avatar
Marc G. Fournier committed
128
				{
129 130
					if (sscanf(buf, "%d", &PoolSize) == 1)
						pool_size = 1;
Marc G. Fournier's avatar
Marc G. Fournier committed
131
				}
132

Marc G. Fournier's avatar
Marc G. Fournier committed
133
			}
134

Marc G. Fournier's avatar
Marc G. Fournier committed
135
			/*------------------------------------------------- number of trials */
136
			else if (strcmp(buf, TRIAL_TAG) == 0)
Marc G. Fournier's avatar
Marc G. Fournier committed
137 138
			{
				i = next_token(file, buf, sizeof(buf));
139

Marc G. Fournier's avatar
Marc G. Fournier committed
140 141
				if (i != EOF)
				{
142 143
					if (sscanf(buf, "%d", &Generations) == 1)
						number_trials = 1;
Marc G. Fournier's avatar
Marc G. Fournier committed
144
				}
145

Marc G. Fournier's avatar
Marc G. Fournier committed
146
			}
147

Marc G. Fournier's avatar
Marc G. Fournier committed
148
			/*------------------------------------------------- optimization effort */
149
			else if (strcmp(buf, EFFORT_TAG) == 0)
Marc G. Fournier's avatar
Marc G. Fournier committed
150 151
			{
				i = next_token(file, buf, sizeof(buf));
152

Marc G. Fournier's avatar
Marc G. Fournier committed
153 154
				if (i != EOF)
				{
155 156 157 158 159 160
					if (strcmp(buf, LOW) == 0)
						effort = LOW_EFFORT;
					else if (strcmp(buf, MEDIUM) == 0)
						effort = MEDIUM_EFFORT;
					else if (strcmp(buf, HIGH) == 0)
						effort = HIGH_EFFORT;
Marc G. Fournier's avatar
Marc G. Fournier committed
161
				}
162

Marc G. Fournier's avatar
Marc G. Fournier committed
163
			}
164

Marc G. Fournier's avatar
Marc G. Fournier committed
165
			/*------------------------------------------- random seed */
166 167
			else if (strcmp(buf, RAND_TAG) == 0)
			{
Marc G. Fournier's avatar
Marc G. Fournier committed
168
				i = next_token(file, buf, sizeof(buf));
169

Marc G. Fournier's avatar
Marc G. Fournier committed
170 171
				if (i != EOF)
				{
172 173
					if (sscanf(buf, "%ld", &RandomSeed) == 1)
						random_seed = 1;
Marc G. Fournier's avatar
Marc G. Fournier committed
174
				}
175

Marc G. Fournier's avatar
Marc G. Fournier committed
176
			}
177

Marc G. Fournier's avatar
Marc G. Fournier committed
178
			/*------------------------------------------- selection bias */
179
			else if (strcmp(buf, BIAS_TAG) == 0)
Marc G. Fournier's avatar
Marc G. Fournier committed
180 181
			{
				i = next_token(file, buf, sizeof(buf));
182

Marc G. Fournier's avatar
Marc G. Fournier committed
183 184
				if (i != EOF)
				{
185 186
					if (sscanf(buf, "%lf", &SelectionBias) == 1)
						selection_bias = 1;
Marc G. Fournier's avatar
Marc G. Fournier committed
187
				}
188

Marc G. Fournier's avatar
Marc G. Fournier committed
189
			}
190

Marc G. Fournier's avatar
Marc G. Fournier committed
191 192 193 194 195 196
			/* unrecognized tags */
			else
			{
				if (i != EOF)
				{
				}
197 198

				elog(DEBUG, "geqo_params: unknown parameter type \"%s\"\nin file \'%s\'", buf, conf_file);
Marc G. Fournier's avatar
Marc G. Fournier committed
199 200

				/* if not at end-of-line, keep reading til we are */
201 202 203
				while (i == 0)
					i = next_token(file, buf, sizeof(buf));
			}
Marc G. Fournier's avatar
Marc G. Fournier committed
204 205
		}

206
		FreeFile(file);
Marc G. Fournier's avatar
Marc G. Fournier committed
207 208 209 210

		pfree(conf_file);
	}

211 212
	else
		elog(DEBUG, "geqo_params: ga parameter file\n\'%s\'\ndoes not exist or permissions are not setup correctly", conf_file);
Marc G. Fournier's avatar
Marc G. Fournier committed
213 214 215 216 217 218

	/*
	 * parameter checkings follow
	 */

	/**************** PoolSize: essential ****************/
219
	if (!(pool_size))
Marc G. Fournier's avatar
Marc G. Fournier committed
220 221 222
	{
		PoolSize = gimme_pool_size(string_length);

223
		elog(DEBUG, "geqo_params: no pool size specified;\nusing computed value of %d", PoolSize);
Marc G. Fournier's avatar
Marc G. Fournier committed
224
	}
225 226


Marc G. Fournier's avatar
Marc G. Fournier committed
227
	/**************** Effort: essential ****************/
228
	if (!(effort))
Marc G. Fournier's avatar
Marc G. Fournier committed
229 230 231 232 233
	{
		if (PoolSize == MAX_POOL)
			effort = HIGH_EFFORT;
		else
			effort = MEDIUM_EFFORT;
234 235

		elog(DEBUG, "geqo_params: no optimization effort specified;\nusing value of %d", effort);
Marc G. Fournier's avatar
Marc G. Fournier committed
236 237 238 239

	}

	/**************** Generations: essential ****************/
240
	if (!(number_trials))
Marc G. Fournier's avatar
Marc G. Fournier committed
241 242
	{
		Generations = gimme_number_generations(PoolSize, effort);
243 244

		elog(DEBUG, "geqo_params: no number of trials specified;\nusing computed value of %d", Generations);
Marc G. Fournier's avatar
Marc G. Fournier committed
245 246 247 248

	}

	/* RandomSeed: */
249
	if (!(random_seed))
Marc G. Fournier's avatar
Marc G. Fournier committed
250 251 252
	{
		RandomSeed = (long) time(NULL);

253
		elog(DEBUG, "geqo_params: no random seed specified;\nusing computed value of %ld", RandomSeed);
Marc G. Fournier's avatar
Marc G. Fournier committed
254 255 256
	}

	/* SelectionBias: */
257
	if (!(selection_bias))
Marc G. Fournier's avatar
Marc G. Fournier committed
258 259 260
	{
		SelectionBias = SELECTION_BIAS;

261
		elog(DEBUG, "geqo_params: no selection bias specified;\nusing default value of %f", SelectionBias);
Marc G. Fournier's avatar
Marc G. Fournier committed
262 263 264 265 266 267 268 269
	}

}


/*
 * Grab one token out of fp.  Defined as the next string of non-whitespace
 * in the file.  After we get the token, continue reading until EOF, end of
270
 * line or the next token.	If it's the last token on the line, return '\n'
Marc G. Fournier's avatar
Marc G. Fournier committed
271 272 273
 * for the value.  If we get EOF before reading a token, return EOF.  In all
 * other cases return 0.
 */
274
static int
275
next_token(FILE *fp, char *buf, int bufsz)
Marc G. Fournier's avatar
Marc G. Fournier committed
276
{
277 278
	int			c;
	char	   *eb = buf + (bufsz - 1);
Marc G. Fournier's avatar
Marc G. Fournier committed
279

280 281
	/* Discard inital whitespace */
	while (isspace(c = getc(fp)));
Marc G. Fournier's avatar
Marc G. Fournier committed
282

283 284 285
	/* EOF seen before any token so return EOF */
	if (c == EOF)
		return -1;
Marc G. Fournier's avatar
Marc G. Fournier committed
286

287 288 289 290 291 292 293 294
	/* Form a token in buf */
	do
	{
		if (buf < eb)
			*buf++ = c;
		c = getc(fp);
	} while (!isspace(c) && c != EOF);
	*buf = '\0';
Marc G. Fournier's avatar
Marc G. Fournier committed
295

296 297 298
	/* Discard trailing tabs and spaces */
	while (c == ' ' || c == '\t')
		c = getc(fp);
Marc G. Fournier's avatar
Marc G. Fournier committed
299

300 301
	/* Put back the char that was non-whitespace (putting back EOF is ok) */
	ungetc(c, fp);
Marc G. Fournier's avatar
Marc G. Fournier committed
302

303
	/* If we ended with a newline, return that, otherwise return 0 */
304
	return c == '\n' ? '\n' : 0;
Marc G. Fournier's avatar
Marc G. Fournier committed
305 306
}

307
/* gimme_pool_size
308 309
 *	 compute good estimation for pool size
 *	 according to number of involved rels in a query
Marc G. Fournier's avatar
Marc G. Fournier committed
310
 */
311
static int
Marc G. Fournier's avatar
Marc G. Fournier committed
312 313
gimme_pool_size(int string_length)
{
314 315
	double		exponent;
	double		size;
Marc G. Fournier's avatar
Marc G. Fournier committed
316 317 318

	exponent = (double) string_length + 1.0;

319
	size = pow(2.0, exponent);
Marc G. Fournier's avatar
Marc G. Fournier committed
320

321
	if (size < MIN_POOL)
322
		return MIN_POOL;
323
	else if (size > MAX_POOL)
324
		return MAX_POOL;
325
	else
326
		return (int) ceil(size);
Marc G. Fournier's avatar
Marc G. Fournier committed
327 328
}

329
/* gimme_number_generations
330 331
 *	 compute good estimation for number of generations size
 *	 for convergence
Marc G. Fournier's avatar
Marc G. Fournier committed
332
 */
333
static int
Marc G. Fournier's avatar
Marc G. Fournier committed
334 335
gimme_number_generations(int pool_size, int effort)
{
336
	int			number_gens;
Marc G. Fournier's avatar
Marc G. Fournier committed
337

338
	number_gens = (int) ceil(geqo_log((double) pool_size, 2.0));
Marc G. Fournier's avatar
Marc G. Fournier committed
339

340
	return effort * number_gens;
Marc G. Fournier's avatar
Marc G. Fournier committed
341
}
342 343 344 345 346 347

static double
geqo_log(double x, double b)
{
	return (log(x) / log(b));
}