//
// See the file LICENSE for redistribution information.
//
// Copyright (c) 2002-2003
//	Sleepycat Software.  All rights reserved.
//

static const char revid[] = "$Id: QueryPlan.cpp,v 1.134 2004/01/27 00:31:43 merrells Exp $";

#include "dbxml/XmlPortability.hpp"
#include "dbxml/XmlNamespace.hpp"
#include <float.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cassert>
#include "QueryPlan.hpp"
#include "Log.hpp"
#include "Container.hpp"
#include "QueryContext.hpp"
#include "Value.hpp"
#include "SyntaxManager.hpp"
#include "OperationContext.hpp"
#include "Cursor.hpp"
#include "HighResTimer.hpp"
#include "Document.hpp"

#if defined(DBXML_DOM_XERCES2)
#include <xercesc/dom/DOM.hpp>
#if defined(XERCES_HAS_CPP_NAMESPACE)
  XERCES_CPP_NAMESPACE_USE
#endif
#endif

#if defined(DBXML_XPATH_PATHAN)
#include <pathan/XPathEvaluator.hpp>
#include <pathan/XPathNSResolver.hpp>
#endif

#include "UTF8.hpp"

using namespace DbXml;

//#define DEBUG_RETURNTYPE

static void debugOutput_ids(
    const Container &container,
    const IDS::SharedPtr &ids,
    const char *name,
    const QueryPlan *qp,
    const HighResTimer *aft,
    const HighResTimer *afdt,
    double cost)
{
#if defined(DBG_ENABLED)
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream oss;
		oss << name << " : ";
		if (aft != 0) {
			long seconds, microseconds;
			aft->duration(&seconds, &microseconds);
			double duration = ((double)seconds * 1000) + ((double)microseconds / 1000.0);
			oss << "af=" << duration << " : ";
		}
		if (afdt != 0) {
			long seconds, microseconds;
			afdt->duration(&seconds, &microseconds);
			double duration = ((double)seconds * 1000) + ((double)microseconds / 1000.0);
			oss << "afd=" << duration << " : ";
		}
		if (cost != 0) {
			oss << "efd=" << cost << " : ";
		}
		if (qp != 0) {
			oss << qp->toString().c_str() << " : ";
		}
		if (!ids || ids->size() == 0) {
			oss << "NONE";
		} else {
			oss << "[" << ids->size() << "] ";
			int n = 0;
			IDS::const_iterator p;
			for (p = ids->begin();n < 20 && p != ids->end();++p, ++n) {
				oss << *p << " ";
			}
			if (p != ids->end()) {
				oss << "...";
			}
		}
		container.log(C_QUERY, L_DEBUG, oss);
	}
#endif
}

// QueryExecutionContext

QueryExecutionContext::QueryExecutionContext(const Container &container, QueryContext &context, bool debugging)
	: container(container),
	context(context),
	costToFilterPointer(0),
	debugging_(debugging)
{}

QueryExecutionContext::~QueryExecutionContext()
{}

const Container &QueryExecutionContext::getContainer() const
{
	return container;
}

void QueryExecutionContext::setCostToFilterFunction(CostFunctionPointer cfp)
{
	costToFilterPointer = cfp;
}

double QueryExecutionContext::costToFilter(const IDS::SharedPtr &ids) const
{
	double r = DBL_MAX; // Very costly... keep refining candidate set.
	if (costToFilterPointer != 0) {
		r = (*costToFilterPointer)((!ids ? 0 : ids->size()));
	}
	return r;
}

string QueryExecutionContext::toString() const
{
	return "QueryExecutionContext"; // jcm - could provide a description for debugging
}

void QueryExecutionContext::addExecutionStep(const string &step)
{
	executionPath_ += step;
	executionPath_ += ",";
}

string QueryExecutionContext::getExecutionPath() const
{
	return executionPath_;
}

// QueryPlan

QueryPlan::QueryPlan(Type type)
	: returnType_(RETURNTYPE_CANDIDATESET),
	type_(type),
	costCalculated_(false),
	executionCost_(0.0)
{}

QueryPlan::~QueryPlan()
{}

int QueryPlan::execute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	HighResTimer t;
	t.start();
	int err = doExecute(context, qec, ids);
	t.stop();
	if (moniker() != 0) {
		debugOutput_ids(qec.getContainer(), ids, moniker(), this, 0, &t, cost(context, qec));
	}
	return err;
}

double QueryPlan::cost(OperationContext &context, QueryExecutionContext &qec)
{
	if (!costCalculated_) {
		costCalculated_ = true;
		executionCost_ = doCost(context, qec);
	}
	return executionCost_;
}

bool QueryPlan::is(const QueryPlan::SharedPtr &qp, const Type &type)
{
	return (qp && (qp->getType() == type));
}

int QueryPlan::next(QueryContext &qc, XmlValue &value)
{
	UNUSED(qc);
	UNUSED(value);
	return 0;
}

int QueryPlan::optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int phase)
{
	UNUSED(txn);
	UNUSED(container);
	UNUSED(context);
	UNUSED(indexSpecification);
	UNUSED(phase);
	return 0;
}

void QueryPlan::reset()
{
	costCalculated_ = false; // recalculate cost for each evaluation.
}

double QueryPlan::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	UNUSED(context);
	UNUSED(qec);
	return 0;
}

std::string QueryPlan::getReturnTypeAsString() const
{
	switch (getReturnType()) {
	case QueryPlan::RETURNTYPE_ALL:
		return "A,";
	case QueryPlan::RETURNTYPE_RESULTSET:
		return "RS,";
	case QueryPlan::RETURNTYPE_CANDIDATESET:
		return "";
	case QueryPlan::RETURNTYPE_NONE:
		return "0,";
	case QueryPlan::RETURNTYPE_INHERIT:
		return "I,";
	}
	return "?,";
}

// QueryPlanNode

QueryPlanNode::QueryPlanNode(Type type, QueryPlan::SharedPtr a, QueryPlan::SharedPtr b)
	: QueryPlan(type), l_(a), r_(b)
{
	setReturnType(QueryPlan::RETURNTYPE_INHERIT);
}

QueryPlanNode::~QueryPlanNode()
{}

void QueryPlanNode::setLeft(QueryPlan::SharedPtr a)
{
	l_ = a;
}

void QueryPlanNode::setRight(QueryPlan::SharedPtr b)
{
	r_ = b;
}

QueryPlan::SharedPtr QueryPlanNode::getLeft()
{
	return l_;
}

QueryPlan::SharedPtr QueryPlanNode::getRight()
{
	return r_;
}

const QueryPlan::SharedPtr QueryPlanNode::getLeft() const
{
	return l_;
}

const QueryPlan::SharedPtr QueryPlanNode::getRight() const
{
	return r_;
}

QueryPlan::SharedPtr QueryPlanNode::takeLeft()
{
	QueryPlan::SharedPtr qp = l_;
	l_.reset(0);
	return qp;
}

QueryPlan::SharedPtr QueryPlanNode::takeRight()
{
	QueryPlan::SharedPtr qp = r_;
	r_.reset(0);
	return qp;
}

QueryPlan &QueryPlanNode::rightmost()
{
	if (r_) return r_->rightmost();
	if (l_)	return l_->rightmost();
	return *this;
}

string QueryPlanNode::leftToString() const
{
	string s;
	if (l_)
		s = l_->toString();
	else
		s = "NULL";
	return s;
}

string QueryPlanNode::rightToString() const
{
	string s;
	if (r_)
		s = r_->toString();
	else
		s = "NULL";
	return s;
}

void QueryPlanNode::replace(QueryPlan::SharedPtr original, QueryPlan::SharedPtr replacement)
{
	if (l_ == original)
		setLeft(replacement);
	else if (r_ == original)
		setRight(replacement);
	else
		assert(0); // Programming Error
}

void QueryPlanNode::reset()
{
	if (l_)
		l_->reset();
	if (r_)
		r_->reset();
}

int QueryPlanNode::optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int phase)
{
	//	outputToDebug(container,"Optimizing",this);
	int ra = 0; // The number of rules applied.
	if (l_) {
		//		outputToDebug(container," Before Left Optimized",l.get());
		l_ = optimize_node(txn, container, context, phase, l_, indexSpecification, ra);
		//		outputToDebug(container," After Left Optimized (1)",l.get());
		assert(l_);
		ra += l_->optimize(txn, container, context, indexSpecification, phase);
		//		outputToDebug(container," After Left Optimized (2)",l.get());
	}
	if (r_) {
		//		outputToDebug(container," Before Right Optimized",r.get());
		r_ = optimize_node(txn, container, context, phase, r_, indexSpecification, ra);
		//		outputToDebug(container," After Left Optimized (1)",r.get());
		assert(r_);
		ra += r_->optimize(txn, container, context, indexSpecification, phase);
		//		outputToDebug(container," After Left Optimized (2)",r.get());
	}
	return ra;
}

void QueryPlanNode::outputToDebug(const Container &container, const char *msg, QueryPlan *qp) const
{
#if defined(DBG_ENABLED)
	if (isLogEnabled(C_OPTIMIZER, L_DEBUG)) {
		ostringstream oss;
		oss << msg << ": " << qp->toString().c_str();
		container.log(C_OPTIMIZER, L_DEBUG, oss);
	}
#endif
}

//
// Intermediate:
//  Glue(x,y)
//  And(x,y)
//  Or(x,y)
//  Step(axis,operation,name(s),value)
//
// Operators:
//  SS                                            - Sequantial Scan
//  RI(index,operation,name1)                     - Restriction Index (node presence)
//  RI(index,operation,name1,value1)              - Restriction Index (node equality)
//  RI(index,operation,name1,name2)               - Restriction Index (edge presence)
//  RI(index,operation,name1,name2,value1)        - Restriction Index (edge equality)
//  RI(index,operation,name1,value1,name2,value2) - Restriction Index (range)
//  u(x,y)                                        - Union
//  n(x,y)                                        - Intersection
//  RFP(X)                                        - Record Filter and Project
//  RF(X)                                         - Record Filter
//  RA(X)                                         - Record Access
//  MDA(X)                                        - Metadata Access
//
// Phase One
//
//  P1R1: Glue(Step(child::x),Step(child::x,op,v))
//                                      ...reduce... Step(child::x,op,v) (*1)
//  P1R2: Glue(Step(child::x),Step({child|attribiute}::x.y))
//                                      ...reduce... Step({child|attribiute}::x.y) (*2)
//  P1R3: Glue(Step(a::x),Step(op,v))   ...reduce... Step(a::x,op,v)
//
// Phase Two
//
//  P2R1: Glue(x,y)                     ...replace... n(x,y)
//  P2R2: Step(axis::x)                 ...replace... RI(node-axis-presence-none,equality,x) or RI(node-axis-equality-*,prefix,x)
//  P2R3: Step(axis::x,operation,value) ...replace... RI(node-axis-equality-syntax,operation,x,value)
//  P2R4: Step(axis::x.y)               ...replace... RI(edge-axis-presence-none,equality,xy) or RI(edge-axis-equality-*,prefix,xy)
//  P2R5: Step(axis::x.y.z)             ...replace... n(P2R4(xy),P2R4(yz))
//  P2R6: And(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//  P2R6: Glue(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//  P2R6: n(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//                                      ...replace... RI(eq,range,n,{GTX|GTE},v1,{LTX|LTE},v2)
//  P2R7: Step(a::n,substring,v)        ...replace... n(RI(eq,eq,n,v[i to i+3]),RI(eq,eq,n,v[i+1 to i+1+3]))...
//
//  P2R8: Step(axis::x.y,operation,value)   ...replace... RI(edge-axis-equality-syntax,operation,xy,value)
//  P2R9: Step(axis::x.y.z,operation,value) ...replace... n(P2R4(xy),P2R8(yz))
//  P2R10: Step(operation,value)        ...replace... SS (*3)
//
// Phase Three
//
//  P3R1: And(x,y)                      ...replace... n(x,y)
//  P3R2: Or(x,y)                       ...replace... u(x,y)
//
// Phase Four
//
//  P4R1: n(SS,x)                       ...reduce... x
//        n(SS,SS)                      ...reduce... SS
//  P4R2: u(SS,x)                       ...reduce... SS
//  P4R3: RF(RA(x)) and x.returntype==resultset
//  P4R4: n(RI(x,presence),RI(x,equality,y)) ...replace... RI(x,equality,y)
//
// Phase Five
//
//  P5R1: RA(RF(RA(x)))                 ...reduce... RF(RA(x))
//  P5R2: MDA(RF(RA(x)))                ...reduce... RFP(RA(x))
//
// Notes
//
// *1) This was introduced to solve SR#8527. The query processor
//     was not dealing with text() and edge indexes correctly.
//     The Step contextNode flag was introduced so that we can
//     tell the difference between a step for a given name, and
//     a step for the context node. In a query like /a/b[text()='']
//     this rule helps us get to a.b=''.
//
// *2) If edge indexing has been enabled for y, then x and x.y can
//     be combined into a single step.
//
// *3) P2R10 is designed to mop up Steps that didn't get combined
//     in P1R3.
//
// jcm -  A and ( B or C )                ...expand...  ( (A and B) or (A and C) )
// JCM - P2R5 and P2R9 are no longer needed.
//
QueryPlan::SharedPtr QueryPlanNode::optimize_node(DbTxn *txn, const Container &container, XmlQueryContext &context, int phase, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied)
{
	QueryPlan::SharedPtr r;
	switch (phase) {
	case 1:
		r = optimize_node_phase_one(txn, container, context, me, indexSpecification, rulesApplied);
		break;
	case 2:
		r = optimize_node_phase_two(txn, container, context, me, indexSpecification, rulesApplied);
		break;
	case 3:
		r = optimize_node_phase_three(txn, container, context, me, rulesApplied);
		break;
	case 4:
		r = optimize_node_phase_four(txn, container, context, me, rulesApplied);
		break;
	case 5:
		r = optimize_node_phase_five(txn, container, context, me, rulesApplied);
		break;
	}
	return r;
}

QueryPlan::SharedPtr QueryPlanNode::optimize_node_phase_one(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied)
{
	// P1R1: Glue(Step(child::x),Step(child::x,op,v))
	//                                      ...reduce... Step(child::x,op,v) (*1)
	if (QueryPlan::is(me, QueryPlan::GLUE)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		QueryPlan::SharedPtr right = x->getRight();
		if (left->getType() == QueryPlan::STEP &&
		    right->getType() == QueryPlan::STEP) {
			StepQP *leftStep = ((StepQP*)left.get());
			StepQP *rightStep = ((StepQP*)right.get());
			bool leftMatch =
			    leftStep->getAxis() == StepQP::AXIS_CHILD &&
			    leftStep->getOperation() == Database::NONE;
			bool rightMatch =
			    rightStep->getAxis() == StepQP::AXIS_CHILD &&
			    !rightStep->isAnywhere() &&
			    rightStep->isContextNode();
			if (leftMatch && rightMatch && leftStep->getName()==rightStep->getName()) {
				x->takeRight();
				rightStep->setContextNode(false);
				logRuleApplication(container, "P1R1", x, right.get());
				me = right;
				rulesApplied++;
			}
		}
	}
	if (QueryPlan::is(me, QueryPlan::GLUE)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		QueryPlan::SharedPtr right = x->getRight();
		if (left->getType() == QueryPlan::STEP &&
		    right->getType() == QueryPlan::STEP) {
			StepQP *leftStep = ((StepQP*)left.get());
			StepQP *rightStep = ((StepQP*)right.get());
			bool leftMatch =
			    leftStep->getAxis() == StepQP::AXIS_CHILD &&
			    leftStep->getOperation() == Database::NONE &&
			    leftStep->countNames()==1;
			bool rightMatch =
			    (rightStep->getAxis() == StepQP::AXIS_CHILD ||
			     rightStep->getAxis() == StepQP::AXIS_ATTRIBUTE) &&
			    rightStep->countNames()==2;
			if (leftMatch && rightMatch && leftStep->getName()==rightStep->getName()) {
				// Check if the right step is edge indexed
				const IndexVector *iv = indexSpecification.getIndexOrDefault(rightStep->getName(1).c_str());
				bool indexEnabled = false;
				Index index(
				    Index::PATH_EDGE |
				    (rightStep->getAxis() == StepQP::AXIS_ATTRIBUTE ? Index::NODE_ATTRIBUTE : Index::NODE_ELEMENT));
				if (iv) {
					switch (rightStep->getOperation()) {
					case Database::NONE:
						// Check for a presence index to perform an equality operation against
						index.set(Index::KEY_PRESENCE);
						indexEnabled = iv->isEnabled(index, Index::PNKS_MASK);
						if (!indexEnabled) {
							// check for an equality index to perform a prefix operation against
							index.set(Index::KEY_EQUALITY);
							index.set(Syntax::NONE);
							indexEnabled = iv->isEnabled(index, Index::PNK_MASK);
							if (!indexEnabled) {
								// check for a substring index to perform a prefix operation against
								index.set(Index::KEY_SUBSTRING);
								indexEnabled = iv->isEnabled(index, Index::PNK_MASK);
							}
						}
						break;
					case Database::SUBSTRING:
						index.set(Index::KEY_SUBSTRING);
						indexEnabled = iv->isEnabled(index, Index::PNK_MASK);
						break;
					default:
						index.set(Index::KEY_EQUALITY);
						//
						// If the value is a variable reference, then we can dereference
						// to find its type. If the user is compiling the query ahead of
						// execution then it would be wise of them to place a dummy value
						// for the variable in the context so that we get a hint as to its
						// type. In this case there is no support for variables that change
						// type between query executions.
						//
						XmlValue value = rightStep->getValue();
						Syntax::Type type = Syntax::NONE;
						if (!value.isNull()) {
							type = ((Value*)value)->getSyntaxType(context);
						}
						index.set(type);
						indexEnabled = iv->isEnabled(index, (type == Syntax::NONE ? Index::PNK_MASK : Index::PNKS_MASK));
					}
				}
				if (indexEnabled) {
					x->takeLeft();
					leftStep->addName(rightStep->getName(1));
					leftStep->setAxis(rightStep->getAxis());
					leftStep->setOperation(rightStep->getOperation());
					leftStep->setValue(rightStep->getValue());
					logRuleApplication(container, "P1R2", x, left.get());
					me = left;
					rulesApplied++;
				}
			}
		}
	}
	//  P1R3: Glue(Step(a::x),Step(op,v))   ...reduce... Step(a::x,op,v)
	if (QueryPlan::is(me, QueryPlan::GLUE)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		QueryPlan::SharedPtr right = x->getRight();
		if (left->getType() == QueryPlan::STEP &&
		    right->getType() == QueryPlan::STEP) {
			StepQP *leftStep = ((StepQP*)left.get());
			StepQP *rightStep = ((StepQP*)right.get());
			bool leftMatch =
			    leftStep->getAxis() != StepQP::AXIS_NONE &&
			    leftStep->countNames() > 0 &&
			    leftStep->getOperation() == Database::NONE;
			leftStep->getValue().isNull();
			bool rightMatch =
			    rightStep->getAxis() == StepQP::AXIS_NONE &&
			    rightStep->countNames() == 0 &&
			    rightStep->getOperation() != Database::NONE &&
			    !rightStep->getValue().isNull();
			if (leftMatch && rightMatch) {
				leftStep->setOperation(rightStep->getOperation());
				leftStep->setValue(rightStep->getValue());
				logRuleApplication(container, "P1R3", x, left.get());
				x->takeLeft();
				me = left;
				rulesApplied++;
			}
		}
	}
	return me;
}

QueryPlan::SharedPtr QueryPlanNode::optimize_node_phase_two(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied)
{
	// P2R1: Glue(x,y)                   ...replace... n(x,y)
	if (QueryPlan::is(me, QueryPlan::GLUE)) {
		QueryPlan::SharedPtr x(me);
		QueryPlan::SharedPtr left = ((QueryPlanNode*)x.get())->takeLeft();
		QueryPlan::SharedPtr right = ((QueryPlanNode*)x.get())->takeRight();
		me.reset(new SetOperationIntersectionQP(left, right));
		logRuleApplication(container, "P2R1", x.get(), me.get());
		rulesApplied++;
	}
	if (QueryPlan::is(me, QueryPlan::STEP)) {
		//
		// The most general case of a step operation is:
		//
		//   Step(axis::x.y.z,operation,value)
		//
		// The distinct cases that actually occur are:
		//
		//   Step(axis::x,none,0)
		//   Step(axis::x.y,none,0)
		//   Step(axis::x.y.z,none,0)
		//   Step(axis::x,operation,value)
		//   Step(axis::x.y,operation,value)
		//   Step(axis::x.y.z,operation,value)
		//
		// The substring operation is special because the value is busted up
		// into multiple three character values. Each tuple becoming its own
		// index lookup. Each of the other operations are mapped onto a single
		// index lookup.
		//
		//  P2R2: Step(axis::x)                     ...replace... RI(node-axis-presence-none,equality,x) or RI(node-axis-equality-*,prefix,x)
		//  P2R4: Step(axis::x.y)                   ...replace... RI(edge-axis-presence-none,equality,xy) or RI(edge-axis-equality-*,prefix,xy)
		//  P2R5: Step(axis::x.y.z)                 ...replace... n(P2R4(xy),P2R4(yz))
		//  P2R3: Step(axis::x,operation,value)     ...replace... RI(node-axis-equality-syntax,operation,x,value)
		//  P2R8: Step(axis::x.y,operation,value)   ...replace... RI(edge-axis-equality-syntax,operation,xy,value)
		//  P2R9: Step(axis::x.y.z,operation,value) ...replace... n(P2R4(xy),P2R8(yz))
		//
		StepQP *x = (StepQP *)me.get();
		int count = x->countNames();
		if (count == 0) {
			// There's no index available...
			me.reset(new SequentialScanQP());
			me->setReturnType(QueryPlan::RETURNTYPE_CANDIDATESET);
			logRuleApplication(container, "P2R10", x, me.get());
		} else {
			if (x->getOperation() == Database::NONE) {
				switch (count) {
				case 1:
					//  P2R2: Step(axis::x) ...replace... RI(node-axis-presence-none,equality,x) or RI(node-axis-equality-*,prefix,x)
					me = optimize_node_p2r2(txn, container, context, me, indexSpecification);
					break;
				case 2:
					//  P2R4: Step(axis::x.y) ...replace... RI(edge-axis-presence-none,equality,xy) or RI(edge-axis-equality-*,prefix,xy)
					me = optimize_node_p2r4(txn, container, context, me, indexSpecification);
					break;
				default:
					//  P2R5: Step(axis::x.y.z) ...replace... n(P2R4(xy),P2R4(yz))
					me = optimize_node_p2r5(txn, container, context, me, indexSpecification);
					break;
				}
			} else {
				switch (count) {
				case 1:
					//  P2R3: Step(axis::x,operation,value) ...replace... RI(node-axis-equality-syntax,operation,x,value)
					me = optimize_node_p2r3(txn, container, context, me, indexSpecification);
					break;
				case 2:
					//  P2R8: Step(axis::x.y,operation,value) ...replace... RI(edge-axis-equality-syntax,operation,xy,value)
					me = optimize_node_p2r8(txn, container, context, me, indexSpecification);
					break;
				default:
					//  P2R9: Step(axis::x.y.z,operation,value) ...replace... n(P2R4(xy),P2R8(yz))
					me = optimize_node_p2r9(txn, container, context, me, indexSpecification);
					break;
				}
			}
		}
		rulesApplied++;
	}
	//  P2R6: And(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
	//  P2R6: Glue(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
	//  P2R6: n(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
	//                                    ...replace... RI(eq,range,n,GT?,v1,LT?,v2)
	if (
	    QueryPlan::is(me, QueryPlan::AND) ||
	    QueryPlan::is(me, QueryPlan::GLUE) ||
	    QueryPlan::is(me, QueryPlan::SET_OPERATION_INTERSECTION)) {
		QueryPlan::SharedPtr left = ((QueryPlanNode*)me.get())->getLeft();
		QueryPlan::SharedPtr right = ((QueryPlanNode*)me.get())->getRight();
		if (left->getType() == QueryPlan::STEP && right->getType() == QueryPlan::STEP) {
			StepQP *leftStep = (StepQP*)left.get();
			StepQP *rightStep = (StepQP*)right.get();
			if (leftStep->countNames()==rightStep->countNames() &&
				leftStep->getNames()==rightStep->getNames()) {
				Database::Operation leftOperation = leftStep->getOperation();
				Database::Operation rightOperation = rightStep->getOperation();
				bool leftLess = (leftOperation == Database::LTX || leftOperation == Database::LTE);
				bool leftGreater = (leftOperation == Database::GTX || leftOperation == Database::GTE);
				bool rightLess = (rightOperation == Database::LTX || rightOperation == Database::LTE);
				bool rightGreater = (rightOperation == Database::GTX || rightOperation == Database::GTE);
				if ((leftLess && rightGreater) || (leftGreater && rightLess)) {
					QueryPlan::SharedPtr x(me);
					me= optimize_node_p2r6(txn, container, context, me, indexSpecification, 0 /*nameIndex*/, leftStep->countNames()==2 /*edge*/);
					logRuleApplication(container, "P2R6", x.get(), me.get());
					rulesApplied++;
				}
			}
		}
	}

	return me;
}

//  P2R2: Step(a::n) ...replace... RI(node-axis-presence-none,equality,n) or RI(node-axis-equality-string,prefix,n)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r2(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr x(me);
	me = optimize_node_presence(txn, container, context, me, indexSpecification, 0 /*nameIndex*/, false /*edge*/);
	logRuleApplication(container, "P2R2", x.get(), me.get());
	return me;
}

//  P2R4: Step(axis::x.y) ...replace... RI(edge-axis-presence-none,equality,xy) or RI(edge-axis-equality-string,prefix,xy)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r4(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr x(me);
	me = optimize_node_presence(txn, container, context, me, indexSpecification, 0 /*nameIndex*/, true /*edge*/);
	logRuleApplication(container, "P2R4", x.get(), me.get());
	return me;
}

//  P2R5: Step(axis::x.y.z) ...replace... n(P2R4(xy),P2R4(yz))
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r5(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr x(me);
	QueryPlanNode *current = 0;
	int count = ((StepQP*)x.get())->countNames();
	for (int i = 0;i < count - 1;++i) {
		QueryPlan::SharedPtr ri(optimize_node_presence(txn, container, context, x, indexSpecification, i, true /*edge*/));
		QueryPlan::SharedPtr sop;
		if (i < count - 2) {
			sop.reset(new SetOperationIntersectionQP(ri, QueryPlan::SharedPtr(0)));
		} else {
			sop.reset(0);
		}
		if (i == 0) {
			me = (sop ? sop : ri);
			current = (QueryPlanNode *)sop.get();
		}
		if (i > 0) {
			assert(current != 0);
			current->setRight((sop ? sop : ri));
			current = (QueryPlanNode *)sop.get();
		}
	}
	//	if (x->isResultGenerator()) me->setGeneratesResults();
	logRuleApplication(container, "P2R5", x.get(), me.get());
	return me;
}

//  P2R2: Step(axis::x) ...replace... RI(node-axis-presence-none,equality,x) or RI(node-axis-equality-*,prefix,x)
//  P2R4: Step(axis::x.y) ...replace... RI(edge-axis-presence-none,equality,xy) or RI(edge-axis-equality-*,prefix,xy)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_presence(DbTxn *txn, const Container &container, XmlQueryContext &context, const QueryPlan::SharedPtr &me, const IndexSpecification &indexSpecification, int nameIndex, bool edge)
{
	UNUSED(context);
	QueryPlan::SharedPtr r;
	const StepQP *x = (const StepQP *)me.get();
	const IndexVector *iv = indexSpecification.getIndexOrDefault(x->getName(nameIndex + (edge ? 1 : 0)).c_str());
	Index index;
	index.set(edge ? Index::PATH_EDGE : Index::PATH_NODE);
	index.set(x->getAxis() == StepQP::AXIS_ATTRIBUTE ? Index::NODE_ATTRIBUTE : Index::NODE_ELEMENT);
	Index index_nxp(index);
	index_nxp.set(Index::KEY_PRESENCE);
	Database::Operation operation = Database::NONE;
	if (iv) {
		if (iv->isEnabled(index_nxp, Index::PNKS_MASK)) {
			// Equality operation against a presence key.
			index.set(Index::KEY_PRESENCE);
			operation = Database::EQUALITY;
		} else {
			// Prefix operation against an equality or substring key.
			int i = 0;
			const Syntax *syntax = 0;
			syntax = SyntaxManager::getInstance()->getNextSyntax(i);
			while (syntax != 0) {
				if (syntax->getType() != Syntax::NONE) {
					Index index_nxes(index);
					index_nxes.set(Index::KEY_EQUALITY | (Index::Type)syntax->getType());
					if (iv->isEnabled(index_nxes, Index::PNKS_MASK)) {
						index.set(Index::KEY_EQUALITY | (Index::Type)syntax->getType());
						operation = Database::PREFIX;
						syntax = 0; // terminate the loop
					} else {
						index_nxes.set(Index::KEY_SUBSTRING);
						if (iv->isEnabled(index_nxes, Index::PNKS_MASK)) {
							index.set(Index::KEY_SUBSTRING | (Index::Type)syntax->getType());
							operation = Database::PREFIX;
							syntax = 0; // terminate the loop
						}
					}
				}
				if (syntax != 0) {
					syntax = SyntaxManager::getInstance()->getNextSyntax(i);
				}
			}
		}
	}
	if (index.getKey() != Index::KEY_NONE) {
		r.reset(new RestrictionIndexingQP(index, operation, x->getName(nameIndex)));
		if (edge) {
			((RestrictionIndexingQP*)r.get())->setName2(x->getName(nameIndex + 1));
		}
		r->setReturnType(x->getReturnType());
	} else {
		if (strncmp(x->getName().c_str(), metaDataNamespace_uri, strlen(metaDataNamespace_uri)) == 0) {
			// jcm - ok, this is a total hack to get //x//y to work when x is
			// indexed and y is a metadata attribute. We say that the SS will
			// return a result set so that the optimizer will think that x//y
			// returns a result set so RF won't be needed. [I'm sure there's
			// a more appropriate solution, but it'll need to wait until we're
			// doing our own result projection.]
			//
			r.reset(new SequentialScanQP());
			r->setReturnType(QueryPlan::RETURNTYPE_RESULTSET);
		} else {
			if(edge) {
				// No edge index available, check for a node index.
				r= optimize_node_presence(txn, container, context, me, indexSpecification, nameIndex+1, false);
			} else {
				// There's no index available...
				r.reset(new SequentialScanQP());
				r->setReturnType(QueryPlan::RETURNTYPE_CANDIDATESET);
				//r->setReturnType(me->getReturnType());
			}
		}
	}
	return r;
}

//  P2R6: And(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//  P2R6: Glue(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//  P2R6: n(Step(a::n,{LTX|LTE},v1),Step(a::n,{GTX|GTE},v2))
//                                    ...replace... RI(eq,range,n,GT?,v1,LT?,v2)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r6(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int nameIndex, bool edge)
{
	QueryPlan::SharedPtr r;
	QueryPlan::SharedPtr left = ((QueryPlanNode*)me.get())->getLeft();
	QueryPlan::SharedPtr right = ((QueryPlanNode*)me.get())->getRight();
	StepQP *leftStep = (StepQP*)left.get();
	StepQP *rightStep = (StepQP*)right.get();
	Database::Operation leftOperation = leftStep->getOperation();
	Database::Operation rightOperation = rightStep->getOperation();
	bool leftLess = (leftOperation == Database::LTX || leftOperation == Database::LTE);
	bool leftGreater = (leftOperation == Database::GTX || leftOperation == Database::GTE);
	bool rightLess = (rightOperation == Database::LTX || rightOperation == Database::LTE);
	bool rightGreater = (rightOperation == Database::GTX || rightOperation == Database::GTE);
	//
	// Check if node value equality indexing has been specified for this node.
	// Node could be either attribute or element.
	//
	Index index(
		(edge ? Index::PATH_EDGE : Index::PATH_NODE) |
	    (leftStep->getAxis() == StepQP::AXIS_ATTRIBUTE ?
	     Index::NODE_ATTRIBUTE :
	     Index::NODE_ELEMENT) |
	    Index::KEY_EQUALITY);
	//
	// If the value is a variable reference, then we can dereference
	// to find its type. If the user is compiling the query ahead of
	// execution then it would be wise of them to place a dummy value
	// for the variable in the context so that we get a hint as to its
	// type. In this case there is no support for variables that change
	// type between query executions. If the user hasn't provided a
	// dummy value, then we leave the check until execution time.
	//
	XmlValue leftValue = leftStep->getValue();
	XmlValue rightValue = rightStep->getValue();
	Syntax::Type type = Syntax::NONE;
	Syntax::Type leftType = Syntax::NONE;
	Syntax::Type rightType = Syntax::NONE;
	if (!leftValue.isNull()) {
		leftType = ((Value*)leftValue)->getSyntaxType(context);
	}
	if (!rightValue.isNull()) {
		rightType = ((Value*)rightValue)->getSyntaxType(context);
	}
	if (leftType == rightType ||
	    (leftType != Syntax::NONE && rightType == Syntax::NONE)) {
		type = leftType;
	} else if (leftType == Syntax::NONE && rightType != Syntax::NONE) {
		type = rightType;
	} else {
		// We don't know the syntax type of the value. We just have to
		// assume that the user knows what they are doing.
		// JCM - assume number?
	}
	index.set(type);
	const IndexVector *iv = indexSpecification.getIndexOrDefault(leftStep->getName(nameIndex + (edge ? 1 : 0)).c_str());
	if (iv && type != Syntax::NONE && iv->isEnabled(index, Index::PNKS_MASK)) {
		if (leftLess && rightGreater) {
			StepQP* tmpStep = leftStep;
			leftStep = rightStep;
			rightStep = tmpStep;
			leftLess = rightGreater = false;
			leftGreater = rightLess = true;
			Database::Operation tmpOp = leftOperation;
			leftOperation = rightOperation;
			rightOperation = tmpOp;
		}
		if (leftGreater && rightLess) {
			// We have the right pattern (x>v1 && x<v2), but v1 and v2 could be
			// either literal numbers, or variables. If they're both numbers then
			// we could check that v1<v2, and optimize away this whole query. But,
			// if they're variables then in the preparsed case we don't have access
			// to the bound values, so we can't do anything. Best to just create
			// the range operation and let things work themselves out at runtime.
			//
			XmlValue leftValue = leftStep->getValue();
			XmlValue rightValue = rightStep->getValue();
			QueryPlan::ReturnType rt = me->getReturnType();
			r.reset(new RestrictionIndexingQP(index, leftStep->getName(nameIndex), leftOperation, leftValue, rightOperation, rightValue));
			if (edge) {
				((RestrictionIndexingQP*)r.get())->setName2(leftStep->getName(nameIndex + 1));
			}
			r->setReturnType(rt);
		}
	} else {
		if(edge) {
			// No edge index available, check for a node index.
			r= optimize_node_p2r6(txn, container, context, me, indexSpecification, nameIndex+1, false);
		} else {
			// There's no index available...
			r.reset(new SequentialScanQP());
			r->setReturnType(QueryPlan::RETURNTYPE_CANDIDATESET);
		}
	}
	return r;
}

//  P2R3: Step(axis::x,operation,value) ...replace... RI(node-axis-equality-syntax,operation,x,value)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r3(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr x(me);
	me = optimize_node_equality(txn, container, context, me, indexSpecification, /*nameIndex=*/0, /*edge=*/false, me->getReturnType());
	logRuleApplication(container, "P2R3", x.get(), me.get());
	return me;
}

//  P2R8: Step(axis::x.y,operation,value) ...replace... RI(edge-axis-equality-syntax,operation,xy,value)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r8(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr x(me);
	me = optimize_node_equality(txn, container, context, me, indexSpecification, /*nameIndex=*/0, /*edge=*/true, me->getReturnType());
	logRuleApplication(container, "P2R8", x.get(), me.get());
	return me;
}

//  P2R9: Step(axis::x.y.z,operation,value) ...replace... n(P2R4(xy),P2R8(yz))
QueryPlan::SharedPtr QueryPlanNode::optimize_node_p2r9(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification)
{
	QueryPlan::SharedPtr r;
	QueryPlan::SharedPtr x(me);
	QueryPlanNode *current = 0;
	int count = ((StepQP *)x.get())->countNames();
	for (int i = 0;i < count - 1;++i) {
		QueryPlan::SharedPtr ri;
		QueryPlan::SharedPtr sop;
		if (i < count - 2) {
			ri = optimize_node_presence(txn, container, context, me, indexSpecification, i, /*edge=*/true);
			sop.reset(new SetOperationIntersectionQP(ri, QueryPlan::SharedPtr(0)));
		} else {
			ri = optimize_node_equality(txn, container, context, me, indexSpecification, i, /*edge=*/true, QueryPlan::RETURNTYPE_CANDIDATESET);
			sop.reset(0);
		}
		if (i == 0) {
			r = (sop ? sop : ri);
			current = (QueryPlanNode *)sop.get();
		}
		if (i > 0) {
			assert(current != 0);
			current->setRight((sop ? sop : ri));
			current = (QueryPlanNode *)sop.get();
		}
	}
	logRuleApplication(container, "P2R9", x.get(), me.get());
	return r;
}

//  P2R3: Step(axis::x,operation,value) ...replace... RI(node-axis-equality-*,operation,x,value)
//  P2R8: Step(axis::x.y,operation,value) ...replace... RI(edge-axis-equality-*,operation,xy,value)
QueryPlan::SharedPtr QueryPlanNode::optimize_node_equality(DbTxn *txn, const Container &container, XmlQueryContext &context, const QueryPlan::SharedPtr &me, const IndexSpecification &indexSpecification, int nameIndex, bool edge, QueryPlan::ReturnType returnType)
{
	QueryPlan::SharedPtr r;
	const StepQP *x = (const StepQP *)me.get();
	XmlValue value = x->getValue();
	if (::strcmp(metaDataName_uri_id, x->getName(nameIndex + (edge ? 1 : 0)).c_str()) == 0) {
		if (!value.isNull()) {
			r.reset(new GetDocumentQP((u_int32_t)value.asNumber(&context)));
			r->setReturnType(QueryPlan::RETURNTYPE_RESULTSET);
		}
	} else {
		const IndexVector *iv = indexSpecification.getIndexOrDefault(x->getName(nameIndex + (edge ? 1 : 0)).c_str());
		if (iv) {
			{
				Database::Operation operation= x->getOperation();
				Index index;
				index.set(edge ? Index::PATH_EDGE : Index::PATH_NODE);
				index.set(x->getAxis() == StepQP::AXIS_ATTRIBUTE ? Index::NODE_ATTRIBUTE : Index::NODE_ELEMENT);
				index.set(operation == Database::SUBSTRING ? Index::KEY_SUBSTRING : Index::KEY_EQUALITY);
				//
				// If the value is a variable reference, then we can dereference
				// to find its type. If the user is compiling the query ahead of
				// execution then it would be wise of them to place a dummy value
				// for the variable in the context so that we get a hint as to its
				// type. In this case there is no support for variables that change
				// type between query executions. If the user hasn't provided a
				// dummy value, then we assume the value is a string.
				//
				Syntax::Type type = Syntax::NONE;
				if (!value.isNull() && value.getType(0) != XmlValue::VARIABLE) {
					type = ((Value*)value)->getSyntaxType(context);
				} else {
					// We don't know the syntax type of the value.
					// Let's assume the value is a string.
					//
					type = Syntax::STRING;
				}
				index.set(type);
				bool enabled= false;
				if (type != Syntax::NONE) {
					if (iv->isEnabled(index, Index::PNKS_MASK)) {
						enabled= true;
						if (operation == Database::SUBSTRING) {
							operation= Database::EQUALITY;
						}
					}
					else
					{
						// If an Equality index wasn't available for a Prefix operation,
						// then look for a Substring index to do a Substring operation.
						//
						if (operation == Database::PREFIX) {
							index.set(Index::KEY_SUBSTRING);
							if (iv->isEnabled(index, Index::PNKS_MASK)) {
								operation= Database::EQUALITY;
								enabled= true;
							}
						}
					}
				}
				if (enabled) {
					const Syntax *syntax = SyntaxManager::getInstance()->getSyntax(type);
					string stringValue(value.asString(0));
					size_t stringValueLength = stringValue.length();
					unsigned int nKeys= syntax->countKeys(index, stringValue.c_str(), stringValueLength);
					if(nKeys>0)
					{
						if(index.equalsMask(Index::KEY_SUBSTRING, Index::KEY_MASK))
						{	
							// JCM - We don't support contains(n,$v) yet. We'd need to delay this bit of query plan translation until execution.
							if (!value.isVariable(&context)) {
								QueryPlanNode *current = 0;
								const char *keyBuffer= 0;
								size_t keyLength= 0;
								unsigned int i= 0;
								KeyGenerator::Ptr kg= syntax->getKeyGenerator(index, stringValue.c_str(), stringValueLength);
								while(kg->next(keyBuffer, keyLength)) {
									QueryPlan::SharedPtr ri(new RestrictionIndexingQP(index, operation, x->getName(nameIndex), XmlValue(string(keyBuffer,keyLength))));
									ri->setReturnType(QueryPlan::RETURNTYPE_CANDIDATESET);
									if (edge) {
										((RestrictionIndexingQP*)ri.get())->setName2(x->getName(nameIndex + 1));
									}
									QueryPlan::SharedPtr sop;
									if (i < nKeys - 1) {
										sop.reset(new SetOperationIntersectionQP(ri, QueryPlan::SharedPtr(0)));
									} else {
										sop.reset(0);
									}
									if (i == 0) {
										r = (sop ? sop : ri);
										current = (QueryPlanNode *)sop.get();
									}
									if (i > 0) {
										assert(current != 0);
										current->setRight((sop ? sop : ri));
										current = (QueryPlanNode *)sop.get();
									}
									++i;
								}
							}
						}
						else
						{
							r.reset(new RestrictionIndexingQP(index, operation, x->getName(nameIndex), value));
							r->setReturnType(returnType);
							if (edge) {
								((RestrictionIndexingQP*)r.get())->setName2(x->getName(nameIndex + 1));
							}
						}
					}
				}
			}
			if(!r) {
				// 
				// A suitable equality index could not be found, so look for a presence index instead.
				//
				Index index;
				index.set(edge ? Index::PATH_EDGE : Index::PATH_NODE);
				index.set(x->getAxis() == StepQP::AXIS_ATTRIBUTE ? Index::NODE_ATTRIBUTE : Index::NODE_ELEMENT);
				index.set(Index::KEY_PRESENCE);
				if (iv->isEnabled(index, Index::PNKS_MASK)) {
					// Equality operation against a presence key.
					r.reset(new RestrictionIndexingQP(index, Database::EQUALITY, x->getName(nameIndex)));
					r->setReturnType(returnType);
					if (edge) {
						((RestrictionIndexingQP*)r.get())->setName2(x->getName(nameIndex + 1));
					}
				}
			}
		}
	}
	if (!r) {
		if(edge) {
			// No edge index available, check for a node index.
			r= optimize_node_equality(txn, container, context, me, indexSpecification, nameIndex+1, false, returnType);
		} else {
			// There's no index available...
			r.reset(new SequentialScanQP());
			r->setReturnType(QueryPlan::RETURNTYPE_CANDIDATESET);
		}
	}
	return r;
}

QueryPlan::SharedPtr QueryPlanNode::optimize_node_phase_three(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied)
{
	UNUSED(txn);
	UNUSED(context);

	// P3R1: And(x,y)                    ...replace... n(x.y)
	if (QueryPlan::is(me, QueryPlan::AND)) {
		QueryPlan::SharedPtr x(me);
		QueryPlan::SharedPtr left = ((QueryPlanNode*)x.get())->takeLeft();
		QueryPlan::SharedPtr right = ((QueryPlanNode*)x.get())->takeRight();
		me.reset(new SetOperationIntersectionQP(left, right));
		logRuleApplication(container, "P3R1", x.get(), me.get());
		rulesApplied++;
	}
	// P3R2: Or(x,y)                     ...replace... u(x.y)
	if (QueryPlan::is(me, QueryPlan::OR)) {
		QueryPlan::SharedPtr x(me);
		QueryPlan::SharedPtr left = ((QueryPlanNode*)x.get())->takeLeft();
		QueryPlan::SharedPtr right = ((QueryPlanNode*)x.get())->takeRight();
		me.reset(new SetOperationUnionQP(left, right));
		logRuleApplication(container, "P3R4", x.get(), me.get());
		rulesApplied++;
	}
	return me;
}

QueryPlan::SharedPtr QueryPlanNode::optimize_node_phase_four(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied)
{
	UNUSED(txn);
	UNUSED(context);

	// P4R1: n(SS,x)                  ...reduce... x
	//       n(SS,SS)                 ...reduce... SS
	if (QueryPlan::is(me, QueryPlan::SET_OPERATION_INTERSECTION)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		QueryPlan::SharedPtr right = x->getRight();
		bool leftMatch = left->getType() == QueryPlan::SEQUENTIAL_SCAN;
		bool rightMatch = right->getType() == QueryPlan::SEQUENTIAL_SCAN;
		if (leftMatch || rightMatch) {
			QueryPlan::SharedPtr replacement;
			QueryPlan::ReturnType rt = me->getReturnType();
			if (leftMatch) {
				replacement = x->takeRight();
			} else {
				replacement = x->takeLeft();
			}
			replacement->setReturnType(rt);
			logRuleApplication(container, "P4R1", x, replacement.get());
			me = replacement;
			rulesApplied++;
		}
	}
	// P4R2: u(SS,x)                  ...reduce... SS
	if (QueryPlan::is(me, QueryPlan::SET_OPERATION_UNION)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		QueryPlan::SharedPtr right = x->getRight();
		bool leftMatch = left->getType() == QueryPlan::SEQUENTIAL_SCAN;
		bool rightMatch = right->getType() == QueryPlan::SEQUENTIAL_SCAN;
		if (leftMatch || rightMatch) {
			QueryPlan::SharedPtr replacement;
			if (leftMatch) {
				replacement = x->takeLeft();
			} else {
				replacement = x->takeRight();
			}
			logRuleApplication(container, "P4R3", x, replacement.get());
			me = replacement;
			rulesApplied++;
		}
	}
	//  P4R3: RF(RA(x)) and x.results==true ...reduce... x
	if (QueryPlan::is(me, QueryPlan::RESTRICTION_FILTER)) {
		QueryPlanNode *x = (QueryPlanNode *)me.get();
		QueryPlan::SharedPtr left = x->getLeft();
		if (QueryPlan::is(left, QueryPlan::RECORD_ACCESS)) {
			QueryPlanNode *x2 = (QueryPlanNode *)left.get();
			QueryPlan::SharedPtr left2 = x2->getLeft();
			if (left2 && left2->getReturnType() == QueryPlan::RETURNTYPE_RESULTSET) {
				x->takeLeft();
				logRuleApplication(container, "P4R3", x, left2.get());
				me = left2;
				rulesApplied++;
			}
		}
	}
	//  P4R4: n(RI(x,presence),RI(x,equality,y)) ...replace... RI(x,equality,y)
	if (QueryPlan::is(me, QueryPlan::SET_OPERATION_INTERSECTION)) {
		QueryPlan::SharedPtr x(me);
		QueryPlan::SharedPtr left = ((QueryPlanNode*)x.get())->getLeft();
		if (left->getType() == QueryPlan::RESTRICTION_INDEXING) {
			RestrictionIndexingQP* l = (RestrictionIndexingQP*)left.get();
			if (l->getOperation() == Database::PREFIX &&
			    l->getValue1().isNull() &&
			    (l->getIndex().getKey() == Index::KEY_EQUALITY || l->getIndex().getKey() == Index::KEY_SUBSTRING)) {
				QueryPlan::SharedPtr right = ((QueryPlanNode*)x.get())->getRight();
				if (optimize_node_p4r4(left, right)) {
					me = right;
					logRuleApplication(container, "P4R4", x.get(), me.get());
				}
			}
		} else {
			QueryPlan::SharedPtr right = ((QueryPlanNode*)x.get())->getRight();
			if (right->getType() == QueryPlan::RESTRICTION_INDEXING) {
				RestrictionIndexingQP* r = (RestrictionIndexingQP*)right.get();
				if (r->getOperation() == Database::PREFIX &&
				    r->getValue1().isNull() &&
				    (r->getIndex().getKey() == Index::KEY_EQUALITY || r->getIndex().getKey() == Index::KEY_SUBSTRING)) {
					QueryPlan::SharedPtr left = ((QueryPlanNode*)x.get())->getLeft();
					if (optimize_node_p4r4(right, left)) {
						me = left;
						logRuleApplication(container, "P4R4", x.get(), me.get());
					}
				}
			}
		}
	}

	return me;
}

bool QueryPlanNode::optimize_node_p4r4(QueryPlan::SharedPtr lm, QueryPlan::SharedPtr rc)
{
	// lm= leftMatch
	// rc= rightCandidate
	if (QueryPlan::is(rc, QueryPlan::SET_OPERATION_INTERSECTION) ||
	    QueryPlan::is(rc, QueryPlan::SET_OPERATION_UNION)) {
		QueryPlan::SharedPtr rcLeft = ((QueryPlanNode*)rc.get())->getLeft();
		QueryPlan::SharedPtr rcRight = ((QueryPlanNode*)rc.get())->getRight();
		return
		    optimize_node_p4r4(lm, rcLeft) ||
		    optimize_node_p4r4(lm, rcRight);
	} else if (QueryPlan::is(rc, QueryPlan::RESTRICTION_INDEXING)) {
		RestrictionIndexingQP* lmri = (RestrictionIndexingQP*)lm.get();
		RestrictionIndexingQP* rcri = (RestrictionIndexingQP*)rc.get();
		return lmri->getName1() == rcri->getName1() &&
	       ((lmri->getIndex().getKey() == Index::KEY_EQUALITY && rcri->getIndex().getKey() == Index::KEY_EQUALITY) ||
			(lmri->getIndex().getKey() == Index::KEY_SUBSTRING && rcri->getIndex().getKey() == Index::KEY_SUBSTRING));
	}
	return false;
}

QueryPlan::SharedPtr QueryPlanNode::optimize_node_phase_five(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied)
{
	UNUSED(txn);
	UNUSED(context);

	//  P5R1: RA(RF(RA(x)))                 ...reduce... RF(RA(x))
	if (QueryPlan::is(me, QueryPlan::RECORD_ACCESS)) {
		QueryPlan::SharedPtr left1 = ((QueryPlanNode *)me.get())->getLeft();
		if (QueryPlan::is(left1, QueryPlan::RESTRICTION_FILTER)) {
			QueryPlan::SharedPtr left2 = ((QueryPlanNode *)left1.get())->getLeft();
			if (QueryPlan::is(left2, QueryPlan::RECORD_ACCESS)) {
				logRuleApplication(container, "P5R1", me.get(), left1.get());
				me = left1;
				rulesApplied++;
			}
		}
	}
	//  P5R2: MDA(RF(RA(x)))                ...reduce... RFP(RA(x))
	if (QueryPlan::is(me, QueryPlan::METADATA_ACCESS)) {
		QueryPlan::SharedPtr left1 = ((QueryPlanNode *)me.get())->getLeft();
		if (QueryPlan::is(left1, QueryPlan::RESTRICTION_FILTER)) {
			QueryPlan::SharedPtr left2 = ((QueryPlanNode *)left1.get())->getLeft();
			if (QueryPlan::is(left2, QueryPlan::RECORD_ACCESS)) {
				logRuleApplication(container, "P5R2", me.get(), left1.get());
				me = left1;
				((RestrictionFilterAndOrProjectQP *)me.get())->setProject(true);
				rulesApplied++;
			}
		}
	}
	return me;
}

void QueryPlanNode::logRuleApplication(const Container &container, const char *ruleName, const QueryPlan *original, const QueryPlan *replacement) const
{
#if defined(DBG_ENABLED)
	assert(original != 0);
	assert(replacement != 0);
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream oss;
		oss << ruleName << " '" << original->toString().c_str() << "' TO '" << replacement->toString().c_str() << "'";
		container.log(C_QUERY, L_DEBUG, oss);
	}
#endif
}

//
// RootQP
//
RootQP::RootQP(QueryPlan::SharedPtr qp)
	: QueryPlanNode(ROOT, qp, QueryPlan::SharedPtr(0))
{}

string RootQP::toString() const
{
	return leftToString();
}

int RootQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	getLeft()->reset(); // Call reset on all query plan nodes.
	return getLeft()->execute(context, qec, ids);
}

int RootQP::next(QueryContext &qc, XmlValue &value)
{
	return getLeft()->next(qc, value);
}

size_t RootQP::getResultSize() const
{
	return getLeft()->getResultSize();
}

int RootQP::optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int ignore)
{
	UNUSED(ignore);

	int ra = 0; // The number of rules applied.
	int phase = 1;
	int lr = 0;
	do {
		if (isLogEnabled(C_OPTIMIZER, L_DEBUG)) {
			ostringstream oss;
			oss << "Query Plan Optimization Phase: " << phase << " Query Plan:" << toString().c_str();
			container.log(C_OPTIMIZER, L_DEBUG, oss);
		}
		do {
			lr = QueryPlanNode::optimize(txn, container, context, indexSpecification, phase);
			ra += lr;
		} while (lr > 0);
		phase++;
	} while (phase < 6); // There are five optimization phases...
	return ra;
}

// SetOperationUnionQP

SetOperationUnionQP::SetOperationUnionQP(QueryPlan::SharedPtr a, QueryPlan::SharedPtr b)
	: QueryPlanNode(QueryPlan::SET_OPERATION_UNION, a, b)
{}

int SetOperationUnionQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	int err = 0;
	QueryPlan::SharedPtr left = getLeft();
	QueryPlan::SharedPtr right = getRight();
	IDS::SharedPtr lrs;
	if (left) {
		err = left->execute(context, qec, lrs); // could throw
	}
	if (err == 0) {
		IDS::SharedPtr rrs;
		if (right) {
			err = right->execute(context, qec, rrs); // could throw
		}
		if (err == 0) {
			if (!lrs || !rrs) {
				// NONE u NONE => NONE
				// NONE u X => X
				//
				ids = !lrs ? rrs : lrs;
			} else {
				// X u Y => union(X,Y)
				//
				ids.reset(new IDS);
				ids->set_union(lrs, rrs);
			}
			if (qec.debugging())
				qec.addExecutionStep("u");
		}
	}
	return err;
}

double SetOperationUnionQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	double r = 0;
	QueryPlan::SharedPtr left = getLeft();
	QueryPlan::SharedPtr right = getRight();
	assert(left);
	assert(right);
	double lc = (left ? left->cost(context, qec) : 0);
	double rc = (right ? right->cost(context, qec) : 0);
	// jcm - Plus the cpu cost of two insertion sorts and a union or intersection.
	// jcm - For now let's just assume there is no cost for this.
	r = lc + rc;
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream s;
		s << "efd=" << r << " for " << toString();
		qec.getContainer().log(C_QUERY, L_DEBUG, s);
	}
	return r;
}

string SetOperationUnionQP::toString() const
{
#if defined(DEBUG_RETURNTYPE)
	string s("u(" + getReturnTypeAsString() + leftToString() + "," + rightToString() + ")");
#else

		string s("u(" + leftToString() + "," + rightToString() + ")");
#endif

	return s;
}

QueryPlan::ReturnType SetOperationUnionQP::getReturnType() const
{
	ReturnType rt = RETURNTYPE_NONE;
	if (returnType_ == QueryPlan::RETURNTYPE_INHERIT) {
		QueryPlan::SharedPtr l(getLeft());
		QueryPlan::SharedPtr r(getRight());
		ReturnType lrt = RETURNTYPE_NONE;
		ReturnType rrt = RETURNTYPE_NONE;
		if (l)
			lrt = l->getReturnType();
		if (r)
			rrt = r->getReturnType();
		if (!l && r) {
			rt = rrt;
		} else if (l && !r) {
			rt = lrt;
		} else if (l && r) {
			if (lrt == RETURNTYPE_ALL || rrt == RETURNTYPE_ALL) {
				rt = RETURNTYPE_ALL;
			} else if (lrt == RETURNTYPE_CANDIDATESET || rrt == RETURNTYPE_CANDIDATESET) {
				rt = RETURNTYPE_CANDIDATESET;
			} else if (lrt == RETURNTYPE_RESULTSET || rrt == RETURNTYPE_RESULTSET) {
				rt = RETURNTYPE_RESULTSET;
			} else {
				rt = RETURNTYPE_NONE;
			}
		}
	} else {
		rt = returnType_;
	}
	return rt;
}

// SetOperationIntersectionQP

SetOperationIntersectionQP::SetOperationIntersectionQP(QueryPlan::SharedPtr a, QueryPlan::SharedPtr b)
	: QueryPlanNode(QueryPlan::SET_OPERATION_INTERSECTION, a, b)
{}

int SetOperationIntersectionQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	int err = 0;
	QueryPlan::SharedPtr left = getLeft();
	QueryPlan::SharedPtr right = getRight();
	assert(left);
	assert(right);
	//
	// Check which side is cheapest to execute.
	// Execute the cheapest side first
	// By switching the cheapest to the left.
	//
	double lc = left->cost(context, qec);
	double rc = right->cost(context, qec);
	if (lc > rc) {
		QueryPlan::SharedPtr t = left;
		left = right;
		right = t;
		rc = lc;
	}
	IDS::SharedPtr lrs;
	if (left) {
		err = left->execute(context, qec, lrs);
	}
	if (err == 0) {
		if (!lrs) {
			// NONE n NONE => NONE
			// NONE n X => NONE
			// Short circuit to avoid calculating the RHS.
			//
			ids = lrs;
		} else {
			// If the LHS candidates can be filtered more cheaply than
			// refining the candidates with the RHS candidates then it's
			// better to crap out here than to continue.
			//
			double fc = qec.costToFilter(lrs);
			if (rc > fc) {
				ids = lrs;
			} else {
				IDS::SharedPtr rrs;
				if (right) {
					err = right->execute(context, qec, rrs);
				}
				if (err == 0) {
					if (!rrs) {
						// X n NONE => NONE
						// That sucks, we needn't have bothered calculating the
						// LHS candidate set. Maybe the cost function isn't good
						// enough.
						//
						ids = rrs;
					} else {
						// X n Y => intersection(X,Y)
						//
						ids.reset(new IDS);
						ids->set_intersection(lrs, rrs);
					}
				}
			}
		}
	}
	if (qec.debugging())
		qec.addExecutionStep("n");
	return err;
}

double SetOperationIntersectionQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	double r = 0;
	QueryPlan::SharedPtr left = getLeft();
	QueryPlan::SharedPtr right = getRight();
	assert(left);
	assert(right);
	double lc = (left ? left->cost(context, qec) : 0);
	double rc = (right ? right->cost(context, qec) : 0);
	//
	// jcm - Plus the cpu cost of two insertion sorts and a union or intersection.
	// jcm - For now let's just assume there is no cost for this.
	//
	// If one side returns no records and is the cheapest side
	// then the cost of the intersection is just the cost of
	// that side. Also, we want to make sure that we execute
	// the cheapest side first in case the candidate list
	// becomes short enough that it becomes cheaper to filter
	// them than to keep trying to refine the candidate set.
	//
	r = (lc < rc) ? lc : rc;
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream s;
		s << "efd=" << r << " for " << toString();
		qec.getContainer().log(C_QUERY, L_DEBUG, s);
	}
	return r;
}

string SetOperationIntersectionQP::toString() const
{

#if defined(DEBUG_RETURNTYPE)
	string s("n(" + getReturnTypeAsString() + leftToString() + "," + rightToString() + ")");
#else

		string s("n(" + leftToString() + "," + rightToString() + ")");
#endif

	return s;
}

QueryPlan::ReturnType SetOperationIntersectionQP::getReturnType() const
{
	ReturnType rt = RETURNTYPE_NONE;
	if (returnType_ == QueryPlan::RETURNTYPE_INHERIT) {
		QueryPlan::SharedPtr l(getLeft());
		QueryPlan::SharedPtr r(getRight());
		ReturnType lrt = RETURNTYPE_NONE;
		ReturnType rrt = RETURNTYPE_NONE;
		if (l)
			lrt = l->getReturnType();
		if (r)
			rrt = r->getReturnType();
		if (!l && r) {
			rt = rrt;
		} else if (l && !r) {
			rt = lrt;
		} else if (l && r) {
			if (lrt == RETURNTYPE_NONE || rrt == RETURNTYPE_NONE) {
				rt = RETURNTYPE_NONE;
			} else if (lrt == RETURNTYPE_CANDIDATESET || rrt == RETURNTYPE_CANDIDATESET) {
				rt = RETURNTYPE_CANDIDATESET;
			} else if (lrt == RETURNTYPE_RESULTSET || rrt == RETURNTYPE_RESULTSET) {
				rt = RETURNTYPE_RESULTSET;
			} else {
				rt = RETURNTYPE_ALL;
			}
		}
	} else {
		rt = returnType_;
	}
	return rt;
}

// RestrictionIndexingQP

RestrictionIndexingQP::RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1)
	: QueryPlan(QueryPlan::RESTRICTION_INDEXING),
	index_(index),
	operation_(operation),
	lessThanOperation_(Database::NONE),
	greaterThanOperation_(Database::NONE),
	name1_(name1),
	keysCreated_(false),
	numberOfKeys_(0)
{}

RestrictionIndexingQP::RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1, const string &name2)
	: QueryPlan(QueryPlan::RESTRICTION_INDEXING),
	index_(index),
	operation_(operation),
	lessThanOperation_(Database::NONE),
	greaterThanOperation_(Database::NONE),
	name1_(name1),
	name2_(name2),
	keysCreated_(false),
	numberOfKeys_(0)
{}

RestrictionIndexingQP::RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1, const XmlValue &value1)
	: QueryPlan(QueryPlan::RESTRICTION_INDEXING),
	index_(index),
	operation_(operation),
	lessThanOperation_(Database::NONE),
	greaterThanOperation_(Database::NONE),
	name1_(name1),
	value1_(value1),
	keysCreated_(false),
	numberOfKeys_(0)
{}

RestrictionIndexingQP::RestrictionIndexingQP(Index index, const string &name1, Database::Operation gto, const XmlValue &value1, Database::Operation lto, const XmlValue &value2)
	: QueryPlan(QueryPlan::RESTRICTION_INDEXING),
	index_(index),
	operation_(Database::RANGE),
	lessThanOperation_(lto),
	greaterThanOperation_(gto),
	name1_(name1),
	value1_(value1),
	value2_(value2),
	keysCreated_(false),
	numberOfKeys_(0)
{}

void RestrictionIndexingQP::createKeys(DbTxn *txn, QueryExecutionContext &qec)
{
	// Construct the keys to lookup in the index.
	//
	// Note that range operations have two keys, the lower and
	// upper bound of the range.
	//
	if (!keysCreated_) {
		createKey(txn, key1_, qec.getContainer(), qec.getContext(), value1_);
		if (operation_ == Database::RANGE) {
			createKey(txn, key2_, qec.getContainer(), qec.getContext(), value2_);
		}
		keysCreated_ = true;
	}
}

void RestrictionIndexingQP::createKey(DbTxn *txn, Key &key, const Container &container, QueryContext &context, XmlValue &v)
{
	// Construct the key to lookup in the index
	ID id1;
	container.lookupName(txn, name1_, id1);
	if (id1 != 0) {
		if (index_.getPath() == Index::PATH_EDGE) {
			ID id2;
			container.lookupName(txn, name2_, id2);
			if (id2 != 0) {
				key.set(index_, id1, id2, v, &context);
			} else {
				// We've never been given a document that contains an
				// element with this tag name. The key is empty, so
				// will resolve to an empty result set.
				//
				key.reset();
			}
		} else {
			key.set(index_, id1, 0, v, &context);
		}
	} else {
		// We've never been given a document that contains an
		// element with this tag name. The key is empty, so
		// will resolve to an empty result set.
		//
		key.reset();
	}
	// If key index is NONE then no key could be constructed.
	// This means the result of the index restriction is an empty set.
}

void RestrictionIndexingQP::reset()
{
	// Reset the cached state so that the query plan can be reused.
	keysCreated_ = false;
	QueryPlan::reset();
}

int RestrictionIndexingQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	int err = 0;
	createKeys(context.txn(), qec);
	if (!key1_.getIndex().equals(Index::NONE)) {
		// This is icky, but this code relies on a side-effect in cost().
		// We need to know the the number of keys we're going to pull
		// back so that we create an id vector just big enough. But, cost()
		// is only called when there's a decision point in the query plan
		// execution. So, we call it here to make sure it's been called.
		// The result is cached, so it's no big deal.
		//
		cost(context, qec);
		ids.reset(new IDS((unsigned int)numberOfKeys_)); // numberOfKeys comes from the statistics read in the cost() method
		//
		// In some cases the IDs will come out of the index operation
		// in ascending order, in some cases they won't. As we iterate
		// over the cursor we suppress duplicates and check if the IDs
		// will need to be sorted once we're done.
		//
		// JCM - If the value is a variable, and didn't have a value
		// when the expression was compiled, then we don't know what
		// syntax type the value had, so we couldn't check if there
		// was an appropriate index available, so we may have a query
		// with no indexes to answer the query...
		//
		SecondaryDatabase *database = qec.getContainer().getIndex(key1_.getSyntaxType());
		scoped_ptr<SecondaryCursor> cursor;
		if (operation_ == Database::RANGE) {
			err = database->createCursor(context.txn(), cursor, greaterThanOperation_, &key1_, lessThanOperation_, &key2_);
		} else {
			err = database->createCursor(context.txn(), cursor, operation_, &key1_);
		}
		if (err == 0) {
			ID id;
			ID lastid;
			bool dosort = false;
			//
			// jcm - perf - Could we use the DB bulk get() instead here? Maybe just for equality?
			//
			err = cursor->first(id); // could throw
			while (err == 0 && id != 0) {
				if (id != lastid) {
					ids->push_back(id);
					if (!dosort && id < lastid)
						dosort = true;
					lastid = id;
				}
				err = cursor->next(id); // could throw
			}
			if (dosort) {
				// jcm - perf - perhaps we can ask the cursor if they need sorting, and/or uniquing...?
				ids->sort();
				ids->unique();
			}
		}
	}
	if (qec.debugging())
		qec.addExecutionStep(toString());
	return err;
}

double RestrictionIndexingQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	double r = 0;
	createKeys(context.txn(), qec);
	if (!key1_.getIndex().equals(Index::NONE)) {
		// usable_page_size= (pagesize-overhead)*page_fill_factor
		//
		// DB4.1 has btree page overhead of 26. Fill factor for a full page
		// is between 50% and 100%... let's guess 75%.
		//
		const Container &container = qec.getContainer();
		double pageSize = (container.getPrimaryDatabase()->getPageSize() - 26) * 0.75;
		container.getStatistics(context, key1_, statistics_);
		if (index_.getKey() == Index::KEY_EQUALITY) {
			// Let's just assume that the distribution of keys across
			// the domain of possible values is flat. There are probably
			// more clever things we could do.
			//
			switch (operation_) {
			case Database::EQUALITY:
				// jcm - could use key_range... but is this more accurate?
				// (number of equality keys / number of unique keys)
				numberOfKeys_ =
				    (statistics_.numUniqueKeys_ > 0
				     ? (double)statistics_.numIndexedKeys_ / (double)statistics_.numUniqueKeys_
				     : 0);
				break;
			case Database::PREFIX:
				if (key1_.getValueSize() == 0) {
					// Doing a prefix search on just the structure.
					numberOfKeys_ = statistics_.numIndexedKeys_;
					// BREAK!
					break;
				} else {
					// Doing a prefix search on the structure, and the start of the value.
					// FALL THROUGH!
				}
			case Database::LTX:
			case Database::LTE:
			case Database::GTX:
			case Database::GTE:
			case Database::RANGE: {
					SecondaryDatabase *database = container.getIndex(key1_.getSyntaxType());
					double percentageOfKeys = database->cost(context, operation_, greaterThanOperation_, lessThanOperation_, key1_, key2_);
					numberOfKeys_ = (double)statistics_.numIndexedKeys_ * percentageOfKeys;
				}
				break;
			default:  // keep compilers quiet
				break;
			}
		} else if (index_.getKey() == Index::KEY_PRESENCE) {
			numberOfKeys_ = statistics_.numIndexedKeys_;
		}
		//
		// (number_of_keys * (average_key_value_pair_size+pair_overhead) / usable_page_size
		//
		// DB4.1 has btree key value pair overhead of 5 bytes per item, so 10 bytes for a pair.
		//
		r = (numberOfKeys_ * (statistics_.averageKeyValueSize() + 10)) / pageSize;
		if (isLogEnabled(C_QUERY, L_DEBUG)) {
			ostringstream s;
			s << "ef= " << r << " for " << toString() << " : " << statistics_.asString() << " : num=" << numberOfKeys_;
			container.log(C_QUERY, L_DEBUG, s);
		}
	}
	return r;
}

string RestrictionIndexingQP::toString() const
{
	string s;
	s += "RI(";
#if defined(DEBUG_RETURNTYPE)

	s += getReturnTypeAsString();
#endif

	s += index_.asString();
	s += ",";
	s += Database::operationToString(operation_);
	s += "," + name1_;
	if (index_.getPath() == Index::PATH_EDGE) {
		s += "." + name2_;
	}
	if (!value1_.isNull()) {
		s += "," + value1_.asString(0);
		if (!value2_.isNull()) {
			s += "," + value2_.asString(0) + ")";
		} else {
			s += ")";
		}
	} else {
		s += ")";
	}
	return s;
}

// SequentialScanQP

SequentialScanQP::SequentialScanQP()
	: QueryPlan(QueryPlan::SEQUENTIAL_SCAN)
{}

int SequentialScanQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	int err = 0;
	ids.reset(new IDS(512)); // jcm - perf - could ask the statistics how many documents there are.
	PrimaryDatabase *database = qec.getContainer().getPrimaryDatabase();
	scoped_ptr<PrimaryCursor> cursor;
	err = database->createCursor(context.txn(), cursor);
	if (err == 0) {
		//
		// jcm - perf - Could we use the BDB bulk get here?
		//
		ID id;
		err = cursor->first(id); // could throw
		while (err == 0 && id != 0) {
			// We know that the IDs will come out of the primary document
			// database in ascending order, so no need to unique or sort.
			ids->push_back(id);
			err = cursor->next(id); // could throw
		}
		if (qec.debugging())
			qec.addExecutionStep(toString());
	}
	return err;
}

double SequentialScanQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	UNUSED(context);

	// Number of pages in the primary database.
	// jcm - Plus the cpu cost of an insertion cost.
	double r = qec.getContainer().getPrimaryDatabase()->getNumberOfPages();
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream s;
		s << "ef=" << r << " for " << toString();
		qec.getContainer().log(C_QUERY, L_DEBUG, s);
	}
	return r;
}

string SequentialScanQP::toString() const
{
#if defined(DEBUG_RETURNTYPE)
	return "SS(" + getReturnTypeAsString() + ")";
#else

		return "SS";
#endif
}

// RecordAccessQP

RecordAccessQP::RecordAccessQP(QueryPlan::SharedPtr qp)
	: QueryPlanNode(QueryPlan::RECORD_ACCESS, qp, QueryPlan::SharedPtr(0)),
	container_(0),
	ids_(0),
	pids_(0),
	afTimer_(new HighResTimer)
{
	assert(qp);
}

RecordAccessQP::~RecordAccessQP()
{
	delete pids_;
	delete afTimer_;
}

void RecordAccessQP::reset()
{
	// Reset the cached state so that the query plan can be reused.
	container_ = 0;
	if (ids_)
		ids_->clear();
	delete pids_;
	pids_ = 0;
	QueryPlanNode::reset();
}

int RecordAccessQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(ids);

	// Execute the child query plans. All those that can occur below
	// a Record Access will generate a set of document IDs.
	//
	// Store the candidate id set. The caller will iterate over them
	// using the iteration interface.
	//
	int err = getLeft()->execute(context, qec, ids_);
	container_ = &qec.getContainer();
	if (qec.debugging())
		qec.addExecutionStep("RA");
	return err;
}

int RecordAccessQP::next(QueryContext &qc, XmlValue &value)
{
	OperationContext &oc = qc.getOperationContext();
	int err = 0;
	bool done = !ids_ || ids_->size() == 0;
	if (!done) {
		if (pids_ == 0) {
			pids_ = new IDS::const_iterator();
			*pids_ = ids_->begin();
		} else if (*pids_ == ids_->end()) {
			debugOutput_ids(*container_, ids_, "RA", 0, afTimer_, 0, 0);
			done = true;
		}
	}
	if (!done) {
		afTimer_->start();
		XmlDocument document;
		err = container_->getDocument(oc, **pids_, document, 0);
		if (err == 0) {
			value = document;
		} else {
			// GetDocument could return an ID for a document that does not exist.
			// All the other QP nodes must return IDs that do exist, otherwise
			// the indexes have gone bad. It'd be good to assert that.
			//
			value = XmlValue();
		}
		++(*pids_);
		afTimer_->stop();
	} else {
		value = XmlValue();
	}
	return err;
}

double RecordAccessQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	UNUSED(context);
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream s;
		s << "ef=" << 1 << " for " << toString();
		qec.getContainer().log(C_QUERY, L_DEBUG, s);
	}
	return 1;
}

size_t RecordAccessQP::getResultSize() const
{
	if (!ids_)
		return 0;
	else
		return ids_->size();
}

string RecordAccessQP::toString() const
{
	return "RA(" + leftToString() + ")";
}

// GetDocumentQP

GetDocumentQP::GetDocumentQP(u_int32_t id )
	: QueryPlanNode(QueryPlan::GET_DOCUMENT, QueryPlan::SharedPtr(0), QueryPlan::SharedPtr(0)),
	container_(0),
	id_(id)
{}

GetDocumentQP::~GetDocumentQP()
{
	container_ = 0;
}

string GetDocumentQP::toString() const
{
	std::ostringstream s;
	s << "GD(" << id_ << ")";
	return s.str();
}

int GetDocumentQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(context);
	ids.reset(new IDS(1));
	ids->push_back(id_);
	if (qec.debugging())
		qec.addExecutionStep("GD");
	return 0;
}

size_t GetDocumentQP::getResultSize() const
{
	return 1;
}

// MetaDataAccessQP

MetaDataAccessQP::MetaDataAccessQP(const string &name)
	: QueryPlanNode(QueryPlan::METADATA_ACCESS, QueryPlan::SharedPtr(0), QueryPlan::SharedPtr(0)),
	container_(0),
	name_(name),
	ids_(0),
	pids_(0)
{}

MetaDataAccessQP::~MetaDataAccessQP()
{
	container_ = 0;
	delete pids_;
}

void MetaDataAccessQP::reset()
{
	// Reset the cached state so that the query plan can be reused.
	if (ids_)
		ids_->clear();
	delete pids_;
	pids_ = 0;
	QueryPlanNode::reset();
}

int MetaDataAccessQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(ids);
	//
	// Execute the child query plans. All those that can occur below
	// a Metadata Access will generate a set of document IDs.
	//
	// Store the candidate id set. The user will iterate over them
	// using the iteration interface next/done.
	//
	int err = 0;
	container_ = &qec.getContainer();
	err = container_->lookupName(context.txn(), name_, nid_);
	if (err == 0) {
		err = getLeft()->execute(context, qec, ids_);
	} else {
		err = 0; // This piece of meta data isn't known about.
	}
	if (qec.debugging())
		qec.addExecutionStep("MDA");
	return err;
}

int MetaDataAccessQP::next(QueryContext &qc, XmlValue &value)
{
	OperationContext &oc = qc.getOperationContext();
	int err = 0;
	bool done = !ids_ || ids_->size() == 0;
	if (!done) {
		if (pids_ == 0) {
			pids_ = new IDS::const_iterator();
			*pids_ = ids_->begin();
		} else if (*pids_ == ids_->end()) {
			done = true;
		}
	}
	if (!done) {
		if (nid_ == container_->getNIDForID()) {
			double id = (**pids_).raw();
			value = XmlValue(id); // jcm: value.set(id) would be cheaper
		} else {
			err = container_->getMetaDataItem(oc, **pids_, nid_, value);
		}
		++(*pids_);
	} else {
		value = XmlValue();
	}
	return err;
}

string MetaDataAccessQP::toString() const
{
	string s("MDA(" + name_ + ",");
	if (!getLeft()) {
		s += "null)";
	} else {
		s += leftToString() + ")";
	}
	return s;
}

size_t MetaDataAccessQP::getResultSize() const
{
	if (!ids_)
		return 0;
	else
		return ids_->size();
}

// RestrictionFilterAndOrProjectQP

#if defined(DBXML_XPATH_PATHAN)
RestrictionFilterAndOrProjectQP::RestrictionFilterAndOrProjectQP(const string& xpath, QueryPlan::SharedPtr qp, bool project)
	: QueryPlanNode((project ? QueryPlan::RESTRICTION_FILTER_AND_PROJECT : QueryPlan::RESTRICTION_FILTER), qp, QueryPlan::SharedPtr(0)),
	container_(0),
	xpath_(xpath),
	project_(project),
	ids_(new IDS),
	vvi_(vv_.end()),
	nsDocument_(0),
	docNSResolver_(0),
	parsedExpression_(0),
	afTimer_(new HighResTimer),
	afdTimer_(new HighResTimer)
{
	assert(qp);
}

RestrictionFilterAndOrProjectQP::~RestrictionFilterAndOrProjectQP()
{
	if(nsDocument_)	nsDocument_->release();
	delete docNSResolver_;
	delete parsedExpression_;
	delete afTimer_;
	delete afdTimer_;
}
#endif

int RestrictionFilterAndOrProjectQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &idsPassedThrough)
{
	// When building the candidate set there's a point at which
	// it becomes cheaper to filter the set built so far than to
	// continue trying to refine the candidate set further.
	//
	qec.setCostToFilterFunction(costToFilter);
	//
	// Generate the candidate list.
	//
	int err = getLeft()->execute(context, qec, idsPassedThrough);
	//
	// The XPath evaluator is setup before every execution because the query
	// context could have changed. i.e. namespace mapping, variable bindings.
	//
	if (nsDocument_ == 0) {
		DOMImplementation *factory = DOMImplementation::getImplementation();
		nsDocument_ = factory->createDocument(NULL, NULL, NULL);
	}
	QueryContext &qc= qec.getContext();
	qc.setupXPathQueryContext(qc.getXPathEvaluator(), nsDocument_, &docNSResolver_);
	//
	container_ = &qec.getContainer();
	if (qec.debugging())
		qec.addExecutionStep("RF");
	return err;
}

int RestrictionFilterAndOrProjectQP::next(QueryContext &qc, XmlValue &value)
{
	int err = 0;
	if(project_ && vvi_!=vv_.end())
	{
		value= *vvi_++;
	}
	else
	{
		bool match = false;
		ID id;
		value = XmlValue();
		afdTimer_->start();
		while (!match && (err = getLeft()->next(qc, value)) == 0 && !value.isNull()) {
			afTimer_->start();
			XmlDocument document(value.asDocument(0));
			id = document.getID();
			vv_.clear();
			match = applyFilter(qc, document, vv_);
			if (project_) vvi_= vv_.begin();
			afTimer_->stop();
		}
		if (match) {
			ids_->push_back(id);
			if (project_) value= *vvi_++;
		}
		afdTimer_->stop();
		if (value.isNull()) {
			debugOutput_ids(*container_, ids_, "RF", 0, afTimer_, afdTimer_, 0);
		}
	}
	return err;
}

double RestrictionFilterAndOrProjectQP::doCost(OperationContext &context, QueryExecutionContext &qec)
{
	UNUSED(context);

	// JCM - It depends on how many documents have to be filtered.
	// There could be a QueryPlan method that returns an estimate of that.
	if (isLogEnabled(C_QUERY, L_DEBUG)) {
		ostringstream s;
		s << "ef=" << 1 << " for " << toString();
		qec.getContainer().log(C_QUERY, L_DEBUG, s);
	}
	return 1;
}

size_t RestrictionFilterAndOrProjectQP::getResultSize() const
{
	return getLeft()->getResultSize();
}

#if defined(DBXML_XPATH_PATHAN)
//
// This is the Xerces/Pathan implementation.
//
bool RestrictionFilterAndOrProjectQP::applyFilter(QueryContext &qc, const XmlDocument &xmlDocument, XmlValueVector &vv)
{
	bool r = false;
	try {
		//
		// Create an XPathExpression using the XPathEvaluator factory class.
		//
		if (parsedExpression_ == 0) {
			UTF8ToXMLCh xmlch(xpath_);
			parsedExpression_ = qc.getXPathEvaluator().createExpression(xmlch.str(), docNSResolver_);
		}
		const Document& document= (const Document&)xmlDocument;
		r = document.evaluateXPath(xmlDocument, qc, *parsedExpression_, vv, project_);
	} catch (const XPathException &e) {
		throw XmlException(XmlException::XPATH_EVALUATION_ERROR, e.getString().c_str());
	}
	return r;
}
#endif

string RestrictionFilterAndOrProjectQP::toString() const
{
	if (project_) {
		return "RP(RF(" + leftToString() + "))";
	} else {
		return "RF(" + leftToString() + ")";
	}
}

double RestrictionFilterAndOrProjectQP::costToFilter(long numDocuments)
{
	// JCM - The cost of filtering is one disk access to retrieve the document,
	// plus the cpu of parsing the document and applying the full XPath
	// implementation against the resultant DOM. For the moment let's just
	// assume that this is also expensive, being equivalent in time to
	// one disk access.
	//
	return numDocuments*2.0;
}

// ConstantQP

ConstantQP::~ConstantQP()
{}

void ConstantQP::reset()
{
	done_ = false;
	QueryPlan::reset();
}

int ConstantQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(context);
	UNUSED(qec);
	UNUSED(ids);
	return 0;
}

int ConstantQP::next(QueryContext &qc, XmlValue &value)
{
	UNUSED(qc);

	if (!done_) {
		value = v_;
		done_ = true;
	} else {
		value = XmlValue();
	}
	return 0;
}

string ConstantQP::toString() const
{
	return v_.asString(0);
}

// PlaceHolderQP

PlaceHolderQP::PlaceHolderQP(Type type, const string &name)
: QueryPlanNode(type, QueryPlan::SharedPtr(0), QueryPlan::SharedPtr(0)),
name_(name)
{}

PlaceHolderQP::PlaceHolderQP(Type type, const string &name, QueryPlan::SharedPtr a, QueryPlan::SharedPtr b)
	: QueryPlanNode(type, a, b),
	name_(name)
{}

string PlaceHolderQP::toString() const
{
	string s(name_);
	if (getLeft() || getRight()) {
		s += "(" + leftToString() + "," + rightToString() + ")";
	}
	return s;
}

int PlaceHolderQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(context);
	UNUSED(qec);
	UNUSED(ids);

	// This is an intermediate query plan node. It should
	// never appear in an executable query plan.
	assert(false);
	return 0;
}

// StepQP

StepQP::StepQP(Database::Operation operation, const XmlValue &value)
	: QueryPlan(QueryPlan::STEP),
	axis_(AXIS_NONE),
	operation_(operation),
	value_(value),
	anywhere_(false),
	contextNode_(false)
{
}

StepQP::StepQP(const string &axis, const string &n1, const string &n2)
	: QueryPlan(QueryPlan::STEP),
	axis_(AXIS_NONE),
	operation_(Database::NONE),
	anywhere_(false),
	contextNode_(false)
{
	if (axis.compare("attribute") == 0) {
		axis_ = AXIS_ATTRIBUTE;
	} else if (axis.compare("") == 0 || axis.compare("child") == 0) {
		axis_ = AXIS_CHILD;
	} else {
		axis_ = AXIS_OTHER;
	}
	if(!n1.empty()) addName(n1);
	if(!n2.empty())	addName(n2);
}

void StepQP::addName(const string &name)
{
	names_.push_back(name);
}

void StepQP::addNames(const vector<string> &newNames)
{
	//	names.assign(newNames.begin(),newNames.end());
	copy(newNames.begin(), newNames.end(), back_inserter(names_));
}

const string &StepQP::getName(unsigned int index) const
{
	assert(index < names_.size());
	return names_[index];
}

int StepQP::doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids)
{
	UNUSED(context);
	UNUSED(qec);
	UNUSED(ids);

	// This is an intermediate query plan node. It should
	// never appear in an executable query plan.
	assert(false);
	return 0;
}

string StepQP::toString() const
{
	std::ostringstream s;
	s << "Step(";
#if defined(DEBUG_RETURNTYPE)

	s << getReturnTypeAsString();
#endif

	switch (axis_) {
	case AXIS_ATTRIBUTE:
		s << "attribute";
		break;
	case AXIS_CHILD:
		s << "child";
		break;
	case AXIS_OTHER:
		s << "other";
		break;
	case AXIS_NONE:
		s << "none";
		break;
	}
	s << "::";
	vector<string>::const_iterator p;
	bool first = true;
	for (p = names_.begin();p != names_.end();++p) {
		if (first) {
			first = false;
		} else {
			s << ".";
		}
		s << *p;
	}
	if (operation_ != Database::NONE) {
		s << ",";
		s << Database::operationToString(operation_);
		if (value_.isNull())
			s << ",(null)";
		else
			s << "," << value_.asString(0);
	}
	s << ")";
	return s.str();
}
