You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by th...@apache.org on 2014/12/09 13:35:24 UTC
svn commit: r1644039 - in
/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak:
plugins/index/counter/jmx/ plugins/index/property/strategy/ util/
Author: thomasm
Date: Tue Dec 9 12:35:23 2014
New Revision: 1644039
URL: http://svn.apache.org/r1644039
Log:
OAK-1907 Better cost estimates for traversal, property, and ordered indexes
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java?rev=1644039&r1=1644038&r2=1644039&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java Tue Dec 9 12:35:23 2014
@@ -18,7 +18,9 @@
*/
package org.apache.jackrabbit.oak.plugins.index.counter.jmx;
+import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Type;
@@ -82,6 +84,12 @@ public class NodeCounter implements Node
// node not found
return 0;
}
+ if (!max) {
+ long syncCount = ApproximateCounter.getCountSync(s);
+ if (syncCount != -1) {
+ return syncCount;
+ }
+ }
PropertyState p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
if (p != null) {
long x = p.getValue(Type.LONG);
@@ -91,7 +99,6 @@ public class NodeCounter implements Node
}
return x;
}
-
// check in the counter index (if it exists)
s = child(root,
IndexConstants.INDEX_DEFINITIONS_NAME,
@@ -107,9 +114,8 @@ public class NodeCounter implements Node
long x = 0;
if (max) {
// in the index, the resolution is lower
- x += ApproximateCounter.COUNT_RESOLUTION * 10;
+ x += ApproximateCounter.COUNT_RESOLUTION * 20;
}
-
return x;
}
p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
@@ -118,7 +124,7 @@ public class NodeCounter implements Node
long x = 0;
if (max) {
// in the index, the resolution is lower
- x += ApproximateCounter.COUNT_RESOLUTION * 10;
+ x += ApproximateCounter.COUNT_RESOLUTION * 20;
}
return x;
}
@@ -152,8 +158,14 @@ public class NodeCounter implements Node
if (!s.exists()) {
return;
}
+ ArrayList<String> names = new ArrayList<String>();
for (ChildNodeEntry c : s.getChildNodeEntries()) {
- String child = PathUtils.concat(path, c.getName());
+ names.add(c.getName());
+ }
+ Collections.sort(names);
+ for (String cn : names) {
+ s.getChildNode(cn);
+ String child = PathUtils.concat(path, cn);
collectCounts(buff, child, level - 1);
}
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java?rev=1644039&r1=1644038&r2=1644039&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java Tue Dec 9 12:35:23 2014
@@ -90,10 +90,10 @@ public class ContentMirrorStoreStrategy
}
private void remove(NodeBuilder index, String key, String value) {
- ApproximateCounter.adjustCount(index, -1);
+ ApproximateCounter.adjustCountSync(index, -1);
NodeBuilder builder = index.getChildNode(key);
if (builder.exists()) {
- ApproximateCounter.adjustCount(builder, -1);
+ ApproximateCounter.adjustCountSync(builder, -1);
// Collect all builders along the given path
Deque<NodeBuilder> builders = newArrayDeque();
builders.addFirst(builder);
@@ -115,10 +115,10 @@ public class ContentMirrorStoreStrategy
}
private void insert(NodeBuilder index, String key, String value) {
- ApproximateCounter.adjustCount(index, 1);
+ ApproximateCounter.adjustCountSync(index, 1);
// NodeBuilder builder = index.child(key);
NodeBuilder builder = fetchKeyNode(index, key);
- ApproximateCounter.adjustCount(builder, 1);
+ ApproximateCounter.adjustCountSync(builder, 1);
for (String name : PathUtils.elements(value)) {
builder = builder.child(name);
}
@@ -191,9 +191,9 @@ public class ContentMirrorStoreStrategy
}
}
if (count == 0) {
- PropertyState ap = index.getProperty(ApproximateCounter.COUNT_PROPERTY_NAME);
- if (ap != null) {
- return ap.getValue(Type.LONG);
+ long approxCount = ApproximateCounter.getCountSync(index);
+ if (approxCount != -1) {
+ return approxCount;
}
}
CountingNodeVisitor v = new CountingNodeVisitor(max);
@@ -229,14 +229,14 @@ public class ContentMirrorStoreStrategy
}
long approxMax = 0;
if (count == 0) {
- PropertyState ap = index.getProperty(ApproximateCounter.COUNT_PROPERTY_NAME);
- if (ap != null) {
+ long approxCount = ApproximateCounter.getCountSync(index);
+ if (approxCount != -1) {
for (String p : values) {
NodeState s = index.getChildNode(p);
if (s.exists()) {
- ap = s.getProperty(ApproximateCounter.COUNT_PROPERTY_NAME);
- if (ap != null) {
- approxMax += ap.getValue(Type.LONG);
+ long a = ApproximateCounter.getCountSync(s);
+ if (a != -1) {
+ approxMax += a;
}
}
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java?rev=1644039&r1=1644038&r2=1644039&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java Tue Dec 9 12:35:23 2014
@@ -58,7 +58,7 @@ public class UniqueEntryStoreStrategy im
}
private static void remove(NodeBuilder index, String key, String value) {
- ApproximateCounter.adjustCount(index, -1);
+ ApproximateCounter.adjustCountSync(index, -1);
NodeBuilder builder = index.getChildNode(key);
if (builder.exists()) {
// there could be (temporarily) multiple entries
@@ -81,7 +81,7 @@ public class UniqueEntryStoreStrategy im
}
private static void insert(NodeBuilder index, String key, String value) {
- ApproximateCounter.adjustCount(index, 1);
+ ApproximateCounter.adjustCountSync(index, 1);
NodeBuilder k = index.child(key);
ArrayList<String> list = new ArrayList<String>();
list.add(value);
@@ -157,9 +157,9 @@ public class UniqueEntryStoreStrategy im
}
}
if (count == 0) {
- PropertyState ap = index.getProperty(ApproximateCounter.COUNT_PROPERTY_NAME);
- if (ap != null) {
- return ap.getValue(Type.LONG);
+ long approxCount = ApproximateCounter.getCountSync(index);
+ if (approxCount != -1) {
+ return approxCount;
}
}
count = 1 + index.getChildNodeCount(max);
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java?rev=1644039&r1=1644038&r2=1644039&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java Tue Dec 9 12:35:23 2014
@@ -19,18 +19,21 @@
package org.apache.jackrabbit.oak.util;
import java.util.Random;
+import java.util.UUID;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Type;
import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
/**
* An approximate counter algorithm.
*/
public class ApproximateCounter {
- public static final String COUNT_PROPERTY_NAME = ":count";
+ public static final String COUNT_PROPERTY_PREFIX = ":count_";
public static final int COUNT_RESOLUTION = 100;
+ public static final int COUNT_MAX = 10000000;
private static final Random RANDOM = new Random();
@@ -97,26 +100,75 @@ public class ApproximateCounter {
}
/**
- * Adjust a counter in the given node.
+ * Adjust a counter in the given node. This is less accurate, but can be
+ * used in a multi-threaded environment, as it uses unique property names.
*
* @param builder the node builder
* @param offset the offset
*/
- public static void adjustCount(NodeBuilder builder, long offset) {
- offset = ApproximateCounter.calculateOffset(
- offset, COUNT_RESOLUTION);
+ public static void adjustCountSync(NodeBuilder builder, long offset) {
if (offset == 0) {
return;
}
- PropertyState p = builder.getProperty(COUNT_PROPERTY_NAME);
- long count = p == null ? 0 : p.getValue(Type.LONG);
- offset = ApproximateCounter.adjustOffset(count,
- offset, COUNT_RESOLUTION);
- if (offset == 0) {
+ boolean added = offset > 0;
+ for (long i = 0; i < Math.abs(offset); i++) {
+ adjustCountSync(builder, added);
+ }
+ }
+
+ public static void adjustCountSync(NodeBuilder builder, boolean added) {
+ if (RANDOM.nextInt(COUNT_RESOLUTION) != 0) {
+ return;
+ }
+ int max = getMaxCount(builder, added);
+ if (max >= COUNT_MAX) {
+ return;
+ }
+ // TODO is this the right approach? divide by count_resolution
+ int x = Math.max(COUNT_RESOLUTION, max * 2) / COUNT_RESOLUTION;
+ if (RANDOM.nextInt(x) > 0) {
return;
}
- count += offset;
- builder.setProperty(COUNT_PROPERTY_NAME, count);
+ long value = x * COUNT_RESOLUTION;
+ String propertyName = COUNT_PROPERTY_PREFIX + UUID.randomUUID();
+ builder.setProperty(propertyName, added ? value : -value);
+ }
+
+ public static int getMaxCount(NodeBuilder node, boolean added) {
+ long max = 0;
+ for (PropertyState p : node.getProperties()) {
+ if (!p.getName().startsWith(COUNT_PROPERTY_PREFIX)) {
+ continue;
+ }
+ long x = p.getValue(Type.LONG);
+ if (added == x > 0) {
+ max = Math.max(max, Math.abs(x));
+ }
+ }
+ max = Math.min(Integer.MAX_VALUE, max);
+ return (int) max;
+ }
+
+ public static long getCountSync(NodeState node) {
+ boolean hasCountProperty = false;
+ long added = 0;
+ long removed = 0;
+ for (PropertyState p : node.getProperties()) {
+ if (!p.getName().startsWith(COUNT_PROPERTY_PREFIX)) {
+ continue;
+ }
+ hasCountProperty = true;
+ long x = p.getValue(Type.LONG);
+ if (x > 0) {
+ added += x;
+ } else {
+ removed -= x;
+ }
+ }
+ if (!hasCountProperty) {
+ return -1;
+ }
+ return Math.max(added / 2, added - removed);
}
}