gist_rtree.cc

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

    return (cmpFcts[level > 1][q->argType][q->oper](pred, predLen, *sarg));
}


/////////////////////////////////////////////////////////////////////////
// rtbase_ext_t::union_bp - generate BR for collection of predicates
//
// Description:
//	- if !bpIsValid, create one from scratch by unioning the predicates
//	  on the page
//	- if either pred1 or pred2 is passed in, union them to the BP 
//	  incrementally
//
/////////////////////////////////////////////////////////////////////////

void
rtbase_ext_t::union_bp(
    const gist_predcursor_t& pcursor, // in
    const gist_p& page, // in
    const vec_t& pred1, // in
    const vec_t& pred2, // in
    vec_t& bp, // in/out
    bool& bpChanged, // out
    bool bpIsValid) // in
    const
{
    int level = page.level();
    void* bpPtr = bp.ptr(0);
    int bpLen = bp.len(0);

    rt_pred* newBp = NULL; // the first 'expand' will create a predicate
    int d; // dimension of predicates
    if (!bpIsValid) {
	// need to build a BP for the predicates on the page from scratch
	assert(pcursor.numElems > 0);
	d = convFcts[level > 1][rt_dim](pcursor.elems[0].keyLen);
	bpLen = convFcts[1][rt_size](d); // size of BP
	bp.set(bpPtr, bpLen);
	bpChanged = true; // we're generating a new one

	for (int i = 0; i < pcursor.numElems; i++) {
	    newBp = expandFcts[level > 1](newBp, pcursor.elems[i].key,
		pcursor.elems[i].keyLen, true);
	}
    } else {
	// if a BP is given, we know it's an internal node predicate (level > 1 == true)
	d = convFcts[true][rt_dim](bpLen);
	bpChanged = false;
	newBp = expandFcts[1](NULL, bpPtr, bpLen, false); // copy existing BP
    }

    // add the extra predicates to the BP
    if (pred1.len(0) != 0) {
	newBp = expandFcts[level > 1](newBp, pred1.ptr(0), pred1.len(0), true);
    }
    if (pred2.len(0) != 0) {
	newBp = expandFcts[level > 1](newBp, pred2.ptr(0), pred2.len(0), true);
    }

    // flag whether or not we need to change the stored BP
    if (bpIsValid) {
	bpChanged = bpChanged || !bpCmpFcts[rt_bpequal](bpPtr, bpLen, *newBp);
    }

    if (bpChanged) {
	(void) memcpy(bpPtr, newBp->coords(), bpLen);
    }
    delete newBp;
}


gist_cursorext_t*
rtbase_ext_t::queryCursor(
    const gist_query_t* query) const
{
    rt_query_t* q = (rt_query_t*) query;
    rt_query_t::rt_oper op = q->oper;
    assert(op >= 0 && op < rt_query_t::rt_numoper);
    gist_cursorext_t::gist_cursorext_id id = opTbl[op];
    assert(id >= 0 && id < gist_cursorext_t::cext_numext);
    return(gist_cursorext_t::gist_cursorext_list[id]);
}

bool
rtbase_ext_t::check(
    const void *bp, 
    int bplen, 
    const void *pred, 
    int predlen, 
    int level) const
{
    rt_pred* p = expandFcts[level > 1](NULL, pred, predlen, false);
    bool res = bpCmpFcts[rt_bpint](bp, bplen, *p);
    if (!res) {
	int x = 1;			// gdb watch/break line
    }
    assert(convFcts[level > 1][rt_dim](predlen) == convFcts[1][rt_dim](bplen));
    delete p;
    return res;
}


///////////////////////////////////////////////////////////////////////////////
// rt_ext_t methods
///////////////////////////////////////////////////////////////////////////////

void
rt_ext_t::penalty(
    const void *subtreePred,
    int predLen,
    int level,
    const void *newKey,
    int keyLen,
    gist_penalty_t &p) const
{
    rt_pred* newBp = expandFcts[1](NULL, subtreePred, predLen, false);
    double oldSpan = propFcts[1][rt_span](*newBp);
    (void) expandFcts[0](newBp, newKey, keyLen, true);
    double newSpan = propFcts[1][rt_span](*newBp);
    p.p = (newSpan > oldSpan) ? (newSpan - oldSpan) : 0.0;
    delete newBp;
}

void
rt_ext_t::pickSplit(
    gist_predcursor_t &pcursor,
    const gist_p& page,
    int rightEntries[] /*out*/,
    int &numRight /*out*/,
    const void *oldBp,
    int oldLen,
    void *leftBp /*out*/,
    int &leftLen /*in/out*/,
    void *rightBp /*out*/,
    int &rightLen /*in/out*/) const
{
    // Guttman's original quadratic split algorithm works as follows:
    // - pick two seed entries by (quadratically) finding the pair A,B
    //   with the lowest 'waste' factor:
    //		waste(A,B) = area(union(A,B)) - area(A) - area(B)
    // - assign the remaining entries to one of the two clusters, X,Y,
    //   based on their 'enlargement' factor:
    //		enlarge(X,A) = area(union(X,A)) - area(X)
    //   - find some item A with max{|enlarge(X,A) - enlarge(Y,A)|}
    //   - assign A to X,Y based on min{enlarge(X,A),enlarge(Y,A)}
    //     (using min{area(X),area(Y)} and min{|X|,|Y|}, respectively, 
    //     to break ties; these are the same assignment criteria as for
    //     the linear split algorithm)
    //   this step is also quadratic since both the inner and outer
    //   loops are linear.

    // in order to use this pickSplit(), the bp type must support a
    // way to compute its span (i.e., volume).

    int level = page.level();
    int itemCnt = pcursor.numElems;	// # of items on the page
    if (itemCnt < 2) {			// we can't split with fewer entries!
	// XXX nicer error-handling goes here.
	assert(0);
    }

    int i, j;

    // find the item pair that cause the most waste.
    double maxWaste = -1.0;
    int leftSeed = -1, rightSeed = -1;
    double* spans = new double[itemCnt];
    rt_pred* tmpBp = NULL;
    for (i = 0; i < itemCnt; ++i) {
	assert(pcursor.elems[0].keyLen == pcursor.elems[i].keyLen);
	tmpBp = expandFcts[level > 1](tmpBp, pcursor.elems[i].key,
	    pcursor.elems[i].keyLen, false);
	spans[i] = propFcts[1][rt_span](*tmpBp);
    }
    for (i = 0; i < itemCnt; ++i) {
	const void* k1 = pcursor.elems[i].key;
	int k1len = pcursor.elems[i].keyLen;
	for (j = i + 1; j < itemCnt; ++j) { // XXX assumes union is symmetric
	    tmpBp = expandFcts[level > 1](tmpBp, k1, k1len, false);

	    const void* k2 = pcursor.elems[j].key;
	    int k2len = pcursor.elems[j].keyLen;

	    (void) expandFcts[level > 1](tmpBp, k2, k2len, true);
	    double bpspan = propFcts[1][rt_span](*tmpBp);
	    if (bpspan - (spans[i] + spans[j]) >= maxWaste) {
		leftSeed = i;
		rightSeed = j;
		maxWaste = bpspan - (spans[i] + spans[j]);
	    }
	}
    }
    delete tmpBp;
    delete [] spans;
    // at this point, leftSeed and rightSeed must be valid because we
    // must have at least one pair and therefore must have a maximally
    // wasteful pair.

    // initialize the left and right clusters using the new seeds.
    // leftPred and rightPred are actually instances of the
    // appropriate bp class.
    rt_pred* leftPred = (rt_pred*)
	expandFcts[level > 1](NULL, pcursor.elems[leftSeed].key,
	    pcursor.elems[leftSeed].keyLen, false);
    rt_pred* rightPred = (rt_pred*)
	expandFcts[level > 1](NULL, pcursor.elems[rightSeed].key,
	    pcursor.elems[rightSeed].keyLen, false);
    int d = convFcts[level > 1][rt_dim](pcursor.elems[leftSeed].keyLen);
    leftLen = rightLen = convFcts[1][rt_size](d);
    int numLeft = numRight = 1;
    rightEntries[0] = rightSeed;
    int remaining = itemCnt - 2;

    if (remaining > 0) {
	// 'which' tracks the items that have not yet been assigned to
	// any cluster.  we assume that the order in which the items
	// on a page are processed does not matter (which may not be
	// reasonable for all trees).
	int* which = new int[remaining];
	for (i = 0, j = 0; i < itemCnt; ++i) {
	    if (i != leftSeed && i != rightSeed) {
		which[j++] = i;
	    }
	}

	int threshold = (int) (MINSPLITUTIL * itemCnt);
	rt_pred* tmpPred = NULL;
	while (remaining > 0) {
	    // if one of the clusters is now guaranteed to fall under
	    // the minimum utilization, we just assign the remaining
	    // entries to that cluster and quit.
	    rt_pred* fixup = NULL;
	    if (numLeft + remaining < threshold) {
		numLeft += remaining;
		fixup = leftPred;
	    } else if (numRight + remaining < threshold) {
		fixup = rightPred;
	    }
	    if (fixup) {
		for (i = 0; i < remaining; ++i) {
		    (void) expandFcts[level > 1](fixup,
			pcursor.elems[which[i]].key,
			pcursor.elems[which[i]].keyLen, true);
		    if (fixup == rightPred) {
			rightEntries[numRight] = which[i];
			++numRight;
		    }
		}
		remaining = 0;
		continue; // break while
	    }

	    // otherwise, choose the next item for assignment using
	    // the enlargement factor.
	    double leftSpan = propFcts[1][rt_span](*leftPred);
	    double rightSpan = propFcts[1][rt_span](*rightPred);
	    double maxDiff = -1.0;
	    double leftEnlarge = -1.0, rightEnlarge = -1.0;
	    int chosen = -1;
	    for (i = 0; i < remaining; ++i) {
		const void* k = pcursor.elems[which[i]].key;
		int klen = pcursor.elems[which[i]].keyLen;

		tmpPred = expandFcts[1](tmpPred, leftPred->coords(), leftLen,
		    false);
		(void) expandFcts[level > 1](tmpPred, k, klen, true);
		double newLeft = propFcts[1][rt_span](*tmpPred) - leftSpan;

		tmpPred = expandFcts[1](tmpPred, rightPred->coords(), rightLen,
		    false);
		(void) expandFcts[level > 1](tmpPred, k, klen, true);
		double newRight = propFcts[1][rt_span](*tmpPred) - rightSpan;

		double newDiff = fabs(newLeft - newRight);
		if (newDiff > maxDiff) {
		    chosen = i;
		    maxDiff = newDiff;
		    leftEnlarge = newLeft;
		    rightEnlarge = newRight;
		}
	    }
	    assert(chosen >= 0 && chosen < remaining);

	    // now, choose the target cluster for this item.
	    bool pickLeft = true;
	    if (leftEnlarge != rightEnlarge) {
		pickLeft = (leftEnlarge < rightEnlarge);
	    } else if (leftSpan != rightSpan) {
		pickLeft = (leftSpan < rightSpan);
	    } else if (numLeft != numRight) {
		pickLeft = (numLeft < numRight);
	    }
	    rt_pred* pickPred;
	    if (pickLeft) {
		pickPred = leftPred;
		++numLeft;
	    } else {
		pickPred = rightPred;
		rightEntries[numRight] = which[chosen];
		++numRight;
	    }
	    (void) expandFcts[level > 1](pickPred,
		pcursor.elems[which[chosen]].key,
		pcursor.elems[which[chosen]].keyLen, true);

	    // now, fix up 'which' so that only unchosen items remain
	    // in the valid portion of the array.
	    which[chosen] = which[remaining - 1];
	    --remaining;
	}
	delete tmpPred;
	delete [] which;
    }

    // finally, just save 'leftPred' and 'rightPred' into 'leftBp' and
    // 'rightBp' and we're done.
    (void) memcpy(leftBp, leftPred->coords(), leftLen);
    (void) memcpy(rightBp, rightPred->coords(), rightLen);
    delete leftPred;
    delete rightPred;

    assert(numLeft + numRight == itemCnt);
}