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