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

   1 package com.google.appengine.api.datastore;
   2
   3 import static com.google.common.base.Preconditions.checkArgument;
   4
   5 import com.google.apphosting.datastore.DatastoreV3Pb;
   6 import com.google.apphosting.datastore.DatastoreV3Pb.Query.Filter;
   7 import com.google.apphosting.datastore.DatastoreV3Pb.RegionPoint;
   8
   9 import java.util.ArrayList;
  10 import java.util.Collections;
  11 import java.util.List;
  12
  13 /**
  14  * Simulates the filter matching process used in the datastore for a single
  15  * property name.
  16  *
  17  * The true behavior of the datastore becomes extremely strange for multi-valued
  18  * properties especially when there are inequality and equality filters on the
  19  * same property. Here is the current logic that governs filtering:
  20  *
  21  * All inequality filters are merged together into a range so that:
  22  * a > 1 && a <=3 && a >=2
  23  * becomes
  24  * "There exists an x such that x is an element of a and 2 <= x <= 3"
  25  *
  26  * All equality filters are handled independently so:
  27  * a == 1 && a == 4
  28  * becomes
  29  * "For all x in [1, 4] there x is an element of a"
  30  *
  31  * When there are both equality and inequality filters 'a' must meet both
  32  * requirements.
  33  *
  34  * For example consider:
  35  * a < 0 && a == 4
  36  *
  37  * This may seem like a query with this filter should always return an empty
  38  * result set, but this is actually not the case when 'a' has multiple values.
  39  * This is currently planned in the datastore as a composite index scan on the
  40  * index (a, a) where the first 'a' is set to 4 and the second 'a' has 'a < 0'
  41  * imposed on it.
  42  *
  43  * so that the value:
  44  * a = [-1, 4, 2] will produces the following index data:
  45  *  -1, -1
  46  *  -1,  2
  47  *  -1,  4
  48  *   2, -1
  49  *   2,  2
  50  *   2,  4
  51  *   4, -1
  52  *   4,  2
  53  *   4,  4
  54  *
  55  * the a = 4 is applied first so we restrict our scan of the index to:
  56  *   4, -1
  57  *   4,  2
  58  *   4,  4
  59  *
  60  * then a < 0 is applied to restrict our scan further to:
  61  *   4, -1
  62  *
  63  * thus a = [-1, 4, 2] matches our query.
  64  *
  65  * It is also important to note that 'a < 0 && a > 1' will always return no
  66  * results as this is converted into '1 < a < 0' before being applied.
  67  *
  68  */
  69 class FilterMatcher {
  70   public static final FilterMatcher MATCH_ALL = new FilterMatcher() {
  71       @Override
  72       public void addFilter(Filter filter) {
  73         throw new UnsupportedOperationException("FilterMatcher.MATCH_ALL is immutable");
  74       }
  75
  76       @Override
  77       public boolean matches(List<Comparable<Object>> values) {
  78         return true;
  79       }
  80
  81       @Override
  82       boolean matchesRange(Comparable<Object> value) {
  83         return true;
  84       }
  85
  86     };
  87
  88   static class NoValue implements Comparable<Object> {
  89     static final FilterMatcher.NoValue INSTANCE = new NoValue();
  90
  91     private NoValue() {}
  92
  93     @Override
  94     public int compareTo(Object o) {
  95       throw new UnsupportedOperationException();
  96     }
  97   }
  98
  99   Comparable<Object> min = NoValue.INSTANCE;
 100   boolean minInclusive;
 101
 102   Comparable<Object> max = NoValue.INSTANCE;
 103   boolean maxInclusive;
 104   List<Comparable<Object>> equalValues = new ArrayList<Comparable<Object>>();
 105   List<Query.GeoRegion> geoRegions = new ArrayList<>();
 106
 107   /**
 108    * Returns true if the given value should be taken into account when determining order.
 109    */
 110   public boolean considerValueForOrder(Comparable<Object> value) {
 111     return matchesRange(value);
 112   }
 113
 114   boolean matchesRange(Comparable<Object> value) {
 115     if (min != NoValue.INSTANCE) {
 116       int cmp = EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(value, min);
 117       if (cmp < 0 || (cmp == 0 && !minInclusive)) {
 118         return false;
 119       }
 120     }
 121
 122     if (max != NoValue.INSTANCE) {
 123       int cmp = EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(value, max);
 124       if (cmp > 0 || (cmp == 0 && !maxInclusive)) {
 125         return false;
 126       }
 127     }
 128
 129     return true;
 130   }
 131
 132   /**
 133    * Returns true if the given values match the filters provided through {@link #addFilter}.
 134    */
 135   public boolean matches(List<Comparable<Object>> values) {
 136     if (values.size() > 1) {
 137       Collections.sort(values, EntityProtoComparators.MULTI_TYPE_COMPARATOR);
 138     }
 139     for (Comparable<Object> eqValue : equalValues) {
 140       if (Collections.binarySearch(
 141           values, eqValue, EntityProtoComparators.MULTI_TYPE_COMPARATOR) < 0) {
 142         return false;
 143       }
 144     }
 145
 146     for (Query.GeoRegion region : geoRegions) {
 147       boolean contained = false;
 148       for (Comparable<Object> value : values) {
 149         Object o = value;
 150         if (o instanceof GeoPt && region.contains((GeoPt) o)) {
 151           contained = true;
 152           break;
 153         }
 154       }
 155       if (!contained) {
 156         return false;
 157       }
 158     }
 159
 160     for (Comparable<Object> value : values) {
 161       if (matchesRange(value)) {
 162         return true;
 163       }
 164     }
 165
 166     return false;
 167   }
 168
 169   public void addFilter(Filter filter) {
 170     Comparable<Object> value = DataTypeTranslator.getComparablePropertyValue(filter.getProperty(0));
 171     switch (filter.getOpEnum()) {
 172       case EQUAL:
 173         equalValues.add(value);
 174         break;
 175       case GREATER_THAN:
 176         if (min == NoValue.INSTANCE ||
 177             EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(min, value) <= 0) {
 178           min = value;
 179           minInclusive = false;
 180         }
 181         break;
 182       case GREATER_THAN_OR_EQUAL:
 183         if (min == NoValue.INSTANCE ||
 184             EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(min, value) < 0) {
 185           min = value;
 186           minInclusive = true;
 187         }
 188         break;
 189       case LESS_THAN:
 190         if (max == NoValue.INSTANCE ||
 191             EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(max, value) >= 0) {
 192           max = value;
 193           maxInclusive = false;
 194         }
 195         break;
 196       case LESS_THAN_OR_EQUAL:
 197         if (max == NoValue.INSTANCE ||
 198             EntityProtoComparators.MULTI_TYPE_COMPARATOR.compare(max, value) > 0) {
 199           max = value;
 200           maxInclusive = true;
 201         }
 202         break;
 203       case EXISTS:
 204         break;
 205       case CONTAINED_IN_REGION:
 206         geoRegions.add(fromProto(filter.getGeoRegion()));
 207         break;
 208       default:
 209         throw new IllegalArgumentException(
 210             "Unable to perform filter using operator " + filter.getOp());
 211     }
 212   }
 213
 214   private static GeoPt fromProto(RegionPoint point) {
 215     return new GeoPt((float) point.getLatitude(), (float) point.getLongitude());
 216   }
 217
 218   private static Query.GeoRegion fromProto(DatastoreV3Pb.GeoRegion pb) {
 219     if (pb.hasCircle()) {
 220       return new Query.GeoRegion.Circle(fromProto(pb.getCircle().getCenter()),
 221           pb.getCircle().getRadiusMeters());
 222     }
 223     checkArgument(pb.hasRectangle());
 224     return new Query.GeoRegion.Rectangle(fromProto(pb.getRectangle().getSouthwest()),
 225         fromProto(pb.getRectangle().getNortheast()));
 226   }
 227
 228   @Override
 229   public String toString() {
 230     StringBuilder result = new StringBuilder("FilterMatcher [");
 231
 232     if (min != NoValue.INSTANCE || max != NoValue.INSTANCE) {
 233       if (min != NoValue.INSTANCE) {
 234         result.append(min);
 235         result.append(minInclusive ? " <= " : " < ");
 236       }
 237       result.append("X");
 238       if (max != NoValue.INSTANCE) {
 239         result.append(maxInclusive ? " <= " : " < ");
 240         result.append(max);
 241       }
 242       if (!equalValues.isEmpty()) {
 243         result.append(" && ");
 244       }
 245     }
 246     if (!equalValues.isEmpty()) {
 247       result.append("X CONTAINS ");
 248       result.append(equalValues);
 249     }
 250
 251     result.append("]");
 252     return result.toString();
 253   }
 254 }