View Javadoc

1   /*
2    * ModeShape (http://www.modeshape.org)
3    * See the COPYRIGHT.txt file distributed with this work for information
4    * regarding copyright ownership.  Some portions may be licensed
5    * to Red Hat, Inc. under one or more contributor license agreements.
6    * See the AUTHORS.txt file in the distribution for a full listing of 
7    * individual contributors.
8    *
9    * ModeShape is free software. Unless otherwise indicated, all code in ModeShape
10   * is licensed to you under the terms of the GNU Lesser General Public License as
11   * published by the Free Software Foundation; either version 2.1 of
12   * the License, or (at your option) any later version.
13   * 
14   * ModeShape is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17   * Lesser General Public License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this software; if not, write to the Free
21   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
22   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
23   */
24  package org.modeshape.graph.query.optimize;
25  
26  import java.util.Collections;
27  import java.util.HashSet;
28  import java.util.LinkedList;
29  import java.util.Set;
30  import net.jcip.annotations.Immutable;
31  import org.modeshape.graph.query.QueryContext;
32  import org.modeshape.graph.query.model.Column;
33  import org.modeshape.graph.query.model.Constraint;
34  import org.modeshape.graph.query.model.EquiJoinCondition;
35  import org.modeshape.graph.query.model.JoinCondition;
36  import org.modeshape.graph.query.model.PropertyExistence;
37  import org.modeshape.graph.query.model.PropertyValue;
38  import org.modeshape.graph.query.model.ReferenceValue;
39  import org.modeshape.graph.query.model.SameNodeJoinCondition;
40  import org.modeshape.graph.query.model.SelectorName;
41  import org.modeshape.graph.query.model.Visitable;
42  import org.modeshape.graph.query.model.Visitors;
43  import org.modeshape.graph.query.model.Visitors.AbstractVisitor;
44  import org.modeshape.graph.query.plan.PlanNode;
45  import org.modeshape.graph.query.plan.PlanUtil;
46  import org.modeshape.graph.query.plan.PlanNode.Property;
47  import org.modeshape.graph.query.plan.PlanNode.Type;
48  
49  /**
50   * An {@link OptimizerRule optimizer rule} that copies SELECT nodes that apply to one side of a equi-join condition so that they
51   * also apply to the other side fo the equi-join condition.
52   */
53  @Immutable
54  public class CopyCriteria implements OptimizerRule {
55  
56      public static final CopyCriteria INSTANCE = new CopyCriteria();
57  
58      /**
59       * {@inheritDoc}
60       * 
61       * @see org.modeshape.graph.query.optimize.OptimizerRule#execute(org.modeshape.graph.query.QueryContext,
62       *      org.modeshape.graph.query.plan.PlanNode, java.util.LinkedList)
63       */
64      public PlanNode execute( QueryContext context,
65                               PlanNode plan,
66                               LinkedList<OptimizerRule> ruleStack ) {
67          Set<PlanNode> copiedSelectNodes = new HashSet<PlanNode>();
68  
69          for (PlanNode join : plan.findAllAtOrBelow(Type.JOIN)) {
70              // Get the join condition ...
71              JoinCondition joinCondition = join.getProperty(Property.JOIN_CONDITION, JoinCondition.class);
72              if (joinCondition instanceof EquiJoinCondition) {
73                  EquiJoinCondition equiJoinCondition = (EquiJoinCondition)joinCondition;
74                  SelectorName selector1 = equiJoinCondition.getSelector1Name();
75                  SelectorName selector2 = equiJoinCondition.getSelector2Name();
76                  String property1 = equiJoinCondition.getProperty1Name();
77                  String property2 = equiJoinCondition.getProperty2Name();
78  
79                  // Walk up the tree looking for SELECT nodes that apply to one of the sides ...
80                  PlanNode node = join.getParent();
81                  while (node != null) {
82                      if (!copiedSelectNodes.contains(node)) {
83                          PlanNode copy = copySelectNode(context, node, selector1, property1, selector2, property2);
84                          if (copy != null) {
85                              node.insertAsParent(copy);
86                              copiedSelectNodes.add(node);
87                              copiedSelectNodes.add(copy);
88                          } else {
89                              copy = copySelectNode(context, node, selector2, property2, selector1, property1);
90                              if (copy != null) {
91                                  node.insertAsParent(copy);
92                                  copiedSelectNodes.add(node);
93                                  copiedSelectNodes.add(copy);
94                              }
95                          }
96                      }
97                      node = node.getParent();
98                  }
99              }
100 
101             if (joinCondition instanceof EquiJoinCondition || joinCondition instanceof SameNodeJoinCondition) {
102                 // Then for each side of the join ...
103                 PlanNode left = join.getFirstChild();
104                 PlanNode right = join.getLastChild();
105                 copySelectNodes(context, left, right);
106                 copySelectNodes(context, right, left);
107             }
108         }
109         return plan;
110     }
111 
112     protected void copySelectNodes( QueryContext context,
113                                     PlanNode fromJoined,
114                                     PlanNode toJoined ) {
115         // Find all of the selectors used on the 'to' side ...
116         Set<SelectorName> toSelectors = new HashSet<SelectorName>();
117         for (PlanNode toNode : toJoined.findAllAtOrBelow()) {
118             toSelectors.addAll(toNode.getSelectors());
119         }
120 
121         PlanNode nodeBelowSelects = null;
122 
123         // Walk down the 'fromJoined' side looking for all SELECT nodes ...
124         for (PlanNode select : fromJoined.findAllAtOrBelow(Type.SELECT)) {
125             // If all of the SELECT's selectors are also found on the right ...
126             if (toSelectors.containsAll(select.getSelectors())) {
127                 // Copy the criteria ...
128                 PlanNode copy = new PlanNode(Type.SELECT, select.getSelectors());
129                 copy.setProperty(Property.SELECT_CRITERIA, select.getProperty(Property.SELECT_CRITERIA));
130 
131                 if (nodeBelowSelects == null) {
132                     nodeBelowSelects = toJoined.findAtOrBelow(Type.SOURCE, Type.JOIN, Type.SET_OPERATION, Type.NULL);
133                     if (nodeBelowSelects == null) {
134                         nodeBelowSelects = toJoined;
135                     }
136                 }
137                 nodeBelowSelects.insertAsParent(copy);
138                 nodeBelowSelects = copy;
139             }
140         }
141     }
142 
143     protected PlanNode copySelectNode( QueryContext context,
144                                        PlanNode selectNode,
145                                        SelectorName selectorName,
146                                        String propertyName,
147                                        SelectorName copySelectorName,
148                                        String copyPropertyName ) {
149         if (selectNode.isNot(Type.SELECT)) return null;
150         if (selectNode.getSelectors().size() != 1 || !selectNode.getSelectors().contains(selectorName)) return null;
151 
152         Constraint constraint = selectNode.getProperty(Property.SELECT_CRITERIA, Constraint.class);
153         Set<Column> columns = getColumnsReferencedBy(constraint);
154         if (columns.size() != 1) return null;
155         Column column = columns.iterator().next();
156         if (!column.getSelectorName().equals(selectorName)) return null;
157         if (!column.getPropertyName().equals(propertyName)) return null;
158 
159         // We know that this constraint ONLY applies to the referenced selector and property,
160         // so we will duplicate this constraint ...
161 
162         // Create the new node ...
163         PlanNode copy = new PlanNode(Type.SELECT, copySelectorName);
164 
165         // Copy the constraint, but change the references to the copy selector and property ...
166         PlanUtil.ColumnMapping mappings = new PlanUtil.ColumnMapping(selectorName);
167         mappings.map(propertyName, new Column(copySelectorName, copyPropertyName, copyPropertyName));
168         Constraint newCriteria = PlanUtil.replaceReferences(context, constraint, mappings, copy);
169         copy.setProperty(Property.SELECT_CRITERIA, newCriteria);
170 
171         return copy;
172     }
173 
174     /**
175      * {@inheritDoc}
176      * 
177      * @see java.lang.Object#toString()
178      */
179     @Override
180     public String toString() {
181         return getClass().getSimpleName();
182     }
183 
184     /**
185      * Get the set of Column objects that represent those columns referenced by the visitable object.
186      * 
187      * @param visitable the object to be visited
188      * @return the set of Column objects, with column names that always are the string-form of the
189      *         {@link Column#getPropertyName() property name}; never null
190      */
191     public static Set<Column> getColumnsReferencedBy( Visitable visitable ) {
192         if (visitable == null) return Collections.emptySet();
193         final Set<Column> symbols = new HashSet<Column>();
194         // Walk the entire structure, so only supply a StrategyVisitor (that does no navigation) ...
195         Visitors.visitAll(visitable, new AbstractVisitor() {
196             protected void addColumnFor( SelectorName selectorName,
197                                          String property ) {
198                 symbols.add(new Column(selectorName, property, property));
199             }
200 
201             @Override
202             public void visit( Column column ) {
203                 symbols.add(column);
204             }
205 
206             @Override
207             public void visit( EquiJoinCondition joinCondition ) {
208                 addColumnFor(joinCondition.getSelector1Name(), joinCondition.getProperty1Name());
209                 addColumnFor(joinCondition.getSelector2Name(), joinCondition.getProperty2Name());
210             }
211 
212             @Override
213             public void visit( PropertyExistence prop ) {
214                 addColumnFor(prop.getSelectorName(), prop.getPropertyName());
215             }
216 
217             @Override
218             public void visit( PropertyValue prop ) {
219                 addColumnFor(prop.getSelectorName(), prop.getPropertyName());
220             }
221 
222             @Override
223             public void visit( ReferenceValue ref ) {
224                 String propertyName = ref.getPropertyName();
225                 if (propertyName != null) {
226                     addColumnFor(ref.getSelectorName(), propertyName);
227                 }
228             }
229         });
230         return symbols;
231     }
232 
233 }