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.List;
  20 import java.util.Map;
  21 import java.util.Set;
  22
  23 /**
  24  * Composite index management operations needed by the datastore api.
  25  *
  26  */
  27 public class CompositeIndexManager {
  28
  29   /**
  30    * The format of a datastore-index xml element when it has properties.
  31    */
  32   private static final String DATASTORE_INDEX_WITH_PROPERTIES_XML_FORMAT =
  33       "    <datastore-index kind=\"%s\" ancestor=\"%s\" source=\"%s\">\n%s"
  34     + "    </datastore-index>\n\n";
  35
  36   /**
  37    * The format of a datastore-index xml element when it does not have
  38    * properties.
  39    */
  40   private static final String DATASTORE_INDEX_NO_PROPERTIES_XML_FORMAT =
  41       "    <datastore-index kind=\"%s\" ancestor=\"%s\" source=\"%s\"/>\n\n";
  42
  43   /**
  44    * The format of a property xml element.
  45    */
  46   private static final String PROPERTY_XML_FORMAT =
  47       "        <property name=\"%s\" direction=\"%s\"/>\n";
  48
  49   /**
  50    * Apologies for the lowercase literals, but the whole point of these enums
  51    * is to represent constants in an xml document, and it's silly to have
  52    * the code literals not match the xml literals - you end up with a bunch
  53    * of case conversion just support the java naming conversion.
  54    */
  55
  56   /**
  57    * The source of an index in the index file.  These are used as literals
  58    * in an xml document that we read and write.
  59    */
  60   protected enum IndexSource { auto, manual }
  61
  62   /**
  63    * Generate an xml representation of the provided {@link Index}.
  64    *
  65    * <datastore-indexes autoGenerate="true">
  66    *     <datastore-index kind="a" ancestor="false">
  67    *         <property name="yam" direction="asc"/>
  68    *         <property name="not yam" direction="desc"/>
  69    *     </datastore-index>
  70    * </datastore-indexes>
  71    *
  72    * @param index The index for which we want an xml representation.
  73    * @param source The source of the provided index.
  74    * @return The xml representation of the provided index.
  75    */
  76   protected String generateXmlForIndex(Index index, IndexSource source) {
  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     DatastorePb.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     Map<List<Property>, Pair<Set<String>, Boolean>> remainingMap =
 186         new HashMap<List<Property>, Pair<Set<String>, Boolean>>();
 187
 188 index_for:
 189     for (Index index : indexes) {
 190       if (
 191           !indexOnlyQuery.getQuery().getKind().equals(index.getEntityType()) ||
 192           (!indexOnlyQuery.getQuery().hasAncestor() && index.isAncestor())) {
 193         continue;
 194       }
 195
 196       int postfixSplit = index.propertySize();
 197       for (IndexComponent component : Lists.reverse(indexOnlyQuery.getPostfix())) {
 198         if (!component.matches(index.propertys().subList(postfixSplit - component.size(),
 199             postfixSplit))) {
 200           continue index_for;
 201         }
 202         postfixSplit -= component.size();
 203       }
 204
 205       Set<String> indexEqProps = Sets.newHashSetWithExpectedSize(postfixSplit);
 206       for (Property prop : index.propertys().subList(0, postfixSplit)) {
 207         if (!indexOnlyQuery.getPrefix().contains(prop.getName())) {
 208           continue index_for;
 209         }
 210         indexEqProps.add(prop.getName());
 211       }
 212
 213       List<Property> indexPostfix = index.propertys().subList(postfixSplit, index.propertySize());
 214
 215       Set<String> remainingEqProps;
 216       boolean remainingAncestor;
 217       {
 218         Pair<Set<String>, Boolean> remaining = remainingMap.get(indexPostfix);
 219         if (remaining == null) {
 220           remainingEqProps = Sets.newHashSet(indexOnlyQuery.getPrefix());
 221           remainingAncestor = indexOnlyQuery.getQuery().hasAncestor();
 222         } else {
 223           remainingEqProps = remaining.first;
 224           remainingAncestor = remaining.second;
 225         }
 226       }
 227
 228       boolean modified = remainingEqProps.removeAll(indexEqProps);
 229       if (remainingAncestor && index.isAncestor()) {
 230         modified = true;
 231         remainingAncestor = false;
 232       }
 233
 234       if (remainingEqProps.isEmpty() && !remainingAncestor) {
 235         return null;
 236       }
 237
 238       if (!modified) {
 239         continue;
 240       }
 241
 242       remainingMap.put(indexPostfix, Pair.of(remainingEqProps, remainingAncestor));
 243     }
 244
 245     if (remainingMap.isEmpty()) {
 246       return suggestedIndex;
 247     }
 248
 249     int minimumCost = Integer.MAX_VALUE;
 250     List<Property> minimumPostfix = null;
 251     Pair<Set<String>, Boolean> minimumRemaining = null;
 252     for (Map.Entry<List<Property>, Pair<Set<String>, Boolean>> entry : remainingMap.entrySet()) {
 253       int cost = entry.getValue().first.size();
 254       if (entry.getValue().second) {
 255         cost += 2;
 256       }
 257       if (cost < minimumCost) {
 258         minimumCost = cost;
 259         minimumPostfix = entry.getKey();
 260         minimumRemaining = entry.getValue();
 261       }
 262     }
 263
 264     suggestedIndex.clearProperty();
 265     suggestedIndex.setAncestor(minimumRemaining.second);
 266     for (String name : minimumRemaining.first) {
 267       suggestedIndex.addProperty().setName(name).setDirection(Direction.ASCENDING);
 268     }
 269     Collections.sort(suggestedIndex.mutablePropertys(), PROPERTY_NAME_COMPARATOR);
 270
 271     suggestedIndex.mutablePropertys().addAll(minimumPostfix);
 272     return suggestedIndex;
 273   }
 274
 275   /**
 276    * Protected alias that allows us to make this class available to the local
 277    * datastore without publicly exposing it in the api.
 278    */
 279   protected static class IndexComponentsOnlyQuery
 280       extends com.google.appengine.api.datastore.IndexComponentsOnlyQuery {
 281     public IndexComponentsOnlyQuery(DatastorePb.Query query) {
 282       super(query);
 283     }
 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 ValidatedQuery
 291       extends com.google.appengine.api.datastore.ValidatedQuery {
 292     public ValidatedQuery(DatastorePb.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 KeyTranslator extends com.google.appengine.api.datastore.KeyTranslator {
 302     protected KeyTranslator() { }
 303   }
 304 }