You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@accumulo.apache.org by ec...@apache.org on 2011/12/27 19:19:44 UTC

svn commit: r1224966 [3/10] - in /incubator/accumulo/branches/1.4: ./ contrib/accumulo_sample/ contrib/accumulo_sample/ingest/src/main/java/aggregator/ contrib/accumulo_sample/ingest/src/main/java/ingest/ contrib/accumulo_sample/ingest/src/test/java/ag...

Modified: incubator/accumulo/branches/1.4/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java
URL: http://svn.apache.org/viewvc/incubator/accumulo/branches/1.4/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java?rev=1224966&r1=1224965&r2=1224966&view=diff
==============================================================================
--- incubator/accumulo/branches/1.4/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java (original)
+++ incubator/accumulo/branches/1.4/contrib/accumulo_sample/query/src/main/java/iterator/BooleanLogicIterator.java Tue Dec 27 18:19:43 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,1924 @@ 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 = new ArrayList<BooleanLogicTreeNode>();
+  private ArrayList<BooleanLogicTreeNode> rangerators;
+  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()) {
+      FieldIndexIterator.setLogLevel(Level.DEBUG);
+    } else {
+      FieldIndexIterator.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("'", "");
+          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("'", "");
+          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();
+          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("'", "");
+            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();
+            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();
+            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.clear();
+    
+    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() {
+  }
+  
+  private void reHeapPriorityQueue(BooleanLogicTreeNode node) {
+    positives.clear();
+    Enumeration<?> dfe = node.depthFirstEnumeration();
+    BooleanLogicTreeNode elem;
+    while (dfe.hasMoreElements()) {
+      elem = (BooleanLogicTreeNode) dfe.nextElement();
+      if (elem.isLeaf() && !elem.isNegated()) {
+        positives.add(elem);
+      }
+    }
+  }
+
+  /* *************************************************************************
+   * 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) {
+    if (k == null || k.getColumnFamily() == null) {
+      return null;
+    } else {
+      return k.getColumnFamily().toString();
+    }
+  }
+  
+  private String getIndexKeyUid(Key k) {
+    try {
+      int idx = 0;
+      String sKey = k.getColumnQualifier().toString();
+      idx = sKey.indexOf("\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()) {
-                        log.debug("adding child node: " + child.getContents());
-                    }

[... 1766 lines stripped ...]