amdb_analysis.cc

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

{
    // write filename (length in network order)
    int len = (filename == NULL ? 0 : strlen(filename));
    len = htonl(len);
    s.write((char *) &len, sizeof(len));
    if (filename != NULL) {
        s.write(filename, strlen(filename)); // don't use len!
    }

    // write map, profile, wkldStats, splitStats and penaltyStats,
    // together with indicators
    int notNull = htonl(map != NULL);
    s.write((char *) &notNull, sizeof(notNull));
    if (map != NULL) {
	W_DO(map->write(s, ascii));
    }
    notNull = htonl(profile != NULL);
    s.write((char *) &notNull, sizeof(notNull));
    if (profile != NULL) {
	W_DO(profile->write(s, ascii));
    }
    notNull = htonl(wkldStats != NULL);
    s.write((char *) &notNull, sizeof(notNull));
    if (wkldStats != NULL) {
	W_DO(wkldStats->write(s, ascii));
    }
    notNull = htonl(splitStats != NULL);
    s.write((char *) &notNull, sizeof(notNull));
    if (splitStats != NULL) {
	W_DO(splitStats->write(s, ascii));
    }
    notNull = htonl(penaltyStats != NULL);
    s.write((char *) &notNull, sizeof(notNull));
    if (penaltyStats != NULL) {
	W_DO(penaltyStats->write(s, ascii));
    }

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// amdb_analysis::analyzeWkld - compute wkld stats
//
// Description:
//	- for now, we ignore 'optTree'
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::analyzeWkld(
    bool optTree) // in: if true, analyze opt. tree
{
    TreeAnalysis* target = (optTree ? &optAnalysis : &actualAnalysis);;

    // need optClustering to compute metrics
    W_DO(_computeOptClustering());

    target->wkldStats = new amdb_wkldstats();
    target->wkldStats->computeStats(*target->profile, *target->map, *optClustering,
        parameters);
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// amdb_analysis::analyzeSplit - run splits on leaves and compute metrics
//
// Description:
//	- if done for optTree and optTree doesn't exist yet, compute it
//	  (give it same name as actual tree, plus "opt-" prefix)
//	- compute averages when done with all leaves
//
// Return Values:
//      RCOK
//	eHASSPLITSTATS
/////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::analyzeSplit(
    bool optTree) // in: if true, analyze split in opt. tree
{
    TreeAnalysis* target = (optTree ? &optAnalysis : &actualAnalysis);;
    //if (target->splitStats != NULL) {
        //return(eHASSPLITSTATS);
    //}

    if (optTree && target->tree == NULL) {
        W_DO(_createOptTree());
    }
    W_DO(_openTree(*target));

    if (_queries == NULL) {
        W_DO(_loadQueries());
    }

    int rightEntries[gist_p::max_scnt];
    int numRight;
    gist::AlignedPred x, y;
    vec_t leftBp(x.pred, gist_p::max_tup_sz);
    vec_t rightBp(y.pred, gist_p::max_tup_sz);

    target->splitStats = new amdb_splitstats();
    amdb_treemap::PageMap::iterator it;
    for (it = target->map->pageMap.begin();
        it != target->map->pageMap.end(); it++) {

	amdb_treemap::PageInfo* info = (amdb_treemap::PageInfo *)
	    (*it).second;
	if (info->level > 1) {
	    // this is not a leaf, ignore it
	    continue;
	}
	shpid_t pageno = (shpid_t) (*it).first;
	W_DO(target->tree->pickSplit(pageno, rightEntries, numRight,
	    leftBp, rightBp));
	W_DO(target->splitStats->evalSplit(*target->tree, *target->profile,
	    *target->map, *_queries, pageno, rightEntries, numRight, leftBp,
	    rightBp));
    }
    target->splitStats->computeAvgStats(parameters.targetUtil, *target->map);

    return(RCOK);
}


////////////////////////////////////////////////////////////////////////////////
// amdb_analysis::analyzePenalty - compute penalty metrics for sample insertions
//
// Description:
//	- evaluates insertions of keys in loadfile
//
// Return Values:
//      RCOK
//	eHASPENALTYSTATS
//	eCANTPARSEPRED
//	eFILEERROR
//	ePARSEERROR
////////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::analyzePenalty(
    bool optTree, // in: if true, analyze split in opt. tree
    const char* loadfile) // in: name of file containing keys
{
    TreeAnalysis* target = (optTree ? &optAnalysis : &actualAnalysis);;
    if (target->penaltyStats != NULL) {
        return(eHASPENALTYSTATS);
    }

    if (optTree && target->tree == NULL) {
        W_DO(_createOptTree());
    }
    W_DO(_openTree(*target));

    if (_queries == NULL) {
        W_DO(_loadQueries());
    }

    // make sure extension can parse predicates
    gist_ext_t* ext = target->tree->extension();
    if (ext->parsePred == NULL) {
	return(eCANTPARSEPRED);
    }

    ifstream s(loadfile);
    if (s.fail()) {
	return(eFILEERROR);;
    }

    target->penaltyStats = new amdb_penaltystats();
    // read lines and parse them
    // (format: "\"<key>\"")
    char buf[_MAXLINE];
    char keystr[_MAXLINE];
    char key[gist_p::max_tup_sz];
    int klen;
    vec_t keyv;
    shpid_t targetLeaf;
    while (s.getline(buf, sizeof(buf))) {
	istrstream s(buf); // scan input line for "<key>"
	if (_scanString(s, keystr) != RCOK) {
	    return(ePARSEERROR);
	}

	if (ext->parsePred(keystr, (void *) key, klen) != RCOK) {
	    return(ePARSEERROR);
	}

	// find the target leaf, then evaluate it
	keyv.set(key, klen);
	W_DO(target->tree->locateTargetLeaf(keyv, targetLeaf));
	W_DO(target->penaltyStats->evalPenalty(*target->tree, *target->profile,
	    *target->map, *_queries, targetLeaf, keyv));
    }

    s.close();

    target->penaltyStats->computeAvgStats(parameters.targetUtil,
        *target->splitStats, *target->map);

    return(RCOK);
}

/////////////////////////////////////////////////////////////////////////
// amdb_analysis::_computeOptClustering - compute hypergraph clustering
//
// Description:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::_computeOptClustering()
{
    if (optClustering != NULL) {
	// it's already been computed
        return(RCOK);
    }
    amdb_clustering::ResultSet* resultSets;
    actualAnalysis.profile->extractResultSets(resultSets);

    int dummyInt;
    optClustering = new amdb_clustering::Clustering();
    W_DO(amdb_clustering::optClustering(resultSets, actualAnalysis.profile->queries.size(),
        parameters.targetUtil, 0, 10, 1, *actualAnalysis.map, *optClustering,
	dummyInt, dummyInt));

    delete [] resultSets;

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// amdb_analysis::_createOptTree - create and save optAnalysis.tree
//
// Description:
//	- opt tree saved in file "opt-" + actualAnalysis.filename
//	- also creates the tree map and translateMap
//	- create optAnalysis.profile and copy result sets from 
//	  actualAnalysis.profile
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::_createOptTree()
{
    if (optClustering == NULL) {
        W_DO(_computeOptClustering());
    }

    // construct filename and create opt tree
    char* prefix = "opt-";
    int totalLen = strlen(actualAnalysis.filename) + strlen(prefix) + 1;
    optAnalysis.filename = new char[totalLen];
    (void) strcpy(optAnalysis.filename, prefix);
    char* rest = optAnalysis.filename + strlen(prefix);
    (void) strcpy(rest, actualAnalysis.filename);
    optAnalysis.tree = new gist();
    assert(optAnalysis.tree != NULL);
    Rid2ItemIdMap ridMap;
    W_DO(actualAnalysis.tree->createOpt(optAnalysis.filename, parameters.targetUtil,
        *actualAnalysis.profile, *optClustering, *actualAnalysis.map, ridMap));
    W_DO(optAnalysis.tree->open(optAnalysis.filename));

    // create tree map
    optAnalysis.map = new amdb_treemap();
    W_DO(optAnalysis.tree->computeTreeMap(optAnalysis.map));

    // compute translateMap
    TranslationMap* translateMap = new TranslationMap();
    //translateMap = new TranslationMap();
    amdb_treemap::ItemMap::iterator it;
    ItemId optId; // index into optAnalysis.map->itemMap
    for (it = optAnalysis.map->itemMap.begin(), optId = 0;
        it != optAnalysis.map->itemMap.end(); it++, optId++) {

	amdb_treemap::RecInfo* info = (amdb_treemap::RecInfo*) *it;
	ItemId origId = ridMap[info->loc.treeLoc];
	// should I do Rid2ItemIdMap::iterator rit = ridMap->find(info->treeLoc]?
	(*translateMap)[origId] = (void *) optId;
    }

    // create profile with result sets
    optAnalysis.profile = new amdb_wkldprofile();
    optAnalysis.profile->copyResultSets(*actualAnalysis.profile, *translateMap);
    delete translateMap; // no longer needed

    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::_scanString
//
// Description:
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::_scanString(
    istream& s, // in: input stream
    char* str) // out: string stripped off '"'s
{
    char ch;
    s >> ws; // discard whitespace
    s >> ch;
    if (ch != '"') return(ePARSEERROR);
    int i = 0;
    do {
	s.get(ch);
	str[i] = ch;
	i++;
    } while (!s.eof() && ch != '"');
    if (s.eof()) return(ePARSEERROR); // key isn't terminated
    assert(ch == '"');
    str[i-1] = '\0'; // replace terminating double quote
    if (i == 1) return(ePARSEERROR); // no key specified
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::_loadQueries - parse qualifications stored in profile
//
// Description:
//	- allocate _queries as well as the gist_query_t objects
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::_loadQueries()
{
    _queries = new Vector();
    amdb_wkldprofile::QueryVect::const_iterator it;
    amdb_wkldprofile* prof = actualAnalysis.profile;
    for (it = prof->queries.begin(); it != prof->queries.end(); it++) {
	const amdb_wkldprofile::Query* query =
	    (amdb_wkldprofile::Query *) *it;
        gist_query_t* queryStruct;
        rc_t status = actualAnalysis.tree->extension()->parseQuery(
	    query->qual, queryStruct);
        if (status != RCOK) {
            return(ePARSEERROR);
        }
	_queries->push_back((void *) queryStruct);
    }
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::TreeAnalysis::~TreeAnalysis - destructor
//
// Description:
//	- dealloc state and close tree
///////////////////////////////////////////////////////////////////////////////

amdb_analysis::TreeAnalysis::~TreeAnalysis()
{
    delete tree;
    delete [] filename;
    delete map;
    delete profile;
    delete wkldStats;
    delete splitStats;
    delete penaltyStats;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::Parameters::write - write to output stream
//
// Description:
//	- write integer in network order
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::Parameters::write(
    ostream& s,
    bool ascii)
{
    int runs = htonl(randomRuns);
    s.write((char *) &runs, sizeof(runs));
    s.write((char *) &targetUtil, sizeof(targetUtil));
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::Parameters::read - read from input stream
//
// Description:
//	- convert integers from network to host order
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::Parameters::read(
    istream& s)
{
    s.read((char *) &randomRuns, sizeof(randomRuns));
    randomRuns = ntohl(randomRuns);
    s.read((char *) &targetUtil, sizeof(targetUtil));
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_analysis::_openTree - open target tree
//
// Description:
//	- open tree in target analysis if it's not already open
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_analysis::_openTree(
    TreeAnalysis& target)
{
    if (target.tree != NULL) {
        // it's already open
	return(RCOK);
    }
    // open tree
    assert(target.filename != NULL);
    target.tree = new gist();
    W_DO(target.tree->open(target.filename));
    return(RCOK);
}