From 5a2aeb3ab59f286a6d2a5d8b7d62f4b17132b2b7 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Wed, 30 Aug 2006 02:24:36 +0000
Subject: Add core repository implementations

---
 .../repo/indexed/IndexEntryAccessCapability.java   |  40 ++
 .../carbonado/repo/indexed/IndexEntryAccessor.java |  73 ++++
 .../repo/indexed/IndexEntryGenerator.java          | 173 ++++++++
 .../carbonado/repo/indexed/IndexedCursor.java      | 183 +++++++++
 .../carbonado/repo/indexed/IndexedRepository.java  | 184 +++++++++
 .../repo/indexed/IndexedRepositoryBuilder.java     | 114 ++++++
 .../carbonado/repo/indexed/IndexedStorage.java     | 408 +++++++++++++++++++
 .../carbonado/repo/indexed/IndexesTrigger.java     | 102 +++++
 .../carbonado/repo/indexed/ManagedIndex.java       | 440 +++++++++++++++++++++
 .../carbonado/repo/indexed/StoredIndexInfo.java    |  84 ++++
 .../amazon/carbonado/repo/indexed/Unindexed.java   |  27 ++
 .../carbonado/repo/indexed/package-info.java       |  26 ++
 12 files changed, 1854 insertions(+)
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessCapability.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessor.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryGenerator.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexedCursor.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepository.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepositoryBuilder.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/IndexesTrigger.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/StoredIndexInfo.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/Unindexed.java
 create mode 100644 src/main/java/com/amazon/carbonado/repo/indexed/package-info.java

(limited to 'src/main/java/com/amazon/carbonado/repo/indexed')

diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessCapability.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessCapability.java
new file mode 100644
index 0000000..82f9d1f
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessCapability.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.capability.Capability;
+
+/**
+ * Capability for gaining low-level access to index data, which can be used for
+ * manual inspection and repair.
+ *
+ * @author Brian S O'Neill
+ */
+public interface IndexEntryAccessCapability extends Capability {
+    /**
+     * Returns index entry accessors for the known indexes of the given
+     * storable type. The array might be empty, but it is never null. The array
+     * is a copy, and so it may be safely modified.
+     */
+    <S extends Storable> IndexEntryAccessor<S>[] getIndexEntryAccessors(Class<S> storableType)
+        throws RepositoryException;
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessor.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessor.java
new file mode 100644
index 0000000..16a980d
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryAccessor.java
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.Comparator;
+
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+
+import com.amazon.carbonado.capability.IndexInfo;
+
+/**
+ * Provides low-level access to index data, which can be used for manual
+ * inspection and repair.
+ *
+ * @author Brian S O'Neill
+ */
+public interface IndexEntryAccessor<S extends Storable> extends IndexInfo {
+    /**
+     * Returns the index entry storage. Index entry properties can only be
+     * accessed via reflection.
+     */
+    Storage<?> getIndexEntryStorage();
+
+    /**
+     * Loads the master object referenced by the given index entry.
+     *
+     * @param indexEntry index entry which points to master
+     * @return master or null if missing
+     */
+    S loadMaster(Storable indexEntry) throws FetchException;
+
+    /**
+     * Sets all the properties of the given index entry, using the applicable
+     * properties of the given master.
+     *
+     * @param indexEntry index entry whose properties will be set
+     * @param master source of property values
+     */
+    void setAllProperties(Storable indexEntry, S master);
+
+    /**
+     * Returns true if the properties of the given index entry match those
+     * contained in the master, exluding any version property. This will always
+     * return true after a call to setAllProperties.
+     *
+     * @param indexEntry index entry whose properties will be tested
+     * @param master source of property values
+     */
+    boolean isConsistent(Storable indexEntry, S master);
+
+    /**
+     * Returns a comparator for ordering index entries.
+     */
+    Comparator<? extends Storable> getComparator();
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryGenerator.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryGenerator.java
new file mode 100644
index 0000000..3da1a5b
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexEntryGenerator.java
@@ -0,0 +1,173 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.Comparator;
+import java.util.Map;
+import java.util.WeakHashMap;
+import java.lang.ref.Reference;
+import java.lang.ref.SoftReference;
+
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.SupportException;
+import com.amazon.carbonado.info.StorableIndex;
+import com.amazon.carbonado.info.StorableProperty;
+import com.amazon.carbonado.synthetic.SyntheticStorableReferenceBuilder;
+
+/**
+ * IndexEntryGenerator creates new kinds of Storables suitable for indexing a
+ * master Storable.
+ *
+ * @author Brian S O'Neill
+ * @author Don Schneider
+ *
+ */
+class IndexEntryGenerator <S extends Storable> {
+
+    // cache for generators
+    private static Map<StorableIndex, Reference<IndexEntryGenerator>> cCache =
+            new WeakHashMap<StorableIndex, Reference<IndexEntryGenerator>>();
+
+
+    /**
+     * Returns a new or cached generator instance. The caching of generators is
+     * soft, so if no references remain to a given instance it may be garbage
+     * collected. A subsequent call will return a newly created instance.
+     *
+     * <p>In addition to generating an index entry storable, this class
+     * contains methods to operate on it. Care must be taken to ensure that the
+     * index entry instances are of the same type that the generator expects.
+     * Since the generator may be garbage collected freely of the generated
+     * index entry class, it is possible for index entries to be passed to a
+     * generator instance that does not understand it. For example:
+     *
+     * <pre>
+     * StorableIndex index = ...
+     * Class indexEntryClass = IndexEntryGenerator.getInstance(index).getIndexEntryClass();
+     * ...
+     * garbage collection
+     * ...
+     * Storable indexEntry = instance of indexEntryClass
+     * // Might fail because generator instance is new
+     * IndexEntryGenerator.getInstance(index).setAllProperties(indexEntry, source);
+     * </pre>
+     *
+     * The above code can be fixed by saving a local reference to the generator:
+     *
+     * <pre>
+     * StorableIndex index = ...
+     * IndexEntryGenerator generator = IndexEntryGenerator.getInstance(index);
+     * Class indexEntryClass = generator.getIndexEntryClass();
+     * ...
+     * Storable indexEntry = instance of indexEntryClass
+     * generator.setAllProperties(indexEntry, source);
+     * </pre>
+     *
+     * @throws SupportException if any non-primary key property doesn't have a
+     * public read method.
+     */
+    public static <S extends Storable> IndexEntryGenerator<S>
+            getInstance(StorableIndex<S> index) throws SupportException
+    {
+        synchronized(cCache) {
+            IndexEntryGenerator<S> generator;
+            Reference<IndexEntryGenerator> ref = cCache.get(index);
+            if (ref != null) {
+                generator = ref.get();
+                if (generator != null) {
+                    return generator;
+                }
+            }
+            generator = new IndexEntryGenerator<S>(index);
+            cCache.put(index, new SoftReference<IndexEntryGenerator>(generator));
+            return generator;
+        }
+    }
+
+    private SyntheticStorableReferenceBuilder<S> mBuilder;
+
+    /**
+     * Convenience class for gluing new "builder" style synthetics to the traditional
+     * generator style.
+     * @param index Generator style index specification
+     */
+    public IndexEntryGenerator(StorableIndex<S> index) throws SupportException {
+        // Need to try to find the base type.  This is an awkward way to do it,
+        // but we have nothing better available to us
+        Class<S> type = index.getProperty(0).getEnclosingType();
+
+        mBuilder = new SyntheticStorableReferenceBuilder<S>(type, index.isUnique());
+
+        for (int i=0; i<index.getPropertyCount();  i++) {
+            StorableProperty source = index.getProperty(i);
+            mBuilder.addKeyProperty(source.getName(), index.getPropertyDirection(i));
+        }
+        mBuilder.build();
+    }
+
+    /**
+     * Returns generated index entry class, which is abstract.
+     *
+     * @return class of index entry, which is a custom Storable
+     */
+    public Class<? extends Storable> getIndexEntryClass() {
+        return mBuilder.getStorableClass();
+    }
+
+    /**
+     * Loads the master object referenced by the given index entry.
+     *
+     * @param indexEntry index entry which points to master
+     * @return master or null if missing
+     */
+    public S loadMaster(Storable ref)  throws FetchException {
+        return mBuilder.loadMaster(ref);
+    }
+
+    /**
+     * Sets all the properties of the given index entry, using the applicable
+     * properties of the given master.
+     *
+     * @param indexEntry index entry whose properties will be set
+     * @param master source of property values
+     */
+    public void setAllProperties(Storable indexEntry, S master) {
+        mBuilder.setAllProperties(indexEntry, master);
+    }
+
+    /**
+     * Returns true if the properties of the given index entry match those
+     * contained in the master. This will always return true after a call to
+     * setAllProperties.
+     *
+     * @param indexEntry index entry whose properties will be tested
+     * @param master source of property values
+     */
+    public boolean isConsistent(Storable indexEntry, S master) {
+        return mBuilder.isConsistent(indexEntry, master);
+    }
+
+    /**
+     * Returns a comparator for ordering index entries.
+     */
+    public Comparator<? extends Storable> getComparator() {
+        return mBuilder.getComparator();
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedCursor.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedCursor.java
new file mode 100644
index 0000000..a6df5e0
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedCursor.java
@@ -0,0 +1,183 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.NoSuchElementException;
+
+import org.apache.commons.logging.LogFactory;
+
+import com.amazon.carbonado.Cursor;
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.Transaction;
+
+import com.amazon.carbonado.cursor.AbstractCursor;
+
+import com.amazon.carbonado.spi.RepairExecutor;
+
+/**
+ * Wraps another cursor which contains index entries and extracts master
+ * objects from them.
+ *
+ * @author Brian S O'Neill
+ */
+class IndexedCursor<S extends Storable> extends AbstractCursor<S> {
+    private final Cursor<? extends Storable> mCursor;
+    private final IndexedStorage<S> mStorage;
+    private final IndexEntryGenerator<S> mGenerator;
+
+    private S mNext;
+
+    IndexedCursor(Cursor<? extends Storable> indexEntryCursor,
+                  IndexedStorage<S> storage,
+                  IndexEntryGenerator<S> indexEntryGenerator) {
+        mCursor = indexEntryCursor;
+        mStorage = storage;
+        mGenerator = indexEntryGenerator;
+    }
+
+    public void close() throws FetchException {
+        mCursor.close();
+    }
+
+    public boolean hasNext() throws FetchException {
+        synchronized (mCursor) {
+            if (mNext != null) {
+                return true;
+            }
+            while (mCursor.hasNext()) {
+                final Storable indexEntry = mCursor.next();
+                S master = mGenerator.loadMaster(indexEntry);
+                if (master == null) {
+                    LogFactory.getLog(getClass()).warn
+                        ("Master is missing for index entry: " + indexEntry);
+                } else {
+                    if (mGenerator.isConsistent(indexEntry, master)) {
+                        mNext = master;
+                        return true;
+                    }
+
+                    // This index entry is stale. Repair is needed.
+
+                    // Insert a correct index entry, just to be sure.
+                    try {
+                        final IndexedRepository repo = mStorage.mRepository;
+                        final Storage<?> indexEntryStorage =
+                            repo.getIndexEntryStorageFor(mGenerator.getIndexEntryClass());
+                        Storable newIndexEntry = indexEntryStorage.prepare();
+                        mGenerator.setAllProperties(newIndexEntry, master);
+
+                        if (newIndexEntry.tryLoad()) {
+                            // Good, the correct index entry exists. We'll see
+                            // the master record eventually, so skip.
+                        } else {
+                            // We have no choice but to return the master, at
+                            // the risk of seeing it multiple times. This is
+                            // better than seeing it never.
+                            LogFactory.getLog(getClass()).warn
+                                ("Inconsistent index entry: " + indexEntry);
+                            mNext = master;
+                        }
+
+                        // Repair the stale index entry.
+                        RepairExecutor.execute(new Runnable() {
+                            public void run() {
+                                Transaction txn = repo.enterTransaction();
+                                try {
+                                    // Reload master and verify inconsistency.
+                                    S master = mGenerator.loadMaster(indexEntry);
+                                    if (mGenerator.isConsistent(indexEntry, master)) {
+                                        return;
+                                    }
+
+                                    Storable newIndexEntry = indexEntryStorage.prepare();
+                                    mGenerator.setAllProperties(newIndexEntry, master);
+
+                                    newIndexEntry.tryInsert();
+
+                                    indexEntry.tryDelete();
+                                    txn.commit();
+                                } catch (FetchException fe) {
+                                    LogFactory.getLog(IndexedCursor.class).warn
+                                        ("Unable to check if repair required for " +
+                                         "inconsistent index entry " +
+                                         indexEntry, fe);
+                                } catch (PersistException pe) {
+                                    LogFactory.getLog(IndexedCursor.class).error
+                                        ("Unable to repair inconsistent index entry " +
+                                         indexEntry, pe);
+                                } finally {
+                                    try {
+                                        txn.exit();
+                                    } catch (PersistException pe) {
+                                        LogFactory.getLog(IndexedCursor.class).error
+                                            ("Unable to repair inconsistent index entry " +
+                                             indexEntry, pe);
+                                    }
+                                }
+                            }
+                        });
+                    } catch (RepositoryException re) {
+                        LogFactory.getLog(getClass()).error
+                            ("Unable to inspect inconsistent index entry " +
+                             indexEntry, re);
+                    }
+
+                    if (mNext != null) {
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+    }
+
+    public S next() throws FetchException {
+        synchronized (mCursor) {
+            if (hasNext()) {
+                S next = mNext;
+                mNext = null;
+                return next;
+            }
+        }
+        throw new NoSuchElementException();
+    }
+
+    public int skipNext(int amount) throws FetchException {
+        synchronized (mCursor) {
+            if (mNext == null) {
+                return mCursor.skipNext(amount);
+            }
+
+            if (amount <= 0) {
+                if (amount < 0) {
+                    throw new IllegalArgumentException("Cannot skip negative amount: " + amount);
+                }
+                return 0;
+            }
+
+            mNext = null;
+            return 1 + mCursor.skipNext(amount - 1);
+        }
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepository.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepository.java
new file mode 100644
index 0000000..714e938
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepository.java
@@ -0,0 +1,184 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Map;
+import java.util.IdentityHashMap;
+
+import com.amazon.carbonado.Cursor;
+import com.amazon.carbonado.IsolationLevel;
+import com.amazon.carbonado.MalformedTypeException;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.SupportException;
+import com.amazon.carbonado.Transaction;
+
+import com.amazon.carbonado.capability.Capability;
+import com.amazon.carbonado.capability.IndexInfo;
+import com.amazon.carbonado.capability.IndexInfoCapability;
+import com.amazon.carbonado.capability.StorableInfoCapability;
+
+import com.amazon.carbonado.info.StorableIntrospector;
+
+/**
+ * Wraps another repository in order to make it support indexes. The wrapped
+ * repository must support creation of new types.
+ *
+ * @author Brian S O'Neill
+ */
+class IndexedRepository implements Repository,
+                                   IndexInfoCapability,
+                                   StorableInfoCapability,
+                                   IndexEntryAccessCapability
+{
+    private final Repository mRepository;
+    private final String mName;
+    private final Map<Class<?>, IndexedStorage<?>> mStorages;
+
+    IndexedRepository(String name, Repository repository) {
+        mRepository = repository;
+        mName = name;
+        mStorages = new IdentityHashMap<Class<?>, IndexedStorage<?>>();
+        if (repository.getCapability(IndexInfoCapability.class) == null) {
+            throw new UnsupportedOperationException
+                ("Wrapped repository doesn't support being indexed");
+        }
+    }
+
+    public String getName() {
+        return mName;
+    }
+
+    @SuppressWarnings("unchecked")
+    public <S extends Storable> Storage<S> storageFor(Class<S> type)
+        throws MalformedTypeException, SupportException, RepositoryException
+    {
+        synchronized (mStorages) {
+            IndexedStorage<S> storage = (IndexedStorage<S>) mStorages.get(type);
+            if (storage == null) {
+                Storage<S> masterStorage = mRepository.storageFor(type);
+
+                if (Unindexed.class.isAssignableFrom(type)) {
+                    // Verify no indexes.
+                    int indexCount = IndexedStorage
+                        .gatherRequiredIndexes(StorableIntrospector.examine(type)).size();
+                    if (indexCount > 0) {
+                        throw new MalformedTypeException
+                            (type, "Storable cannot have any indexes: " + type +
+                             ", " + indexCount);
+                    }
+                    return mRepository.storageFor(type);
+                }
+
+                storage = new IndexedStorage<S>(this, masterStorage);
+                mStorages.put(type, storage);
+            }
+            return storage;
+        }
+    }
+
+    public Transaction enterTransaction() {
+        return mRepository.enterTransaction();
+    }
+
+    public Transaction enterTransaction(IsolationLevel level) {
+        return mRepository.enterTransaction(level);
+    }
+
+    public Transaction enterTopTransaction(IsolationLevel level) {
+        return mRepository.enterTopTransaction(level);
+    }
+
+    public IsolationLevel getTransactionIsolationLevel() {
+        return mRepository.getTransactionIsolationLevel();
+    }
+
+    @SuppressWarnings("unchecked")
+    public <C extends Capability> C getCapability(Class<C> capabilityType) {
+        if (capabilityType.isInstance(this)) {
+            return (C) this;
+        }
+        return mRepository.getCapability(capabilityType);
+    }
+
+    public <S extends Storable> IndexInfo[] getIndexInfo(Class<S> storableType)
+        throws RepositoryException
+    {
+        return ((IndexedStorage) storageFor(storableType)).getIndexInfo();
+    }
+
+    public <S extends Storable> IndexEntryAccessor<S>[]
+        getIndexEntryAccessors(Class<S> storableType)
+        throws RepositoryException
+    {
+        return ((IndexedStorage<S>) storageFor(storableType)).getIndexEntryAccessors();
+    }
+
+    public String[] getUserStorableTypeNames() throws RepositoryException {
+        StorableInfoCapability cap = mRepository.getCapability(StorableInfoCapability.class);
+        if (cap == null) {
+            return new String[0];
+        }
+        ArrayList<String> names =
+            new ArrayList<String>(Arrays.asList(cap.getUserStorableTypeNames()));
+
+        // Exclude our own metadata types as well as indexes.
+
+        names.remove(StoredIndexInfo.class.getName());
+
+        Cursor<StoredIndexInfo> cursor =
+            mRepository.storageFor(StoredIndexInfo.class)
+            .query().fetch();
+
+        while (cursor.hasNext()) {
+            StoredIndexInfo info = cursor.next();
+            names.remove(info.getIndexName());
+        }
+
+        return names.toArray(new String[names.size()]);
+    }
+
+    public boolean isSupported(Class<Storable> type) {
+        StorableInfoCapability cap = mRepository.getCapability(StorableInfoCapability.class);
+        return (cap == null) ? null : cap.isSupported(type);
+    }
+
+    public boolean isPropertySupported(Class<Storable> type, String name) {
+        StorableInfoCapability cap = mRepository.getCapability(StorableInfoCapability.class);
+        return (cap == null) ? null : cap.isPropertySupported(type, name);
+    }
+
+    public void close() {
+        mRepository.close();
+    }
+
+    Storage<?> getIndexEntryStorageFor(Class<? extends Storable> indexEntryClass)
+        throws RepositoryException
+    {
+        return mRepository.storageFor(indexEntryClass);
+    }
+
+    Repository getWrappedRepository() {
+        return mRepository;
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepositoryBuilder.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepositoryBuilder.java
new file mode 100644
index 0000000..cfbe128
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedRepositoryBuilder.java
@@ -0,0 +1,114 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.Collection;
+
+import com.amazon.carbonado.ConfigurationException;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryBuilder;
+import com.amazon.carbonado.RepositoryException;
+
+import com.amazon.carbonado.spi.AbstractRepositoryBuilder;
+
+/**
+ * Repository builder for the indexed repository.
+ * <p>
+ * In addition to supporting the capabilities of the wrapped repository, the
+ * following extra capabilities are supported:
+ * <ul>
+ * <li>{@link com.amazon.carbonado.capability.IndexInfoCapability IndexInfoCapability}
+ * <li>{@link com.amazon.carbonado.capability.StorableInfoCapability StorableInfoCapability}
+ * <li>{@link IndexEntryAccessCapability IndexEntryAccessCapability}
+ * </ul>
+ *
+ * @author Brian S O'Neill
+ */
+public class IndexedRepositoryBuilder extends AbstractRepositoryBuilder {
+    private String mName;
+    private boolean mIsMaster = true;
+    private RepositoryBuilder mRepoBuilder;
+
+    public IndexedRepositoryBuilder() {
+    }
+
+    public Repository build(RepositoryReference rootRef) throws RepositoryException {
+        assertReady();
+
+        Repository wrapped;
+
+        boolean originalOption = mRepoBuilder.isMaster();
+        try {
+            mRepoBuilder.setMaster(mIsMaster);
+            wrapped = mRepoBuilder.build(rootRef);
+        } finally {
+            mRepoBuilder.setMaster(originalOption);
+        }
+
+        if (wrapped instanceof IndexedRepository) {
+            return wrapped;
+        }
+
+        Repository repo = new IndexedRepository(getName(), wrapped);
+        rootRef.set(repo);
+        return repo;
+    }
+
+    public String getName() {
+        String name = mName;
+        if (name == null && mRepoBuilder != null) {
+            name = mRepoBuilder.getName();
+        }
+        return name;
+    }
+
+    public void setName(String name) {
+        mName = name;
+    }
+
+    public boolean isMaster() {
+        return mIsMaster;
+    }
+
+    public void setMaster(boolean b) {
+        mIsMaster = b;
+    }
+
+    /**
+     * @return wrapped respository
+     */
+    public RepositoryBuilder getWrappedRepository() {
+        return mRepoBuilder;
+    }
+
+    /**
+     * Set the required wrapped respository, which must support the
+     * {@link com.amazon.carbonado.capability.IndexInfoCapability IndexInfoCapability}.
+     */
+    public void setWrappedRepository(RepositoryBuilder repoBuilder) {
+        mRepoBuilder = repoBuilder;
+    }
+
+    public void errorCheck(Collection<String> messages) throws ConfigurationException {
+        super.errorCheck(messages);
+        if (null == getWrappedRepository()) {
+            messages.add("wrapped repository missing");
+        }
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
new file mode 100644
index 0000000..dd8b2b5
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
@@ -0,0 +1,408 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+
+import com.amazon.carbonado.Cursor;
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.PersistNoneException;
+import com.amazon.carbonado.Query;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.SupportException;
+import com.amazon.carbonado.Transaction;
+import com.amazon.carbonado.Trigger;
+import com.amazon.carbonado.UniqueConstraintException;
+
+import com.amazon.carbonado.capability.IndexInfo;
+import com.amazon.carbonado.capability.IndexInfoCapability;
+
+import com.amazon.carbonado.filter.Filter;
+
+import com.amazon.carbonado.info.Direction;
+import com.amazon.carbonado.info.StorableInfo;
+import com.amazon.carbonado.info.StorableIntrospector;
+import com.amazon.carbonado.info.StorableIndex;
+
+import com.amazon.carbonado.cursor.MergeSortBuffer;
+
+import com.amazon.carbonado.spi.BaseQueryEngine;
+import com.amazon.carbonado.spi.BoundaryType;
+import com.amazon.carbonado.spi.RepairExecutor;
+import com.amazon.carbonado.spi.StorableIndexSet;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class IndexedStorage<S extends Storable> implements Storage<S> {
+    static <S extends Storable> StorableIndexSet<S> gatherRequiredIndexes(StorableInfo<S> info) {
+        StorableIndexSet<S> indexSet = new StorableIndexSet<S>();
+        indexSet.addIndexes(info);
+        indexSet.addAlternateKeys(info);
+        return indexSet;
+    }
+
+    final IndexedRepository mRepository;
+    final Storage<S> mMasterStorage;
+
+    private final Map<StorableIndex<S>, IndexInfo> mIndexInfoMap;
+
+    private final QueryEngine<S> mQueryEngine;
+
+    @SuppressWarnings("unchecked")
+    IndexedStorage(IndexedRepository repository, Storage<S> masterStorage)
+        throws RepositoryException
+    {
+        mRepository = repository;
+        mMasterStorage = masterStorage;
+        mIndexInfoMap = new IdentityHashMap<StorableIndex<S>, IndexInfo>();
+
+        StorableInfo<S> info = StorableIntrospector.examine(masterStorage.getStorableType());
+
+        // Determine what the set of indexes should be.
+        StorableIndexSet<S> newIndexSet = gatherRequiredIndexes(info);
+
+        // Mix in the indexes we get for free, but remove after reduce. A free
+        // index is one that the underlying storage is providing for us. We
+        // don't want to create redundant indexes.
+        IndexInfo[] infos = repository.getWrappedRepository()
+            .getCapability(IndexInfoCapability.class)
+            .getIndexInfo(masterStorage.getStorableType());
+
+        StorableIndex<S>[] freeIndexes = new StorableIndex[infos.length];
+        for (int i=0; i<infos.length; i++) {
+            try {
+                freeIndexes[i] = new StorableIndex<S>(masterStorage.getStorableType(), infos[i]);
+                newIndexSet.add(freeIndexes[i]);
+                mIndexInfoMap.put(freeIndexes[i], infos[i]);
+            } catch (IllegalArgumentException e) {
+                // Assume index is bogus, so ignore it.
+            }
+        }
+
+        newIndexSet.reduce(Direction.ASCENDING);
+
+        // Gather current indexes.
+        StorableIndexSet<S> currentIndexSet = new StorableIndexSet<S>();
+        // Gather indexes to remove.
+        StorableIndexSet<S> indexesToRemove = new StorableIndexSet<S>();
+
+        Query<StoredIndexInfo> query = repository.getWrappedRepository()
+            .storageFor(StoredIndexInfo.class)
+            // Primary key of StoredIndexInfo is an index descriptor, which
+            // starts with the storable type name. This emulates a "wildcard at
+            // the end" search.
+            .query("indexName >= ? & indexName < ?")
+            .with(getStorableType().getName() + '~')
+            .with(getStorableType().getName() + '~' + '\uffff');
+
+        for (StoredIndexInfo indexInfo : query.fetch().toList()) {
+            String name = indexInfo.getIndexName();
+            StorableIndex index;
+            try {
+                index = StorableIndex.parseNameDescriptor(name, info);
+            } catch (IllegalArgumentException e) {
+                // Remove unrecognized descriptors.
+                unregisterIndex(name);
+                continue;
+            }
+            if (index.getTypeDescriptor().equals(indexInfo.getIndexTypeDescriptor())) {
+                currentIndexSet.add(index);
+            } else {
+                indexesToRemove.add(index);
+            }
+        }
+
+        nonUniqueSearch: {
+            // If any current indexes are non-unique, then indexes are for an
+            // older version. For compatibility, don't uniquify the
+            // indexes. Otherwise, these indexes would need to be rebuilt.
+            for (StorableIndex<S> index : currentIndexSet) {
+                if (!index.isUnique()) {
+                    break nonUniqueSearch;
+                }
+            }
+
+            // The index implementation includes all primary key properties
+            // anyhow, so adding them here allows query analyzer to see these
+            // properties. As a side-effect of uniquify, all indexes are
+            // unique, and thus have 'U' in the descriptor. Each time
+            // nonUniqueSearch is run, it will not find any non-unique indexes.
+            newIndexSet.uniquify(info);
+        }
+
+        // Remove any old indexes.
+        {
+            indexesToRemove.addAll(currentIndexSet);
+
+            // Remove "free" indexes, since they don't need to be built.
+            for (int i=0; i<freeIndexes.length; i++) {
+                newIndexSet.remove(freeIndexes[i]);
+            }
+
+            indexesToRemove.removeAll(newIndexSet);
+
+            for (StorableIndex<S> index : indexesToRemove) {
+                removeIndex(index);
+            }
+        }
+
+        currentIndexSet = newIndexSet;
+
+        // Open all the indexes.
+        List<ManagedIndex<S>> managedIndexList = new ArrayList<ManagedIndex<S>>();
+        for (StorableIndex<S> index : currentIndexSet) {
+            IndexEntryGenerator<S> builder = IndexEntryGenerator.getInstance(index);
+            Class<? extends Storable> indexEntryClass = builder.getIndexEntryClass();
+            Storage<?> indexEntryStorage = repository.getIndexEntryStorageFor(indexEntryClass);
+            ManagedIndex managedIndex = new ManagedIndex<S>(index, builder, indexEntryStorage);
+
+            registerIndex(managedIndex);
+
+            mIndexInfoMap.put(index, managedIndex);
+            managedIndexList.add(managedIndex);
+        }
+
+        if (managedIndexList.size() > 0) {
+            // Add trigger to keep indexes up-to-date.
+            ManagedIndex<S>[] managedIndexes =
+                managedIndexList.toArray(new ManagedIndex[managedIndexList.size()]);
+
+            if (!addTrigger(new IndexesTrigger<S>(managedIndexes))) {
+                throw new RepositoryException("Unable to add trigger for managing indexes");
+            }
+        }
+
+        // Add "free" indexes back, in order for query engine to consider them.
+        for (int i=0; i<freeIndexes.length; i++) {
+            currentIndexSet.add(freeIndexes[i]);
+        }
+
+        mQueryEngine = new QueryEngine<S>(info, repository, this, currentIndexSet);
+    }
+
+    public Class<S> getStorableType() {
+        return mMasterStorage.getStorableType();
+    }
+
+    public S prepare() {
+        return mMasterStorage.prepare();
+    }
+
+    public Query<S> query() throws FetchException {
+        return mQueryEngine.getCompiledQuery();
+    }
+
+    public Query<S> query(String filter) throws FetchException {
+        return mQueryEngine.getCompiledQuery(filter);
+    }
+
+    public Query<S> query(Filter<S> filter) throws FetchException {
+        return mQueryEngine.getCompiledQuery(filter);
+    }
+
+    public boolean addTrigger(Trigger<? super S> trigger) {
+        return mMasterStorage.addTrigger(trigger);
+    }
+
+    public boolean removeTrigger(Trigger<? super S> trigger) {
+        return mMasterStorage.removeTrigger(trigger);
+    }
+
+    public IndexInfo[] getIndexInfo() {
+        IndexInfo[] infos = new IndexInfo[mIndexInfoMap.size()];
+        return mIndexInfoMap.values().toArray(infos);
+    }
+
+    @SuppressWarnings("unchecked")
+    public IndexEntryAccessor<S>[] getIndexEntryAccessors() {
+        List<IndexEntryAccessor<S>> accessors =
+            new ArrayList<IndexEntryAccessor<S>>(mIndexInfoMap.size());
+        for (IndexInfo info : mIndexInfoMap.values()) {
+            if (info instanceof IndexEntryAccessor) {
+                accessors.add((IndexEntryAccessor<S>) info);
+            }
+        }
+        return accessors.toArray(new IndexEntryAccessor[accessors.size()]);
+    }
+
+    Storage<S> getStorageFor(StorableIndex<S> index) {
+        if (mIndexInfoMap.get(index) instanceof ManagedIndex) {
+            // Index is managed by this storage, which is typical.
+            return this;
+        }
+        // Index is managed by master storage, most likely a primary key index.
+        return mMasterStorage;
+    }
+
+    ManagedIndex<S> getManagedIndex(StorableIndex<S> index) {
+        return (ManagedIndex<S>) mIndexInfoMap.get(index);
+    }
+
+    private void registerIndex(ManagedIndex<S> managedIndex)
+        throws RepositoryException
+    {
+        StorableIndex index = managedIndex.getIndex();
+
+        if (StoredIndexInfo.class.isAssignableFrom(getStorableType())) {
+            throw new IllegalStateException("StoredIndexInfo cannot have indexes");
+        }
+        StoredIndexInfo info = mRepository.getWrappedRepository()
+            .storageFor(StoredIndexInfo.class).prepare();
+        info.setIndexName(index.getNameDescriptor());
+
+        if (info.tryLoad()) {
+            // Index already exists and is registered.
+            return;
+        }
+
+        // New index, so populate it.
+        managedIndex.populateIndex(mRepository, mMasterStorage);
+
+        Transaction txn = mRepository.getWrappedRepository().enterTransaction();
+        try {
+            if (!info.tryLoad()) {
+                info.setIndexTypeDescriptor(index.getTypeDescriptor());
+                info.setCreationTimestamp(System.currentTimeMillis());
+                info.setVersionNumber(0);
+                info.insert();
+                txn.commit();
+            }
+        } finally {
+            txn.exit();
+        }
+    }
+
+    private void unregisterIndex(StorableIndex index) throws RepositoryException {
+        if (StoredIndexInfo.class.isAssignableFrom(getStorableType())) {
+            // Can't unregister when register wasn't allowed.
+            return;
+        }
+        unregisterIndex(index.getNameDescriptor());
+    }
+
+    private void unregisterIndex(String indexName) throws RepositoryException {
+        StoredIndexInfo info = mRepository.getWrappedRepository()
+            .storageFor(StoredIndexInfo.class).prepare();
+        info.setIndexName(indexName);
+        info.delete();
+    }
+
+    @SuppressWarnings("unchecked")
+    private void removeIndex(StorableIndex index) throws RepositoryException {
+        Log log = LogFactory.getLog(IndexedStorage.class);
+        if (log.isInfoEnabled()) {
+            StringBuilder b = new StringBuilder();
+            b.append("Removing index on ");
+            b.append(getStorableType().getName());
+            b.append(": ");
+            try {
+                index.appendTo(b);
+            } catch (java.io.IOException e) {
+                // Not gonna happen.
+            }
+            log.info(b.toString());
+        }
+
+        Class<? extends Storable> indexEntryClass =
+            IndexEntryGenerator.getInstance(index).getIndexEntryClass();
+
+        Storage<?> indexEntryStorage;
+        try {
+            indexEntryStorage = mRepository.getIndexEntryStorageFor(indexEntryClass);
+        } catch (Exception e) {
+            // Assume it doesn't exist.
+            unregisterIndex(index);
+            return;
+        }
+
+        // Doesn't completely remove the index, but it should free up space.
+        // TODO: when truncate method exists, call that instead
+        indexEntryStorage.query().deleteAll();
+        unregisterIndex(index);
+    }
+
+    private static class QueryEngine<S extends Storable> extends BaseQueryEngine<S> {
+
+        QueryEngine(StorableInfo<S> info,
+                    Repository repo,
+                    IndexedStorage<S> storage,
+                    StorableIndexSet<S> indexSet) {
+            super(info, repo, storage, null, indexSet);
+        }
+
+        @Override
+        protected Storage<S> getStorageFor(StorableIndex<S> index) {
+            return storage().getStorageFor(index);
+        }
+
+        protected Cursor<S> openCursor(StorableIndex<S> index,
+                                       Object[] exactValues,
+                                       BoundaryType rangeStartBoundary,
+                                       Object rangeStartValue,
+                                       BoundaryType rangeEndBoundary,
+                                       Object rangeEndValue,
+                                       boolean reverseRange,
+                                       boolean reverseOrder)
+            throws FetchException
+        {
+            // Note: this code ignores the reverseRange parameter to avoid
+            // double reversal. Only the lowest storage layer should examine
+            // this parameter.
+
+            ManagedIndex<S> indexInfo = storage().getManagedIndex(index);
+            Query<?> query = indexInfo.getIndexEntryQueryFor
+                (exactValues == null ? 0 : exactValues.length,
+                 rangeStartBoundary, rangeEndBoundary, reverseOrder);
+
+            if (exactValues != null) {
+                query = query.withValues(exactValues);
+            }
+
+            if (rangeStartBoundary != BoundaryType.OPEN) {
+                query = query.with(rangeStartValue);
+            }
+            if (rangeEndBoundary != BoundaryType.OPEN) {
+                query = query.with(rangeEndValue);
+            }
+
+            Cursor<? extends Storable> indexEntryCursor = query.fetch();
+
+            return new IndexedCursor<S>
+                (indexEntryCursor, storage(), indexInfo.getIndexEntryClassBuilder());
+        }
+
+        private IndexedStorage<S> storage() {
+            return (IndexedStorage<S>) super.getStorage();
+        }
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexesTrigger.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexesTrigger.java
new file mode 100644
index 0000000..ab718e4
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexesTrigger.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Trigger;
+import com.amazon.carbonado.UniqueConstraintException;
+
+/**
+ * Handles index updates.
+ *
+ * @author Brian S O'Neill
+ */
+class IndexesTrigger<S extends Storable> extends Trigger<S> {
+    private final ManagedIndex<S>[] mManagedIndexes;
+
+    /**
+     * @param managedIndexes all the indexes that need to be updated.
+     */
+    IndexesTrigger(ManagedIndex<S>[] managedIndexes) {
+        mManagedIndexes = managedIndexes;
+    }
+
+    @Override
+    public void afterInsert(S storable, Object state) throws PersistException {
+        for (ManagedIndex<S> managed : mManagedIndexes) {
+            if (!managed.insertIndexEntry(storable)) {
+                throw new UniqueConstraintException
+                    ("Alternate key constraint: " + storable.toString() +
+                     ", " + managed);
+            }
+        }
+    }
+
+    @Override
+    public void afterTryInsert(S storable, Object state) throws PersistException {
+        for (ManagedIndex<S> managed : mManagedIndexes) {
+            if (!managed.insertIndexEntry(storable)) {
+                throw abortTry();
+            }
+        }
+    }
+
+    @Override
+    public Object beforeUpdate(S storable) throws PersistException {
+        // Return old storable for afterUpdate.
+        S copy = (S) storable.copy();
+        try {
+            if (copy.tryLoad()) {
+                return copy;
+            }
+        } catch (FetchException e) {
+            throw e.toPersistException();
+        }
+        // If this point is reached, then afterUpdate is not called because
+        // update will fail.
+        return null;
+    }
+
+    @Override
+    public void afterUpdate(S storable, Object state) throws PersistException {
+        // Cast old storable as provided by beforeUpdate.
+        S oldStorable = (S) state;
+        for (ManagedIndex<S> managed : mManagedIndexes) {
+            managed.updateIndexEntry(storable, oldStorable);
+        }
+    }
+
+    @Override
+    public Object beforeDelete(S storable) throws PersistException {
+        // Delete index entries referenced by existing storable.
+        S copy = (S) storable.copy();
+        try {
+            if (copy.tryLoad()) {
+                for (ManagedIndex<S> managed : mManagedIndexes) {
+                    managed.deleteIndexEntry(copy);
+                }
+            }
+        } catch (FetchException e) {
+            throw e.toPersistException();
+        }
+        return null;
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
new file mode 100644
index 0000000..107067c
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
@@ -0,0 +1,440 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import java.util.Comparator;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+
+import com.amazon.carbonado.Cursor;
+import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.PersistException;
+import com.amazon.carbonado.Query;
+import com.amazon.carbonado.Repository;
+import com.amazon.carbonado.RepositoryException;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Storage;
+import com.amazon.carbonado.SupportException;
+import com.amazon.carbonado.Transaction;
+import com.amazon.carbonado.UniqueConstraintException;
+
+import com.amazon.carbonado.info.Direction;
+import com.amazon.carbonado.info.StorableIndex;
+
+import com.amazon.carbonado.cursor.MergeSortBuffer;
+
+import com.amazon.carbonado.spi.RepairExecutor;
+
+import com.amazon.carbonado.qe.BoundaryType;
+
+/**
+ * Encapsulates info and operations for a single index.
+ *
+ * @author Brian S O'Neill
+ */
+class ManagedIndex<S extends Storable> implements IndexEntryAccessor<S> {
+    private static final int POPULATE_BATCH_SIZE = 256;
+
+    private final StorableIndex mIndex;
+    private final IndexEntryGenerator<S> mGenerator;
+    private final Storage<?> mIndexEntryStorage;
+
+    private final Query<?>[] mQueryCache;
+
+    ManagedIndex(StorableIndex<S> index,
+                 IndexEntryGenerator<S> generator,
+                 Storage<?> indexEntryStorage)
+        throws SupportException
+    {
+        mIndex = index;
+        mGenerator = generator;
+        mIndexEntryStorage = indexEntryStorage;
+
+        // Cache keys are encoded as follows:
+        // bits 1..0: range end boundary
+        //            0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used
+        // bits 3..2: range start boundary
+        //            0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used
+        // bit     4: 0=forward order, 1=reverse
+        // bits n..5: exact property match count
+
+        // The size of the cache is dependent on the number of possible
+        // exactly matching properties, which is the property count of the
+        // index. If the index contained a huge number of properties, say
+        // 31, the cache size would be 1024.
+
+        int cacheSize = Integer.highestOneBit(index.getPropertyCount()) << (1 + 5);
+
+        mQueryCache = new Query[cacheSize];
+    }
+
+    public String getName() {
+        return mIndex.getNameDescriptor();
+    }
+
+    public String[] getPropertyNames() {
+        int i = mIndex.getPropertyCount();
+        String[] names = new String[i];
+        while (--i >= 0) {
+            names[i] = mIndex.getProperty(i).getName();
+        }
+        return names;
+    }
+
+    public Direction[] getPropertyDirections() {
+        int i = mIndex.getPropertyCount();
+        Direction[] directions = new Direction[i];
+        while (--i >= 0) {
+            directions[i] = mIndex.getPropertyDirection(i);
+        }
+        return directions;
+    }
+
+    public boolean isUnique() {
+        return mIndex.isUnique();
+    }
+
+    public boolean isClustered() {
+        return false;
+    }
+
+    public StorableIndex getIndex() {
+        return mIndex;
+    }
+
+    // Required by IndexEntryAccessor interface.
+    public Storage<?> getIndexEntryStorage() {
+        return mIndexEntryStorage;
+    }
+
+    // Required by IndexEntryAccessor interface.
+    public S loadMaster(Storable indexEntry) throws FetchException {
+        return mGenerator.loadMaster(indexEntry);
+    }
+
+    // Required by IndexEntryAccessor interface.
+    public void setAllProperties(Storable indexEntry, S master) {
+        mGenerator.setAllProperties(indexEntry, master);
+    }
+
+    // Required by IndexEntryAccessor interface.
+    public boolean isConsistent(Storable indexEntry, S master) {
+        return mGenerator.isConsistent(indexEntry, master);
+    }
+
+    // Required by IndexEntryAccessor interface.
+    public Comparator<? extends Storable> getComparator() {
+        return mGenerator.getComparator();
+    }
+
+    public IndexEntryGenerator<S> getIndexEntryClassBuilder() {
+        return mGenerator;
+    }
+
+    public Query<?> getIndexEntryQueryFor(int exactMatchCount,
+                                          BoundaryType rangeStartBoundary,
+                                          BoundaryType rangeEndBoundary,
+                                          boolean reverse)
+        throws FetchException
+    {
+        int key = exactMatchCount << 5;
+        if (rangeEndBoundary != BoundaryType.OPEN) {
+            if (rangeEndBoundary == BoundaryType.INCLUSIVE) {
+                key |= 0x01;
+            } else {
+                key |= 0x02;
+            }
+        }
+        if (rangeStartBoundary != BoundaryType.OPEN) {
+            if (rangeStartBoundary == BoundaryType.INCLUSIVE) {
+                key |= 0x04;
+            } else {
+                key |= 0x08;
+            }
+        }
+
+        if (reverse) {
+            key |= 0x10;
+        }
+
+        Query<?> query = mQueryCache[key];
+        if (query == null) {
+            StorableIndex index = mIndex;
+
+            StringBuilder filter = new StringBuilder();
+
+            int i;
+            for (i=0; i<exactMatchCount; i++) {
+                if (i > 0) {
+                    filter.append(" & ");
+                }
+                filter.append(index.getProperty(i).getName());
+                filter.append(" = ?");
+            }
+
+            boolean addOrderBy = false;
+
+            if (rangeStartBoundary != BoundaryType.OPEN) {
+                addOrderBy = true;
+                if (filter.length() > 0) {
+                    filter.append(" & ");
+                }
+                filter.append(index.getProperty(i).getName());
+                if (rangeStartBoundary == BoundaryType.INCLUSIVE) {
+                    filter.append(" >= ?");
+                } else {
+                    filter.append(" > ?");
+                }
+            }
+
+            if (rangeEndBoundary != BoundaryType.OPEN) {
+                addOrderBy = true;
+                if (filter.length() > 0) {
+                    filter.append(" & ");
+                }
+                filter.append(index.getProperty(i).getName());
+                if (rangeEndBoundary == BoundaryType.INCLUSIVE) {
+                    filter.append(" <= ?");
+                } else {
+                    filter.append(" < ?");
+                }
+            }
+
+            if (filter.length() == 0) {
+                query = mIndexEntryStorage.query();
+            } else {
+                query = mIndexEntryStorage.query(filter.toString());
+            }
+
+            if (addOrderBy || reverse) {
+                // Enforce ordering of properties for range searches and
+                // reverse ordering to work properly. Underlying repository
+                // should have ordered index properly, so this shouldn't
+                // cause a sort.
+                // TODO: should somehow warn if a sort is triggered
+                String[] orderProperties = new String[exactMatchCount + 1];
+                for (i=0; i<orderProperties.length; i++) {
+                    Direction dir = index.getPropertyDirection(i);
+                    if (reverse) {
+                        dir = dir.reverse();
+                    }
+                    orderProperties[i] = dir.toCharacter() + index.getProperty(i).getName();
+                }
+                query = query.orderBy(orderProperties);
+            }
+
+            mQueryCache[key] = query;
+        }
+
+        return query;
+    }
+
+    public String toString() {
+        StringBuilder b = new StringBuilder();
+        b.append("IndexInfo ");
+        try {
+            mIndex.appendTo(b);
+        } catch (java.io.IOException e) {
+            // Not gonna happen.
+        }
+        return b.toString();
+    }
+
+    /** Assumes caller is in a transaction */
+    boolean deleteIndexEntry(S userStorable) throws PersistException {
+        return makeIndexEntry(userStorable).tryDelete();
+    }
+
+    /** Assumes caller is in a transaction */
+    boolean insertIndexEntry(S userStorable) throws PersistException {
+        return insertIndexEntry(userStorable, makeIndexEntry(userStorable));
+    }
+
+    /** Assumes caller is in a transaction */
+    boolean updateIndexEntry(S userStorable, S oldUserStorable) throws PersistException {
+        Storable newIndexEntry = makeIndexEntry(userStorable);
+
+        if (oldUserStorable != null) {
+            Storable oldIndexEntry = makeIndexEntry(oldUserStorable);
+            if (oldIndexEntry.equalPrimaryKeys(newIndexEntry)) {
+                // Index entry didn't change, so nothing to do. If the
+                // index entry has a version, it will lag behind the
+                // master's version until the index entry changes, at which
+                // point the version will again match the master.
+                return true;
+            }
+
+            oldIndexEntry.tryDelete();
+        }
+
+        return insertIndexEntry(userStorable, newIndexEntry);
+    }
+
+    /**
+     * Populates the entire index, repairing as it goes.
+     *
+     * @param repo used to enter transactions
+     */
+    void populateIndex(Repository repo, Storage<S> masterStorage) throws RepositoryException {
+        Cursor<S> cursor = masterStorage.query().fetch();
+        if (!cursor.hasNext()) {
+            // Nothing exists in master, so nothing to populate.
+            cursor.close();
+            return;
+        }
+
+        Log log = LogFactory.getLog(IndexedStorage.class);
+        if (log.isInfoEnabled()) {
+            StringBuilder b = new StringBuilder();
+            b.append("Populating index on ");
+            b.append(masterStorage.getStorableType().getName());
+            b.append(": ");
+            try {
+                mIndex.appendTo(b);
+            } catch (java.io.IOException e) {
+                // Not gonna happen.
+            }
+            log.info(b.toString());
+        }
+
+        // Preload and sort all index entries for improved performance.
+
+        MergeSortBuffer buffer = new MergeSortBuffer(mIndexEntryStorage);
+        Comparator c = mGenerator.getComparator();
+        buffer.prepare(c);
+
+        while (cursor.hasNext()) {
+            buffer.add(makeIndexEntry(cursor.next()));
+        }
+
+        buffer.sort();
+
+        if (isUnique()) {
+            // If index is unique, scan buffer and check for duplicates
+            // _before_ inserting index entries. If there are duplicates,
+            // fail, since unique index cannot be built.
+
+            Object last = null;
+            for (Object obj : buffer) {
+                if (last != null) {
+                    if (c.compare(last, obj) == 0) {
+                        buffer.close();
+                        throw new UniqueConstraintException
+                            ("Cannot build unique index because duplicates exist: "
+                             + this);
+                    }
+                }
+                last = obj;
+            }
+        }
+
+        Transaction txn = repo.enterTransaction();
+        try {
+            int totalInserted = 0;
+            for (Object obj : buffer) {
+                Storable indexEntry = (Storable) obj;
+                if (!indexEntry.tryInsert()) {
+                    // repair
+                    indexEntry.tryDelete();
+                    indexEntry.tryInsert();
+                }
+                totalInserted++;
+                if (totalInserted % POPULATE_BATCH_SIZE == 0) {
+                    txn.commit();
+                    txn.exit();
+                    txn = repo.enterTransaction();
+                }
+            }
+            txn.commit();
+        } finally {
+            txn.exit();
+            buffer.close();
+        }
+    }
+
+    private Storable makeIndexEntry(S userStorable) {
+        Storable indexEntry = mIndexEntryStorage.prepare();
+        mGenerator.setAllProperties(indexEntry, userStorable);
+        return indexEntry;
+    }
+
+    /** Assumes caller is in a transaction */
+    private boolean insertIndexEntry(final S userStorable, final Storable indexEntry)
+        throws PersistException
+    {
+        if (indexEntry.tryInsert()) {
+            return true;
+        }
+
+        // If index entry already exists, then index might be corrupt.
+        {
+            Storable freshEntry = mIndexEntryStorage.prepare();
+            mGenerator.setAllProperties(freshEntry, userStorable);
+            indexEntry.copyVersionProperty(freshEntry);
+            if (freshEntry.equals(indexEntry)) {
+                // Existing entry is exactly what we expect. Return false
+                // exception if alternate key constraint, since this is
+                // user error.
+                return !isUnique();
+            }
+        }
+
+        // Run the repair outside a transaction.
+
+        RepairExecutor.execute(new Runnable() {
+            public void run() {
+                try {
+                    // Blow it away entry and re-insert. Don't simply update
+                    // the entry, since record version number may prevent
+                    // update.
+
+                    // Since we may be running outside transaction now, user
+                    // storable may have changed. Reload to get latest data.
+
+                    S freshUserStorable = (S) userStorable.copy();
+                    if (!freshUserStorable.tryLoad()) {
+                        // Gone now, nothing we can do. Assume index entry
+                        // was properly deleted.
+                        return;
+                    }
+
+                    Storable freshEntry = mIndexEntryStorage.prepare();
+                    mGenerator.setAllProperties(freshEntry, freshUserStorable);
+
+                    // Blow it away entry and re-insert. Don't simply update
+                    // the entry, since record version number may prevent
+                    // update.
+                    freshEntry.tryDelete();
+                    freshEntry.tryInsert();
+                } catch (FetchException fe) {
+                    LogFactory.getLog(IndexedStorage.class).warn
+                        ("Unable to check if repair is required: " +
+                         userStorable.toStringKeyOnly(), fe);
+                } catch (PersistException pe) {
+                    LogFactory.getLog(IndexedStorage.class).error
+                        ("Unable to repair index entry for " +
+                         userStorable.toStringKeyOnly(), pe);
+                }
+            }
+        });
+
+        return true;
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/StoredIndexInfo.java b/src/main/java/com/amazon/carbonado/repo/indexed/StoredIndexInfo.java
new file mode 100644
index 0000000..915f90b
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/StoredIndexInfo.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+import com.amazon.carbonado.Nullable;
+import com.amazon.carbonado.PrimaryKey;
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.Version;
+
+import com.amazon.carbonado.layout.Unevolvable;
+
+/**
+ * Stores basic information about the indexes managed by IndexedRepository.
+ *
+ * <p>Note: This storable cannot have indexes defined, since it is used to
+ * discover information about indexes. It would create a cyclic dependency.
+ *
+ * @author Brian S O'Neill
+ */
+@PrimaryKey("indexName")
+public interface StoredIndexInfo extends Storable, Unevolvable, Unindexed {
+    /**
+     * Returns the index name, which is also a valid index name
+     * descriptor. This descriptor is defined by {@link
+     * com.amazon.carbonado.info.StorableIndex}. The name descriptor does not
+     * contain type information.
+     */
+    String getIndexName();
+
+    void setIndexName(String name);
+
+    /**
+     * Returns the types of the index properties. This descriptor is defined by
+     * {@link com.amazon.carbonado.info.StorableIndex}.
+     */
+    @Nullable
+    String getIndexTypeDescriptor();
+
+    void setIndexTypeDescriptor(String descriptor);
+
+    /**
+     * Returns the milliseconds from 1970-01-01T00:00:00Z when this record was
+     * created.
+     */
+    long getCreationTimestamp();
+
+    void setCreationTimestamp(long timestamp);
+
+    /**
+     * Record version number for this StoredIndexInfo instance. Some encoding
+     * strategies require a version number.
+     */
+    @Version
+    int getVersionNumber();
+
+    void setVersionNumber(int version);
+
+    /**
+     * Since this record cannot evolve, this property allows it to be extended
+     * without conflicting with existing records. This record cannot evolve
+     * because an evolution strategy likely depends on this interface remaining
+     * stable, avoiding a cyclic dependency.
+     */
+    @Nullable
+    byte[] getExtraData();
+
+    void setExtraData(byte[] data);
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/Unindexed.java b/src/main/java/com/amazon/carbonado/repo/indexed/Unindexed.java
new file mode 100644
index 0000000..e5a4cff
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/Unindexed.java
@@ -0,0 +1,27 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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 com.amazon.carbonado.repo.indexed;
+
+/**
+ * Marker interface for storables that are not allowed to have indexes.
+ *
+ * @author Brian S O'Neill
+ */
+public interface Unindexed {
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/package-info.java b/src/main/java/com/amazon/carbonado/repo/indexed/package-info.java
new file mode 100644
index 0000000..9f01bb9
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/package-info.java
@@ -0,0 +1,26 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.
+ *
+ * Licensed 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.
+ */
+
+/**
+ * Repository implementation that adds index support for repositories that have
+ * little or no index support. The wrapped repository must support creation of
+ * new types.
+ *
+ * @see com.amazon.carbonado.repo.indexed.IndexedRepositoryBuilder
+ */
+package com.amazon.carbonado.repo.indexed;
-- 
cgit v1.2.3