You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@accumulo.apache.org by bi...@apache.org on 2011/12/05 21:05:51 UTC
svn commit: r1210600 [5/16] - in
/incubator/accumulo/trunk/contrib/accumulo_sample: ./ ingest/
ingest/src/main/java/aggregator/ ingest/src/main/java/ingest/
ingest/src/main/java/iterator/ ingest/src/main/java/normalizer/
ingest/src/main/java/protobuf/ ...
Modified: incubator/accumulo/trunk/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java
URL: http://svn.apache.org/viewvc/incubator/accumulo/trunk/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java?rev=1210600&r1=1210599&r2=1210600&view=diff
==============================================================================
--- incubator/accumulo/trunk/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java (original)
+++ incubator/accumulo/trunk/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java Mon Dec 5 20:05:49 2011
@@ -1,19 +1,19 @@
/*
-* Licensed to the Apache Software Foundation (ASF) under one or more
-* contributor license agreements. See the NOTICE file distributed with
-* this work for additional information regarding copyright ownership.
-* The ASF licenses this file to You under the Apache License, Version 2.0
-* (the "License"); you may not use this file except in compliance with
-* the License. You may obtain a copy of the License at
-*
-* http://www.apache.org/licenses/LICENSE-2.0
-*
-* Unless required by applicable law or agreed to in writing, software
-* distributed under the License is distributed on an "AS IS" BASIS,
-* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-* See the License for the specific language governing permissions and
-* limitations under the License.
-*/
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
package iterator;
import java.io.IOException;
@@ -66,1957 +66,1932 @@ import util.FieldIndexKeyParser;
import com.google.common.collect.Multimap;
-public class BooleanLogicIterator implements SortedKeyValueIterator<Key, Value>, OptionDescriber {
-
- private static final Collection<ByteSequence> EMPTY_COL_FAMS = new ArrayList<ByteSequence>();
- protected static final Logger log = Logger.getLogger(BooleanLogicIterator.class);
- public static final String QUERY_OPTION = "expr";
- public static final String TERM_CARDINALITIES = "TERM_CARDINALITIES"; // comma separated list of term : count
- public static final String FIELD_INDEX_QUERY = "FIELD_INDEX_QUERY";
- public static final String FIELD_NAME_PREFIX = "fi\0";
- //--------------------------------------------------------------------------
- private static IteratorEnvironment env = new DefaultIteratorEnvironment();
- protected Text nullText = new Text();
- private Key topKey = null;
- private Value topValue = null;
- private SortedKeyValueIterator<Key, Value> sourceIterator;
- private BooleanLogicTreeNode root;
- private PriorityQueue<BooleanLogicTreeNode> positives;
- private ArrayList<BooleanLogicTreeNode> negatives;
- private ArrayList<BooleanLogicTreeNode> rangerators;
- private String originalQuery;
- private String updatedQuery;
- private Map<String, Long> termCardinalities = new HashMap<String, Long>();
- private Range overallRange = null;
- private FieldIndexKeyParser keyParser;
-
- public BooleanLogicIterator() {
- keyParser = new FieldIndexKeyParser();
- rangerators = new ArrayList<BooleanLogicTreeNode>();
- }
-
- public BooleanLogicIterator(BooleanLogicIterator other, IteratorEnvironment env) {
- if (other.sourceIterator != null) {
- this.sourceIterator = other.sourceIterator.deepCopy(env);
- }
- keyParser = new FieldIndexKeyParser();
- rangerators = new ArrayList<BooleanLogicTreeNode>();
- log.debug("Congratulations, you've reached the BooleanLogicIterator");
- }
-
- public static void setLogLevel(Level lev) {
- log.setLevel(lev);
- }
-
- public void setDebug(Level lev) {
- log.setLevel(lev);
- }
-
- public SortedKeyValueIterator<Key, Value> deepCopy(IteratorEnvironment env) {
- return new BooleanLogicIterator(this, env);
- }
-
- /**
- * <b>init</b> is responsible for setting up the iterator. It will pull the serialized boolean
- * parse tree from the options mapping and construct the appropriate sub-iterators
- *
- * Once initialized, this iterator will automatically seek to the first matching instance. If no top key exists, that means
- * an event matching the boolean logic did not exist in the partition. Subsequent calls to next will move the iterator and all
- * sub-iterators to the next match.
- *
- * @param source The underlying SortedkeyValueIterator.
- * @param options A Map<String, String> of options.
- * @param env The iterator environment
- * @throws IOException
- */
- public void init(SortedKeyValueIterator<Key, Value> source, Map<String, String> options, IteratorEnvironment env) throws IOException {
- validateOptions(options);
- try {
- if (log.isDebugEnabled()) {
- log.debug("Congratulations, you've reached the BooleanLogicIterator.init method");
- }
- // Copy the source iterator
- sourceIterator = source.deepCopy(env);
-
- // Potentially take advantage of term cardinalities
- String[] terms = null;
- if (null != options.get(TERM_CARDINALITIES)) {
- terms = options.get(TERM_CARDINALITIES).split(",");
- for (String term : terms) {
- int idx = term.indexOf(":");
- if (-1 != idx) {
- termCardinalities.put(term.substring(0, idx), Long.parseLong(term.substring(idx + 1)));
- }
- }
+public class BooleanLogicIterator implements SortedKeyValueIterator<Key,Value>, OptionDescriber {
+
+ private static final Collection<ByteSequence> EMPTY_COL_FAMS = new ArrayList<ByteSequence>();
+ protected static final Logger log = Logger.getLogger(BooleanLogicIterator.class);
+ public static final String QUERY_OPTION = "expr";
+ public static final String TERM_CARDINALITIES = "TERM_CARDINALITIES"; // comma separated list of term : count
+ public static final String FIELD_INDEX_QUERY = "FIELD_INDEX_QUERY";
+ public static final String FIELD_NAME_PREFIX = "fi\0";
+ // --------------------------------------------------------------------------
+ private static IteratorEnvironment env = new DefaultIteratorEnvironment();
+ protected Text nullText = new Text();
+ private Key topKey = null;
+ private Value topValue = null;
+ private SortedKeyValueIterator<Key,Value> sourceIterator;
+ private BooleanLogicTreeNode root;
+ private PriorityQueue<BooleanLogicTreeNode> positives;
+ private ArrayList<BooleanLogicTreeNode> negatives;
+ private ArrayList<BooleanLogicTreeNode> rangerators;
+ private String originalQuery;
+ private String updatedQuery;
+ private Map<String,Long> termCardinalities = new HashMap<String,Long>();
+ private Range overallRange = null;
+ private FieldIndexKeyParser keyParser;
+
+ public BooleanLogicIterator() {
+ keyParser = new FieldIndexKeyParser();
+ rangerators = new ArrayList<BooleanLogicTreeNode>();
+ }
+
+ public BooleanLogicIterator(BooleanLogicIterator other, IteratorEnvironment env) {
+ if (other.sourceIterator != null) {
+ this.sourceIterator = other.sourceIterator.deepCopy(env);
+ }
+ keyParser = new FieldIndexKeyParser();
+ rangerators = new ArrayList<BooleanLogicTreeNode>();
+ log.debug("Congratulations, you've reached the BooleanLogicIterator");
+ }
+
+ public static void setLogLevel(Level lev) {
+ log.setLevel(lev);
+ }
+
+ public void setDebug(Level lev) {
+ log.setLevel(lev);
+ }
+
+ public SortedKeyValueIterator<Key,Value> deepCopy(IteratorEnvironment env) {
+ return new BooleanLogicIterator(this, env);
+ }
+
+ /**
+ * <b>init</b> is responsible for setting up the iterator. It will pull the serialized boolean parse tree from the options mapping and construct the
+ * appropriate sub-iterators
+ *
+ * Once initialized, this iterator will automatically seek to the first matching instance. If no top key exists, that means an event matching the boolean
+ * logic did not exist in the partition. Subsequent calls to next will move the iterator and all sub-iterators to the next match.
+ *
+ * @param source
+ * The underlying SortedkeyValueIterator.
+ * @param options
+ * A Map<String, String> of options.
+ * @param env
+ * The iterator environment
+ * @throws IOException
+ */
+ public void init(SortedKeyValueIterator<Key,Value> source, Map<String,String> options, IteratorEnvironment env) throws IOException {
+ validateOptions(options);
+ try {
+ if (log.isDebugEnabled()) {
+ log.debug("Congratulations, you've reached the BooleanLogicIterator.init method");
+ }
+ // Copy the source iterator
+ sourceIterator = source.deepCopy(env);
+
+ // Potentially take advantage of term cardinalities
+ String[] terms = null;
+ if (null != options.get(TERM_CARDINALITIES)) {
+ terms = options.get(TERM_CARDINALITIES).split(",");
+ for (String term : terms) {
+ int idx = term.indexOf(":");
+ if (-1 != idx) {
+ termCardinalities.put(term.substring(0, idx), Long.parseLong(term.substring(idx + 1)));
+ }
+ }
+ }
+
+ // Step 1: Parse the query
+ if (log.isDebugEnabled()) {
+ log.debug("QueryParser");
+ }
+ QueryParser qp = new QueryParser();
+ qp.execute(this.updatedQuery); // validateOptions updates the updatedQuery
+
+ // need to build the query tree based on jexl parsing.
+ // Step 2: refactor QueryTree - inplace modification
+ if (log.isDebugEnabled()) {
+ log.debug("transformTreeNode");
+ }
+ TreeNode tree = qp.getIteratorTree();
+ this.root = transformTreeNode(tree);
+
+ if (log.isDebugEnabled()) {
+ log.debug("refactorTree");
+ }
+ this.root = refactorTree(this.root);
+
+ if (log.isDebugEnabled()) {
+ log.debug("collapseBranches");
+ }
+ collapseBranches(root);
+
+ // Step 3: create iterators where we need them.
+ createIteratorTree(this.root);
+ if (log.isDebugEnabled()) {
+ log.debug("Query tree after iterator creation:\n\t" + this.root.getContents());
+ }
+ // Step 4: split the positive and negative leaves
+ splitLeaves(this.root);
+
+ } catch (ParseException ex) {
+ log.error("ParseException in init: " + ex);
+ throw new IllegalArgumentException("Failed to parse query", ex);
+ } catch (Exception ex) {
+ throw new IllegalArgumentException("probably had no indexed terms", ex);
+ }
+
+ }
+
+ /* *************************************************************************
+ * Methods for sub iterator creation.
+ */
+ private void createIteratorTree(BooleanLogicTreeNode root) throws IOException {
+ if (log.isDebugEnabled()) {
+ log.debug("BoolLogic createIteratorTree()");
+ }
+ // Walk the tree, if all of your children are leaves, roll you into the
+ // appropriate iterator.
+ Enumeration<?> dfe = root.depthFirstEnumeration();
+
+ while (dfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
+ if (!node.isLeaf() && node.getType() != ParserTreeConstants.JJTJEXLSCRIPT) {
+ // try to roll up.
+ if (canRollUp(node)) {
+ node.setRollUp(true);
+ if (node.getType() == ParserTreeConstants.JJTANDNODE) {
+ if (log.isDebugEnabled()) {
+ log.debug("creating IntersectingIterator");
+ }
+ node.setUserObject(createIntersectingIterator(node));
+ } else if (node.getType() == ParserTreeConstants.JJTORNODE) {
+ node.setUserObject(createOrIterator(node));
+ } else {
+ // throw an error.
+ log.debug("createIteratorTree, encounterd a node type I do not know about: " + node.getType());
+ log.debug("createIteratorTree, node contents: " + node.getContents());
+ }
+ node.removeAllChildren();
+ }
+ }
+ }
+
+ // now for remaining leaves, create basic iterators.
+ // you can add in specialized iterator mappings here if necessary.
+ dfe = root.depthFirstEnumeration();
+ while (dfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
+ if (node.isLeaf() && node.getType() != ParserTreeConstants.JJTANDNODE && node.getType() != ParserTreeConstants.JJTORNODE) {
+ node.setUserObject(createFieldIndexIterator(node));
+ }
+ }
+ }
+
+ private AndIterator createIntersectingIterator(BooleanLogicTreeNode node) throws IOException {
+ if (log.isDebugEnabled()) {
+ log.debug("createIntersectingIterator(node)");
+ log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
+ }
+ Text[] columnFamilies = new Text[node.getChildCount()];
+ Text[] termValues = new Text[node.getChildCount()];
+ boolean[] negationMask = new boolean[node.getChildCount()];
+ Enumeration<?> children = node.children();
+ int i = 0;
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+ columnFamilies[i] = child.getFieldName();
+ termValues[i] = child.getFieldValue();
+ negationMask[i] = child.isNegated();
+ i++;
+ }
+
+ AndIterator ii = new AndIterator();
+ Map<String,String> options = new HashMap<String,String>();
+ options.put(AndIterator.columnFamiliesOptionName, AndIterator.encodeColumns(columnFamilies));
+ options.put(AndIterator.termValuesOptionName, AndIterator.encodeTermValues(termValues));
+ options.put(AndIterator.notFlagsOptionName, AndIterator.encodeBooleans(negationMask));
+
+ ii.init(sourceIterator.deepCopy(env), options, env);
+ return ii;
+ }
+
+ private OrIterator createOrIterator(BooleanLogicTreeNode node) throws IOException {
+ if (log.isDebugEnabled()) {
+ log.debug("createOrIterator(node)");
+ log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
+ }
+
+ Enumeration<?> children = node.children();
+ ArrayList<Text> fams = new ArrayList<Text>();
+ ArrayList<Text> quals = new ArrayList<Text>();
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+ fams.add(child.getFieldName());
+ quals.add(child.getFieldValue());
+ }
+
+ OrIterator iter = new OrIterator();
+ SortedKeyValueIterator<Key,Value> source = sourceIterator.deepCopy(env);
+ for (int i = 0; i < fams.size(); i++) {
+ iter.addTerm(source, fams.get(i), quals.get(i), env);
+ }
+
+ return iter;
+ }
+
+ /*
+ * This takes the place of the SortedKeyIterator used previously. This iterator is bound to the partitioned table structure. When next is called it will jump
+ * rows as necessary internally versus needing to do it externally as was the case with the SortedKeyIterator.
+ */
+ private FieldIndexIterator createFieldIndexIterator(BooleanLogicTreeNode node) throws IOException {
+ if (log.isDebugEnabled()) {
+ log.debug("BoolLogic.createFieldIndexIterator()");
+ log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
+ }
+ Text rowId = null;
+ sourceIterator.seek(new Range(), EMPTY_COL_FAMS, false);
+ if (sourceIterator.hasTop()) {
+ rowId = sourceIterator.getTopKey().getRow();
+ }
+
+ FieldIndexIterator iter = new FieldIndexIterator(node.getType(), rowId, node.getFieldName(), node.getFieldValue(), node.isNegated(),
+ node.getFieldOperator());
+
+ Map<String,String> options = new HashMap<String,String>();
+ iter.init(sourceIterator.deepCopy(env), options, env);
+ if (log.isDebugEnabled()) {
+ iter.setLogLevel(Level.DEBUG);
+ } else {
+ iter.setLogLevel(Level.OFF);
+ }
+
+ return iter;
+ }
+
+ /* *************************************************************************
+ * Methods for testing the tree WRT boolean logic.
+ */
+ // After all iterator pointers have been advanced, test if the current
+ // record passes the boolean logic.
+ private boolean testTreeState() {
+ if (log.isDebugEnabled()) {
+ log.debug("BoolLogic testTreeState() begin");
+ }
+ Enumeration<?> dfe = this.root.depthFirstEnumeration();
+ while (dfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
+ if (!node.isLeaf()) {
+
+ int type = node.getType();
+ if (type == ParserTreeConstants.JJTANDNODE) { // BooleanLogicTreeNode.NodeType.AND) {
+ handleAND(node);
+ } else if (type == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) {
+ handleOR(node);
+ } else if (type == ParserTreeConstants.JJTJEXLSCRIPT) {// BooleanLogicTreeNode.NodeType.HEAD) {
+ handleHEAD(node);
+ } else if (type == ParserTreeConstants.JJTNOTNODE) { // BooleanLogicTreeNode.NodeType.NOT) {
+ // there should not be any "NOT"s.
+ // throw new Exception();
+ }
+ } else {
+ // it is a leaf, if it is an AND or OR do something
+ if (node.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { //OrIterator
+ node.setValid(node.hasTop());
+ node.reSet();
+ node.addToSet(node.getTopKey());
+
+ } else if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTEQNODE
+ || node.getType() == ParserTreeConstants.JJTERNODE || node.getType() == ParserTreeConstants.JJTLENODE
+ || node.getType() == ParserTreeConstants.JJTLTNODE || node.getType() == ParserTreeConstants.JJTGENODE
+ || node.getType() == ParserTreeConstants.JJTGTNODE) {
+ // sub iterator guarantees it is in its internal range,
+ // otherwise, no top.
+ node.setValid(node.hasTop());
+ }
+ }
+ }
+
+ if (log.isDebugEnabled()) {
+ log.debug("BoolLogic.testTreeState end, treeState:: " + this.root.getContents() + " , valid: " + root.isValid());
+ }
+ return this.root.isValid();
+ }
+
+ private void handleHEAD(BooleanLogicTreeNode node) {
+ Enumeration<?> children = node.children();
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+
+ if (child.getType() == ParserTreeConstants.JJTANDNODE) {// BooleanLogicTreeNode.NodeType.AND) {
+ node.setValid(child.isValid());
+ node.setTopKey(child.getTopKey());
+ } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) {
+ node.setValid(child.isValid());
+ node.setTopKey(child.getTopKey());
+ } else if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTERNODE
+ || child.getType() == ParserTreeConstants.JJTGTNODE || child.getType() == ParserTreeConstants.JJTGENODE
+ || child.getType() == ParserTreeConstants.JJTLTNODE || child.getType() == ParserTreeConstants.JJTLENODE) {// BooleanLogicTreeNode.NodeType.SEL) {
+ node.setValid(true);
+ node.setTopKey(child.getTopKey());
+ if (child.getTopKey() == null) {
+ node.setValid(false);
+ }
+ }
+ }// end while
+
+ // I have to be valid AND have a top key
+ if (node.isValid() && !node.hasTop()) {
+ node.setValid(false);
+ }
+ }
+
+ private void handleAND(BooleanLogicTreeNode me) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND::" + me.getContents());
+ }
+ Enumeration<?> children = me.children();
+ me.setValid(true); // it's easier to prove false than true
+
+ HashSet<Key> goodSet = new HashSet<Key>();
+ HashSet<Key> badSet = new HashSet<Key>();
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+
+ if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTANDNODE
+ || child.getType() == ParserTreeConstants.JJTERNODE || child.getType() == ParserTreeConstants.JJTNENODE
+ || child.getType() == ParserTreeConstants.JJTGENODE || child.getType() == ParserTreeConstants.JJTLENODE
+ || child.getType() == ParserTreeConstants.JJTGTNODE || child.getType() == ParserTreeConstants.JJTLTNODE) {
+
+ if (child.isNegated()) {
+ if (child.hasTop()) {
+ badSet.add(child.getTopKey());
+ if (goodSet.contains(child.getTopKey())) {
+ me.setValid(false);
+ return;
+ }
+ if (child.isValid()) {
+ me.setValid(false);
+ return;
}
-
- // Step 1: Parse the query
- if (log.isDebugEnabled()) {
- log.debug("QueryParser");
- }
- QueryParser qp = new QueryParser();
- qp.execute(this.updatedQuery); // validateOptions updates the updatedQuery
-
- // need to build the query tree based on jexl parsing.
- // Step 2: refactor QueryTree - inplace modification
+ }
+ } else {
+ if (child.hasTop()) {
if (log.isDebugEnabled()) {
- log.debug("transformTreeNode");
+ log.debug("handleAND, child node: " + child.getContents());
}
- TreeNode tree = qp.getIteratorTree();
- this.root = transformTreeNode(tree);
-
- if (log.isDebugEnabled()) {
- log.debug("refactorTree");
+ // if you're in the bad set, you're done.
+ if (badSet.contains(child.getTopKey())) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child is in bad set, setting parent false");
+ }
+ me.setValid(false);
+ return;
+ }
+
+ // if good set is empty, add it.
+ if (goodSet.isEmpty()) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, goodSet is empty, adding child: " + child.getContents());
+ }
+ goodSet.add(child.getTopKey());
+ } else {
+ // must be in the good set & not in the bad set
+ // if either fails, I'm false.
+ if (!goodSet.contains(child.getTopKey())) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, goodSet is not empty, and does NOT contain child, setting false. child: " + child.getContents());
+ }
+ me.setValid(false);
+ return;
+ } else {
+ // trim the good set to this one value
+ // (handles the case were the initial encounters were ORs)
+ goodSet = new HashSet<Key>();
+ goodSet.add(child.getTopKey());
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child in goodset, trim to this value: " + child.getContents());
+ }
+ }
}
- this.root = refactorTree(this.root);
-
+ } else {
+ // test if its children are all false
+ if (child.getChildCount() > 0) {
+ Enumeration<?> subchildren = child.children();
+ boolean allFalse = true;
+ while (subchildren.hasMoreElements()) {
+ BooleanLogicTreeNode subchild = (BooleanLogicTreeNode) subchildren.nextElement();
+ if (!subchild.isNegated()) {
+ allFalse = false;
+ break;
+ } else if (subchild.isNegated() && subchild.hasTop()) {
+ allFalse = false;
+ break;
+ }
+ }
+ if (!allFalse) {
+ me.setValid(false);
+ return;
+ }
+ } else {
+ // child returned a null value and is not a negation, this in turn makes me false.
+ me.setValid(false);
+ return;
+ }
+ }
+ }
+
+ } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) {
+
+ // NOTE: The OR may be an OrIterator in which case it will only produce
+ // a single unique identifier, or it may be a pure logical construct and
+ // be capable of producing multiple unique identifiers.
+ // This should handle all cases.
+ Iterator<?> iter = child.getSetIterator();
+ boolean goodSetEmpty = goodSet.isEmpty();
+ boolean matchedOne = false;
+ boolean pureNegations = true;
+ if (!child.isValid()) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child is an OR and it is not valid, setting false, ALL NEGATED?: " + child.isChildrenAllNegated());
+ }
+ me.setValid(false); // I'm an AND if one of my children is false, I'm false.
+ return;
+ } else if (child.isValid() && !child.hasTop()) {
+ // pure negation, do nothing
+ } else if (child.isValid() && child.hasTop()) { // I need to match one
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child OR, valid and has top, means not pureNegations");
+ }
+ pureNegations = false;
+ while (iter.hasNext()) {
+ Key i = (Key) iter.next();
+ if (child.isNegated()) {
+ badSet.add(i);
+ if (goodSet.contains(i)) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child OR, goodSet contains bad value: " + i);
+ }
+ me.setValid(false);
+ return;
+ }
+ } else {
+ // if the good set is empty, then push all of my ids.
+ if (goodSetEmpty && !badSet.contains(i)) {
+ goodSet.add(i);
+ matchedOne = true;
+ } else {
+ // I need at least one to match
+ if (goodSet.contains(i)) {
+ matchedOne = true;
+ }
+ }
+ }
+ }
+ }
+
+ // is the goodSet still empty? that means were were only negations
+ // otherwise, if it's not empty and we didn't match one, false
+ if (child.isNegated()) {
+ // we're ok
+ } else {
+ if (goodSet.isEmpty() && !pureNegations) {
if (log.isDebugEnabled()) {
- log.debug("collapseBranches");
+ log.debug("handleAND, child OR, empty goodset && !pureNegations, set false");
}
- collapseBranches(root);
-
- // Step 3: create iterators where we need them.
- createIteratorTree(this.root);
- if (log.isDebugEnabled()) {
- log.debug("Query tree after iterator creation:\n\t" + this.root.getContents());
+ // that's bad, we weren't negated, should've pushed something in there.
+ me.setValid(false);
+ return;
+ } else if (!goodSet.isEmpty() && !pureNegations) { // goodSet contains values.
+ if (!matchedOne) { // but we didn't match any.
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND, child OR, goodSet had values but I didn't match any, false");
+ }
+ me.setValid(false);
+ return;
+ }
+
+ // we matched something, trim the set.
+ // i.e. two child ORs
+ goodSet = child.getIntersection(goodSet);
+ }
+ }
+
+ }
+ }// end while
+
+ if (goodSet.isEmpty()) { // && log.isDebugEnabled()) {
+ if (log.isDebugEnabled()) {
+ log.debug("handleAND-> goodSet is empty, pure negations?");
+ }
+ } else {
+ me.setTopKey(Collections.min(goodSet));
+ if (log.isDebugEnabled()) {
+ log.debug("End of handleAND, this node's topKey: " + me.getTopKey());
+ }
+ }
+ }
+
+ private void handleOR(BooleanLogicTreeNode me) {
+ Enumeration<?> children = me.children();
+ // I'm an OR node, need at least one positive.
+ me.setValid(false);
+ me.reSet();
+ me.setTopKey(null);
+ boolean allNegated = true;
+ while (children.hasMoreElements()) {
+ // 3 cases for child: SEL, AND, OR
+ // and negation
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+ // if (child.getType() == BooleanLogicTreeNode.NodeType.SEL || child.getType() == BooleanLogicTreeNode.NodeType.AND) {
+ if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTNENODE
+ || child.getType() == ParserTreeConstants.JJTANDNODE || child.getType() == ParserTreeConstants.JJTERNODE
+ || child.getType() == ParserTreeConstants.JJTNRNODE || child.getType() == ParserTreeConstants.JJTLENODE
+ || child.getType() == ParserTreeConstants.JJTLTNODE || child.getType() == ParserTreeConstants.JJTGENODE
+ || child.getType() == ParserTreeConstants.JJTGTNODE) {
+
+ if (child.hasTop()) {
+ if (child.isNegated()) {
+ // do nothing.
+ } else {
+ allNegated = false;
+ // I have something add it to my set.
+ if (child.isValid()) {
+ me.addToSet(child.getTopKey());
+ }
+ }
+ } else if (!child.isNegated()) { // I have a non-negated child
+ allNegated = false;
+ // that child could be pure negations in which case I'm true
+ me.setValid(child.isValid());
+ }
+
+ } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) {
+ if (child.hasTop()) {
+ if (!child.isNegated()) {
+ allNegated = false;
+ // add its rowIds to my rowIds
+ Iterator<?> iter = child.getSetIterator();
+ while (iter.hasNext()) {
+ Key i = (Key) iter.next();
+ if (i != null) {
+ me.addToSet(i);
+ }
}
- // Step 4: split the positive and negative leaves
- splitLeaves(this.root);
-
- } catch (ParseException ex) {
- log.error("ParseException in init: " + ex);
- throw new IllegalArgumentException("Failed to parse query", ex);
- } catch (Exception ex) {
- throw new IllegalArgumentException("probably had no indexed terms", ex);
- }
-
- }
-
- /* *************************************************************************
- * Methods for sub iterator creation.
- */
- private void createIteratorTree(BooleanLogicTreeNode root) throws IOException {
- if (log.isDebugEnabled()) {
- log.debug("BoolLogic createIteratorTree()");
- }
- // Walk the tree, if all of your children are leaves, roll you into the
- // appropriate iterator.
- Enumeration<?> dfe = root.depthFirstEnumeration();
-
- while (dfe.hasMoreElements()) {
- BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
- if (!node.isLeaf() && node.getType() != ParserTreeConstants.JJTJEXLSCRIPT) {
- //try to roll up.
- if (canRollUp(node)) {
- node.setRollUp(true);
- if (node.getType() == ParserTreeConstants.JJTANDNODE) {
- if (log.isDebugEnabled()) {
- log.debug("creating IntersectingIterator");
- }
- node.setUserObject(createIntersectingIterator(node));
- } else if (node.getType() == ParserTreeConstants.JJTORNODE) {
- node.setUserObject(createOrIterator(node));
- } else {
- // throw an error.
- log.debug("createIteratorTree, encounterd a node type I do not know about: " + node.getType());
- log.debug("createIteratorTree, node contents: " + node.getContents());
- }
- node.removeAllChildren();
- }
+ }
+ } else {
+ // Or node that doesn't have a top, check if it's valid or not
+ // because it could be pure negations itself.
+ if (child.isValid()) {
+ me.setValid(true);
+ }
+ }
+ }
+ }// end while
+
+ if (allNegated) {
+ // do all my children have top?
+ children = me.children();
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+ if (!child.hasTop()) {
+ me.setValid(true);
+ me.setTopKey(null);
+ return;
+ }
+ }
+ me.setValid(false);
+
+ } else {
+ Key k = me.getMinUniqueID();
+ if (k == null) {
+ me.setValid(false);
+ } else {
+ me.setValid(true);
+ me.setTopKey(k);
+ }
+ }
+ }
+
+ /* *************************************************************************
+ * Utility methods.
+ */
+ // Transforms the TreeNode tree of query.parser into the
+ // BooleanLogicTreeNodeJexl form.
+ public BooleanLogicTreeNode transformTreeNode(TreeNode node) throws ParseException {
+ if (node.getType().equals(ASTEQNode.class) || node.getType().equals(ASTNENode.class)) {
+ if (log.isDebugEnabled()) {
+ log.debug("Equals Node");
+ }
+
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "");
+ String fullquery = fName + ":" + fValue;
+ boolean negated = t.getOperator().equals("!=");
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTEQNODE, fName, fValue, negated);
+ return child;
+ }
+ }
+ }
+
+ if (node.getType().equals(ASTERNode.class) || node.getType().equals(ASTNRNode.class)) {
+ if (log.isDebugEnabled()) {
+ log.debug("Regex Node");
+ }
+
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "");
+ String fullquery = fName + ":" + fValue;
+ boolean negated = node.getType().equals(ASTNRNode.class);
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+
+ BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTERNODE, fName, fValue, negated);
+ return child;
+ }
+ }
+ }
+
+ if (node.getType().equals(ASTLTNode.class) || node.getType().equals(ASTLENode.class) || node.getType().equals(ASTGTNode.class)
+ || node.getType().equals(ASTGENode.class)) {
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "").toLowerCase();
+ String fullquery = fName + ":" + fValue;
+ boolean negated = false; // to be negated, must be child of Not, which is handled elsewhere.
+ int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator());
+
+ BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated);
+ if (log.isDebugEnabled()) {
+ log.debug("adding child node: " + child.getContents());
+ }
+ return child;
+ }
+ }
+ }
+
+ BooleanLogicTreeNode returnNode = null;
+
+ if (node.getType().equals(ASTAndNode.class) || node.getType().equals(ASTOrNode.class)) {
+ int parentType = node.getType().equals(ASTAndNode.class) ? ParserTreeConstants.JJTANDNODE : ParserTreeConstants.JJTORNODE;
+ if (log.isDebugEnabled()) {
+ log.debug("AND/OR node: " + parentType);
+ }
+ if (node.isLeaf() || !node.getTerms().isEmpty()) {
+ returnNode = new BooleanLogicTreeNode(parentType);
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "");
+ String fullquery = fName + ":" + fValue;
+ boolean negated = t.getOperator().equals("!=");
+ int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator());
+ BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated);
+ if (log.isDebugEnabled()) {
+ log.debug("adding child node: " + child.getContents());
+ }
+ returnNode.add(child);
+ }
+ }
+ } else {
+ returnNode = new BooleanLogicTreeNode(parentType);
+
+ }
+ } else if (node.getType().equals(ASTNotNode.class)) {
+ if (log.isDebugEnabled()) {
+ log.debug("NOT node");
+ }
+ if (node.isLeaf()) {
+ // NOTE: this should be cleaned up a bit.
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "").toLowerCase();
+ String fullquery = fName + ":" + fValue;
+ boolean negated = !t.getOperator().equals("!=");
+ int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator());
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ return new BooleanLogicTreeNode(mytype, fName, fValue, negated);
+ }
+ }
+ } else {
+ returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTNOTNODE);
+ }
+ } else if (node.getType().equals(ASTJexlScript.class) || node.getType().getSimpleName().equals("RootNode")) {
+
+ if (log.isDebugEnabled()) {
+ log.debug("ROOT/JexlScript node");
+ }
+ if (node.isLeaf()) {
+ returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTJEXLSCRIPT);
+ // NOTE: this should be cleaned up a bit.
+ Multimap<String,QueryTerm> terms = node.getTerms();
+ for (String fName : terms.keySet()) {
+ Collection<QueryTerm> values = terms.get(fName);
+
+ if (!fName.startsWith(FIELD_NAME_PREFIX)) {
+ fName = FIELD_NAME_PREFIX + fName;
+ }
+ for (QueryTerm t : values) {
+ if (null == t || null == t.getValue()) {
+ continue;
+ }
+ String fValue = t.getValue().toString();
+ fValue = fValue.replaceAll("'", "").toLowerCase();
+ String fullquery = fName + ":" + fValue;
+ boolean negated = t.getOperator().equals("!=");
+ int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator());
+
+ BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated);
+ returnNode.add(child);
+ return returnNode;
+ }
+ }
+ } else {
+ returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTJEXLSCRIPT);
+ }
+ } else {
+ log.error("Currently Unsupported Node type: " + node.getClass().getName() + " \t" + node.getType());
+ }
+ for (TreeNode child : node.getChildren()) {
+ returnNode.add(transformTreeNode(child));
+ }
+
+ return returnNode;
+ }
+
+ // After tree conflicts have been resolve, we can collapse branches where
+ // leaves have been pruned.
+ public static void collapseBranches(BooleanLogicTreeNode myroot) throws Exception {
+
+ // NOTE: doing a depth first enumeration didn't wory when I started
+ // removing nodes halfway through. The following method does work,
+ // it's essentially a reverse breadth first traversal.
+ List<BooleanLogicTreeNode> nodes = new ArrayList<BooleanLogicTreeNode>();
+ Enumeration<?> bfe = myroot.breadthFirstEnumeration();
+
+ while (bfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement();
+ nodes.add(node);
+ }
+
+ // walk backwards
+ for (int i = nodes.size() - 1; i >= 0; i--) {
+ BooleanLogicTreeNode node = nodes.get(i);
+ if (log.isDebugEnabled()) {
+ log.debug("collapseBranches, inspecting node: " + node.toString() + " " + node.printNode());
+ }
+
+ if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTORNODE) {
+ if (node.getChildCount() == 0 && !node.isRangeNode()) {
+ node.removeFromParent();
+ } else if (node.getChildCount() == 1) {
+ BooleanLogicTreeNode p = (BooleanLogicTreeNode) node.getParent();
+ BooleanLogicTreeNode c = (BooleanLogicTreeNode) node.getFirstChild();
+ node.removeFromParent();
+ p.add(c);
+
+ }
+ } else if (node.getType() == ParserTreeConstants.JJTJEXLSCRIPT) {
+ if (node.getChildCount() == 0) {
+ if (log.isDebugEnabled()) {
+ log.debug("collapseBranches, headNode has no children");
+ }
+ throw new Exception("Head node has no children.");
+ }
+ }
+ }
+
+ }
+
+ public BooleanLogicTreeNode refactorTree(BooleanLogicTreeNode myroot) {
+ List<BooleanLogicTreeNode> nodes = new ArrayList<BooleanLogicTreeNode>();
+ Enumeration<?> bfe = myroot.breadthFirstEnumeration();
+
+ while (bfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement();
+ nodes.add(node);
+ }
+
+ // walk backwards
+ for (int i = nodes.size() - 1; i >= 0; i--) {
+ BooleanLogicTreeNode node = nodes.get(i);
+ if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTORNODE) {
+ // 1. check to see if all children are negated
+ // 2. check to see if we have to handle ranges.
+
+ Map<Text,RangeBounds> ranges = new HashMap<Text,RangeBounds>();
+ Enumeration<?> children = node.children();
+ boolean allNegated = true;
+ while (children.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+ if (!child.isNegated()) {
+ allNegated = false;
+ // break;
+ }
+
+ // currently we are not allowing unbounded ranges, so they must sit under an AND node.
+ if (node.getType() == ParserTreeConstants.JJTANDNODE) {
+ // check for ranges
+ if (child.getType() == JexlOperatorConstants.JJTGTNODE) {
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: GT " + child.getContents());
+ }
+ if (ranges.containsKey(child.getFieldName())) {
+ RangeBounds rb = ranges.get(child.getFieldName());
+ rb.setLower(child.getFieldValue());
+ } else {
+ RangeBounds rb = new RangeBounds();
+ rb.setLower(child.getFieldValue());
+ ranges.put(child.getFieldName(), rb);
+ }
+ } else if (child.getType() == JexlOperatorConstants.JJTGENODE) {
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: GE " + child.getContents());
+ }
+ if (ranges.containsKey(child.getFieldName())) {
+ RangeBounds rb = ranges.get(child.getFieldName());
+ rb.setLower(child.getFieldValue());
+ } else {
+ RangeBounds rb = new RangeBounds();
+ rb.setLower(child.getFieldValue());
+ ranges.put(child.getFieldName(), rb);
+ }
+ } else if (child.getType() == JexlOperatorConstants.JJTLTNODE) {
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: LT " + child.getContents());
+ }
+ if (ranges.containsKey(child.getFieldName())) {
+ RangeBounds rb = ranges.get(child.getFieldName());
+ rb.setUpper(child.getFieldValue());
+ } else {
+ RangeBounds rb = new RangeBounds();
+ rb.setUpper(child.getFieldValue());
+ ranges.put(child.getFieldName(), rb);
+ }
+ } else if (child.getType() == JexlOperatorConstants.JJTLENODE) {
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: LE " + child.getContents());
+ }
+ if (ranges.containsKey(child.getFieldName())) {
+ RangeBounds rb = ranges.get(child.getFieldName());
+ rb.setUpper(child.getFieldValue());
+ } else {
+ RangeBounds rb = new RangeBounds();
+ rb.setUpper(child.getFieldValue());
+ ranges.put(child.getFieldName(), rb);
+ }
}
+ }
}
-
- // now for remaining leaves, create basic iterators.
- // you can add in specialized iterator mappings here if necessary.
- dfe = root.depthFirstEnumeration();
- while (dfe.hasMoreElements()) {
- BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
- if (node.isLeaf() && node.getType() != ParserTreeConstants.JJTANDNODE && node.getType() != ParserTreeConstants.JJTORNODE) {
- node.setUserObject(createFieldIndexIterator(node));
- }
+ if (allNegated) {
+ node.setChildrenAllNegated(true);
}
- }
-
- private AndIterator createIntersectingIterator(BooleanLogicTreeNode node) throws IOException {
+
+ // see if the AND node had a range.
+ if (node.getType() == ParserTreeConstants.JJTANDNODE) {
+
+ // if(ranges.containsKey(node.getFieldName())){
+ if (!ranges.isEmpty()) {
+ // we have a range, process it
+ if (node.getChildCount() <= 2 && ranges.size() == 1) {
+ if (log.isDebugEnabled()) {
+ log.debug("AND range 2 children or less");
+ }
+ // only has a range, modify the node
+ node.setType(ParserTreeConstants.JJTORNODE);
+ node.removeAllChildren();
+ // RangeBounds rb = ranges.get(node.getFieldName());
+
+ for (Entry<Text,RangeBounds> entry : ranges.entrySet()) {
+ Text fName = entry.getKey();
+ RangeBounds rb = entry.getValue();
+ node.setFieldName(fName);
+ node.setFieldValue(new Text(""));
+ node.setLowerBound(rb.getLower());
+ node.setUpperBound(rb.getUpper());
+ node.setRangeNode(true);
+ }
+
+ rangerators.add(node);
+
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: " + node.getContents());
+ log.debug("refactor: " + node.getLowerBound() + " " + node.getUpperBound());
+ }
+
+ } else {
+ if (log.isDebugEnabled()) {
+ log.debug("AND range more than 2 children");
+ }
+ // node has range plus other children, create another node from the range
+ // remove lt,le,gt,ge from parent and push in a single node
+
+ // removing nodes via enumeration doesn't work, push into a list
+ // and walk backwards
+ List<BooleanLogicTreeNode> temp = new ArrayList<BooleanLogicTreeNode>();
+ Enumeration<?> e = node.children();
+ while (e.hasMoreElements()) {
+ BooleanLogicTreeNode c = (BooleanLogicTreeNode) e.nextElement();
+ temp.add(c);
+ }
+
+ for (int j = temp.size() - 1; j >= 0; j--) {
+ BooleanLogicTreeNode c = temp.get(j);
+ if (c.getType() == JexlOperatorConstants.JJTLENODE || c.getType() == JexlOperatorConstants.JJTLTNODE
+ || c.getType() == JexlOperatorConstants.JJTGENODE || c.getType() == JexlOperatorConstants.JJTGTNODE) {
+ c.removeFromParent();
+ }
+ }
+
+ for (Entry<Text,RangeBounds> entry : ranges.entrySet()) {
+ Text fName = entry.getKey();
+ BooleanLogicTreeNode nchild = new BooleanLogicTreeNode(ParserTreeConstants.JJTORNODE, fName.toString(), "");
+ RangeBounds rb = entry.getValue();
+ nchild.setFieldValue(new Text(""));
+ nchild.setLowerBound(rb.getLower());
+ nchild.setUpperBound(rb.getUpper());
+ nchild.setRangeNode(true);
+ node.add(nchild);
+ rangerators.add(nchild);
+ }
+
+ if (log.isDebugEnabled()) {
+ log.debug("refactor: " + node.getContents());
+ }
+ }
+ }
+ }
+
+ }
+ }
+
+ return myroot;
+
+ }
+
+ // If all children are of type SEL, roll this up into an AND or OR node.
+ private static boolean canRollUp(BooleanLogicTreeNode parent) {
+ if (log.isDebugEnabled()) {
+ log.debug("canRollUp: testing " + parent.getContents());
+ }
+ if (parent.getChildCount() < 1) {
+ if (log.isDebugEnabled()) {
+ log.debug("canRollUp: child count < 1, return false");
+ }
+ return false;
+ }
+ Enumeration<?> e = parent.children();
+ while (e.hasMoreElements()) {
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) e.nextElement();
+
+ if (child.getType() != ParserTreeConstants.JJTEQNODE) {// BooleanLogicTreeNode.NodeType.SEL) {
if (log.isDebugEnabled()) {
- log.debug("createIntersectingIterator(node)");
- log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
- }
- Text[] columnFamilies = new Text[node.getChildCount()];
- Text[] termValues = new Text[node.getChildCount()];
- boolean[] negationMask = new boolean[node.getChildCount()];
- Enumeration<?> children = node.children();
- int i = 0;
- while (children.hasMoreElements()) {
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
- columnFamilies[i] = child.getFieldName();
- termValues[i] = child.getFieldValue();
- negationMask[i] = child.isNegated();
- i++;
+ log.debug("canRollUp: child.getType -> " + ParserTreeConstants.jjtNodeName[child.getType()] + " int: " + child.getType() + " return false");
}
-
- AndIterator ii = new AndIterator();
- Map<String, String> options = new HashMap<String, String>();
- options.put(AndIterator.columnFamiliesOptionName, AndIterator.encodeColumns(columnFamilies));
- options.put(AndIterator.termValuesOptionName, AndIterator.encodeTermValues(termValues));
- options.put(AndIterator.notFlagsOptionName, AndIterator.encodeBooleans(negationMask));
-
- ii.init(sourceIterator.deepCopy(env), options, env);
- return ii;
- }
-
- private OrIterator createOrIterator(BooleanLogicTreeNode node) throws IOException {
+ return false;
+ }
+
+ if (child.isNegated()) {
if (log.isDebugEnabled()) {
- log.debug("createOrIterator(node)");
- log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
- }
-
- Enumeration<?> children = node.children();
- ArrayList<Text> fams = new ArrayList<Text>();
- ArrayList<Text> quals = new ArrayList<Text>();
- while (children.hasMoreElements()) {
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
- fams.add(child.getFieldName());
- quals.add(child.getFieldValue());
- }
-
- OrIterator iter = new OrIterator();
- SortedKeyValueIterator<Key, Value> source = sourceIterator.deepCopy(env);
- for (int i = 0; i < fams.size(); i++) {
- iter.addTerm(source, fams.get(i), quals.get(i), env);
+ log.debug("canRollUp: child.isNegated, return false");
}
-
- return iter;
- }
-
- /*
- * This takes the place of the SortedKeyIterator used previously.
- * This iterator is bound to the partitioned table structure. When next
- * is called it will jump rows as necessary internally versus needing to
- * do it externally as was the case with the SortedKeyIterator.
- */
- private FieldIndexIterator createFieldIndexIterator(BooleanLogicTreeNode node) throws IOException {
+ return false;
+ }
+
+ if (child.getFieldValue().toString().contains("*")) {
if (log.isDebugEnabled()) {
- log.debug("BoolLogic.createFieldIndexIterator()");
- log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator());
+ log.debug("canRollUp: child has wildcard: " + child.getFieldValue());
}
- Text rowId = null;
- sourceIterator.seek(new Range(), EMPTY_COL_FAMS, false);
- if (sourceIterator.hasTop()) {
- rowId = sourceIterator.getTopKey().getRow();
- }
-
- FieldIndexIterator iter = new FieldIndexIterator(node.getType(), rowId, node.getFieldName(), node.getFieldValue(), node.isNegated(), node.getFieldOperator());
-
- Map<String, String> options = new HashMap<String, String>();
- iter.init(sourceIterator.deepCopy(env), options, env);
- if (log.isDebugEnabled()) {
- iter.setLogLevel(Level.DEBUG);
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Small utility function to print out the depth-first enumeration of the tree. Specify the root or sub root of the tree you wish to view.
+ *
+ * @param root
+ * The root node of the tree or sub-tree.
+ */
+ public static void showDepthFirstTraversal(BooleanLogicTreeNode root) {
+ System.out.println("DepthFirstTraversal");
+ Enumeration<?> e = root.depthFirstEnumeration();
+ int i = -1;
+ while (e.hasMoreElements()) {
+ i += 1;
+ BooleanLogicTreeNode n = (BooleanLogicTreeNode) e.nextElement();
+ System.out.println(i + " : " + n);
+ }
+ }
+
+ public static void showBreadthFirstTraversal(BooleanLogicTreeNode root) {
+ System.out.println("BreadthFirstTraversal");
+ log.debug("BooleanLogicIterator.showBreadthFirstTraversal()");
+ Enumeration<?> e = root.breadthFirstEnumeration();
+ int i = -1;
+ while (e.hasMoreElements()) {
+ i += 1;
+ BooleanLogicTreeNode n = (BooleanLogicTreeNode) e.nextElement();
+ System.out.println(i + " : " + n);
+ log.debug(i + " : " + n);
+ }
+ }
+
+ private void splitLeaves(BooleanLogicTreeNode node) {
+ if (log.isDebugEnabled()) {
+ log.debug("BoolLogic: splitLeaves()");
+ }
+ positives = new PriorityQueue<BooleanLogicTreeNode>(10, new BooleanLogicTreeNodeComparator());
+ // positives = new ArrayList<BooleanLogicTreeNodeJexl>();
+ negatives = new ArrayList<BooleanLogicTreeNode>();
+
+ Enumeration<?> dfe = node.depthFirstEnumeration();
+ while (dfe.hasMoreElements()) {
+ BooleanLogicTreeNode elem = (BooleanLogicTreeNode) dfe.nextElement();
+
+ if (elem.isLeaf()) {
+ if (elem.isNegated()) {
+ negatives.add(elem);
} else {
- iter.setLogLevel(Level.OFF);
+ positives.add(elem);
}
-
- return iter;
+ }
}
-
- /* *************************************************************************
- * Methods for testing the tree WRT boolean logic.
- */
- // After all iterator pointers have been advanced, test if the current
- // record passes the boolean logic.
- private boolean testTreeState() {
+ }
+
+ /* *************************************************************************
+ * The iterator interface methods.
+ */
+ public boolean hasTop() {
+ return (topKey != null);
+ }
+
+ public Key getTopKey() {
+ if (log.isDebugEnabled()) {
+ log.debug("getTopKey: " + topKey);
+ }
+ return topKey;
+ }
+
+ private void setTopKey(Key key) {
+ if (this.overallRange != null && key != null) {
+ if (overallRange.getEndKey() != null) { // if null end key, that means range is to the end of the tablet.
+ if (!this.overallRange.contains(key)) {
+ topKey = null;
+ return;
+ }
+ }
+ }
+ topKey = key;
+ }
+
+ public Value getTopValue() {
+ if (topValue == null) {
+ topValue = new Value(new byte[0]);
+ }
+ return topValue;
+ }
+
+ private void resetNegatives() {
+ for (BooleanLogicTreeNode neg : negatives) {
+ neg.setTopKey(null);
+ neg.setValid(true);
+ }
+ }
+
+ private String getEventKeyUid(Key k) {
+ String uid = null;
+ if (k == null || k.getColumnFamily() == null) {
+ return uid;
+ } else {
+ String[] parts = k.getColumnFamily().toString().split("\0");
+ if (parts.length < 2) {
+ return uid;
+ } else {
+ return parts[parts.length - 1];
+ }
+ }
+ }
+
+ private String getIndexKeyUid(Key k) {
+ try {
+ int idx = 0;
+ String sKey = k.getColumnQualifier().toString();
+ idx = sKey.lastIndexOf("\0");
+ return sKey.substring(idx + 1);
+ } catch (Exception e) {
+ return null;
+ }
+ }
+
+ /*
+ * Remember, the Key in the BooleanLogicTreeNode is different structurally than the Key in its sub iterator because the key BooleanLogic needs to return is an
+ * event key created from the index key (which is what the sub iterators are looking at!)
+ */
+ private Key getOptimizedAdvanceKey() throws IOException {
+ if (log.isDebugEnabled()) {
+ log.debug("getOptimizedAdvanceKey() called");
+ }
+ Enumeration<?> bfe = root.breadthFirstEnumeration();
+ ArrayList<BooleanLogicTreeNode> bfl = new ArrayList<BooleanLogicTreeNode>();
+ while (bfe.hasMoreElements()) {
+ BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement();
+ if (!node.isNegated()) {
+ node.setAdvanceKey(node.getTopKey());
+ node.setDone(false);
+ bfl.add(node);
+ }
+ }
+
+ // walk the tree backwards
+ for (int i = bfl.size() - 1; i >= 0; i--) {
+ if (bfl.get(i).isLeaf() || bfl.get(i).isNegated()) {
if (log.isDebugEnabled()) {
- log.debug("BoolLogic testTreeState() begin");
- }
- Enumeration<?> dfe = this.root.depthFirstEnumeration();
- while (dfe.hasMoreElements()) {
- BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement();
- if (!node.isLeaf()) {
-
- int type = node.getType();
- if (type == ParserTreeConstants.JJTANDNODE) { //BooleanLogicTreeNode.NodeType.AND) {
- handleAND(node);
- } else if (type == ParserTreeConstants.JJTORNODE) {//BooleanLogicTreeNode.NodeType.OR) {
- handleOR(node);
- } else if (type == ParserTreeConstants.JJTJEXLSCRIPT) {//BooleanLogicTreeNode.NodeType.HEAD) {
- handleHEAD(node);
- } else if (type == ParserTreeConstants.JJTNOTNODE) { //BooleanLogicTreeNode.NodeType.NOT) {
- // there should not be any "NOT"s.
- //throw new Exception();
- }
- } else {
- // it is a leaf, if it is an AND or OR do something
- if (node.getType() == ParserTreeConstants.JJTORNODE) {//BooleanLogicTreeNode.NodeType.OR) { //OrIterator
- node.setValid(node.hasTop());
- node.reSet();
- node.addToSet(node.getTopKey());
-
- } else if (node.getType() == ParserTreeConstants.JJTANDNODE
- || node.getType() == ParserTreeConstants.JJTEQNODE
- || node.getType() == ParserTreeConstants.JJTERNODE
- || node.getType() == ParserTreeConstants.JJTLENODE
- || node.getType() == ParserTreeConstants.JJTLTNODE
- || node.getType() == ParserTreeConstants.JJTGENODE
- || node.getType() == ParserTreeConstants.JJTGTNODE) {
- // sub iterator guarantees it is in its internal range,
- // otherwise, no top.
- node.setValid(node.hasTop());
- }
- }
+ log.debug("leaf, isDone?: " + bfl.get(i).isDone());
}
-
- if (log.isDebugEnabled()) {
- log.debug("BoolLogic.testTreeState end, treeState:: " + this.root.getContents() + " , valid: " + root.isValid());
- }
- return this.root.isValid();
- }
-
- private void handleHEAD(BooleanLogicTreeNode node) {
+ continue;
+ }
+
+ BooleanLogicTreeNode node = bfl.get(i);
+ node.setDone(false);
+ if (log.isDebugEnabled()) {
+ log.debug("for loop, node: " + node + " isDone? " + node.isDone());
+ }
+ if (node.getType() == ParserTreeConstants.JJTANDNODE) {
+ // get max
+ BooleanLogicTreeNode max = null;
Enumeration<?> children = node.children();
+ boolean firstTime = true;
while (children.hasMoreElements()) {
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
-
- if (child.getType() == ParserTreeConstants.JJTANDNODE) {//BooleanLogicTreeNode.NodeType.AND) {
- node.setValid(child.isValid());
- node.setTopKey(child.getTopKey());
- } else if (child.getType() == ParserTreeConstants.JJTORNODE) {//BooleanLogicTreeNode.NodeType.OR) {
- node.setValid(child.isValid());
- node.setTopKey(child.getTopKey());
- } else if (child.getType() == ParserTreeConstants.JJTEQNODE
- || child.getType() == ParserTreeConstants.JJTERNODE
- || child.getType() == ParserTreeConstants.JJTGTNODE
- || child.getType() == ParserTreeConstants.JJTGENODE
- || child.getType() == ParserTreeConstants.JJTLTNODE
- || child.getType() == ParserTreeConstants.JJTLENODE) {//BooleanLogicTreeNode.NodeType.SEL) {
- node.setValid(true);
- node.setTopKey(child.getTopKey());
- if (child.getTopKey() == null) {
- node.setValid(false);
- }
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+
+ if (child.isNegated() || child.isChildrenAllNegated()) {
+ continue;
+ }
+
+ // all advance keys were initially set from topkey for the leaves.
+ if (child.getAdvanceKey() == null) {
+ log.debug("\tchild does not advance key: " + child.printNode());
+ // i'm an and, i have a child that's done, mark me as done.
+ node.setDone(true);
+ break;
+ } else {
+ log.debug("\tchild advanceKey: " + child.getAdvanceKey());
+ }
+
+ if (firstTime) {
+ firstTime = false;
+ max = child;
+ if (log.isDebugEnabled()) {
+ log.debug("\tAND block, first valid child: " + child);
+ }
+ continue;
+ }
+
+ log.debug("\tAND block, max: " + max);
+ log.debug("\tAND block, child: " + child);
+
+ // first test row
+ if (max.getAdvanceKey().getRow().compareTo(child.getAdvanceKey().getRow()) < 0) {
+ max = child;
+ if (log.isDebugEnabled()) {
+ log.debug("\tAND block, child row greater, new max.");
+ }
+ continue;
+ }
+
+ // if rows are equal, test uids
+ String uid_max = getEventKeyUid(max.getAdvanceKey());
+ String uid_child = getEventKeyUid(child.getAdvanceKey());
+ if (log.isDebugEnabled()) {
+ if (uid_max == null) {
+ log.debug("\tuid_max is currently null");
+ } else {
+ log.debug("\tuid_max: " + uid_max);
}
- }//end while
-
- // I have to be valid AND have a top key
- if (node.isValid() && !node.hasTop()) {
- node.setValid(false);
- }
- }
-
- private void handleAND(BooleanLogicTreeNode me) {
+ if (uid_child == null) {
+ log.debug("\tuid_child is null");
+ } else {
+ log.debug("\tuid_child: " + uid_child);
+ }
+ }
+
+ if (uid_max != null && uid_child != null) {
+ if (uid_max.compareTo(uid_child) < 0) {
+ max = child;
+ }
+ } else if (uid_child == null) { // one or the other is null so we want the next row
+ max = child;
+ log.debug("uid_child is null, we need to grab the next row.");
+ break;
+ } else {
+ log.debug("max is null and child is not, who should we keep? child: " + child);
+ break;
+ }
+ } // end while
if (log.isDebugEnabled()) {
- log.debug("handleAND::" + me.getContents());
+ log.debug("attemptOptimization: AND with children, max: " + max);
}
- Enumeration<?> children = me.children();
- me.setValid(true); //it's easier to prove false than true
-
- HashSet<Key> goodSet = new HashSet<Key>();
- HashSet<Key> badSet = new HashSet<Key>();
- while (children.hasMoreElements()) {
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
-
- if (child.getType() == ParserTreeConstants.JJTEQNODE
- || child.getType() == ParserTreeConstants.JJTANDNODE
- || child.getType() == ParserTreeConstants.JJTERNODE
- || child.getType() == ParserTreeConstants.JJTNENODE
- || child.getType() == ParserTreeConstants.JJTGENODE
- || child.getType() == ParserTreeConstants.JJTLENODE
- || child.getType() == ParserTreeConstants.JJTGTNODE
- || child.getType() == ParserTreeConstants.JJTLTNODE) {
-
- if (child.isNegated()) {
- if (child.hasTop()) {
- badSet.add(child.getTopKey());
- if (goodSet.contains(child.getTopKey())) {
- me.setValid(false);
- return;
- }
- if (child.isValid()) {
- me.setValid(false);
- return;
- }
- }
- } else {
- if (child.hasTop()) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child node: " + child.getContents());
- }
- // if you're in the bad set, you're done.
- if (badSet.contains(child.getTopKey())) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child is in bad set, setting parent false");
- }
- me.setValid(false);
- return;
- }
-
- // if good set is empty, add it.
- if (goodSet.isEmpty()) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, goodSet is empty, adding child: " + child.getContents());
- }
- goodSet.add(child.getTopKey());
- } else {
- //must be in the good set & not in the bad set
- //if either fails, I'm false.
- if (!goodSet.contains(child.getTopKey())) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, goodSet is not empty, and does NOT contain child, setting false. child: " + child.getContents());
- }
- me.setValid(false);
- return;
- } else {
- //trim the good set to this one value
- //(handles the case were the initial encounters were ORs)
- goodSet = new HashSet<Key>();
- goodSet.add(child.getTopKey());
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child in goodset, trim to this value: " + child.getContents());
- }
- }
- }
- } else {
- //test if its children are all false
- if (child.getChildCount() > 0) {
- Enumeration<?> subchildren = child.children();
- boolean allFalse = true;
- while (subchildren.hasMoreElements()) {
- BooleanLogicTreeNode subchild = (BooleanLogicTreeNode) subchildren.nextElement();
- if (!subchild.isNegated()) {
- allFalse = false;
- break;
- } else if (subchild.isNegated() && subchild.hasTop()) {
- allFalse = false;
- break;
- }
- }
- if (!allFalse) {
- me.setValid(false);
- return;
- }
- } else {
- //child returned a null value and is not a negation, this in turn makes me false.
- me.setValid(false);
- return;
- }
- }
- }
-
- } else if (child.getType() == ParserTreeConstants.JJTORNODE) {//BooleanLogicTreeNode.NodeType.OR) {
-
- // NOTE: The OR may be an OrIterator in which case it will only produce
- // a single unique identifier, or it may be a pure logical construct and
- // be capable of producing multiple unique identifiers.
- // This should handle all cases.
- Iterator<?> iter = child.getSetIterator();
- boolean goodSetEmpty = goodSet.isEmpty();
- boolean matchedOne = false;
- boolean pureNegations = true;
- if (!child.isValid()) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child is an OR and it is not valid, setting false, ALL NEGATED?: " + child.isChildrenAllNegated());
- }
- me.setValid(false); // I'm an AND if one of my children is false, I'm false.
- return;
- } else if (child.isValid() && !child.hasTop()) {
- // pure negation, do nothing
- } else if (child.isValid() && child.hasTop()) { // I need to match one
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child OR, valid and has top, means not pureNegations");
- }
- pureNegations = false;
- while (iter.hasNext()) {
- Key i = (Key) iter.next();
- if (child.isNegated()) {
- badSet.add(i);
- if (goodSet.contains(i)) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child OR, goodSet contains bad value: " + i);
- }
- me.setValid(false);
- return;
- }
- } else {
- //if the good set is empty, then push all of my ids.
- if (goodSetEmpty && !badSet.contains(i)) {
- goodSet.add(i);
- matchedOne = true;
- } else {
- //I need at least one to match
- if (goodSet.contains(i)) {
- matchedOne = true;
- }
- }
- }
- }
- }
-
- //is the goodSet still empty? that means were were only negations
- //otherwise, if it's not empty and we didn't match one, false
- if (child.isNegated()) {
- //we're ok
- } else {
- if (goodSet.isEmpty() && !pureNegations) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child OR, empty goodset && !pureNegations, set false");
- }
- //that's bad, we weren't negated, should've pushed something in there.
- me.setValid(false);
- return;
- } else if (!goodSet.isEmpty() && !pureNegations) { // goodSet contains values.
- if (!matchedOne) { //but we didn't match any.
- if (log.isDebugEnabled()) {
- log.debug("handleAND, child OR, goodSet had values but I didn't match any, false");
- }
- me.setValid(false);
- return;
- }
-
- // we matched something, trim the set.
- // i.e. two child ORs
- goodSet = child.getIntersection(goodSet);
- }
- }
-
- }
- }//end while
-
- if (goodSet.isEmpty()) { //&& log.isDebugEnabled()) {
- if (log.isDebugEnabled()) {
- log.debug("handleAND-> goodSet is empty, pure negations?");
- }
+ if (max != null) {
+ node.setAdvanceKey(max.getAdvanceKey());
} else {
- me.setTopKey(Collections.min(goodSet));
- if (log.isDebugEnabled()) {
- log.debug("End of handleAND, this node's topKey: " + me.getTopKey());
- }
- }
- }
-
- private void handleOR(BooleanLogicTreeNode me) {
- Enumeration<?> children = me.children();
- //I'm an OR node, need at least one positive.
- me.setValid(false);
- me.reSet();
- me.setTopKey(null);
- boolean allNegated = true;
+ if (log.isDebugEnabled()) {
+ log.debug("AND block finished, max is null");
+ }
+ node.setDone(true);
+ }
+
+ } else if (node.getType() == ParserTreeConstants.JJTORNODE) {
+ // get min
+ BooleanLogicTreeNode min = null;
+ Enumeration<?> children = node.children();
+ boolean firstTime = true;
+ int numChildren = node.getChildCount();
+ int allChildrenDone = 0;
+
while (children.hasMoreElements()) {
- // 3 cases for child: SEL, AND, OR
- // and negation
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
- //if (child.getType() == BooleanLogicTreeNode.NodeType.SEL || child.getType() == BooleanLogicTreeNode.NodeType.AND) {
- if (child.getType() == ParserTreeConstants.JJTEQNODE
- || child.getType() == ParserTreeConstants.JJTNENODE
- || child.getType() == ParserTreeConstants.JJTANDNODE
- || child.getType() == ParserTreeConstants.JJTERNODE
- || child.getType() == ParserTreeConstants.JJTNRNODE
- || child.getType() == ParserTreeConstants.JJTLENODE
- || child.getType() == ParserTreeConstants.JJTLTNODE
- || child.getType() == ParserTreeConstants.JJTGENODE
- || child.getType() == ParserTreeConstants.JJTGTNODE) {
-
- if (child.hasTop()) {
- if (child.isNegated()) {
- // do nothing.
- } else {
- allNegated = false;
- //I have something add it to my set.
- if (child.isValid()) {
- me.addToSet(child.getTopKey());
- }
- }
- } else if (!child.isNegated()) { //I have a non-negated child
- allNegated = false;
- // that child could be pure negations in which case I'm true
- me.setValid(child.isValid());
- }
-
- } else if (child.getType() == ParserTreeConstants.JJTORNODE) {//BooleanLogicTreeNode.NodeType.OR) {
- if (child.hasTop()) {
- if (!child.isNegated()) {
- allNegated = false;
- //add its rowIds to my rowIds
- Iterator<?> iter = child.getSetIterator();
- while (iter.hasNext()) {
- Key i = (Key) iter.next();
- if (i != null) {
- me.addToSet(i);
- }
- }
- }
- } else {
- // Or node that doesn't have a top, check if it's valid or not
- // because it could be pure negations itself.
- if (child.isValid()) {
- me.setValid(true);
- }
+ BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
+
+ if (log.isDebugEnabled()) {
+ log.debug("\tOR block start, child: " + child);
+ }
+ if (child.isNegated() || child.isChildrenAllNegated()) {
+ if (log.isDebugEnabled()) {
+ log.debug("\tskip negated child: " + child);
+ }
+ numChildren -= 1;
+ continue;
+ }
+ if (child.isDone()) {
+ if (log.isDebugEnabled()) {
+ log.debug("\tchild is done: " + child);
+ }
+ allChildrenDone += 1;
+ if (numChildren == allChildrenDone) {
+ if (log.isDebugEnabled()) {
+ log.debug("\tnumChildren==allChildrenDone, setDone & break");
+ }
+ // we're done here
+ node.setDone(true);
+ break;
+ }
+ }
+
+ if (child.getAdvanceKey() == null) {
+ log.debug("\tOR child doesn't have top or an AdvanceKey");
+ continue;
+ }
+ if (firstTime) {
+ if (log.isDebugEnabled()) {
+ log.debug("\tOR block, first valid node, min=child: " + child + " advanceKey: " + child.getAdvanceKey());
+ }
+
+ firstTime = false;
+ min = child;
+ continue;
+ }
+ if (log.isDebugEnabled()) {
+ log.debug("\tOR block, min: " + min);
+ log.debug("\tOR block, child: " + child);
+ }
+ if (min.getAdvanceKey().getRow().toString().compareTo(child.getAdvanceKey().getRow().toString()) > 0) {
+ // child row is less than min, set min to child
+ min = child;
+ if (log.isDebugEnabled()) {
+ log.debug("\tmin row was greater than child, min=child: " + min);
+ }
+ continue;
+
+ } else if (min.getAdvanceKey().getRow().compareTo(child.getAdvanceKey().getRow()) < 0) {
+ // min row is less child, skip
+ if (log.isDebugEnabled()) {
+ log.debug("\tmin row less than childs, keep min: " + min);
+ }
+ continue;
+
+ } else { // they're equal, test uids
+ String uid_min = getEventKeyUid(min.getAdvanceKey());
+ String uid_child = getEventKeyUid(child.getAdvanceKey());
+ if (log.isDebugEnabled()) {
+ log.debug("\ttesting uids, uid_min: " + uid_min + " uid_child: " + uid_child);
+ }
+ if (uid_min != null && uid_child != null) {
+ if (uid_min.compareTo(uid_child) > 0) {
+
+ min = child;
+ if (log.isDebugEnabled()) {
+ log.debug("\tuid_min > uid_child, set min to child: " + min);
}
+ }
+ } else if (uid_min == null) {
+ if (log.isDebugEnabled()) {
+ log.debug("\tuid_min is null, take childs: " + uid_child);
+ }
+ min = child;
}
+ }
}// end while
-
-
- if (allNegated) {
- // do all my children have top?
- children = me.children();
- while (children.hasMoreElements()) {
- BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement();
- if (!child.hasTop()) {
- me.setValid(true);
- me.setTopKey(null);
- return;
- }
- }
- me.setValid(false);
-
- } else {
- Key k = me.getMinUniqueID();
- if (k == null) {
- me.setValid(false);
- } else {
- me.setValid(true);
- me.setTopKey(k);
- }
- }
- }
-
- /* *************************************************************************
- * Utility methods.
- */
- // Transforms the TreeNode tree of query.parser into the
- // BooleanLogicTreeNodeJexl form.
- public BooleanLogicTreeNode transformTreeNode(TreeNode node) throws ParseException {
- if (node.getType().equals(ASTEQNode.class) || node.getType().equals(ASTNENode.class)) {
- if (log.isDebugEnabled()) {
- log.debug("Equals Node");
- }
-
- Multimap<String, QueryTerm> terms = node.getTerms();
- for (String fName : terms.keySet()) {
- Collection<QueryTerm> values = terms.get(fName);
-
- for (QueryTerm t : values) {
- if (null == t || null == t.getValue()) {
- continue;
- }
- String fValue = t.getValue().toString();
- fValue = fValue.replaceAll("'", "");
- String fullquery = fName + ":" + fValue;
- boolean negated = t.getOperator().equals("!=");
-
- if (!fName.startsWith(FIELD_NAME_PREFIX)) {
- fName = FIELD_NAME_PREFIX + fName;
- }
- BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTEQNODE, fName, fValue, negated);
- return child;
- }
- }
- }
-
- if (node.getType().equals(ASTERNode.class) || node.getType().equals(ASTNRNode.class)) {
- if (log.isDebugEnabled()) {
- log.debug("Regex Node");
- }
-
- Multimap<String, QueryTerm> terms = node.getTerms();
- for (String fName : terms.keySet()) {
- Collection<QueryTerm> values = terms.get(fName);
- for (QueryTerm t : values) {
- if (null == t || null == t.getValue()) {
- continue;
- }
- String fValue = t.getValue().toString();
- fValue = fValue.replaceAll("'", "");
- String fullquery = fName + ":" + fValue;
- boolean negated = node.getType().equals(ASTNRNode.class);
-
- if (!fName.startsWith(FIELD_NAME_PREFIX)) {
- fName = FIELD_NAME_PREFIX + fName;
- }
-
- BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTERNODE, fName, fValue, negated);
- return child;
- }
- }
- }
-
- if (node.getType().equals(ASTLTNode.class) || node.getType().equals(ASTLENode.class)
- || node.getType().equals(ASTGTNode.class) || node.getType().equals(ASTGENode.class)) {
- Multimap<String, QueryTerm> terms = node.getTerms();
- for (String fName : terms.keySet()) {
- Collection<QueryTerm> values = terms.get(fName);
-
- if (!fName.startsWith(FIELD_NAME_PREFIX)) {
- fName = FIELD_NAME_PREFIX + fName;
- }
- for (QueryTerm t : values) {
- if (null == t || null == t.getValue()) {
- continue;
- }
- String fValue = t.getValue().toString();
- fValue = fValue.replaceAll("'", "").toLowerCase();
- String fullquery = fName + ":" + fValue;
- boolean negated = false; // to be negated, must be child of Not, which is handled elsewhere.
- int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator());
-
- BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated);
- if (log.isDebugEnabled()) {
[... 1775 lines stripped ...]