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

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