001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 2006-2007.
003: * Copyright James Leigh (c) 2006.
004: *
005: * Licensed under the Aduna BSD-style license.
006: */
007: package org.openrdf.query.algebra.evaluation.impl;
008:
009: import java.util.HashSet;
010: import java.util.Set;
011:
012: import org.openrdf.query.algebra.BinaryTupleOperator;
013: import org.openrdf.query.algebra.EmptySet;
014: import org.openrdf.query.algebra.Join;
015: import org.openrdf.query.algebra.LeftJoin;
016: import org.openrdf.query.algebra.QueryModelNode;
017: import org.openrdf.query.algebra.SingletonSet;
018: import org.openrdf.query.algebra.StatementPattern;
019: import org.openrdf.query.algebra.TupleExpr;
020: import org.openrdf.query.algebra.UnaryTupleOperator;
021: import org.openrdf.query.algebra.Var;
022: import org.openrdf.query.algebra.helpers.QueryModelVisitorBase;
023:
024: /**
025: * Supplies various query model statistics to the query engine/optimizer.
026: *
027: * @author Arjohn Kampman
028: * @author James Leigh
029: */
030: public class EvaluationStatistics {
031:
032: public double getCardinality(TupleExpr expr) {
033: return getCardinality(expr, new HashSet<String>());
034: }
035:
036: public double getCardinality(TupleExpr expr, Set<String> boundVars) {
037: CardinalityCalculator cc = getCardinalityCalculator(boundVars);
038: expr.visit(cc);
039: return cc.getCardinality();
040: }
041:
042: protected CardinalityCalculator getCardinalityCalculator(
043: Set<String> boundVars) {
044: return new CardinalityCalculator(boundVars);
045: }
046:
047: /*-----------------------------------*
048: * Inner class CardinalityCalculator *
049: *-----------------------------------*/
050:
051: protected static class CardinalityCalculator extends
052: QueryModelVisitorBase<RuntimeException> {
053:
054: protected Set<String> boundVars;
055:
056: protected double cardinality;
057:
058: public CardinalityCalculator(Set<String> boundVars) {
059: this .boundVars = boundVars;
060: }
061:
062: public double getCardinality() {
063: return cardinality;
064: }
065:
066: @Override
067: public void meet(EmptySet node) {
068: cardinality = 0;
069: }
070:
071: @Override
072: public void meet(SingletonSet node) {
073: cardinality = 1;
074: }
075:
076: @Override
077: public void meet(StatementPattern sp) {
078: cardinality = 1000.0;
079:
080: int constantVarCount = countConstantVars(sp);
081: int boundVarCount = countBoundVars(sp);
082:
083: int sqrtFactor = 2 * boundVarCount + constantVarCount;
084:
085: if (sqrtFactor >= 2) {
086: cardinality = Math.pow(cardinality, 1.0 / sqrtFactor);
087: }
088:
089: // int unboundVars = 4 - countBoundVars(sp) - countConstantVars(sp);
090: // cardinality = 1 << unboundVars; // 2 ^ unboundVars
091: }
092:
093: protected int countConstantVars(StatementPattern sp) {
094: int constantVarCount = 0;
095:
096: Var[] spVars = new Var[] { sp.getSubjectVar(),
097: sp.getPredicateVar(), sp.getObjectVar(),
098: sp.getContextVar() };
099:
100: for (Var var : spVars) {
101: if (var != null && var.hasValue()) {
102: constantVarCount++;
103: }
104: }
105:
106: return constantVarCount;
107: }
108:
109: protected int countBoundVars(StatementPattern sp) {
110: int boundVarCount = 0;
111:
112: Var[] spVars = new Var[] { sp.getSubjectVar(),
113: sp.getPredicateVar(), sp.getObjectVar(),
114: sp.getContextVar() };
115:
116: for (Var var : spVars) {
117: if (var != null
118: && this .boundVars.contains(var.getName())) {
119: boundVarCount++;
120: }
121: }
122:
123: return boundVarCount;
124: }
125:
126: @Override
127: public void meet(Join node) {
128: node.getLeftArg().visit(this );
129: double leftArgCost = this .cardinality;
130:
131: node.getRightArg().visit(this );
132: cardinality *= leftArgCost;
133: }
134:
135: @Override
136: public void meet(LeftJoin node) {
137: node.getLeftArg().visit(this );
138: double leftArgCost = this .cardinality;
139:
140: node.getRightArg().visit(this );
141: cardinality *= leftArgCost;
142: }
143:
144: @Override
145: protected void meetBinaryTupleOperator(BinaryTupleOperator node) {
146: node.getLeftArg().visit(this );
147: double leftArgCost = this .cardinality;
148:
149: node.getRightArg().visit(this );
150: cardinality += leftArgCost;
151: }
152:
153: @Override
154: protected void meetUnaryTupleOperator(UnaryTupleOperator node) {
155: node.getArg().visit(this );
156: }
157:
158: @Override
159: protected void meetNode(QueryModelNode node) {
160: throw new IllegalArgumentException("Unhandled node type: "
161: + node.getClass());
162: }
163: }
164: }
|