amdb_penaltystats.cc

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

    // determine pre- and actualExcCovLoss:
    // first, construct pre- and post-insertion BP
    gist::AlignedPred x, y;
    vec_t preBp(x.pred, gist_p::max_tup_sz);
    vec_t postBp(y.pred, gist_p::max_tup_sz);
    W_DO(tree.getBp(leaf, preBp));
    (void) memcpy(postBp.ptr(0), preBp.ptr(0), preBp.len(0));
    postBp.set(y.pred, preBp.len(0));
    bool dummyBool;
    tree.unionBp(leaf, postBp, true, key, vec_t(), dummyBool);

    // set pre- and actualExcCovLoss
    _computeExcCovLoss(tree, profile, tmap, leaf, preBp, postBp,
        key, matches, queryStructs, stats->preExcCovLoss, stats->actualExcCovLoss);

    penaltyStats.push_back((void *) stats);

    return(RCOK);
}

/////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::_computeExtraIos - 
//	return additional I/Os to leaf after (virtual) insertion
//
// Description:
//	- counts those queries that don't retrieve anything from 
//	  currently but their gist_query_t intersects with the new key
//
// Return Values:
//      number of additional I/Os
/////////////////////////////////////////////////////////////////////////

int
amdb_penaltystats::_computeExtraIos(
    const gist& tree, // in: supplies extension
    const amdb_wkldprofile& profile, // in
    const amdb_treemap& tmap, // in
    shpid_t leaf, // in: node we're inserting on
    const vec_t& key, // in: key that's being inserted
    const Vector& matches) // in: vector<int>, indices of matching queries
{
    amdb_itemset leafSet;
    leafSet.pageItems(tmap, leaf);

    int debug = 0;

    if (debug) {
	//copy(leafSet.itemIds.begin(), leafSet.itemIds.end(),
	    //ostream_iterator<ItemId>(cout, " "));
	//cout << endl;
    }

    gist_ext_t* ext = tree.extension();
    amdb_ext_t* amdbext = amdb_ext_t::extension(ext);

    int cnt = 0;
    Vector::const_iterator it;
    amdb_itemset intersection;
    for (it = matches.begin(); it != matches.end(); it++) {
	int index = (int) *it;
	amdb_wkldprofile::Query* query = (amdb_wkldprofile::Query *)
	    profile.queries[index];
	// count those queries that so far don't visit the leaf in question,
	if (!intersection.intersection(leafSet, query->resultSet,
	    query->resultSetSize)) {

	    cnt++;
	}

	if (debug) {
	    // XXX debug 
	    //copy(optResultSets[index], optResultSets[index] + query->resultSetSize,
		//ostream_iterator<ItemId>(cout, " "));
	    //cout << endl;
	    //copy(intersection.itemIds.begin(), intersection.itemIds.end(),
		//ostream_iterator<ItemId>(cout, " "));
	    cout << endl;
	}
    }
    return(cnt);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::_computeExcCovLoss -
// 	compute pre- and post-insertion excess coverage loss for evalPenalty()
//
// Description:
//	- construct post-insertion BP with unionBp()
//	- computations based on optTree (optMap and optResultSets)
//	- ignore queries that already retrieve something from the node in
//	  question or would retrieve the new item (which would change an excess
//	  coverage I/O into data access, even if the BP didn't change at all)
///////////////////////////////////////////////////////////////////////////////

void
amdb_penaltystats::_computeExcCovLoss(
    const gist& tree, // in: target tree
    const amdb_wkldprofile& profile, // in
    const amdb_treemap& tmap, // in: map of target tree
    shpid_t leaf, // in: node we're inserting on
    const vec_t& preBp, // in: pre-insertion BP
    const vec_t& postBp, // in: post-insertion BP
    const vec_t& key, // in: key we're inserting
    const Vector& matches, // in: vector<int>, indices of queries matching key
    const Vector& queryStructs, // in: vector<gist_query_t *>
    int& preExcCovLoss, // out: pre-insertion loss
    int& postExcCovLoss) // out: post-insertion loss
{
    amdb_itemset leafSet;
    leafSet.pageItems(tmap, leaf);

    gist_ext_t* ext = tree.extension();
    amdb_ext_t* amdbext = amdb_ext_t::extension(ext);

    preExcCovLoss = postExcCovLoss = 0;
    amdb_itemset intersection;
    int i, j = 0;
    for (i = 0; i < profile.queries.size(); i++) {
        if (j < matches.size() && i == (int) matches[j]) {
	    // query i would retrieve 'key', we ignore it
	    j++;
	    continue;
	}

	amdb_wkldprofile::Query* queryInfo = (amdb_wkldprofile::Query *)
	    profile.queries[i];
	gist_query_t* query = (gist_query_t *) queryStructs[i];
	if (!intersection.intersection(leafSet, queryInfo->resultSet,
	    queryInfo->resultSetSize)) {

	    if (amdbext->consistent(ext, query, preBp, 2)) {
	        preExcCovLoss++;
	    }
	    if (amdbext->consistent(ext, query, postBp, 2)) {
	        postExcCovLoss++;
	    }
	}

	// XXX debug
	//copy(intersection.begin(), intersection.end(),
	    //ostream_iterator<ItemId>(cout, " "));
	//cout << endl;
    }
}


/////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::_computeMatches - compute indices of queries matching given key
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

void
amdb_penaltystats::_computeMatches(
    const gist& tree, // in
    const Vector& queryStructs, // in: vector<gist_query_t *>
    const vec_t& key, // in
    Vector& matches) // out: vector<int> of indices into queryStructs
{
    gist_ext_t* ext = tree.extension();
    amdb_ext_t* amdbext = amdb_ext_t::extension(ext);

    Vector::const_iterator it;
    int i;
    matches.erase(matches.begin(), matches.end());
    for (it = queryStructs.begin(), i = 0; it != queryStructs.end(); it++, i++) {
	if (amdbext->consistent(ext, (gist_query_t *) *it, key, 1)) {
	    matches.push_back((void *) i);
	}
    }
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::PenaltyStats::add
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void 
amdb_penaltystats::PenaltyStats::add(
    const PenaltyStats& s)
{
    actualAddIos += s.actualAddIos;
    optAddIos += s.optAddIos;
    preExcCovLoss += s.preExcCovLoss;
    actualExcCovLoss += s.actualExcCovLoss;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::FullPenaltyStats::clear
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void 
amdb_penaltystats::FullPenaltyStats::clear()
{
    _actualIos = 0.0;
    _actualAddIos = 0.0;
    _actualAddWeighted = 0.0;
    _optAddIos = 0.0;
    _optAddWeighted = 0.0;
    preExcCovLoss = 0.0;
    actualExcCovLoss = 0.0;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::FullPenaltyStats::set
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void
amdb_penaltystats::FullPenaltyStats::set(
    const PenaltyStats& stats, // in
    float targetUtil, // in
    const amdb_splitstats& splitStats, // in: needed for preIos
    const amdb_treemap& tmap) // in: needed for util
{
    clear();
    add(stats, targetUtil, splitStats, tmap);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::FullPenaltyStats::add
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void
amdb_penaltystats::FullPenaltyStats::add(
    const PenaltyStats& stats, // in
    float targetUtil, // in
    const amdb_splitstats& splitStats, // in: needed for preIos
    const amdb_treemap& tmap) // in: needed for util
{
    amdb_splitstats::SplitStats* ss = (amdb_splitstats::SplitStats *) 
        (*splitStats.splitStats.find(stats.actualLeaf)).second;
    assert(ss != NULL);
    _actualIos += (float) (ss->preIos + stats.actualAddIos);
    _actualAddIos += (float) stats.actualAddIos;
    _actualAddWeighted += (float) stats.actualAddIos *
        tmap.util(stats.actualLeaf) / targetUtil;
    _optAddIos += (float) stats.optAddIos;
    _optAddWeighted += (float) stats.optAddIos *
        tmap.util(stats.optLeaf) / targetUtil;
    preExcCovLoss += (float) stats.preExcCovLoss;
    actualExcCovLoss += (float) stats.actualExcCovLoss;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_penaltystats::computeAvgStats - 
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void
amdb_penaltystats::computeAvgStats(
    float targetUtil,
    const amdb_splitstats& splitStats,
    const amdb_treemap& tmap)
{
    avgStats.clear();
    PenaltyStatsVect::iterator it;
    for (it = penaltyStats.begin(); it != penaltyStats.end(); it++) {
	PenaltyStats* s = (PenaltyStats *) *it;
	avgStats.add(*s, targetUtil, splitStats, tmap);
    }
    int cnt = penaltyStats.size();
    avgStats._actualIos /= (float) cnt;
    avgStats._actualAddIos /= (float) cnt;
    avgStats._actualAddWeighted /= (float) cnt;
    avgStats._optAddIos /= (float) cnt;
    avgStats._optAddWeighted /= (float) cnt;
    avgStats.preExcCovLoss /= (float) cnt;
    avgStats.actualExcCovLoss /= (float) cnt;
}