1 // Copyright 2009 Google Inc. All Rights Reserved.
2 package com
.google
.appengine
.api
.datastore
;
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
;
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
;
23 * Composite index management operations needed by the datastore api.
26 public class CompositeIndexManager
{
29 * The format of a datastore-index xml element when it has properties.
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";
36 * The format of a datastore-index xml element when it does not have
39 private static final String DATASTORE_INDEX_NO_PROPERTIES_XML_FORMAT
=
40 " <datastore-index kind=\"%s\" ancestor=\"%s\" source=\"%s\"/>\n\n";
43 * The format of a property xml element.
45 private static final String PROPERTY_XML_FORMAT
=
46 " <property name=\"%s\" direction=\"%s\"/>\n";
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.
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.
59 protected enum IndexSource
{ auto
, manual
}
62 * Generate an xml representation of the provided {@link Index}.
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"/>
69 * </datastore-indexes>
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.
75 protected String
generateXmlForIndex(Index index
, IndexSource source
) {
77 boolean isAncestor
= index
.isAncestor();
78 if (index
.propertySize() == 0) {
80 DATASTORE_INDEX_NO_PROPERTIES_XML_FORMAT
,
81 index
.getEntityType(), isAncestor
, source
);
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
));
89 DATASTORE_INDEX_WITH_PROPERTIES_XML_FORMAT
,
90 index
.getEntityType(), isAncestor
, source
, sb
.toString());
94 * Given a {@link IndexComponentsOnlyQuery}, return the {@link Index}
95 * needed to fulfill the query, or {@code null} if no index is needed.
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.
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.
105 protected Index
compositeIndexForQuery(final IndexComponentsOnlyQuery indexOnlyQuery
) {
106 DatastoreV3Pb
.Query query
= indexOnlyQuery
.getQuery();
108 boolean hasKind
= query
.hasKind();
109 boolean isAncestor
= query
.hasAncestor();
110 List
<Filter
> filters
= query
.filters();
111 List
<Order
> orders
= query
.orders();
113 if (filters
.isEmpty() && orders
.isEmpty()) {
117 List
<String
> eqProps
= indexOnlyQuery
.getPrefix();
118 List
<Property
> indexProperties
= getRecommendedIndexProps(indexOnlyQuery
);
120 if (hasKind
&& !eqProps
.isEmpty() &&
121 eqProps
.size() == filters
.size() &&
122 !indexOnlyQuery
.hasKeyProperty() &&
127 if (hasKind
&& !isAncestor
&& indexProperties
.size() <= 1 &&
128 (!indexOnlyQuery
.hasKeyProperty() ||
129 indexProperties
.get(0).getDirectionEnum() == Property
.Direction
.ASCENDING
)) {
133 Index index
= new Index();
134 index
.setEntityType(query
.getKind());
135 index
.setAncestor(isAncestor
);
136 index
.mutablePropertys().addAll(indexProperties
);
141 * We compare {@link Property Properties} by comparing their names.
143 private static final Comparator
<Property
> PROPERTY_NAME_COMPARATOR
= new Comparator
<Property
>() {
145 public int compare(Property o1
, Property o2
) {
146 return o1
.getName().compareTo(o2
.getName());
150 private List
<Property
> getRecommendedIndexProps(IndexComponentsOnlyQuery query
) {
151 List
<Property
> indexProps
= new ArrayList
<Property
>();
153 indexProps
.addAll(new UnorderedIndexComponent(Sets
.newHashSet(query
.getPrefix()))
154 .preferredIndexProperties());
156 for (IndexComponent component
: query
.getPostfix()) {
157 indexProps
.addAll(component
.preferredIndexProperties());
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.
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.
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.
177 protected Index
minimumCompositeIndexForQuery(IndexComponentsOnlyQuery indexOnlyQuery
,
178 Collection
<Index
> indexes
) {
180 Index suggestedIndex
= compositeIndexForQuery(indexOnlyQuery
);
181 if (suggestedIndex
== null) {
185 class EqPropsAndAncestorConstraint
{
186 final Set
<String
> equalityProperties
;
187 final boolean ancestorConstraint
;
189 EqPropsAndAncestorConstraint(Set
<String
> equalityProperties
, boolean ancestorConstraint
) {
190 this.equalityProperties
= equalityProperties
;
191 this.ancestorConstraint
= ancestorConstraint
;
195 Map
<List
<Property
>, EqPropsAndAncestorConstraint
> remainingMap
=
196 new HashMap
<List
<Property
>, EqPropsAndAncestorConstraint
>();
199 for (Index index
: indexes
) {
201 !indexOnlyQuery
.getQuery().getKind().equals(index
.getEntityType()) ||
202 (!indexOnlyQuery
.getQuery().hasAncestor() && index
.isAncestor())) {
206 int postfixSplit
= index
.propertySize();
207 for (IndexComponent component
: Lists
.reverse(indexOnlyQuery
.getPostfix())) {
208 if (!component
.matches(index
.propertys().subList(postfixSplit
- component
.size(),
212 postfixSplit
-= component
.size();
215 Set
<String
> indexEqProps
= Sets
.newHashSetWithExpectedSize(postfixSplit
);
216 for (Property prop
: index
.propertys().subList(0, postfixSplit
)) {
217 if (!indexOnlyQuery
.getPrefix().contains(prop
.getName())) {
220 indexEqProps
.add(prop
.getName());
223 List
<Property
> indexPostfix
= index
.propertys().subList(postfixSplit
, index
.propertySize());
225 Set
<String
> remainingEqProps
;
226 boolean remainingAncestor
;
228 EqPropsAndAncestorConstraint remaining
= remainingMap
.get(indexPostfix
);
229 if (remaining
== null) {
230 remainingEqProps
= Sets
.newHashSet(indexOnlyQuery
.getPrefix());
231 remainingAncestor
= indexOnlyQuery
.getQuery().hasAncestor();
233 remainingEqProps
= remaining
.equalityProperties
;
234 remainingAncestor
= remaining
.ancestorConstraint
;
238 boolean modified
= remainingEqProps
.removeAll(indexEqProps
);
239 if (remainingAncestor
&& index
.isAncestor()) {
241 remainingAncestor
= false;
244 if (remainingEqProps
.isEmpty() && !remainingAncestor
) {
252 remainingMap
.put(indexPostfix
,
253 new EqPropsAndAncestorConstraint(remainingEqProps
, remainingAncestor
));
256 if (remainingMap
.isEmpty()) {
257 return suggestedIndex
;
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
) {
268 if (cost
< minimumCost
) {
270 minimumPostfix
= entry
.getKey();
271 minimumRemaining
= entry
.getValue();
275 suggestedIndex
.clearProperty();
276 suggestedIndex
.setAncestor(minimumRemaining
.ancestorConstraint
);
277 for (String name
: minimumRemaining
.equalityProperties
) {
278 suggestedIndex
.addProperty().setName(name
).setDirection(Direction
.ASCENDING
);
280 Collections
.sort(suggestedIndex
.mutablePropertys(), PROPERTY_NAME_COMPARATOR
);
282 suggestedIndex
.mutablePropertys().addAll(minimumPostfix
);
283 return suggestedIndex
;
287 * Protected alias that allows us to make this class available to the local
288 * datastore without publicly exposing it in the api.
290 protected static class IndexComponentsOnlyQuery
291 extends com
.google
.appengine
.api
.datastore
.IndexComponentsOnlyQuery
{
292 public IndexComponentsOnlyQuery(DatastoreV3Pb
.Query query
) {
298 * Protected alias that allows us to make this class available to the local
299 * datastore without publicly exposing it in the api.
301 protected static class ValidatedQuery
302 extends com
.google
.appengine
.api
.datastore
.ValidatedQuery
{
303 public ValidatedQuery(DatastoreV3Pb
.Query query
) {
309 * Protected alias that allows us to make this class available to the local
310 * datastore without publicly exposing it in the api.
312 protected static class KeyTranslator
extends com
.google
.appengine
.api
.datastore
.KeyTranslator
{
313 protected KeyTranslator() { }