jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1574837 [1/2] - in /jackrabbit/oak/trunk: oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/ oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/ oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/ind...
Date Thu, 06 Mar 2014 10:26:07 GMT
Author: thomasm
Date: Thu Mar  6 10:26:06 2014
New Revision: 1574837

URL: http://svn.apache.org/r1574837
Log:
OAK-1263 Optimize oak index to support 'fast ORDER BY' queries

Added:
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedIndex.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndex.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditor.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorProvider.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexLookup.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexProvider.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStoreStrategy.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorTest.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexQueryTest.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStorageStrategyTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderByQueryTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexBaseTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexInsertBaseTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexInsertNoIndexTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexInsertOrderedPropertyTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexInsertStandardPropertyTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexQueryBaseTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexQueryNoIndexTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexQueryOrderedIndexTest.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/OrderedIndexQueryStandardIndexTest.java
Modified:
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/IndexUtils.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndex.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexEditor.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexLookup.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java
    jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java
    jackrabbit/oak/trunk/oak-run/pom.xml
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/BenchmarkRunner.java
    jackrabbit/oak/trunk/oak-run/src/main/java/org/apache/jackrabbit/oak/benchmark/util/OakIndexUtils.java

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/IndexUtils.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/IndexUtils.java?rev=1574837&r1=1574836&r2=1574837&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/IndexUtils.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/IndexUtils.java Thu Mar  6 10:26:06 2014
@@ -107,8 +107,29 @@ public class IndexUtils {
                                              boolean unique,
                                              @Nonnull String[] propertyNames,
                                              @Nullable String[] declaringNodeTypeNames) throws RepositoryException {
+
+        createIndexDefinition(indexNode, indexDefName, unique, propertyNames, declaringNodeTypeNames, PropertyIndexEditorProvider.TYPE);
+    }
+
+    /**
+     * Create a new property index definition below the given {@code indexNode} of the provided {@code propertyIndexType}.
+     * 
+     * @param indexNode
+     * @param indexDefName
+     * @param unique
+     * @param propertyNames
+     * @param declaringNodeTypeNames
+     * @param propertyIndexType
+     * @throws RepositoryException
+     */
+    public static void createIndexDefinition(@Nonnull NodeUtil indexNode, 
+                                             @Nonnull String indexDefName, 
+                                             boolean unique, 
+                                             @Nonnull String[] propertyNames, 
+                                             @Nullable String[] declaringNodeTypeNames, 
+                                             @Nonnull String propertyIndexType) throws RepositoryException {
         NodeUtil entry = indexNode.getOrAddChild(indexDefName, INDEX_DEFINITIONS_NODE_TYPE);
-        entry.setString(TYPE_PROPERTY_NAME, PropertyIndexEditorProvider.TYPE);
+        entry.setString(TYPE_PROPERTY_NAME, propertyIndexType);
         entry.setBoolean(REINDEX_PROPERTY_NAME, true);
         if (unique) {
             entry.setBoolean(UNIQUE_PROPERTY_NAME, true);

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedIndex.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedIndex.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedIndex.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedIndex.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,26 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+/**
+ * interface for shared constants around different actors: QueryIndex, IndexEditors,
+ * IndexEditorProviders, ...
+ */
+public interface OrderedIndex {
+    String TYPE = "ordered";
+}

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndex.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndex.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndex.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndex.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,35 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import static org.apache.jackrabbit.oak.plugins.index.property.OrderedIndex.TYPE;
+
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+public class OrderedPropertyIndex extends PropertyIndex {
+
+    @Override
+    public String getIndexName() {
+        return TYPE;
+    }
+
+    @Override
+    PropertyIndexLookup getLookup(NodeState root) {
+        return new OrderedPropertyIndexLookup(root);
+    }
+}

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditor.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditor.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditor.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditor.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,150 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import java.util.Collections;
+import java.util.Set;
+
+import javax.annotation.Nonnull;
+
+import org.apache.jackrabbit.oak.api.CommitFailedException;
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
+import org.apache.jackrabbit.oak.plugins.index.IndexUpdateCallback;
+import org.apache.jackrabbit.oak.plugins.index.property.strategy.IndexStoreStrategy;
+import org.apache.jackrabbit.oak.plugins.index.property.strategy.OrderedContentMirrorStoreStrategy;
+import org.apache.jackrabbit.oak.spi.commit.Editor;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.base.Strings;
+
+public class OrderedPropertyIndexEditor extends PropertyIndexEditor {
+    private static final Logger log = LoggerFactory.getLogger(OrderedPropertyIndexEditor.class);
+    private static final IndexStoreStrategy ORDERED_MIRROR = new OrderedContentMirrorStoreStrategy();
+
+    private final Set<String> propertyNames;
+
+    private boolean properlyConfigured;
+
+    public OrderedPropertyIndexEditor(NodeBuilder definition, NodeState root,
+                                      IndexUpdateCallback callback) {
+        super(definition, root, callback);
+
+        Set<String> pns = null;
+
+        PropertyState names = definition.getProperty(IndexConstants.PROPERTY_NAMES);
+        if (names != null) {
+            String value = names.getValue(Type.NAME, 0);
+            if (Strings.isNullOrEmpty(value)) {
+                log.warn("Empty value passed as propertyNames. Index not properly configured. Ignoring.");
+            } else {
+                if (names.isArray()) {
+                    log.warn("Only single value supported. '{}' only will be used.", value);
+                }
+                pns = Collections.singleton(value);
+                this.properlyConfigured = true;
+            }
+        }
+
+        this.propertyNames = pns;
+    }
+
+    OrderedPropertyIndexEditor(OrderedPropertyIndexEditor parent, String name) {
+        super(parent, name);
+        this.propertyNames = parent.getPropertyNames();
+    }
+
+    /**
+     * Same as {@link PropertyIndexEditor#getStrategy(boolean)} but ignores the boolean flag.
+     * 
+     * @return the proper index strategy
+     */
+    @Override
+    IndexStoreStrategy getStrategy(boolean unique) {
+        return ORDERED_MIRROR;
+    }
+
+    public boolean isProperlyConfigured() {
+        return properlyConfigured;
+    }
+
+    @Override
+    Set<String> getPropertyNames() {
+        return propertyNames;
+    }
+
+    @Override
+    PropertyIndexEditor getChildIndexEditor(@Nonnull PropertyIndexEditor parent, 
+                                            @Nonnull String name) {
+        return new OrderedPropertyIndexEditor(this, name);
+    }
+
+    @Override
+    public void enter(NodeState before, NodeState after) {
+        log.debug("enter() - before: {} - after: {}", before, after);
+        super.enter(before, after);
+    }
+
+    @Override
+    public void leave(NodeState before, NodeState after) throws CommitFailedException {
+        log.debug("leave() - before: {} - after: {}", before, after);
+        super.leave(before, after);
+    }
+
+    @Override
+    public void propertyAdded(PropertyState after) {
+        log.debug("propertyAdded() - after: {}", after);
+        super.propertyAdded(after);
+    }
+
+    @Override
+    public void propertyChanged(PropertyState before, PropertyState after) {
+        log.debug("propertyChanged() - before: {} - after: {}", before, after);
+        super.propertyChanged(before, after);
+    }
+
+    @Override
+    public void propertyDeleted(PropertyState before) {
+        log.debug("propertyDeleted() -  before: {}", before);
+        super.propertyDeleted(before);
+    }
+
+    @Override
+    public Editor childNodeAdded(String name, NodeState after) {
+        log.debug("childNodeAdded() - name: {} - after: {}", name, after);
+        return super.childNodeAdded(name, after);
+    }
+
+    @Override
+    public Editor childNodeChanged(String name, NodeState before, NodeState after) {
+        log.debug("childNodeChanged() - name: {} - before: {} - after: {}", new Object[] { name,
+                                                                                          before,
+                                                                                          after });
+        return super.childNodeChanged(name, before, after);
+    }
+
+    @Override
+    public Editor childNodeDeleted(String name, NodeState before) {
+        log.debug("childNodeDeleted() - name: {} - before: {}", name, before);
+        return super.childNodeDeleted(name, before);
+    }
+}

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorProvider.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorProvider.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorProvider.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorProvider.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,42 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import javax.annotation.CheckForNull;
+import javax.annotation.Nonnull;
+
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Service;
+import org.apache.jackrabbit.oak.api.CommitFailedException;
+import org.apache.jackrabbit.oak.plugins.index.IndexEditorProvider;
+import org.apache.jackrabbit.oak.plugins.index.IndexUpdateCallback;
+import org.apache.jackrabbit.oak.spi.commit.Editor;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+@Component
+@Service(IndexEditorProvider.class)
+public class OrderedPropertyIndexEditorProvider implements IndexEditorProvider, OrderedIndex {
+   
+   @Override
+   @CheckForNull
+   public Editor getIndexEditor(@Nonnull String type, @Nonnull NodeBuilder definition, @Nonnull NodeState root, @Nonnull IndexUpdateCallback callback) throws CommitFailedException {
+      Editor editor = (TYPE.equals(type)) ? new OrderedPropertyIndexEditor(definition,root,callback) : null;
+      return editor; 
+   }
+}

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexLookup.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexLookup.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexLookup.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexLookup.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,44 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import org.apache.jackrabbit.oak.plugins.index.property.strategy.IndexStoreStrategy;
+import org.apache.jackrabbit.oak.plugins.index.property.strategy.OrderedContentMirrorStoreStrategy;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+/**
+ *
+ */
+public class OrderedPropertyIndexLookup extends PropertyIndexLookup {
+
+    private static final IndexStoreStrategy STORE = new OrderedContentMirrorStoreStrategy();
+
+    public OrderedPropertyIndexLookup(NodeState root) {
+        super(root);
+    }
+
+    @Override
+    IndexStoreStrategy getStrategy(NodeState indexMeta) {
+        return STORE;
+    }
+
+    @Override
+    String getType() {
+        return OrderedIndex.TYPE;
+    }
+}

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexProvider.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexProvider.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexProvider.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexProvider.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,41 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import java.util.List;
+
+import javax.annotation.Nonnull;
+
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Service;
+import org.apache.jackrabbit.oak.spi.query.QueryIndex;
+import org.apache.jackrabbit.oak.spi.query.QueryIndexProvider;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+import com.google.common.collect.ImmutableList;
+
+@Component
+@Service(QueryIndexProvider.class)
+public class OrderedPropertyIndexProvider implements QueryIndexProvider {
+
+    @Override
+    @Nonnull
+    public List<? extends QueryIndex> getQueryIndexes(NodeState nodeState) {
+        return ImmutableList.<QueryIndex> of(new OrderedPropertyIndex());
+    }
+}

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndex.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndex.java?rev=1574837&r1=1574836&r2=1574837&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndex.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndex.java Thu Mar  6 10:26:06 2014
@@ -120,6 +120,16 @@ class PropertyIndex implements QueryInde
         return "property";
     }
 
+    /**
+     * return the proper implementation of the Lookup
+     * 
+     * @param root
+     * @return the lookup
+     */
+    PropertyIndexLookup getLookup(NodeState root) {
+        return new PropertyIndexLookup(root);
+    }
+
     @Override
     public double getCost(Filter filter, NodeState root) {
         if (filter.getFullTextConstraint() != null) {
@@ -127,7 +137,7 @@ class PropertyIndex implements QueryInde
             return Double.POSITIVE_INFINITY;
         }
 
-        PropertyIndexLookup lookup = new PropertyIndexLookup(root);
+        PropertyIndexLookup lookup = getLookup(root);
         for (PropertyRestriction pr : filter.getPropertyRestrictions()) {
             String propertyName = PathUtils.getName(pr.propertyName);
             // TODO support indexes on a path
@@ -157,7 +167,7 @@ class PropertyIndex implements QueryInde
     public Cursor query(Filter filter, NodeState root) {
         Iterable<String> paths = null;
 
-        PropertyIndexLookup lookup = new PropertyIndexLookup(root);
+        PropertyIndexLookup lookup = getLookup(root);
         int depth = 1;
         for (PropertyRestriction pr : filter.getPropertyRestrictions()) {
             String propertyName = PathUtils.getName(pr.propertyName);
@@ -202,7 +212,7 @@ class PropertyIndex implements QueryInde
     public String getPlan(Filter filter, NodeState root) {
         StringBuilder buff = new StringBuilder("property");
         StringBuilder notIndexed = new StringBuilder();
-        PropertyIndexLookup lookup = new PropertyIndexLookup(root);
+        PropertyIndexLookup lookup = getLookup(root);
         for (PropertyRestriction pr : filter.getPropertyRestrictions()) {
             String propertyName = PathUtils.getName(pr.propertyName);
             // TODO support indexes on a path

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexEditor.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexEditor.java?rev=1574837&r1=1574836&r2=1574837&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexEditor.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexEditor.java Thu Mar  6 10:26:06 2014
@@ -31,6 +31,7 @@ import static org.apache.jackrabbit.oak.
 
 import java.util.Set;
 
+import javax.annotation.Nonnull;
 import javax.jcr.PropertyType;
 
 import org.apache.jackrabbit.oak.api.CommitFailedException;
@@ -111,6 +112,8 @@ class PropertyIndexEditor implements Ind
         this.path = "/";
         this.definition = definition;
 
+        //initPropertyNames(definition);
+
         // get property names
         PropertyState names = definition.getProperty(PROPERTY_NAMES);
         if (names.count() == 1) { 
@@ -137,17 +140,26 @@ class PropertyIndexEditor implements Ind
         }
         this.updateCallback = updateCallback;
     }
-
-    private PropertyIndexEditor(PropertyIndexEditor parent, String name) {
+    
+    PropertyIndexEditor(PropertyIndexEditor parent, String name) {
         this.parent = parent;
         this.name = name;
         this.path = null;
         this.definition = parent.definition;
-        this.propertyNames = parent.propertyNames;
+        this.propertyNames = parent.getPropertyNames();
         this.typePredicate = parent.typePredicate;
         this.keysToCheckForUniqueness = parent.keysToCheckForUniqueness;
         this.updateCallback = parent.updateCallback;
     }
+    
+    /**
+     * commodity method for allowing extensions
+     * 
+     * @return the propertyNames
+     */
+    Set<String> getPropertyNames() {
+       return propertyNames;
+    }
 
     /**
      * Returns the path of this node, building it lazily when first requested.
@@ -193,7 +205,7 @@ class PropertyIndexEditor implements Ind
         return keys;
     }
 
-    private static IndexStoreStrategy getStrategy(boolean unique) {
+    IndexStoreStrategy getStrategy(boolean unique) {
         return unique ? UNIQUE : MIRROR;
     }
 
@@ -214,8 +226,8 @@ class PropertyIndexEditor implements Ind
             if (typeChanged) {
                 // possible type change, so ignore diff results and
                 // just load all matching values from both states
-                beforeKeys = getMatchingKeys(before, propertyNames);
-                afterKeys = getMatchingKeys(after, propertyNames);
+                beforeKeys = getMatchingKeys(before, getPropertyNames());
+                afterKeys = getMatchingKeys(after, getPropertyNames());
             }
             if (beforeKeys != null && !typePredicate.apply(before)) {
                 // the before state doesn't match the type, so clear its values
@@ -282,7 +294,7 @@ class PropertyIndexEditor implements Ind
     public void propertyAdded(PropertyState after) {
         String name = after.getName();
         typeChanged = typeChanged || isTypeProperty(name);
-        if (propertyNames.contains(name)) {
+        if (getPropertyNames().contains(name)) {
             afterKeys = addValueKeys(afterKeys, after);
         }
     }
@@ -291,7 +303,7 @@ class PropertyIndexEditor implements Ind
     public void propertyChanged(PropertyState before, PropertyState after) {
         String name = after.getName();
         typeChanged = typeChanged || isTypeProperty(name);
-        if (propertyNames.contains(name)) {
+        if (getPropertyNames().contains(name)) {
             beforeKeys = addValueKeys(beforeKeys, before);
             afterKeys = addValueKeys(afterKeys, after);
         }
@@ -301,25 +313,36 @@ class PropertyIndexEditor implements Ind
     public void propertyDeleted(PropertyState before) {
         String name = before.getName();
         typeChanged = typeChanged || isTypeProperty(name);
-        if (propertyNames.contains(name)) {
+        if (getPropertyNames().contains(name)) {
             beforeKeys = addValueKeys(beforeKeys, before);
         }
     }
 
+    /**
+     * Retrieve a new index editor associated with the child node to process
+     * 
+     * @param parent the index editor related to the parent node
+     * @param name the name of the child node
+     * @return an instance of the PropertyIndexEditor
+     */
+    PropertyIndexEditor getChildIndexEditor(@Nonnull PropertyIndexEditor parent, @Nonnull String name) {
+       return new PropertyIndexEditor(parent, name);
+    }
+    
     @Override
     public Editor childNodeAdded(String name, NodeState after) {
-        return new PropertyIndexEditor(this, name);
+        return getChildIndexEditor(this, name);
     }
 
     @Override
     public Editor childNodeChanged(
             String name, NodeState before, NodeState after) {
-        return new PropertyIndexEditor(this, name);
+        return getChildIndexEditor(this, name);
     }
 
     @Override
     public Editor childNodeDeleted(String name, NodeState before) {
-        return new PropertyIndexEditor(this, name);
+        return getChildIndexEditor(this, name);
     }
 
-}
+}
\ No newline at end of file

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexLookup.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexLookup.java?rev=1574837&r1=1574836&r2=1574837&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexLookup.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/PropertyIndexLookup.java Thu Mar  6 10:26:06 2014
@@ -25,7 +25,6 @@ import static org.apache.jackrabbit.oak.
 import static org.apache.jackrabbit.oak.plugins.index.property.PropertyIndexEditorProvider.TYPE;
 import static org.apache.jackrabbit.oak.plugins.index.property.PropertyIndex.encode;
 
-import java.util.Iterator;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -100,12 +99,11 @@ public class PropertyIndexLookup {
         }
 
         NodeState node = root;
-        Iterator<String> it = PathUtils.elements(path).iterator();
-        while (it.hasNext()) {
+        for (String s : PathUtils.elements(path)) {
             if (getIndexNode(node, propertyName, filter) != null) {
                 return true;
             }
-            node = node.getChildNode(it.next());
+            node = node.getChildNode(s);
         }
         return false;
     }
@@ -117,8 +115,8 @@ public class PropertyIndexLookup {
         }
         return getStrategy(indexMeta).query(filter, propertyName, indexMeta, encode(value));
     }
-        
-    private static IndexStoreStrategy getStrategy(NodeState indexMeta) {
+
+    IndexStoreStrategy getStrategy(NodeState indexMeta) {
         if (indexMeta.getBoolean(IndexConstants.UNIQUE_PROPERTY_NAME)) {
             return UNIQUE;
         }
@@ -130,7 +128,7 @@ public class PropertyIndexLookup {
         if (indexMeta == null) {
             return Double.POSITIVE_INFINITY;
         }
-        return COST_OVERHEAD + 
+        return COST_OVERHEAD +
                 getStrategy(indexMeta).count(indexMeta, encode(value), MAX_COST);
     }
 
@@ -146,8 +144,7 @@ public class PropertyIndexLookup {
      *         node was found
      */
     @Nullable
-    private static NodeState getIndexNode(
-            NodeState node, String propertyName, Filter filter) {
+    private NodeState getIndexNode(NodeState node, String propertyName, Filter filter) {
         // keep a fallback to a matching index def that has *no* node type constraints
         // (initially, there is no fallback)
         NodeState fallback = null;
@@ -156,7 +153,7 @@ public class PropertyIndexLookup {
         for (ChildNodeEntry entry : state.getChildNodeEntries()) {
             NodeState index = entry.getNodeState();
             PropertyState type = index.getProperty(TYPE_PROPERTY_NAME);
-            if (type == null || type.isArray() || !TYPE.equals(type.getValue(Type.STRING))) {
+            if (type == null || type.isArray() || !getType().equals(type.getValue(Type.STRING))) {
                 continue;
             }
             if (contains(index.getNames(PROPERTY_NAMES), propertyName)) {
@@ -184,7 +181,16 @@ public class PropertyIndexLookup {
         }
         return fallback;
     }
-    
+
+    /**
+     * retrieve the type of the index
+     * 
+     * @return the type
+     */
+    String getType() {
+        return TYPE;
+    }
+
     private static Set<String> getSuperTypes(Filter filter) {
         if (filter != null && !filter.matchesAllTypes()) {
             return filter.getSupertypes();
@@ -192,4 +198,4 @@ public class PropertyIndexLookup {
         return null;
     }
 
-}
+}
\ No newline at end of file

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=1574837&r1=1574836&r2=1574837&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 Thu Mar  6 10:26:06 2014
@@ -24,6 +24,8 @@ import java.util.Deque;
 import java.util.Iterator;
 import java.util.Set;
 
+import javax.annotation.Nonnull;
+
 import org.apache.jackrabbit.oak.api.PropertyState;
 import org.apache.jackrabbit.oak.api.Type;
 import org.apache.jackrabbit.oak.commons.PathUtils;
@@ -49,7 +51,7 @@ import com.google.common.collect.Sets;
  * <br>
  * For example for a node that is under {@code /test/node}, the index
  * structure will be {@code /oak:index/index/test/node}:
- *
+ * 
  * <pre>
  * {@code
  * /
@@ -79,7 +81,7 @@ public class ContentMirrorStoreStrategy 
         }
     }
 
-    private static void remove(NodeBuilder index, String key, String value) {
+    private void remove(NodeBuilder index, String key, String value) {
         NodeBuilder builder = index.getChildNode(key);
         if (builder.exists()) {
             // Collect all builders along the given path
@@ -98,18 +100,13 @@ public class ContentMirrorStoreStrategy 
             }
 
             // Prune all index nodes that are no longer needed
-            for (NodeBuilder node : builders) {
-                if (node.getBoolean("match") || node.getChildNodeCount(1) > 0) {
-                    return;
-                } else if (node.exists()) {
-                    node.remove();
-                }
-            }
+            prune(index, builders);
         }
     }
 
-    private static void insert(NodeBuilder index, String key, String value) {
-        NodeBuilder builder = index.child(key);
+    private void insert(NodeBuilder index, String key, String value) {
+        // NodeBuilder builder = index.child(key);
+        NodeBuilder builder = fetchKeyNode(index, key);
         for (String name : PathUtils.elements(value)) {
             builder = builder.child(name);
         }
@@ -126,7 +123,7 @@ public class ContentMirrorStoreStrategy 
                 PathIterator it = new PathIterator(filter, indexName);
                 if (values == null) {
                     it.setPathContainsValue(true);
-                    it.enqueue(index.getChildNodeEntries().iterator());
+                    it.enqueue(getChildNodeEntries(index).iterator());
                 } else {
                     for (String p : values) {
                         NodeState property = index.getChildNode(p);
@@ -142,8 +139,14 @@ public class ContentMirrorStoreStrategy 
         };
     }
 
+    @Nonnull
+    Iterable<? extends ChildNodeEntry> getChildNodeEntries(@Nonnull
+    final NodeState index) {
+        return index.getChildNodeEntries();
+    }
+
     @Override
-    public Iterable<String> query(final Filter filter, final String indexName, 
+    public Iterable<String> query(final Filter filter, final String indexName,
             final NodeState indexMeta, final Iterable<String> values) {
         return query(filter, indexName, indexMeta, INDEX_CONTENT_NODE_NAME, values);
     }
@@ -213,18 +216,18 @@ public class ContentMirrorStoreStrategy 
          * Keep the returned path, to avoid returning duplicate entries.
          */
         private final Set<String> knownPaths = Sets.newHashSet();
-        
+
         PathIterator(Filter filter, String indexName) {
             this.filter = filter;
             this.indexName = indexName;
             parentPath = "";
             currentPath = "/";
         }
-        
+
         void enqueue(Iterator<? extends ChildNodeEntry> it) {
             nodeIterators.addLast(it);
         }
-        
+
         void setPathContainsValue(boolean pathContainsValue) {
             if (init) {
                 throw new IllegalStateException("This iterator is already initialized");
@@ -260,7 +263,7 @@ public class ContentMirrorStoreStrategy 
                 break;
             }
         }
-        
+
         private void fetchNextPossiblyDuplicate() {
             while (!nodeIterators.isEmpty()) {
                 Iterator<? extends ChildNodeEntry> iterator = nodeIterators.getLast();
@@ -287,7 +290,7 @@ public class ContentMirrorStoreStrategy 
                     if (node.getBoolean("match")) {
                         return;
                     }
-                    
+
                 } else {
                     nodeIterators.removeLast();
                     parentPath = PathUtils.getParentPath(parentPath);
@@ -310,37 +313,37 @@ public class ContentMirrorStoreStrategy 
             fetchNext();
             return result;
         }
-        
+
         @Override
         public void remove() {
             throw new UnsupportedOperationException();
         }
-        
+
     }
-    
+
     /**
      * A node visitor to recursively traverse a number of nodes.
      */
     interface NodeVisitor {
         void visit(NodeState state);
     }
-    
+
     /**
      * A node visitor that counts the number of matching nodes up to a given
      * maximum, in order to estimate the number of matches.
      */
     static class CountingNodeVisitor implements NodeVisitor {
-        
+
         /**
          * The maximum number of matching nodes to count.
          */
         final int maxCount;
-        
+
         /**
          * The current count of matching nodes.
          */
         int count;
-        
+
         /**
          * The current depth (number of parent nodes).
          */
@@ -351,7 +354,7 @@ public class ContentMirrorStoreStrategy 
          * calculate the average depth.
          */
         long depthTotal;
-        
+
         CountingNodeVisitor(int maxCount) {
             this.maxCount = maxCount;
         }
@@ -373,7 +376,7 @@ public class ContentMirrorStoreStrategy 
                 depth--;
             }
         }
-        
+
         /**
          * The number of matches (at most the maximum count).
          * 
@@ -382,7 +385,7 @@ public class ContentMirrorStoreStrategy 
         int getCount() {
             return count;
         }
-        
+
         /**
          * The number of estimated matches. This value might be higher than the
          * number of counted matches, if the maximum number of matches has been
@@ -402,7 +405,38 @@ public class ContentMirrorStoreStrategy 
             estimatedNodes = Math.min(estimatedNodes, Integer.MAX_VALUE);
             return Math.max(count, (int) estimatedNodes);
         }
-        
+
+    }
+    
+    /**
+     * fetch from the index the <i>key</i> node
+     * 
+     * @param index
+     *            the current index root
+     * @param key
+     *            the 'key' to fetch from the repo
+     * @return the node representing the key
+     */
+    NodeBuilder fetchKeyNode(@Nonnull NodeBuilder index, 
+                             @Nonnull String key) {
+        return index.child(key);
     }
 
-}
+    /**
+     * Physically prune a list of nodes from the index
+     * 
+     * @param index
+     *            the current index
+     * @param builders
+     *            list of nodes to prune
+     */
+    void prune(final NodeBuilder index, final Deque<NodeBuilder> builders) {
+        for (NodeBuilder node : builders) {
+            if (node.getBoolean("match") || node.getChildNodeCount(1) > 0) {
+                return;
+            } else if (node.exists()) {
+                node.remove();
+            }
+        }
+    }
+}
\ No newline at end of file

Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStoreStrategy.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStoreStrategy.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/OrderedContentMirrorStoreStrategy.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,273 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property.strategy;
+
+import java.util.Collections;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import org.apache.jackrabbit.oak.plugins.memory.EmptyNodeState;
+import org.apache.jackrabbit.oak.spi.state.AbstractChildNodeEntry;
+import org.apache.jackrabbit.oak.spi.state.ChildNodeEntry;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.base.Strings;
+
+/**
+ * Same as for {@link ContentMirrorStoreStrategy} but the order of the keys is kept by using the
+ * following structure
+ * 
+ * <code>
+ *  :index : {
+ *      :start : { :next = n1 },
+ *      n0 : { /content/foo/bar(match=true), :next=n3 },
+ *      n1 : { /content/foo1/bar(match=true), :next=n0 },
+ *      n2 : { /content/foo2/bar(match=true), :next= }, //this is the end of the list
+ *      n3 : { /content/foo3/bar(match=true), :next=n2 }
+ *  }
+ * </code>
+ */
+public class OrderedContentMirrorStoreStrategy extends ContentMirrorStoreStrategy {
+    private static final Logger log = LoggerFactory.getLogger(OrderedContentMirrorStoreStrategy.class);
+
+    /**
+     * the property linking to the next node
+     */
+    public static final String NEXT = ":next";
+
+    /**
+     * node that works as root of the index (start point or 0 element)
+     */
+    public static final String START = ":start";
+
+    /**
+     * a NodeState used for easy creating of an empty :start
+     */
+    public static final NodeState EMPTY_START_NODE = EmptyNodeState.EMPTY_NODE.builder()
+                                                                              .setProperty(NEXT, "")
+                                                                              .getNodeState();
+
+    @Override
+    NodeBuilder fetchKeyNode(@Nonnull NodeBuilder index, @Nonnull String key) {
+        log.debug("fetchKeyNode() - index: {} - key: {}", index, key);
+        NodeBuilder localkey = null;
+        NodeBuilder start = index.child(START);
+
+        // identifying the right place for insert
+        String n = start.getString(NEXT);
+        if (Strings.isNullOrEmpty(n)) {
+            // new/empty index
+            localkey = index.child(key);
+            localkey.setProperty(NEXT, "");
+            start.setProperty(NEXT, key);
+        } else {
+            // specific use-case where the item has to be added as first of the list
+            String nextKey = n;
+            if (key.compareTo(nextKey) < 0) {
+                localkey = index.child(key);
+                localkey.setProperty(NEXT, nextKey);
+                start.setProperty(NEXT, key);
+            } else {
+                Iterable<? extends ChildNodeEntry> children = getChildNodeEntries(index.getNodeState());
+                for (ChildNodeEntry child : children) {
+                    nextKey = child.getNodeState().getString(NEXT);
+                    if (Strings.isNullOrEmpty(nextKey)) {
+                        // we're at the last element, therefore our 'key' has to be appended
+                        index.getChildNode(child.getName()).setProperty(NEXT, key);
+                        localkey = index.child(key);
+                        localkey.setProperty(NEXT, "");
+                    } else {
+                        if (key.compareTo(nextKey) < 0) {
+                            index.getChildNode(child.getName()).setProperty(NEXT, key);
+                            localkey = index.child(key);
+                            localkey.setProperty(NEXT, nextKey);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+
+        return localkey;
+    }
+
+    @Override
+    void prune(final NodeBuilder index, final Deque<NodeBuilder> builders) {
+        for (NodeBuilder node : builders) {
+            if (node.hasProperty("match") || node.getChildNodeCount(1) > 0) {
+                return;
+            } else if (node.exists()) {
+                if (node.hasProperty(NEXT)) {
+                    // it's an index key and we have to relink the list
+                    ChildNodeEntry previous = findPrevious(index.getNodeState(),
+                                                           node.getNodeState()); // (1) find the
+                                                                                 // previous element
+                    log.debug("previous: {}", previous);
+                    String next = node.getString(NEXT); // (2) find the next element
+                    if (next == null) {
+                        next = "";
+                    }
+                    // (3) re-link the previous to the next
+                    index.getChildNode(previous.getName()).setProperty(NEXT, next); 
+                } 
+                node.remove();
+            }
+        }
+    }
+
+    @Nullable
+    ChildNodeEntry findPrevious(@Nonnull final NodeState index, @Nonnull final NodeState node) {
+        ChildNodeEntry previous = null;
+        ChildNodeEntry current = null;
+        boolean found = false;
+        Iterator<? extends ChildNodeEntry> it = getChildNodeEntries(index, true).iterator();
+
+        while (!found && it.hasNext()) {
+            current = it.next();
+            if (previous == null) {
+                // first iteration
+                previous = current;
+            } else {
+                found = node.equals(current.getNodeState());
+                if (!found) {
+                    previous = current;
+                }
+            }
+        }
+
+        return (found) ? previous : null;
+    }
+
+    @Override
+    public void update(NodeBuilder index, String path, Set<String> beforeKeys,
+                       Set<String> afterKeys) {
+        log.debug("update() - index     : {}", index);
+        log.debug("update() - path      : {}", path);
+        log.debug("update() - beforeKeys: {}", beforeKeys);
+        log.debug("update() - afterKeys : {}", afterKeys);
+        super.update(index, path, beforeKeys, afterKeys);
+    }
+
+    /**
+     * retrieve an Iterable for going through the index in the right order without the :start node
+     * 
+     * @param index the root of the index (:index)
+     * @return
+     */
+    @Override
+    @Nonnull
+    Iterable<? extends ChildNodeEntry> getChildNodeEntries(@Nonnull final NodeState index) {
+        return getChildNodeEntries(index, false);
+    }
+
+    /**
+     * Retrieve an Iterable for going through the index in the right order with potentially the
+     * :start node
+     * 
+     * @param index the root of the index (:index)
+     * @param includeStart true if :start should be included as first element
+     * @return
+     */
+    @Nonnull
+    Iterable<? extends ChildNodeEntry> getChildNodeEntries(@Nonnull final NodeState index,
+                                                           final boolean includeStart) {
+        Iterable<? extends ChildNodeEntry> cne = null;
+        final NodeState start = index.getChildNode(START);
+
+        if ((!start.exists() || Strings.isNullOrEmpty(start.getString(NEXT))) && !includeStart) {
+            // if the property is not there or is empty it means we're empty
+            cne = Collections.emptyList();
+        } else {
+            cne = new Iterable<ChildNodeEntry>() {
+                private NodeState localIndex = index;
+                private NodeState localStart = ((includeStart && !start.exists()) ? EMPTY_START_NODE
+                                                                             : start);
+                private NodeState current = localStart;
+                private boolean localIncludeStart = includeStart;
+
+                @Override
+                public Iterator<ChildNodeEntry> iterator() {
+                    return new Iterator<ChildNodeEntry>() {
+
+                        @Override
+                        public boolean hasNext() {
+                            return ((localIncludeStart && localStart.equals(current)) || (!localIncludeStart && !Strings.isNullOrEmpty(current.getString(NEXT))));
+                        }
+
+                        @Override
+                        public ChildNodeEntry next() {
+                            ChildNodeEntry localCNE = null;
+                            if (localIncludeStart && localStart.equals(current)) {
+                                localCNE = new OrderedChildNodeEntry(START, current);
+                                // let's set it to false. We just included it.
+                                localIncludeStart = false; 
+                            } else {
+                                if (hasNext()) {
+                                    final String name = current.getString(NEXT);
+                                    current = localIndex.getChildNode(name);
+                                    localCNE = new OrderedChildNodeEntry(name, current);
+                                } else {
+                                    throw new NoSuchElementException();
+                                }
+                            }
+                            return localCNE;
+                        }
+
+                        @Override
+                        public void remove() {
+                            throw new UnsupportedOperationException();
+                        }
+                    };
+                }
+            };
+        }
+        return cne;
+    }
+
+    private static final class OrderedChildNodeEntry extends AbstractChildNodeEntry {
+        private final String name;
+        private final NodeState state;
+
+        public OrderedChildNodeEntry(@Nonnull
+        final String name, @Nonnull
+        final NodeState state) {
+            this.name = name;
+            this.state = state;
+        }
+
+        @Override
+        @Nonnull
+        public String getName() {
+            return name;
+        }
+
+        @Override
+        @Nonnull
+        public NodeState getNodeState() {
+            return state;
+        }
+    }
+}

Added: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorTest.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorTest.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexEditorTest.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,84 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import static org.easymock.EasyMock.createNiceMock;
+import static org.easymock.EasyMock.expect;
+import static org.easymock.EasyMock.replay;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Arrays;
+
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.junit.Test;
+
+public class OrderedPropertyIndexEditorTest {
+   
+   @Test public void isProperlyConfiguredWithPropertyNames(){
+      NodeBuilder definition = createNiceMock(NodeBuilder.class);
+      PropertyState names = createNiceMock(PropertyState.class);
+      expect(names.count()).andReturn(1);
+      expect(definition.getProperty(IndexConstants.PROPERTY_NAMES)).andReturn(names).anyTimes();
+      replay(names);
+      replay(definition);
+      
+      OrderedPropertyIndexEditor ie = new OrderedPropertyIndexEditor(definition, null, null);
+      assertFalse("With empty or missing property the index should not work.",ie.isProperlyConfigured());
+   }
+   
+   @Test public void isProperlyConfiguredSingleValuePropertyNames(){
+      NodeBuilder definition = createNiceMock(NodeBuilder.class);
+      PropertyState names = createNiceMock(PropertyState.class);
+      expect(names.count()).andReturn(1);
+      expect(names.getValue(Type.NAME,0)).andReturn("jcr:lastModified").anyTimes();
+      expect(definition.getProperty(IndexConstants.PROPERTY_NAMES)).andReturn(names).anyTimes();
+      replay(names);
+      replay(definition);
+      
+      OrderedPropertyIndexEditor ie = new OrderedPropertyIndexEditor(definition, null, null);
+      assertNotNull("With a correct property set 'propertyNames' can't be null",ie.getPropertyNames());
+      assertEquals(1,ie.getPropertyNames().size());
+      assertEquals("jcr:lastModified",ie.getPropertyNames().iterator().next());
+      assertTrue("Expecting a properly configured index",ie.isProperlyConfigured());
+   }
+   
+   @Test public void multiValueProperty(){
+      NodeBuilder definition = createNiceMock(NodeBuilder.class);
+      PropertyState names = createNiceMock(PropertyState.class);
+      expect(names.isArray()).andReturn(true).anyTimes();
+      expect(names.count()).andReturn(2).anyTimes();
+      expect(names.getValue(Type.NAME,0)).andReturn("jcr:lastModified").anyTimes();
+      expect(names.getValue(Type.NAME,1)).andReturn("foo:bar").anyTimes();
+      expect(names.getValue(Type.NAMES)).andReturn(Arrays.asList("jcr:lastModified","foo:bar")).anyTimes();
+      expect(definition.getProperty(IndexConstants.PROPERTY_NAMES)).andReturn(names).anyTimes();
+      replay(names);
+      replay(definition);
+
+      OrderedPropertyIndexEditor ie = new OrderedPropertyIndexEditor(definition, null, null);
+      assertNotNull("With a correct property set 'propertyNames' can't be null",ie.getPropertyNames());
+      assertEquals("When multiple properties are a passed only the first one is taken", 1,ie.getPropertyNames().size());
+      assertEquals("jcr:lastModified",ie.getPropertyNames().iterator().next());
+      assertTrue("Expecting a properly configured index",ie.isProperlyConfigured());
+   }   
+}

Added: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexQueryTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexQueryTest.java?rev=1574837&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexQueryTest.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/index/property/OrderedPropertyIndexQueryTest.java Thu Mar  6 10:26:06 2014
@@ -0,0 +1,340 @@
+/*
+ * 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 org.apache.jackrabbit.oak.plugins.index.property;
+
+import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertFalse;
+import static junit.framework.Assert.assertTrue;
+import static junit.framework.Assert.fail;
+import static org.apache.jackrabbit.JcrConstants.JCR_PRIMARYTYPE;
+import static org.apache.jackrabbit.JcrConstants.NT_UNSTRUCTURED;
+
+import java.text.DecimalFormat;
+import java.text.NumberFormat;
+import java.text.ParseException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import javax.annotation.Nonnull;
+import javax.jcr.RepositoryException;
+
+import org.apache.jackrabbit.oak.Oak;
+import org.apache.jackrabbit.oak.api.CommitFailedException;
+import org.apache.jackrabbit.oak.api.ContentRepository;
+import org.apache.jackrabbit.oak.api.PropertyValue;
+import org.apache.jackrabbit.oak.api.ResultRow;
+import org.apache.jackrabbit.oak.api.Tree;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
+import org.apache.jackrabbit.oak.plugins.index.IndexUtils;
+import org.apache.jackrabbit.oak.plugins.nodetype.write.InitialContent;
+import org.apache.jackrabbit.oak.query.AbstractQueryTest;
+import org.apache.jackrabbit.oak.spi.query.PropertyValues;
+import org.apache.jackrabbit.oak.spi.security.OpenSecurityProvider;
+import org.apache.jackrabbit.oak.util.NodeUtil;
+import org.junit.Test;
+
+import com.google.common.collect.ImmutableMap;
+
+public class OrderedPropertyIndexQueryTest extends AbstractQueryTest {
+    /**
+     * the property used by the index
+     */
+    public static final String ORDERED_PROPERTY = "foo";
+
+    /**
+     * number of nodes to create for testing.
+     * 
+     * It has been found during development that in some cases the order of the nodes creation within the persistence
+     * where the actual expected order.
+     * 
+     * The higher the value the lower the chance for this to happen.
+     */
+    private static final int NUMBER_OF_NODES = 50;
+
+    /**
+     * convenience orderable object that represents a tuple of values and paths
+     * 
+     * where the values are the indexed keys from the index and the paths are the path which hold the key
+     */
+    private class ValuePathTuple implements Comparable<ValuePathTuple> {
+        private final String value;
+        private final String path;
+
+        ValuePathTuple(String value, String path) {
+            this.value = value;
+            this.path = path;
+        }
+
+        @Override
+        public int hashCode() {
+            final int prime = 31;
+            int result = 1;
+            result = prime * result + getOuterType().hashCode();
+            result = prime * result + ((path == null) ? 0 : path.hashCode());
+            result = prime * result + ((value == null) ? 0 : value.hashCode());
+            return result;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (this == obj){
+                return true;
+            }
+            if (obj == null){
+                return false;
+            }
+            if (getClass() != obj.getClass()){
+                return false;
+            }
+            ValuePathTuple other = (ValuePathTuple) obj;
+            if (!getOuterType().equals(other.getOuterType())){
+                return false;
+            }
+            if (path == null) {
+                if (other.path != null){
+                    return false;
+                }
+            } else if (!path.equals(other.path)){
+                return false;
+            }
+            if (value == null) {
+                if (other.value != null){
+                    return false;
+                }
+            } else if (!value.equals(other.value)){
+                return false;
+            }
+            return true;
+        }
+
+        @Override
+        public int compareTo(ValuePathTuple o) {
+            if (this.equals(o)){
+                return 0;
+            }
+            if (this.value.compareTo(o.value) < 0){
+                return -1;
+            }
+            if (this.value.compareTo(o.value) > 0){
+                return 1;
+            }
+            if (this.path.compareTo(o.path) < 0){
+                return -1;
+            }
+            if (this.path.compareTo(o.path) > 0){
+                return 1;
+            }
+            return 0;
+        }
+
+        private OrderedPropertyIndexQueryTest getOuterType() {
+            return OrderedPropertyIndexQueryTest.this;
+        }
+
+    }
+
+    /**
+     * testing for asserting the right comparison behaviour of the custom class
+     */
+    @Test
+    public void valuePathTupleComparison() {
+        try {
+            new ValuePathTuple("value", "path").compareTo(null);
+            fail("It should have raised a NPE");
+        } catch (NullPointerException e) {
+            // so far so good
+        }
+        assertEquals(0, (new ValuePathTuple("value", "path")).compareTo(new ValuePathTuple("value", "path")));
+        assertEquals(-1, (new ValuePathTuple("value", "path")).compareTo(new ValuePathTuple("value1", "path")));
+        assertEquals(-1, (new ValuePathTuple("value1", "path")).compareTo(new ValuePathTuple("value1", "path1")));
+        assertEquals(1, (new ValuePathTuple("value1", "path")).compareTo(new ValuePathTuple("value", "path")));
+        assertEquals(1, (new ValuePathTuple("value1", "path1")).compareTo(new ValuePathTuple("value1", "path")));
+
+        assertEquals(-1,
+            (new ValuePathTuple("value000", "/test/n1")).compareTo(new ValuePathTuple("value001", "/test/n0")));
+        assertEquals(1,
+            (new ValuePathTuple("value001", "/test/n0")).compareTo(new ValuePathTuple("value000", "/test/n1")));
+    }
+
+    @Override
+    protected ContentRepository createRepository() {
+        return new Oak().with(new InitialContent())
+            .with(new OpenSecurityProvider())
+            // .with(new PropertyIndexProvider())
+            // .with(new PropertyIndexEditorProvider())
+            .with(new OrderedPropertyIndexProvider()).with(new OrderedPropertyIndexEditorProvider())
+            .createContentRepository();
+    }
+
+    /**
+     * create a child node for the provided father
+     * 
+     * @param father
+     * @param name
+     *            the name of the node to create
+     * @param propName
+     *            the name of the property to assign
+     * @param propValue
+     *            the value of the property to assign
+     * @return
+     */
+    private static Tree child(Tree father, String name, String propName, String propValue) {
+        Tree child = father.addChild(name);
+        child.setProperty(JCR_PRIMARYTYPE, NT_UNSTRUCTURED, Type.NAME);
+        child.setProperty(propName, propValue, Type.STRING);
+        return child;
+    }
+
+    /**
+     * generate a list of values to be used as ordered set. Will return something like
+     * {@code value000, value001, value002, ...}
+     * 
+     * 
+     * @param amount
+     * @return
+     */
+    private static List<String> generateOrderedValues(int amount) {
+        if (amount > 1000){
+            throw new RuntimeException("amount cannot be greater than 100");
+        }
+        List<String> values = new ArrayList<String>(amount);
+        NumberFormat nf = new DecimalFormat("000");
+        for (int i = 0; i < amount; i++){
+            values.add(String.format("value%s", String.valueOf(nf.format(i))));
+        }
+        return values;
+    }
+
+    /**
+     * convenience method that adds a bunch of nodes in random order and return the order in which they should be
+     * presented by the OrderedIndex
+     * 
+     * @param values
+     *            the values of the property that will be indexed
+     * @param father
+     *            the father under which add the nodes
+     * @return
+     */
+    private List<ValuePathTuple> addChildNodes(final List<String> values, final Tree father) {
+        List<ValuePathTuple> nodes = new ArrayList<ValuePathTuple>();
+        Random rnd = new Random();
+        int counter = 0;
+        while (!values.isEmpty()) {
+            String v = values.remove(rnd.nextInt(values.size()));
+            Tree t = child(father, String.format("n%s", counter++), ORDERED_PROPERTY, v);
+            nodes.add(new ValuePathTuple(v, t.getPath()));
+        }
+
+        Collections.sort(nodes);
+        return nodes;
+    }
+
+    @Override
+    protected void createTestIndexNode() throws Exception {
+        Tree index = root.getTree("/");
+        IndexUtils.createIndexDefinition(new NodeUtil(index.getChild(IndexConstants.INDEX_DEFINITIONS_NAME)),
+            TEST_INDEX_NAME, false, new String[] { ORDERED_PROPERTY }, null, OrderedIndex.TYPE);
+        root.commit();
+    }
+
+    /**
+     * assert the right order of the returned resultset
+     * 
+     * @param orderedSequence
+     *            the right order in which the resultset should be returned
+     * @param resultset
+     *            the resultset
+     */
+    private void assertRightOrder(@Nonnull
+    final List<ValuePathTuple> orderedSequence, @Nonnull
+    final Iterator<? extends ResultRow> resultset) {
+        assertTrue("No results returned", resultset.hasNext());
+        int counter = 0;
+        while (resultset.hasNext() && counter < orderedSequence.size()) {
+            ResultRow row = resultset.next();
+            assertEquals(String.format("Wrong path at the element '%d'", counter), orderedSequence.get(counter).path,
+                row.getPath());
+            counter++;
+        }
+    }
+
+    /**
+     * Query the index for retrieving all the entries
+     * 
+     * @throws CommitFailedException
+     * @throws ParseException
+     * @throws RepositoryException
+     */
+    @Test
+    public void queryAllEntries() throws CommitFailedException, ParseException, RepositoryException {
+        setTravesalEnabled(false);
+
+        // index automatically created by the framework:
+        // {@code createTestIndexNode()}
+
+        Tree rTree = root.getTree("/");
+        Tree test = rTree.addChild("test");
+        List<ValuePathTuple> nodes = addChildNodes(generateOrderedValues(NUMBER_OF_NODES), test);
+        root.commit();
+
+        // querying
+        Iterator<? extends ResultRow> results;
+        results = executeQuery(String.format("SELECT * from [%s] WHERE foo IS NOT NULL", NT_UNSTRUCTURED), SQL2, null)
+            .getRows().iterator();
+        assertRightOrder(nodes, results);
+
+        setTravesalEnabled(true);
+    }
+
+    /**
+     * test the index for returning the items related to a single key
+     * 
+     * @throws CommitFailedException
+     * @throws ParseException
+     */
+    @Test
+    public void queryOneKey() throws CommitFailedException, ParseException {
+        setTravesalEnabled(false);
+
+        // index automatically created by the framework:
+        // {@code createTestIndexNode()}
+
+        Tree rTree = root.getTree("/");
+        Tree test = rTree.addChild("test");
+        List<ValuePathTuple> nodes = addChildNodes(generateOrderedValues(NUMBER_OF_NODES), test);
+        root.commit();
+
+        ValuePathTuple searchfor = nodes.get(NUMBER_OF_NODES / 2); // getting the middle of the random list of
+                                                                         // nodes.
+        Map<String, PropertyValue> filter = ImmutableMap
+            .of(ORDERED_PROPERTY, PropertyValues.newString(searchfor.value));
+        String query = "SELECT * FROM [%s] WHERE %s=$%s";
+        Iterator<? extends ResultRow> results = executeQuery(
+            String.format(query, NT_UNSTRUCTURED, ORDERED_PROPERTY, ORDERED_PROPERTY), SQL2, filter).getRows()
+            .iterator();
+        assertTrue("one element is expected", results.hasNext());
+        assertEquals("wrong path returned", searchfor.path, results.next().getPath());
+        assertFalse("there should be not any more items", results.hasNext());
+
+        setTravesalEnabled(true);
+    }
+}



Mime
View raw message