From oak-commits-return-2192-apmail-jackrabbit-oak-commits-archive=jackrabbit.apache.org@jackrabbit.apache.org Mon Nov 12 15:30:35 2012 Return-Path: X-Original-To: apmail-jackrabbit-oak-commits-archive@minotaur.apache.org Delivered-To: apmail-jackrabbit-oak-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id E031ADA69 for ; Mon, 12 Nov 2012 15:30:35 +0000 (UTC) Received: (qmail 97410 invoked by uid 500); 12 Nov 2012 15:30:35 -0000 Delivered-To: apmail-jackrabbit-oak-commits-archive@jackrabbit.apache.org Received: (qmail 97362 invoked by uid 500); 12 Nov 2012 15:30:35 -0000 Mailing-List: contact oak-commits-help@jackrabbit.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: oak-dev@jackrabbit.apache.org Delivered-To: mailing list oak-commits@jackrabbit.apache.org Received: (qmail 97348 invoked by uid 99); 12 Nov 2012 15:30:34 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 12 Nov 2012 15:30:34 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 12 Nov 2012 15:30:33 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id AF661238897F; Mon, 12 Nov 2012 15:30:13 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1408322 - in /jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query: Query.java SessionQueryEngineImpl.java Date: Mon, 12 Nov 2012 15:30:13 -0000 To: oak-commits@jackrabbit.apache.org From: thomasm@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20121112153013.AF661238897F@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: thomasm Date: Mon Nov 12 15:30:10 2012 New Revision: 1408322 URL: http://svn.apache.org/viewvc?rev=1408322&view=rev Log: OAK-439 Query: if a result limit is set, avoid reading all rows in memory to sort Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SessionQueryEngineImpl.java Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java?rev=1408322&r1=1408321&r2=1408322&view=diff ============================================================================== --- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java (original) +++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java Mon Nov 12 15:30:10 2012 @@ -324,27 +324,32 @@ public class Query { // read and order first; skip and limit afterwards it = new RowIterator(root, Long.MAX_VALUE, 0); } - long resultCount = 0; + long readCount = 0; if (orderings != null) { // TODO "order by" is not necessary if the used index returns // rows in the same order + + // avoid overflow (both offset and limit could be Long.MAX_VALUE) + int keep = (int) (Math.min(Integer.MAX_VALUE, offset) + + Math.min(Integer.MAX_VALUE, limit)); + ArrayList list = new ArrayList(); while (it.hasNext()) { + readCount++; ResultRowImpl r = it.next(); list.add(r); + // from time to time, sort and truncate + // this should results in O(n*log(2*keep)) operations, + // which is close to the optimum O(n*log(keep)) + if (list.size() > keep * 2) { + // remove tail entries right now, to save memory + Collections.sort(list); + keepFirst(list, keep); + } } Collections.sort(list); - // if limit is set, possibly remove the tailing entries - // for list size 10, offset 2, limit 5: remove 3 - resultCount = list.size(); - // avoid overflow (both offset and limit could be Long.MAX_VALUE) - long keep = Math.min(list.size(), offset) + Math.min(list.size(), limit); - while (list.size() > keep) { - // remove tail entries right now, to save memory (don't copy) - // remove the entries starting at the end, - // to avoid n^2 performance - list.remove(list.size() - 1); - } + keepFirst(list, keep); + it = list.iterator(); // skip the head (this is more efficient than removing // if there are many entries) @@ -354,7 +359,7 @@ public class Query { size = list.size() - offset; } else if (measure) { while (it.hasNext()) { - resultCount++; + readCount++; it.next(); } } @@ -368,7 +373,7 @@ public class Query { new String[0], new PropertyValue[] { PropertyValues.newString("query"), - PropertyValues.newLong(resultCount) + PropertyValues.newLong(readCount) }, null); list.add(r); @@ -387,6 +392,20 @@ public class Query { } return it; } + + /** + * Truncate a list. + * + * @param list the list + * @param keep the maximum number of entries to keep + */ + private static void keepFirst(ArrayList list, int keep) { + while (list.size() > keep) { + // remove the entries starting at the end, + // to avoid n^2 performance + list.remove(list.size() - 1); + } + } public int compareRows(PropertyValue[] orderValues, PropertyValue[] orderValues2) { Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SessionQueryEngineImpl.java URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SessionQueryEngineImpl.java?rev=1408322&r1=1408321&r2=1408322&view=diff ============================================================================== --- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SessionQueryEngineImpl.java (original) +++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SessionQueryEngineImpl.java Mon Nov 12 15:30:10 2012 @@ -20,7 +20,6 @@ import java.text.ParseException; import java.util.List; import java.util.Map; -import org.apache.jackrabbit.oak.api.ContentSession; import org.apache.jackrabbit.oak.api.PropertyValue; import org.apache.jackrabbit.oak.api.Result; import org.apache.jackrabbit.oak.api.Root;