From b60ad1c1452bfbd99530deffe66bfc21c9640be9 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Mon, 21 Jan 2008 19:28:53 +0000 Subject: Move StorableIndexSet to qe package. --- .../com/amazon/carbonado/qe/StorableIndexSet.java | 542 +++++++++++++++++++++ .../carbonado/repo/indexed/IndexAnalysis.java | 3 +- .../carbonado/repo/indexed/IndexedStorage.java | 3 +- .../carbonado/repo/sleepycat/BDBStorage.java | 2 +- .../com/amazon/carbonado/spi/StorableIndexSet.java | 542 --------------------- 5 files changed, 545 insertions(+), 547 deletions(-) create mode 100644 src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java delete mode 100644 src/main/java/com/amazon/carbonado/spi/StorableIndexSet.java (limited to 'src/main/java/com/amazon') diff --git a/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java b/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java new file mode 100644 index 0000000..976d5a1 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java @@ -0,0 +1,542 @@ +/* + * 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.qe; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.ListIterator; +import java.util.Map; +import java.util.Set; +import java.util.TreeMap; +import java.util.TreeSet; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.info.Direction; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; +import com.amazon.carbonado.info.StorableInfo; +import com.amazon.carbonado.info.StorableKey; +import com.amazon.carbonado.info.StorableProperty; + +/** + * Manages a set of {@link StorableIndex} objects, intended for reducing the + * set such that the minimal amount of physical indexes need to be defined for + * a specific type of {@link Storable}. + * + * @author Brian S O'Neill + */ +public class StorableIndexSet extends TreeSet> { + + private static final long serialVersionUID = -5840661016235340456L; + + private static final Comparator> STORABLE_INDEX_COMPARATOR = + new StorableIndexComparator(); + + public StorableIndexSet() { + super(STORABLE_INDEX_COMPARATOR); + } + + /** + * Copy constructor. + */ + public StorableIndexSet(StorableIndexSet set) { + super(STORABLE_INDEX_COMPARATOR); + addAll(set); + } + + /** + * Adds all the indexes of the given storable. + * + * @throws IllegalArgumentException if info is null + */ + public void addIndexes(StorableInfo info) { + for (int i=info.getIndexCount(); --i>=0; ) { + add(info.getIndex(i)); + } + } + + /** + * Adds all the indexes of the given storable. + * + * @param defaultDirection default ordering direction to apply to each + * index property + * @throws IllegalArgumentException if any argument is null + */ + public void addIndexes(StorableInfo info, Direction defaultDirection) { + for (int i=info.getIndexCount(); --i>=0; ) { + add(info.getIndex(i).setDefaultDirection(defaultDirection)); + } + } + + /** + * Adds all of the alternate keys of the given storable as indexes by + * calling {@link #addKey addKey}. + * + * @throws IllegalArgumentException if info is null + */ + public void addAlternateKeys(StorableInfo info) { + if (info == null) { + throw new IllegalArgumentException(); + } + for (int i=info.getAlternateKeyCount(); --i>=0; ) { + addKey(info.getAlternateKey(i)); + } + } + + /** + * Adds the primary key of the given storable as indexes by calling {@link + * #addKey addKey}. This method should not be called if the primary key + * cannot be altered because persistent data is already stored against + * it. Instead, the primary key index should be added as a normal index. + * + *

After adding the primary key via this method and after reducing the + * set, call {@link #findPrimaryKeyIndex findPrimaryKeyIndex} to get the + * best index to represent the primary key. + * + * @throws IllegalArgumentException if info is null + */ + public void addPrimaryKey(StorableInfo info) { + if (info == null) { + throw new IllegalArgumentException(); + } + addKey(info.getPrimaryKey()); + } + + /** + * Adds the key as a unique index, preserving the property arrangement. + * + * @throws IllegalArgumentException if key is null + */ + @SuppressWarnings("unchecked") + public void addKey(StorableKey key) { + if (key == null) { + throw new IllegalArgumentException(); + } + add(new StorableIndex(key, Direction.UNSPECIFIED)); + } + + /** + * Reduces the size of the set by removing redundant indexes, and merges + * others together. + */ + public void reduce() { + reduce(Direction.UNSPECIFIED); + } + + /** + * Reduces the size of the set by removing redundant indexes, and merges + * others together. + * + * @param defaultDirection replace unspecified property directions with this + */ + public void reduce(Direction defaultDirection) { + List> group = new ArrayList>(); + Map, StorableIndex> mergedReplacements = + new TreeMap, StorableIndex>(STORABLE_INDEX_COMPARATOR); + + Iterator> it = iterator(); + while (it.hasNext()) { + StorableIndex candidate = it.next(); + + if (group.size() == 0 || isDifferentGroup(group.get(0), candidate)) { + group.clear(); + group.add(candidate); + continue; + } + + if (isRedundant(group, candidate, mergedReplacements)) { + it.remove(); + } else { + group.add(candidate); + } + } + + // Now replace merged indexes. + replaceEntries(mergedReplacements); + + setDefaultDirection(defaultDirection); + } + + /** + * Set the default direction for all index properties. + * + * @param defaultDirection replace unspecified property directions with this + */ + public void setDefaultDirection(Direction defaultDirection) { + // Apply default sort direction to those unspecified. + if (defaultDirection != Direction.UNSPECIFIED) { + Map, StorableIndex> replacements = null; + for (StorableIndex index : this) { + StorableIndex replacement = index.setDefaultDirection(defaultDirection); + if (replacement != index) { + if (replacements == null) { + replacements = new HashMap, StorableIndex>(); + } + replacements.put(index, replacement); + } + } + replaceEntries(replacements); + } + } + + /** + * Marks all indexes as clustered or non-clustered. + * + * @param clustered true to mark clustered; false to mark non-clustered + * @see StorableIndex#isClustered() + * @since 1.2 + */ + public void markClustered(boolean clustered) { + Map, StorableIndex> replacements = null; + for (StorableIndex index : this) { + StorableIndex replacement = index.clustered(clustered); + if (replacement != index) { + if (replacements == null) { + replacements = new HashMap, StorableIndex>(); + } + replacements.put(index, replacement); + } + } + replaceEntries(replacements); + } + + /** + * Augment non-unique indexes with primary key properties, thus making them + * unique. + * + * @throws IllegalArgumentException if info is null + */ + public void uniquify(StorableInfo info) { + if (info == null) { + throw new IllegalArgumentException(); + } + uniquify(info.getPrimaryKey()); + } + + /** + * Augment non-unique indexes with key properties, thus making them unique. + * + * @throws IllegalArgumentException if key is null + */ + public void uniquify(StorableKey key) { + if (key == null) { + throw new IllegalArgumentException(); + } + + + // Replace indexes which were are implied unique, even if they are not + // declared as such. + { + Map, StorableIndex> replacements = null; + for (StorableIndex index : this) { + if (!index.isUnique() && isUniqueImplied(index)) { + if (replacements == null) { + replacements = new HashMap, StorableIndex>(); + } + replacements.put(index, index.unique(true)); + } + } + replaceEntries(replacements); + } + + // Now augment with key properties. + { + Map, StorableIndex> replacements = null; + for (StorableIndex index : this) { + StorableIndex replacement = index.uniquify(key); + if (replacement != index) { + if (replacements == null) { + replacements = new HashMap, StorableIndex>(); + } + replacements.put(index, replacement); + } + } + replaceEntries(replacements); + } + } + + /** + * Finds the best index to represent the primary key. Should be called + * after calling reduce. As long as the primary key was added via {@link + * #addPrimaryKey addPrimaryKey}, this method should never return null. + * + * @throws IllegalArgumentException if info is null + */ + public StorableIndex findPrimaryKeyIndex(StorableInfo info) { + if (info == null) { + throw new IllegalArgumentException(); + } + return findKeyIndex(info.getPrimaryKey()); + } + + /** + * Finds the best index to represent the given key. Should be called after + * calling reduce. As long as the key was added via {@link #addKey addKey}, + * this method should never return null. + * + * @throws IllegalArgumentException if key is null + */ + public StorableIndex findKeyIndex(StorableKey key) { + if (key == null) { + throw new IllegalArgumentException(); + } + + Set> orderedProps = key.getProperties(); + + Set> keyProps = new HashSet>(); + for (OrderedProperty orderedProp : orderedProps) { + keyProps.add(orderedProp.getChainedProperty().getPrimeProperty()); + } + + search: for (StorableIndex index : this) { + if (!index.isUnique() || index.getPropertyCount() != keyProps.size()) { + continue search; + } + for (int i=index.getPropertyCount(); --i>=0; ) { + if (!keyProps.contains(index.getProperty(i))) { + continue search; + } + } + return index; + } + + return null; + } + + /** + * Return true if index is unique or fully contains the members of a unique index. + */ + private boolean isUniqueImplied(StorableIndex candidate) { + if (candidate.isUnique()) { + return true; + } + if (this.size() <= 1) { + return false; + } + + Set> candidateProps = new HashSet>(); + for (int i=candidate.getPropertyCount(); --i>=0; ) { + candidateProps.add(candidate.getProperty(i)); + } + + search: for (StorableIndex index : this) { + if (!index.isUnique()) { + continue search; + } + for (int i=index.getPropertyCount(); --i>=0; ) { + if (!candidateProps.contains(index.getProperty(i))) { + continue search; + } + } + return true; + } + + return false; + } + + private boolean isDifferentGroup(StorableIndex groupLeader, StorableIndex candidate) { + int count = candidate.getPropertyCount(); + if (count > groupLeader.getPropertyCount()) { + return true; + } + for (int i=0; i> group, StorableIndex candidate, + Map, StorableIndex> mergedReplacements) { + // All visited group members will have an equal or greater number of + // properties. This is ensured by the ordering of the set. + int count = candidate.getPropertyCount(); + + ListIterator> it = group.listIterator(); + groupScan: + while (it.hasNext()) { + StorableIndex member = it.next(); + + boolean moreQualified = false; + boolean canReverse = true; + boolean reverse = false; + + for (int i=0; i merged = + new StorableIndex(member.getProperties(), directions) + .unique(member.isUnique()); + mergedReplacements.put(member, merged); + it.set(merged); + } + + // Candidate is redundant. + return true; + } + + return false; + } + + private void replaceEntries(Map, StorableIndex> replacements) { + if (replacements != null) { + for (Map.Entry, StorableIndex> e : replacements.entrySet()) { + remove(e.getKey()); + add(e.getValue()); + } + } + } + + /** + * Orders indexes such that they are grouped by property names. Within + * those groups, indexes are ordered most qualified to least qualified. + */ + private static class StorableIndexComparator implements Comparator> { + public int compare(StorableIndex a, StorableIndex b) { + if (a == b) { + return 0; + } + + int aCount = a.getPropertyCount(); + int bCount = b.getPropertyCount(); + + int count = Math.min(aCount, bCount); + + for (int i=0; i bCount) { + return -1; + } else if (aCount < bCount) { + return 1; + } + + // Counts are the same, property names are the same. Unique indexes + // are first, followed by index with more leading directions. Favor + // ascending direction. + + for (int i=0; i extends TreeSet> { - - private static final long serialVersionUID = -5840661016235340456L; - - private static final Comparator> STORABLE_INDEX_COMPARATOR = - new StorableIndexComparator(); - - public StorableIndexSet() { - super(STORABLE_INDEX_COMPARATOR); - } - - /** - * Copy constructor. - */ - public StorableIndexSet(StorableIndexSet set) { - super(STORABLE_INDEX_COMPARATOR); - addAll(set); - } - - /** - * Adds all the indexes of the given storable. - * - * @throws IllegalArgumentException if info is null - */ - public void addIndexes(StorableInfo info) { - for (int i=info.getIndexCount(); --i>=0; ) { - add(info.getIndex(i)); - } - } - - /** - * Adds all the indexes of the given storable. - * - * @param defaultDirection default ordering direction to apply to each - * index property - * @throws IllegalArgumentException if any argument is null - */ - public void addIndexes(StorableInfo info, Direction defaultDirection) { - for (int i=info.getIndexCount(); --i>=0; ) { - add(info.getIndex(i).setDefaultDirection(defaultDirection)); - } - } - - /** - * Adds all of the alternate keys of the given storable as indexes by - * calling {@link #addKey addKey}. - * - * @throws IllegalArgumentException if info is null - */ - public void addAlternateKeys(StorableInfo info) { - if (info == null) { - throw new IllegalArgumentException(); - } - for (int i=info.getAlternateKeyCount(); --i>=0; ) { - addKey(info.getAlternateKey(i)); - } - } - - /** - * Adds the primary key of the given storable as indexes by calling {@link - * #addKey addKey}. This method should not be called if the primary key - * cannot be altered because persistent data is already stored against - * it. Instead, the primary key index should be added as a normal index. - * - *

After adding the primary key via this method and after reducing the - * set, call {@link #findPrimaryKeyIndex findPrimaryKeyIndex} to get the - * best index to represent the primary key. - * - * @throws IllegalArgumentException if info is null - */ - public void addPrimaryKey(StorableInfo info) { - if (info == null) { - throw new IllegalArgumentException(); - } - addKey(info.getPrimaryKey()); - } - - /** - * Adds the key as a unique index, preserving the property arrangement. - * - * @throws IllegalArgumentException if key is null - */ - @SuppressWarnings("unchecked") - public void addKey(StorableKey key) { - if (key == null) { - throw new IllegalArgumentException(); - } - add(new StorableIndex(key, Direction.UNSPECIFIED)); - } - - /** - * Reduces the size of the set by removing redundant indexes, and merges - * others together. - */ - public void reduce() { - reduce(Direction.UNSPECIFIED); - } - - /** - * Reduces the size of the set by removing redundant indexes, and merges - * others together. - * - * @param defaultDirection replace unspecified property directions with this - */ - public void reduce(Direction defaultDirection) { - List> group = new ArrayList>(); - Map, StorableIndex> mergedReplacements = - new TreeMap, StorableIndex>(STORABLE_INDEX_COMPARATOR); - - Iterator> it = iterator(); - while (it.hasNext()) { - StorableIndex candidate = it.next(); - - if (group.size() == 0 || isDifferentGroup(group.get(0), candidate)) { - group.clear(); - group.add(candidate); - continue; - } - - if (isRedundant(group, candidate, mergedReplacements)) { - it.remove(); - } else { - group.add(candidate); - } - } - - // Now replace merged indexes. - replaceEntries(mergedReplacements); - - setDefaultDirection(defaultDirection); - } - - /** - * Set the default direction for all index properties. - * - * @param defaultDirection replace unspecified property directions with this - */ - public void setDefaultDirection(Direction defaultDirection) { - // Apply default sort direction to those unspecified. - if (defaultDirection != Direction.UNSPECIFIED) { - Map, StorableIndex> replacements = null; - for (StorableIndex index : this) { - StorableIndex replacement = index.setDefaultDirection(defaultDirection); - if (replacement != index) { - if (replacements == null) { - replacements = new HashMap, StorableIndex>(); - } - replacements.put(index, replacement); - } - } - replaceEntries(replacements); - } - } - - /** - * Marks all indexes as clustered or non-clustered. - * - * @param clustered true to mark clustered; false to mark non-clustered - * @see StorableIndex#isClustered() - * @since 1.2 - */ - public void markClustered(boolean clustered) { - Map, StorableIndex> replacements = null; - for (StorableIndex index : this) { - StorableIndex replacement = index.clustered(clustered); - if (replacement != index) { - if (replacements == null) { - replacements = new HashMap, StorableIndex>(); - } - replacements.put(index, replacement); - } - } - replaceEntries(replacements); - } - - /** - * Augment non-unique indexes with primary key properties, thus making them - * unique. - * - * @throws IllegalArgumentException if info is null - */ - public void uniquify(StorableInfo info) { - if (info == null) { - throw new IllegalArgumentException(); - } - uniquify(info.getPrimaryKey()); - } - - /** - * Augment non-unique indexes with key properties, thus making them unique. - * - * @throws IllegalArgumentException if key is null - */ - public void uniquify(StorableKey key) { - if (key == null) { - throw new IllegalArgumentException(); - } - - - // Replace indexes which were are implied unique, even if they are not - // declared as such. - { - Map, StorableIndex> replacements = null; - for (StorableIndex index : this) { - if (!index.isUnique() && isUniqueImplied(index)) { - if (replacements == null) { - replacements = new HashMap, StorableIndex>(); - } - replacements.put(index, index.unique(true)); - } - } - replaceEntries(replacements); - } - - // Now augment with key properties. - { - Map, StorableIndex> replacements = null; - for (StorableIndex index : this) { - StorableIndex replacement = index.uniquify(key); - if (replacement != index) { - if (replacements == null) { - replacements = new HashMap, StorableIndex>(); - } - replacements.put(index, replacement); - } - } - replaceEntries(replacements); - } - } - - /** - * Finds the best index to represent the primary key. Should be called - * after calling reduce. As long as the primary key was added via {@link - * #addPrimaryKey addPrimaryKey}, this method should never return null. - * - * @throws IllegalArgumentException if info is null - */ - public StorableIndex findPrimaryKeyIndex(StorableInfo info) { - if (info == null) { - throw new IllegalArgumentException(); - } - return findKeyIndex(info.getPrimaryKey()); - } - - /** - * Finds the best index to represent the given key. Should be called after - * calling reduce. As long as the key was added via {@link #addKey addKey}, - * this method should never return null. - * - * @throws IllegalArgumentException if key is null - */ - public StorableIndex findKeyIndex(StorableKey key) { - if (key == null) { - throw new IllegalArgumentException(); - } - - Set> orderedProps = key.getProperties(); - - Set> keyProps = new HashSet>(); - for (OrderedProperty orderedProp : orderedProps) { - keyProps.add(orderedProp.getChainedProperty().getPrimeProperty()); - } - - search: for (StorableIndex index : this) { - if (!index.isUnique() || index.getPropertyCount() != keyProps.size()) { - continue search; - } - for (int i=index.getPropertyCount(); --i>=0; ) { - if (!keyProps.contains(index.getProperty(i))) { - continue search; - } - } - return index; - } - - return null; - } - - /** - * Return true if index is unique or fully contains the members of a unique index. - */ - private boolean isUniqueImplied(StorableIndex candidate) { - if (candidate.isUnique()) { - return true; - } - if (this.size() <= 1) { - return false; - } - - Set> candidateProps = new HashSet>(); - for (int i=candidate.getPropertyCount(); --i>=0; ) { - candidateProps.add(candidate.getProperty(i)); - } - - search: for (StorableIndex index : this) { - if (!index.isUnique()) { - continue search; - } - for (int i=index.getPropertyCount(); --i>=0; ) { - if (!candidateProps.contains(index.getProperty(i))) { - continue search; - } - } - return true; - } - - return false; - } - - private boolean isDifferentGroup(StorableIndex groupLeader, StorableIndex candidate) { - int count = candidate.getPropertyCount(); - if (count > groupLeader.getPropertyCount()) { - return true; - } - for (int i=0; i> group, StorableIndex candidate, - Map, StorableIndex> mergedReplacements) { - // All visited group members will have an equal or greater number of - // properties. This is ensured by the ordering of the set. - int count = candidate.getPropertyCount(); - - ListIterator> it = group.listIterator(); - groupScan: - while (it.hasNext()) { - StorableIndex member = it.next(); - - boolean moreQualified = false; - boolean canReverse = true; - boolean reverse = false; - - for (int i=0; i merged = - new StorableIndex(member.getProperties(), directions) - .unique(member.isUnique()); - mergedReplacements.put(member, merged); - it.set(merged); - } - - // Candidate is redundant. - return true; - } - - return false; - } - - private void replaceEntries(Map, StorableIndex> replacements) { - if (replacements != null) { - for (Map.Entry, StorableIndex> e : replacements.entrySet()) { - remove(e.getKey()); - add(e.getValue()); - } - } - } - - /** - * Orders indexes such that they are grouped by property names. Within - * those groups, indexes are ordered most qualified to least qualified. - */ - private static class StorableIndexComparator implements Comparator> { - public int compare(StorableIndex a, StorableIndex b) { - if (a == b) { - return 0; - } - - int aCount = a.getPropertyCount(); - int bCount = b.getPropertyCount(); - - int count = Math.min(aCount, bCount); - - for (int i=0; i bCount) { - return -1; - } else if (aCount < bCount) { - return 1; - } - - // Counts are the same, property names are the same. Unique indexes - // are first, followed by index with more leading directions. Favor - // ascending direction. - - for (int i=0; i