001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 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.Set;
010:
011: import org.openrdf.query.BindingSet;
012: import org.openrdf.query.Dataset;
013: import org.openrdf.query.algebra.Filter;
014: import org.openrdf.query.algebra.Group;
015: import org.openrdf.query.algebra.Join;
016: import org.openrdf.query.algebra.LeftJoin;
017: import org.openrdf.query.algebra.QueryModelNode;
018: import org.openrdf.query.algebra.StatementPattern;
019: import org.openrdf.query.algebra.TupleExpr;
020: import org.openrdf.query.algebra.evaluation.QueryOptimizer;
021: import org.openrdf.query.algebra.helpers.QueryModelVisitorBase;
022: import org.openrdf.query.algebra.helpers.VarNameCollector;
023:
024: /**
025: * Optimizes a query model by pushing {@link Filter}s as far down in the model
026: * tree as possible.
027: *
028: * @author Arjohn Kampman
029: */
030: public class FilterOptimizer implements QueryOptimizer {
031:
032: public void optimize(TupleExpr tupleExpr, Dataset dataset,
033: BindingSet bindings) {
034: tupleExpr.visit(new FilterFinder(tupleExpr));
035: }
036:
037: /*--------------------------*
038: * Inner class FilterFinder *
039: *--------------------------*/
040:
041: protected class FilterFinder extends
042: QueryModelVisitorBase<RuntimeException> {
043:
044: protected final TupleExpr tupleExpr;
045:
046: public FilterFinder(TupleExpr tupleExpr) {
047: this .tupleExpr = tupleExpr;
048: }
049:
050: @Override
051: public void meet(Filter filter) {
052: super .meet(filter);
053: filter.getArg().visit(getFilterRelocator(filter));
054: }
055:
056: protected FilterRelocator getFilterRelocator(Filter filter) {
057: return new FilterRelocator(filter);
058: }
059: }
060:
061: /*-----------------------------*
062: * Inner class FilterRelocator *
063: *-----------------------------*/
064:
065: protected class FilterRelocator extends
066: QueryModelVisitorBase<RuntimeException> {
067:
068: protected final Filter filter;
069:
070: protected final Set<String> filterVars;
071:
072: public FilterRelocator(Filter filter) {
073: this .filter = filter;
074: filterVars = VarNameCollector
075: .process(filter.getCondition());
076: }
077:
078: @Override
079: protected void meetNode(QueryModelNode node) {
080: // By default, do not visit child nodes
081: }
082:
083: @Override
084: public void meet(Join join) {
085: if (join.getLeftArg().getBindingNames().containsAll(
086: filterVars)) {
087: // All required vars are bound by the left expr
088: join.getLeftArg().visit(this );
089: } else if (join.getRightArg().getBindingNames()
090: .containsAll(filterVars)) {
091: // All required vars are bound by the right expr
092: join.getRightArg().visit(this );
093: } else {
094: relocate(filter, join);
095: }
096: }
097:
098: @Override
099: public void meet(LeftJoin leftJoin) {
100: if (leftJoin.getLeftArg().getBindingNames().containsAll(
101: filterVars)) {
102: leftJoin.getLeftArg().visit(this );
103: }
104: }
105:
106: @Override
107: public void meet(StatementPattern sp) {
108: relocate(filter, sp);
109: }
110:
111: @Override
112: public void meet(Filter filter) {
113: // Filters are commutative
114: filter.getArg().visit(this );
115: }
116:
117: @Override
118: public void meet(Group group) {
119: // Prefer evaluation of filters before grouping
120: group.getArg().visit(this );
121: }
122:
123: protected void relocate(Filter filter, TupleExpr newFilterArg) {
124: if (filter.getArg() != newFilterArg) {
125: // Remove filter from its original location
126: filter.replaceWith(filter.getArg());
127:
128: // Insert filter at the new location
129: newFilterArg.replaceWith(filter);
130: filter.setArg(newFilterArg);
131: }
132: }
133: }
134: }
|