java/src/main/com/google/appengine/api/datastore/CompositeIndexManager.java

   1 // Copyright 2009 Google Inc. All Rights Reserved.
   2 package com.google.appengine.api.datastore;
   3
   4 import com.google.apphosting.datastore.DatastoreV3Pb;
   5 import com.google.apphosting.datastore.DatastoreV3Pb.Query.Filter;
   6 import com.google.apphosting.datastore.DatastoreV3Pb.Query.Order;
   7 import com.google.common.collect.Lists;
   8 import com.google.common.collect.Sets;
   9 import com.google.storage.onestore.v3.OnestoreEntity.Index;
  10 import com.google.storage.onestore.v3.OnestoreEntity.Index.Property;
  11 import com.google.storage.onestore.v3.OnestoreEntity.Index.Property.Direction;
  12
  13 import java.util.ArrayList;
  14 import java.util.Collection;
  15 import java.util.Collections;
  16 import java.util.Comparator;
  17 import java.util.HashMap;
  18 import java.util.List;
  19 import java.util.Map;
  20 import java.util.Set;
  21
  22 /**
  23  * Composite index management operations needed by the datastore api.
  24  *
  25  */
  26 public class CompositeIndexManager {
  27
  28   /**
  29    * The format of a datastore-index xml element when it has properties.
  30    */
  31   private static final String DATASTORE_INDEX_WITH_PROPERTIES_XML_FORMAT =
  32       "    <datastore-index kind=\"%s\" ancestor=\"%s\" source=\"%s\">\n%s"
  33     + "    </datastore-index>\n\n";
  34
  35   /**
  36    * The format of a datastore-index xml element when it does not have
  37    * properties.
  38    */
  39   private static final String DATASTORE_INDEX_NO_PROPERTIES_XML_FORMAT =
  40       "    <datastore-index kind=\"%s\" ancestor=\"%s\" source=\"%s\"/>\n\n";
  41
  42   /**
  43    * The format of a property xml element.
  44    */
  45   private static final String PROPERTY_XML_FORMAT =
  46       "        <property name=\"%s\" direction=\"%s\"/>\n";
  47
  48   /**
  49    * Apologies for the lowercase literals, but the whole point of these enums
  50    * is to represent constants in an xml document, and it's silly to have
  51    * the code literals not match the xml literals - you end up with a bunch
  52    * of case conversion just support the java naming conversion.
  53    */
  54
  55   /**
  56    * The source of an index in the index file.  These are used as literals
  57    * in an xml document that we read and write.
  58    */
  59   protected enum IndexSource { auto, manual }
  60
  61   /**
  62    * Generate an xml representation of the provided {@link Index}.
  63    *
  64    * <datastore-indexes autoGenerate="true">
  65    *     <datastore-index kind="a" ancestor="false">
  66    *         <property name="yam" direction="asc"/>
  67    *         <property name="not yam" direction="desc"/>
  68    *     </datastore-index>
  69    * </datastore-indexes>
  70    *
  71    * @param index The index for which we want an xml representation.
  72    * @param source The source of the provided index.
  73    * @return The xml representation of the provided index.
  74    */
  75   protected String generateXmlForIndex(Index index, IndexSource source) {
  76
  77     boolean isAncestor = index.isAncestor();
  78     if (index.propertySize() == 0) {
  79       return String.format(
  80           DATASTORE_INDEX_NO_PROPERTIES_XML_FORMAT,
  81           index.getEntityType(), isAncestor, source);
  82     }
  83     StringBuilder sb = new StringBuilder();
  84     for (Property prop : index.propertys()) {
  85       String dir = prop.getDirectionEnum() == Direction.ASCENDING ? "asc" : "desc";
  86       sb.append(String.format(PROPERTY_XML_FORMAT, prop.getName(), dir));
  87     }
  88     return String.format(
  89         DATASTORE_INDEX_WITH_PROPERTIES_XML_FORMAT,
  90         index.getEntityType(), isAncestor, source, sb.toString());
  91   }
  92
  93   /**
  94    * Given a {@link IndexComponentsOnlyQuery}, return the {@link Index}
  95    * needed to fulfill the query, or {@code null} if no index is needed.
  96    *
  97    * This code needs to remain in sync with its counterparts in other
  98    * languages.  If you modify this code please make sure you make the
  99    * same update in the local datastore for other languages.
 100    *
 101    * @param indexOnlyQuery The query.
 102    * @return The index that must be present in order to fulfill the query, or
 103    * {@code null} if no index is needed.
 104    */
 105   protected Index compositeIndexForQuery(final IndexComponentsOnlyQuery indexOnlyQuery) {
 106     DatastoreV3Pb.Query query = indexOnlyQuery.getQuery();
 107
 108     boolean hasKind = query.hasKind();
 109     boolean isAncestor = query.hasAncestor();
 110     List<Filter> filters = query.filters();
 111     List<Order> orders = query.orders();
 112
 113     if (filters.isEmpty() && orders.isEmpty()) {
 114       return null;
 115     }
 116
 117     List<String> eqProps = indexOnlyQuery.getPrefix();
 118     List<Property> indexProperties = getRecommendedIndexProps(indexOnlyQuery);
 119
 120     if (hasKind && !eqProps.isEmpty() &&
 121         eqProps.size() == filters.size() &&
 122         !indexOnlyQuery.hasKeyProperty() &&
 123         orders.isEmpty()) {
 124       return null;
 125     }
 126
 127     if (hasKind && !isAncestor && indexProperties.size() <= 1 &&
 128         (!indexOnlyQuery.hasKeyProperty() ||
 129             indexProperties.get(0).getDirectionEnum() == Property.Direction.ASCENDING)) {
 130       return null;
 131     }
 132
 133     Index index = new Index();
 134     index.setEntityType(query.getKind());
 135     index.setAncestor(isAncestor);
 136     index.mutablePropertys().addAll(indexProperties);
 137     return index;
 138   }
 139
 140   /**
 141    * We compare {@link Property Properties} by comparing their names.
 142    */
 143   private static final Comparator<Property> PROPERTY_NAME_COMPARATOR = new Comparator<Property>() {
 144     @Override
 145     public int compare(Property o1, Property o2) {
 146       return o1.getName().compareTo(o2.getName());
 147     }
 148   };
 149
 150   private List<Property> getRecommendedIndexProps(IndexComponentsOnlyQuery query) {
 151     List<Property> indexProps = new ArrayList<Property>();
 152
 153     indexProps.addAll(new UnorderedIndexComponent(Sets.newHashSet(query.getPrefix()))
 154         .preferredIndexProperties());
 155
 156     for (IndexComponent component : query.getPostfix()) {
 157       indexProps.addAll(component.preferredIndexProperties());
 158     }
 159
 160     return indexProps;
 161   }
 162
 163   /**
 164    * Given a {@link IndexComponentsOnlyQuery} and a collection of existing
 165    * {@link Index}s, return the minimum {@link Index} needed to fulfill
 166    * the query, or {@code null} if no index is needed.
 167    *
 168    * This code needs to remain in sync with its counterparts in other
 169    * languages.  If you modify this code please make sure you make the
 170    * same update in the local datastore for other languages.
 171    *
 172    * @param indexOnlyQuery The query.
 173    * @param indexes The existing indexes.
 174    * @return The minimum index that must be present in order to fulfill the
 175    * query, or {@code null} if no index is needed.
 176    */
 177   protected Index minimumCompositeIndexForQuery(IndexComponentsOnlyQuery indexOnlyQuery,
 178       Collection<Index> indexes) {
 179
 180     Index suggestedIndex = compositeIndexForQuery(indexOnlyQuery);
 181     if (suggestedIndex == null) {
 182       return null;
 183     }
 184
 185     class EqPropsAndAncestorConstraint {
 186       final Set<String> equalityProperties;
 187       final boolean ancestorConstraint;
 188
 189       EqPropsAndAncestorConstraint(Set<String> equalityProperties, boolean ancestorConstraint) {
 190         this.equalityProperties = equalityProperties;
 191         this.ancestorConstraint = ancestorConstraint;
 192       }
 193     }
 194
 195     Map<List<Property>, EqPropsAndAncestorConstraint> remainingMap =
 196         new HashMap<List<Property>, EqPropsAndAncestorConstraint>();
 197
 198 index_for:
 199     for (Index index : indexes) {
 200       if (
 201           !indexOnlyQuery.getQuery().getKind().equals(index.getEntityType()) ||
 202           (!indexOnlyQuery.getQuery().hasAncestor() && index.isAncestor())) {
 203         continue;
 204       }
 205
 206       int postfixSplit = index.propertySize();
 207       for (IndexComponent component : Lists.reverse(indexOnlyQuery.getPostfix())) {
 208         if (!component.matches(index.propertys().subList(
 209             Math.max(postfixSplit - component.size(), 0), postfixSplit))) {
 210           continue index_for;
 211         }
 212         postfixSplit -= component.size();
 213       }
 214
 215       Set<String> indexEqProps = Sets.newHashSetWithExpectedSize(postfixSplit);
 216       for (Property prop : index.propertys().subList(0, postfixSplit)) {
 217         if (!indexOnlyQuery.getPrefix().contains(prop.getName())) {
 218           continue index_for;
 219         }
 220         indexEqProps.add(prop.getName());
 221       }
 222
 223       List<Property> indexPostfix = index.propertys().subList(postfixSplit, index.propertySize());
 224
 225       Set<String> remainingEqProps;
 226       boolean remainingAncestor;
 227       {
 228         EqPropsAndAncestorConstraint remaining = remainingMap.get(indexPostfix);
 229         if (remaining == null) {
 230           remainingEqProps = Sets.newHashSet(indexOnlyQuery.getPrefix());
 231           remainingAncestor = indexOnlyQuery.getQuery().hasAncestor();
 232         } else {
 233           remainingEqProps = remaining.equalityProperties;
 234           remainingAncestor = remaining.ancestorConstraint;
 235         }
 236       }
 237
 238       boolean modified = remainingEqProps.removeAll(indexEqProps);
 239       if (remainingAncestor && index.isAncestor()) {
 240         modified = true;
 241         remainingAncestor = false;
 242       }
 243
 244       if (remainingEqProps.isEmpty() && !remainingAncestor) {
 245         return null;
 246       }
 247
 248       if (!modified) {
 249         continue;
 250       }
 251
 252       remainingMap.put(indexPostfix,
 253           new EqPropsAndAncestorConstraint(remainingEqProps, remainingAncestor));
 254     }
 255
 256     if (remainingMap.isEmpty()) {
 257       return suggestedIndex;
 258     }
 259
 260     int minimumCost = Integer.MAX_VALUE;
 261     List<Property> minimumPostfix = null;
 262     EqPropsAndAncestorConstraint minimumRemaining = null;
 263     for (Map.Entry<List<Property>, EqPropsAndAncestorConstraint> entry : remainingMap.entrySet()) {
 264       int cost = entry.getValue().equalityProperties.size();
 265       if (entry.getValue().ancestorConstraint) {
 266         cost += 2;
 267       }
 268       if (cost < minimumCost) {
 269         minimumCost = cost;
 270         minimumPostfix = entry.getKey();
 271         minimumRemaining = entry.getValue();
 272       }
 273     }
 274
 275     suggestedIndex.clearProperty();
 276     suggestedIndex.setAncestor(minimumRemaining.ancestorConstraint);
 277     for (String name : minimumRemaining.equalityProperties) {
 278       suggestedIndex.addProperty().setName(name).setDirection(Direction.ASCENDING);
 279     }
 280     Collections.sort(suggestedIndex.mutablePropertys(), PROPERTY_NAME_COMPARATOR);
 281
 282     suggestedIndex.mutablePropertys().addAll(minimumPostfix);
 283     return suggestedIndex;
 284   }
 285
 286   /**
 287    * Protected alias that allows us to make this class available to the local
 288    * datastore without publicly exposing it in the api.
 289    */
 290   protected static class IndexComponentsOnlyQuery
 291       extends com.google.appengine.api.datastore.IndexComponentsOnlyQuery {
 292     public IndexComponentsOnlyQuery(DatastoreV3Pb.Query query) {
 293       super(query);
 294     }
 295   }
 296
 297   /**
 298    * Protected alias that allows us to make this class available to the local
 299    * datastore without publicly exposing it in the api.
 300    */
 301   protected static class ValidatedQuery
 302       extends com.google.appengine.api.datastore.ValidatedQuery {
 303     public ValidatedQuery(DatastoreV3Pb.Query query) {
 304       super(query);
 305     }
 306   }
 307
 308   /**
 309    * Protected alias that allows us to make this class available to the local
 310    * datastore without publicly exposing it in the api.
 311    */
 312   protected static class KeyTranslator extends com.google.appengine.api.datastore.KeyTranslator {
 313     protected KeyTranslator() { }
 314   }
 315 }