amdb_wkldstats.cc

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

	    ((float) query->stats.leafStats.totalIos - qs->leafStats.excCovLoss) *
	    (1.0 - query->stats.leafStats.avgUtil / targetUtil);
	// for internal nodes, we don't have an avg. util., so we need to look
	// at the traversed pages (only the non-empty ones)
	qs->internalStats.utilLoss = 0.0;
	int i;
	for (i = 0; i < query->traversalStatsSize; i++) {
	    amdb_wkldprofile::InternalTraversalStats *ts = &query->traversalStats[i];
	    if (ts->emptyNode) {
		// nothing retrieved, no children traversed: counts fully
		// as excess coverage
	        qs->internalStats.excCovLoss += 1.0;
	    } else {
		// we count util loss in non-empty nodes
		qs->internalStats.utilLoss +=
		    1.0 - tmap.util(ts->pageno) / targetUtil;
		// we count root nodes of empty subtrees as util loss and
		// exch. cov. loss
		if (ts->retrievalCnt == 0) {
		    qs->internalStats.excCovLoss +=
		        tmap.util(ts->pageno) / targetUtil;
		}
	    }
	}

	// compute minIos = ceil(total volume retrieved / target page capacity)
	qs->leafStats.minIos =
	    (int) ceil((float) query->stats.leafStats.retrievalVol /
	    (targetUtil * (float) gist_p::data_sz));

	// optimalIos set in _computeOptimalIos()
	qs->leafStats.optimalOh = (float) qs->leafStats.optimalIos /
	    (float) qs->leafStats.minIos;
	qs->leafStats.optLeafOh = (float) nonEmptyLeaves /
	    (float) qs->leafStats.optimalIos;
	qs->leafStats.minLeafOh = (float) nonEmptyLeaves /
	    (float) qs->leafStats.minIos;
	qs->leafStats.optRandomOh = (float) qs->leafStats.randomIos /
	    (float) qs->leafStats.optimalIos;
	qs->leafStats.minRandomOh = (float) qs->leafStats.randomIos /
	    (float) qs->leafStats.minIos;
	qs->leafStats.optClusterLoss = (query->stats.leafStats.avgUtil /
	    targetUtil * (float) nonEmptyLeaves -
	    (float) qs->leafStats.optimalIos);
	qs->leafStats.optClusterOh = (query->stats.leafStats.avgUtil /
	    targetUtil * (float) nonEmptyLeaves) /
	    (float) qs->leafStats.optimalIos;
	qs->leafStats.minClusterLoss = query->stats.leafStats.avgUtil /
	    targetUtil * nonEmptyLeaves - qs->leafStats.minIos;
	qs->leafStats.minClusterOh = (query->stats.leafStats.avgUtil /
	    targetUtil * (float) nonEmptyLeaves) /
	    (float) qs->leafStats.minIos;
	qs->leafStats.utilOh = targetUtil / query->stats.leafStats.avgUtil;

	qs->leafStats.excCovOh = (float) query->stats.leafStats.totalIos /
	    (float) nonEmptyLeaves;
    }
}


/////////////////////////////////////////////////////////////////////////
// amdb_wkldstats::_computeStatsTotals
//
// Description:
/////////////////////////////////////////////////////////////////////////

// compute statsTotals
void 
amdb_wkldstats::_computeStatsTotals(
    const amdb_wkldprofile& profile,
    float targetUtil)
{
    QueryStatsVect::iterator it;
    for (it = queryStats.begin(); it != queryStats.end(); it++) {
	QueryStats* qs = (QueryStats *) *it;

	statsTotals.leafStats.minIos += qs->leafStats.minIos;
	statsTotals.leafStats.optimalIos += qs->leafStats.optimalIos;
	statsTotals.leafStats.optClusterLoss +=
	    qs->leafStats.optClusterLoss;
	statsTotals.leafStats.minClusterLoss +=
	    qs->leafStats.minClusterLoss;
	statsTotals.leafStats.utilLoss += qs->leafStats.utilLoss;
	statsTotals.leafStats.excCovLoss += qs->leafStats.excCovLoss;

	statsTotals.internalStats.excCovLoss +=
	    qs->internalStats.excCovLoss;
	statsTotals.internalStats.utilLoss += qs->internalStats.utilLoss;
    }
    
    // finalize some aggregates

    statsTotals.leafStats.optimalOh =
	(float) statsTotals.leafStats.optimalIos /
        (float) statsTotals.leafStats.minIos;
    statsTotals.leafStats.optLeafOh =
        (float) profile.statsTotals.stats.leafStats.totalIos /
	((float) statsTotals.leafStats.optimalIos);
    statsTotals.leafStats.minLeafOh =
        (float) profile.statsTotals.stats.leafStats.totalIos /
	(float) statsTotals.leafStats.minIos;

    // randomIos and randomStdDev are computed in computeRandomClustering()
    statsTotals.leafStats.optRandomOh =
        (float) statsTotals.leafStats.randomIos /
        (float) statsTotals.leafStats.optimalIos;
    statsTotals.leafStats.minRandomOh =
        (float) statsTotals.leafStats.randomIos /
        (float) statsTotals.leafStats.minIos;

    statsTotals.leafStats.optClusterOh =
        (float) (statsTotals.leafStats.optClusterLoss +
	statsTotals.leafStats.optimalIos) /
        statsTotals.leafStats.optimalIos;
    statsTotals.leafStats.minClusterOh =
        (float) (statsTotals.leafStats.minClusterLoss +
	statsTotals.leafStats.minIos) /
        statsTotals.leafStats.minIos;
    statsTotals.leafStats.utilOh = targetUtil /
        profile.statsTotals.stats.leafStats.avgUtil;

    statsTotals.leafStats.excCovOh = 
        (float) profile.statsTotals.stats.leafStats.totalIos /
        (float) (profile.statsTotals.stats.leafStats.totalIos -
	statsTotals.leafStats.excCovLoss);
}


/////////////////////////////////////////////////////////////////////////
// amdb_wkldstats::_computeNodeStats - 
//
// Description:
//	- allocate NodeStats for each traversed node and compute
//	  stats
/////////////////////////////////////////////////////////////////////////

void
amdb_wkldstats::_computeNodeStats(
    const amdb_wkldprofile& profile,
    const amdb_treemap& tmap,
    float targetUtil)
{
    int targetCap = (int) (targetUtil * (float) gist_p::data_sz); // target capacity
    amdb_wkldprofile::TraversalStatsMap::const_iterator tsit;
    for (tsit = profile.statsTotals.traversalStats.begin();
        tsit != profile.statsTotals.traversalStats.end(); tsit++) {

	NodeStats* ns = new NodeStats();
	const amdb_wkldprofile::TraversalStats* ts =
	    (amdb_wkldprofile::TraversalStats *) (*tsit).second;
	shpid_t pgno = ts->pageno;
	nodeStats[pgno] = (void *) ns;

	float util = tmap.util(pgno);
	int nonEmpty = ts->traversalCnt - ts->emptyNode; // non-empty accesses
	if (ts->isLeaf) {
	    ns->utilLoss = (float) nonEmpty * (1.0 - util / targetUtil);
	    ns->utilOh = targetUtil / util;
	    // optClusterLoss for page p = sum over all queries q: (data-vol(p) - 
	    // ratio(q) * retrieval-vol(p, q)) / B,
	    // with B = targetUtil * data_sz and ratio(q) = optimalIos(q) * B /
	    // retrieval-vol(q) (the benchmark retrieval ratio);
	    // optClusterOh for page p = |Q| * data-vol(p) / sum over all queries:
	    // ratio(q) * retrieval-vol(p, q)
	    ns->optClusterLoss = 0.0;
	    ns->optClusterOh = 0.0;
	    ns->minClusterLoss = 0.0;
	    ns->minClusterOh = 0.0;
	    int pgFill = (int) (util * (float) gist_p::data_sz);
	    amdb_wkldprofile::QueryVect::const_iterator qit;
	    QueryStatsVect::iterator qsit;
	    for (qit = profile.queries.begin(), qsit = queryStats.begin();
	        qit != profile.queries.end(); qit++, qsit++) {

		amdb_wkldprofile::Query* query = (amdb_wkldprofile::Query *) *qit;
		QueryStats* qs = (QueryStats *) *qsit;
		int vol = profile.retrievalVolume(*query, pgno);
		if (vol > 0) {
		    // this query accessed page pgno

		    // r = benchmark ratio of data accessed / data retrieved in opt
		    // clustering
		    float r_opt = (float) (qs->leafStats.optimalIos * targetCap) /
			(float) query->stats.leafStats.retrievalVol;
		    float r_min = (float) (qs->leafStats.minIos * targetCap) /
			(float) query->stats.leafStats.retrievalVol;
		    ns->optClusterLoss += ((float) pgFill - r_opt * (float) vol)
			/ (float) targetCap;
		    ns->minClusterLoss += ((float) pgFill - r_min * (float) vol)
			/ (float) targetCap;
		    // overhead: we sum up the denominator
		    ns->optClusterOh += r_opt * (float) vol;
		    ns->minClusterOh += r_min * (float) vol;
		}
	    }
	    if (ns->optClusterOh != 0.0) {
		ns->optClusterOh = ((float) (nonEmpty * gist_p::data_sz) * util) /
		    ns->optClusterOh;
	    } else {
		// the leaf was never accessed
		ns->optClusterOh = 1.0;
	    }
	    if (ns->minClusterOh != 0.0) {
		ns->minClusterOh = ((float) (nonEmpty * gist_p::data_sz) * util) /
		    ns->minClusterOh;
	    } else {
		ns->minClusterOh = 1.0;
	    }

	} else {
	    // we don't have numbers for internal nodes yet
	    ns->utilLoss = 0.0;
	    ns->utilOh = 1.0;
	    ns->optClusterLoss = 0.0;
	    ns->optClusterOh = 1.0;
	    ns->minClusterLoss = 0.0;
	    ns->minClusterOh = 1.0;
	}

	ns->excCovLoss = ts->emptyNode;
	if (ts->traversalCnt != 0) {
	    ns->excCovOh = (float) ts->traversalCnt / (float) nonEmpty; // could be \infty
	    ns->excCovOh = (float) ts->traversalCnt / (float) nonEmpty; // could be \infty
	} else {
	    ns->excCovOh = -1.0; // mark it
	}
    }
}


/////////////////////////////////////////////////////////////////////////
// amdb_wkldstats::computeStats - compute all wkld stats
//
// Description:
//	- first, compute random clustering stats (randomIos, randomStdDev,
//	  opt-/minRandomOh)
//	- compute queryStats, statsTotals and nodeStats
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

void
amdb_wkldstats::computeStats(
    amdb_wkldprofile& profile, // in: input profile
    const amdb_treemap& tmap, // in: map of input tree
    const amdb_clustering::Clustering& optClustering, // in: optimal clustering
    const amdb_analysis::Parameters& parameters) // in: analysis parameters
{
    // allocate queryStats
    queryStats.reserve(profile.queries.size());
    int i;
    for (i = 0; i < profile.queries.size(); i++) {
        queryStats.push_back((void *) new QueryStats());
    }

    float fillFactor;
    if  (parameters.targetUtil == 0.0) {
	// take the avg. of the query avg.
        fillFactor = profile.statsTotals.stats.leafStats.avgUtil;
    } else {
         fillFactor = parameters.targetUtil;
    }

    profile.setTreeMap(&tmap); // make sure valid map is set

    // set randomIos in queryStats[]
    _computeRandomIos(profile, tmap, parameters.randomRuns, fillFactor);

    // set optIos in queryStats[]
    _computeOptimalIos(profile, optClustering);

    // computes remaining QueryStats
    _computeQueryStats(profile, tmap, parameters.targetUtil);

    // aggregates QueryStats
    _computeStatsTotals(profile, parameters.targetUtil);

    // computes nodeStats, using the profile's aggregated traversal stats
    _computeNodeStats(profile, tmap, parameters.targetUtil);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_wkldstats::createNodeStats -
// 	create full NodeStats for given query
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
amdb_wkldstats::createNodeStats(
    int queryNo, // in
    const amdb_wkldprofile& profile, // in
    const amdb_treemap& treeMap, // in
    const amdb_analysis::Parameters& parameters, // in
    NodeStatsMap& nsMap) const // out
{
    clearNodeStatsMap(nsMap);

    amdb_wkldprofile::Query* query =
        (amdb_wkldprofile::Query *) profile.queries[queryNo];
    QueryStats* qs = (QueryStats *) queryStats[queryNo];
    assert(query != NULL);
    amdb_wkldprofile::TraversalStatsMap tsMap;
    // compute traversal stats just to see which nodes where visited
    profile.createTraversalStats(*query, tsMap);

    amdb_wkldprofile::TraversalStatsMap::const_iterator it;
    for (it = tsMap.begin(); it != tsMap.end(); it++) {
	shpid_t pageno = (shpid_t) (*it).first;
	amdb_wkldprofile::TraversalStats* ts =
	    (amdb_wkldprofile::TraversalStats* ) (*it).second;
	float util = treeMap.util(pageno);
        NodeStats* stats = new NodeStats();
	nsMap[pageno] = (void *) stats;

	stats->utilLoss = 1.0 - util / parameters.targetUtil;
	stats->utilOh = parameters.targetUtil / util;

	if (!ts->isLeaf || ts->retrievalCnt == 0) {
	    // these stats don't apply here
	    stats->optClusterLoss = 0.0;
	    stats->optClusterOh = 1.0;
	    stats->minClusterLoss = 0.0;
	    stats->minClusterOh = 1.0;
	} else {
	    int targetCap = (int) (parameters.targetUtil * (float) gist_p::data_sz);
	    int pgFill = (int) (util * (float) gist_p::data_sz);
	    float r_min = (float) (qs->leafStats.minIos * targetCap) /
		(float) query->stats.leafStats.retrievalVol;
	    stats->minClusterLoss = ((float) pgFill - r_min * (float) ts->retrievalVol)
		/ (float) targetCap;
	    stats->minClusterOh = (float) pgFill / (r_min * (float) ts->retrievalVol);
	    float r_opt = (float) (qs->leafStats.optimalIos * targetCap) /
		(float) query->stats.leafStats.retrievalVol;
	    stats->optClusterLoss = ((float) pgFill - r_opt * (float) ts->retrievalVol)
		/ (float) targetCap;
	    stats->optClusterOh = (float) pgFill / (r_opt * (float) ts->retrievalVol);
	}

	stats->excCovLoss = (float) ts->emptyNode;
	stats->excCovOh = (float) ts->traversalCnt /
	    (float) (ts->traversalCnt - ts->emptyNode);
    }
}


///////////////////////////////////////////////////////////////////////////////
// amdb_wkldstats::clearNodeStats -
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
amdb_wkldstats::clearNodeStatsMap(
    NodeStatsMap& tmap)
{
    NodeStatsMap::const_iterator it;
    for (it = tmap.begin(); it != tmap.end(); it++) {
        NodeStats* stats = (NodeStats *) (*it).second;
	delete stats;
    }
    tmap.erase(tmap.begin(), tmap.end());
}