amdb_splitstats.cc

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

	    // accesses any of the nodes anyway

	    // check if query accesses leaf anyway (empty access)
	    gist::AlignedPred z;
	    vec_t bp(z.pred, gist_p::max_tup_sz);
	    tree.getBp(leaf, bp);
	    bool preConsistent = false; // XXX debug
	    if (amdbext->consistent(ext, (gist_query_t*) queryStructs[i], bp, 2)) {
	        stats->preExcCovLoss++;
		preConsistent = true;
	    }
	    if (amdbext->consistent(ext, (gist_query_t*) queryStructs[i], leftBp, 2)) {
		stats->actualExcCovLoss++;
		assert(preConsistent); // XXX debug: leftBp shouldn't be bigger than 'bp'
	    }
	    if (amdbext->consistent(ext, (gist_query_t*) queryStructs[i], rightBp, 2)) {
		stats->actualExcCovLoss++;
		assert(preConsistent); // XXX debug
	    }
	}
    }
    cout << endl;

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// amdb_splitstats::initSplitInfo - set SplitInfo data
//
// Description:
//	- make copies of rightEntries, left- and rightBp
//	- can't be done in SplitInfo member function, because we need
//	  the optTree item map to compute left- and rightData
/////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::_splitInfoInit(
    SplitInfo& info, // out
    shpid_t page, // in
    const amdb_treemap& tmap, // in
    int rightEntries[], // in
    int numRight, // in
    const vec_t& leftBp, // in
    const vec_t& rightBp) // in
{

    info.rightEntries = new int[numRight];
    (void) memcpy((void *) info.rightEntries, rightEntries, sizeof(int) * numRight);
    info.numRight = numRight;
    info.leftBp = new char[leftBp.len(0)];
    (void) memcpy((void *) info.leftBp, leftBp.ptr(0), leftBp.len(0));
    info.leftLen = leftBp.len(0);
    info.rightBp = new char[rightBp.len(0)];
    (void) memcpy((void *) info.rightBp, rightBp.ptr(0), rightBp.len(0));
    info.rightLen = rightBp.len(0);

    info.leftData = info.rightData = 0;
    int itemCnt = tmap.itemCnt(page);
    int i, j = 0;
    for (i = 0; i < itemCnt; i++) {
        if (j < info.numRight && i == rightEntries[j]) {
	    info.rightData += tmap.size(page, i);
	    j++;
	} else {
	    info.leftData += tmap.size(page, i);
	}
    }
}


/////////////////////////////////////////////////////////////////////////
// amdb_splitstats::optSplit - produce 'optimal' split
//
// Description:
//	- 'optimal' split: derived by hypergraph partitioning
//	  of result sets projected onto node
//	- projection doesn't contain queries that don't retrieve anything from
//	  node or only retrieved single item
//	- returns sorted array containing the slot indices of items
//	  to be moved to the right sibling
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
amdb_splitstats::optSplit(
    gist& tree, // in
    const amdb_wkldprofile& profile, // in
    const amdb_treemap& tmap, // in
    shpid_t leaf, // in: leaf to be split
    int ubfactor, // in: hmetis balance parameter
    int rightEntries[], // out: slot indices of entries for right sib
    int& numRight,  // out
    vec_t& leftBp, // out
    vec_t& rightBp) // out
{
    // project the query result sets onto items contained in node
    amdb_clustering::ResultSet* projectedSets =
        new amdb_clustering::ResultSet[profile.queries.size()];
	// alloc. max number of result sets, we might end up with fewer
    int numProjectedSets;

    // project translated query result sets onto leaf (translate item numbers
    // in result sets in the process)
    profile.projectToNode(leaf, projectedSets, numProjectedSets);

    // produce bisection (clustering sorted in clusterNo)
    amdb_clustering::Clustering clustering;
    int numClusters;
    int numRetrieved;
    W_DO(amdb_clustering::optClustering(projectedSets, numProjectedSets, 0.5, 2, 10,
        ubfactor, tmap, clustering, numClusters, numRetrieved));
	// numClusters = 2: we want to split it in 2 parts
    clustering.sortClusterNo();

    // fill rightEntries with slot indices of cluster 1
    int pageOffset = tmap.itemOffset(leaf);
    int itemCnt = tmap.itemCnt(leaf);
    numRight = 0;
    amdb_clustering::ClusterInfoVect::iterator cit;
    for (cit = clustering.info.begin(); cit != clustering.info.end(); cit++) {
        if (cit->clusterNo == 1) {
	    rightEntries[numRight] = cit->itemNo - pageOffset;
	    assert(rightEntries[numRight] < itemCnt); // sanity check
	    numRight++;
	}
    }
    sort(rightEntries, rightEntries + numRight);

    // construct left and right page for BP computation
    gist_p leftPg, rightPg;
    tree.splitNode(leaf, leftPg, rightPg, rightEntries, numRight);
    gist_ext_t* ext = tree.extension();
    vec_t dummyPred; // don't have one, either
    bool bpChanged;
    ext->unionBp(leftPg, leftBp, false, dummyPred, dummyPred, bpChanged);
    ext->unionBp(rightPg, rightBp, false, dummyPred, dummyPred, bpChanged);

    // don't need projectedSets anymore
    amdb_clustering::freeResultSets(projectedSets, numProjectedSets);

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// amdb_splitstats::SplitInfo::write - write SplitInfo out in binary
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::SplitInfo::write(
    ostream& s, // in
    bool ascii) // in
{
    s.write((char *) this, sizeof(*this));

    // write rightEntries
    s.write((char *) rightEntries, numRight * sizeof(*rightEntries));

    // write leftBp
    s.write((char *) leftBp, leftLen);

    // write rightBp
    s.write((char *) rightBp, rightLen);
}


/////////////////////////////////////////////////////////////////////////
// amdb_splitstats::SplitInfo::read - read SplitInfo in binary
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::SplitInfo::read(
    istream& s)
{
    s.read((char *) this, sizeof(*this));

    // read rightEntries
    rightEntries = new int[numRight];
    s.read((char *) rightEntries, numRight * sizeof(*rightEntries));

    // read leftBp
    leftBp = new char[leftLen];
    s.read((char *) leftBp, leftLen);

    // read rightBp
    rightBp = new char[rightLen];
    s.read((char *) rightBp, rightLen);
}

amdb_splitstats::SplitInfo::~SplitInfo()
{
	// VCPORT_B
#ifndef WIN32
	if (numRight == 95)
		cout << "amdb_splitstats::SplitInfo::~SplitInfo()" << endl;
#endif
	// VCPORT_E
    delete [] rightEntries;
    delete [] leftBp;
    delete [] rightBp;
}

///////////////////////////////////////////////////////////////////////////////
// amdb_splitstats::SplitStats::add
//
// Description:
///////////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::SplitStats::add(
    const SplitStats& s)
{
    preIos += s.preIos;
    actualLeftIos += s.actualLeftIos;
    actualRightIos += s.actualRightIos;
    optLeftIos += s.optLeftIos;
    optRightIos += s.optRightIos;
    preExcCovLoss += s.preExcCovLoss;
    actualExcCovLoss += s.actualExcCovLoss;
}

amdb_splitstats::SplitStats::~SplitStats()
{
	// VCPORT_B
#ifndef WIN32
  //    actualSplit.~SplitInfo();
  //   optSplit.~SplitInfo();
#endif
	// VCPORT_E

}

///////////////////////////////////////////////////////////////////////////////
// amdb_splitstats::FullSplitStats::add
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::FullSplitStats::add(
    const SplitStats& stats, // in
    float targetUtil, // in: target util parameter for analysis
    float pageUtil) // in: actual util. in page
{
    _preIos += (float) stats.preIos;
    _preWeighted += (float) stats.preIos * pageUtil / targetUtil;
    _actualIos += (float) (stats.actualLeftIos + stats.actualRightIos);
    _actualWeighted += (float) stats.actualLeftIos *
        (float) stats.actualSplit.leftData / ((float) gist_p::data_sz * targetUtil) +
	(float) stats.actualRightIos * 
        (float) stats.actualSplit.rightData / ((float) gist_p::data_sz * targetUtil);
    _optIos += (float) (stats.optLeftIos + stats.optRightIos);
    _optWeighted += (float) stats.optLeftIos *
        (float) stats.optSplit.leftData / ((float) gist_p::data_sz * targetUtil) +
	(float) stats.optRightIos * 
        (float) stats.optSplit.rightData / ((float) gist_p::data_sz * targetUtil);
    preExcCovLoss += (float) stats.preExcCovLoss;
    actualExcCovLoss += (float) stats.actualExcCovLoss;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_splitstats::FullSplitStats::clear
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::FullSplitStats::clear()
{
    _preIos = 0.0;
    _preWeighted = 0.0;
    _actualIos = 0.0;
    _actualWeighted = 0.0;
    _optIos = 0.0;
    _optWeighted = 0.0;
    preExcCovLoss = 0.0;
    actualExcCovLoss = 0.0;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_splitstats::FullSplitStats::set
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::FullSplitStats::set(
    const SplitStats& s,
    float targetUtil,
    float pageUtil)
{
    clear();
    add(s, targetUtil, pageUtil);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_splitstats::computeAvgStats - set avgStats
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
amdb_splitstats::computeAvgStats(
    float targetUtil,
    amdb_treemap& tmap)
{
    avgStats.clear();
    SplitStatsMap::iterator it;
    for (it = splitStats.begin(); it != splitStats.end(); it++) {
        shpid_t pageno = (shpid_t) (*it).first;
        SplitStats* s = (SplitStats *) (*it).second;
	avgStats.add(*s, targetUtil, tmap.util(pageno));
    }
    int cnt = splitStats.size();
    avgStats._preIos /= (float) cnt;
    avgStats._preWeighted /= (float) cnt;
    avgStats._optIos /= (float) cnt;
    avgStats._optWeighted /= (float) cnt;
    avgStats._actualIos /= (float) cnt;
    avgStats._actualWeighted /= (float) cnt;
    avgStats.preExcCovLoss /= (float) cnt;
    avgStats.actualExcCovLoss /= (float) cnt;
}