geqo_pool.c File Reference

#include "postgres.h"
#include <float.h>
#include <limits.h>
#include <math.h>
#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_recombination.h"

Include dependency graph for geqo_pool.c:

Go to the source code of this file.

Functions
static int	compare (const void *arg1, const void *arg2)
Pool *	alloc_pool (PlannerInfo *root, int pool_size, int string_length)
void	free_pool (PlannerInfo *root, Pool *pool)
void	random_init_pool (PlannerInfo *root, Pool *pool)
void	sort_pool (PlannerInfo *root, Pool *pool)
Chromosome *	alloc_chromo (PlannerInfo *root, int string_length)
void	free_chromo (PlannerInfo *root, Chromosome *chromo)
void	spread_chromo (PlannerInfo *root, Chromosome *chromo, Pool *pool)

Function Documentation

alloc_chromo()

Chromosome* alloc_chromo	(	PlannerInfo *	root,
		int	string_length
	)

Definition at line 162 of file geqo_pool.c.

{
    Chromosome *chromo;
 
    chromo = (Chromosome *) palloc(sizeof(Chromosome));
    chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
 
    return chromo;
}

References palloc(), and Chromosome::string.

Referenced by geqo().

alloc_pool()

Pool* alloc_pool	(	PlannerInfo *	root,
		int	pool_size,
		int	string_length
	)

Definition at line 42 of file geqo_pool.c.

{
    Pool       *new_pool;
    Chromosome *chromo;
    int         i;
 
    /* pool */
    new_pool = (Pool *) palloc(sizeof(Pool));
    new_pool->size = (int) pool_size;
    new_pool->string_length = (int) string_length;
 
    /* all chromosome */
    new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
 
    /* all gene */
    chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
    for (i = 0; i < pool_size; i++)
        chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
 
    return new_pool;
}

References Pool::data, for(), i, palloc(), Pool::size, and Pool::string_length.

Referenced by geqo().

compare()

static int compare ( const void *  arg1, const void *  arg2  )

static

Definition at line 145 of file geqo_pool.c.

{
    const Chromosome *chromo1 = (const Chromosome *) arg1;
    const Chromosome *chromo2 = (const Chromosome *) arg2;
 
    if (chromo1->worth == chromo2->worth)
        return 0;
    else if (chromo1->worth > chromo2->worth)
        return 1;
    else
        return -1;
}

References Chromosome::worth.

Referenced by _bt_compare_array_elements(), _bt_load(), ApplyInt32SortComparator(), ApplySortAbbrevFullComparator(), ApplySortComparator(), ApplyUnsignedSortComparator(), binaryheap_allocate(), compare_scalars(), comparetup_cluster(), comparetup_cluster_tiebreak(), comparetup_datum(), comparetup_datum_tiebreak(), comparetup_heap(), comparetup_heap_tiebreak(), comparetup_index_btree(), comparetup_index_btree_tiebreak(), heap_compare_slots(), multi_sort_compare(), pairingheap_allocate(), qsort_tuple_int32_compare(), qsort_tuple_unsigned_compare(), qunique(), qunique_arg(), and sort_pool().

free_chromo()

void free_chromo	(	PlannerInfo *	root,
		Chromosome *	chromo
	)

Definition at line 176 of file geqo_pool.c.

{
    pfree(chromo->string);
    pfree(chromo);
}

References pfree(), and Chromosome::string.

Referenced by geqo().

free_pool()

void free_pool	(	PlannerInfo *	root,
		Pool *	pool
	)

Definition at line 69 of file geqo_pool.c.

{
    Chromosome *chromo;
    int         i;
 
    /* all gene */
    chromo = (Chromosome *) pool->data; /* vector of all chromos */
    for (i = 0; i < pool->size; i++)
        pfree(chromo[i].string);
 
    /* all chromosome */
    pfree(pool->data);
 
    /* pool */
    pfree(pool);
}

References Pool::data, for(), i, pfree(), and Pool::size.

Referenced by geqo().

random_init_pool()

void random_init_pool	(	PlannerInfo *	root,
		Pool *	pool
	)

Definition at line 91 of file geqo_pool.c.

{
    Chromosome *chromo = (Chromosome *) pool->data;
    int         i;
    int         bad = 0;
 
    /*
     * We immediately discard any invalid individuals (those that geqo_eval
     * returns DBL_MAX for), thereby not wasting pool space on them.
     *
     * If we fail to make any valid individuals after 10000 tries, give up;
     * this probably means something is broken, and we shouldn't just let
     * ourselves get stuck in an infinite loop.
     */
    i = 0;
    while (i < pool->size)
    {
        init_tour(root, chromo[i].string, pool->string_length);
        pool->data[i].worth = geqo_eval(root, chromo[i].string,
                                        pool->string_length);
        if (pool->data[i].worth < DBL_MAX)
            i++;
        else
        {
            bad++;
            if (i == 0 && bad >= 10000)
                elog(ERROR, "geqo failed to make a valid plan");
        }
    }
 
#ifdef GEQO_DEBUG
    if (bad > 0)
        elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
             bad, pool->size);
#endif
}

References Pool::data, DEBUG1, elog, ERROR, geqo_eval(), i, init_tour(), root, size, Pool::size, Pool::string_length, while(), and Chromosome::worth.

Referenced by geqo().

sort_pool()

void sort_pool	(	PlannerInfo *	root,
		Pool *	pool
	)

Definition at line 135 of file geqo_pool.c.

{
    qsort(pool->data, pool->size, sizeof(Chromosome), compare);
}

References compare(), Pool::data, qsort, and Pool::size.

Referenced by geqo().

spread_chromo()

void spread_chromo	(	PlannerInfo *	root,
		Chromosome *	chromo,
		Pool *	pool
	)

Definition at line 187 of file geqo_pool.c.

{
    int         top,
                mid,
                bot;
    int         i,
                index;
    Chromosome  swap_chromo,
                tmp_chromo;
 
    /* new chromo is so bad we can't use it */
    if (chromo->worth > pool->data[pool->size - 1].worth)
        return;
 
    /* do a binary search to find the index of the new chromo */
 
    top = 0;
    mid = pool->size / 2;
    bot = pool->size - 1;
    index = -1;
 
    while (index == -1)
    {
        /* these 4 cases find a new location */
 
        if (chromo->worth <= pool->data[top].worth)
            index = top;
        else if (chromo->worth == pool->data[mid].worth)
            index = mid;
        else if (chromo->worth == pool->data[bot].worth)
            index = bot;
        else if (bot - top <= 1)
            index = bot;
 
 
        /*
         * these 2 cases move the search indices since a new location has not
         * yet been found.
         */
 
        else if (chromo->worth < pool->data[mid].worth)
        {
            bot = mid;
            mid = top + ((bot - top) / 2);
        }
        else
        {                       /* (chromo->worth > pool->data[mid].worth) */
            top = mid;
            mid = top + ((bot - top) / 2);
        }
    }                           /* ... while */
 
    /* now we have index for chromo */
 
    /*
     * move every gene from index on down one position to make room for chromo
     */
 
    /*
     * copy new gene into pool storage; always replace worst gene in pool
     */
 
    geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
 
    swap_chromo.string = pool->data[pool->size - 1].string;
    swap_chromo.worth = pool->data[pool->size - 1].worth;
 
    for (i = index; i < pool->size; i++)
    {
        tmp_chromo.string = pool->data[i].string;
        tmp_chromo.worth = pool->data[i].worth;
 
        pool->data[i].string = swap_chromo.string;
        pool->data[i].worth = swap_chromo.worth;
 
        swap_chromo.string = tmp_chromo.string;
        swap_chromo.worth = tmp_chromo.worth;
    }
}

References Pool::data, geqo_copy(), i, root, Pool::size, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by geqo().