Re: XPathQueryResolver Always Collection Scans On UNION [fix]

[Terry Rosenbaum]

Hi, The diff problem is most likely just a line terminator problem (Bill Gates vs. Ken Thompson). I look at the current CVS version and the modified version and see just the changes I made (using CompareIt! on WIN32). Usually you can tell your comparison tool to eliminate whitespace differences. No matter. What I changed was I added the evalUnion method and I added the call to it in the giant switch statement. I have attached the output from running the following GNU diff command (3-line contextual diff usable with patch): diff -w -C 3 XPathQueryResolver-Orig.java XPathQueryResolver-new.java > diffs.txt The key thing to recognize is that a union is easily evaluated by or'ing keysets. Evaluate the left into a keyset, evaluate the right into a keyset, or the left and right keysets together. -Terry Gianugo Rabellino wrote: Terry Rosenbaum wrote: Whenever a UNION operator ("|") is encountered in an XPath, the XPathQueryResolver gives up on using indexes to resolve the query and reverts to a collection scan. This can have horrible performance consequences for a large database even if the proper indexes are in place. A suggested fix is to modify the XPathQueryResolver to perform UNION operation through an index OR operation. I filed a bug report (19024) describing this problem and attached a version of XPathQueryResolver modified to use indexes to resolve UNION operations. http://nagoya.apache.org/bugzilla/show_bug.cgi?id=19204 The fixed version of XPathQueryResolver is attached to the bug report if anyone with commit powers would care to take a look and perhaps commit it. Cool job Terry, thanks! I'm trying to review it (this is one of the scariest pieces of code in the Xindice codebase) before committing, but I'm having quite an hard time since running diff on your file just shows the whole source as changed, so I can't spot exactly where you did your changes (I understand it has to do with the new evalUnion() method...). Care to provide us a diff -u format of what you did, or even just explain us what changed? TIA,

*** XPathQueryResolver-Orig.java        Wed Apr 23 08:38:30 2003
--- XPathQueryResolver-new.java Sun Apr 20 13:40:20 2003
***************
*** 365,371 ****
                 return evalUnaryOperation(op, owner, pos);
  
              case OpCodes.OP_UNION:
!                break;
  
              case OpCodes.OP_VARIABLE:
                 break;
--- 365,371 ----
                 return evalUnaryOperation(op, owner, pos);
  
              case OpCodes.OP_UNION:
!                 return evalUnion(owner, pos);
                  
              case OpCodes.OP_VARIABLE:
                 break;
***************
*** 462,467 ****
--- 462,492 ----
           return new NamedKeys(name, attr, andKeys(ks));
        }
  
+       private Object evalUnion(String owner, int pos) throws Exception {
+          int l = Compiler.getFirstChildPos(pos);
+          int r = cmp.getNextOpPos(l);
+          Object left = evaluate(owner, l);
+          
+          if ( left instanceof NamedKeys &&
+             ((NamedKeys)left).keys != null)
+          {
+              Object right = evaluate(owner, r);
+ 
+ 
+              
+              if ( right instanceof NamedKeys &&
+                 ((NamedKeys)right).keys != null)
+              {
+                 Key[][] keys = new Key[][] { ((NamedKeys)left).keys, 
((NamedKeys)right).keys };
+                 return new NamedKeys(null, false, 
QueryEngine.orKeySets(keys));
+              }
+          }
+          // no index query of left part of union
+          // or no index query of right part of union => must do
+          /// collection scan
+          return null;
+       }
+ 
        private Object evalSetComparison(int op, String owner, int pos) throws 
Exception {
           int l = Compiler.getFirstChildPos(pos);
           int r = cmp.getNextOpPos(l);