<commit_before>// Copyright 2018 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.firebase.firestore.local;

import static com.google.firebase.firestore.util.Assert.hardAssert;
import static com.google.firebase.firestore.util.Util.values;

import com.google.firebase.database.collection.ImmutableSortedMap;
import com.google.firebase.database.collection.ImmutableSortedSet;
import com.google.firebase.firestore.core.Query;
import com.google.firebase.firestore.core.Target;
import com.google.firebase.firestore.local.IndexManager.IndexType;
import com.google.firebase.firestore.model.Document;
import com.google.firebase.firestore.model.DocumentKey;
import com.google.firebase.firestore.model.FieldIndex;
import com.google.firebase.firestore.model.FieldIndex.IndexOffset;
import com.google.firebase.firestore.model.SnapshotVersion;
import com.google.firebase.firestore.util.Logger;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import javax.annotation.Nullable;

/**
 * The Firestore query engine.
 *
 * <p>Firestore queries can be executed in three modes. The Query Engine determines what mode to use
 * based on what data is persisted. The mode only determines the runtime complexity of the query -
 * the result set is equivalent across all implementations.
 *
 * <p>The Query engine will use indexed-based execution if a user has configured any index that can
 * be used to execute query (via {@link FirebaseFirestore#setIndexConfiguation}). Otherwise, the
 * engine will try to optimize the query by re-using a previously persisted query result. If that is
 * not possible, the query will be executed via a full collection scan.
 *
 * <p>Index-based execution is the default when available. The query engine supports partial indexed
 * execution and merges the result from the index lookup with documents that have not yet been
 * indexed. The index evaluation matches the backend's format and as such, the SDK can use indexing
 * for all queries that the backend supports.
 *
 * <p>If no index exists, the query engine tries to take advantage of the target document mapping in
 * the TargetCache. These mappings exists for all queries that have been synced with the backend at
 * least once and allow the query engine to only read documents that previously matched a query plus
 * any documents that were edited after the query was last listened to.
 *
 * <p>There are some cases where this specific optimization is not guaranteed to produce the same
 * results as full collection scans. In these cases, query processing falls back to full scans.
 * These cases are:
 *
 * <ol>
 *   <li>Limit queries where a document that matched the query previously no longer matches the
 *       query.
 *   <li>Limit queries where a document edit may cause the document to sort below another document
 *       that is in the local cache.
 *   <li>Queries that have never been CURRENT or free of limbo documents.
 * </ol>
 */
public class QueryEngine {
  private static final String LOG_TAG = "QueryEngine";

  private LocalDocumentsView localDocumentsView;
  private IndexManager indexManager;
  private boolean initialized;

  public void initialize(LocalDocumentsView localDocumentsView, IndexManager indexManager) {
    this.localDocumentsView = localDocumentsView;
    this.indexManager = indexManager;
    this.initialized = true;
  }

  public ImmutableSortedMap<DocumentKey, Document> getDocumentsMatchingQuery(
      Query query,
      SnapshotVersion lastLimboFreeSnapshotVersion,
      ImmutableSortedSet<DocumentKey> remoteKeys) {
    hardAssert(initialized, "initialize() not called");

    ImmutableSortedMap<DocumentKey, Document> result =
        performQueryUsingIndex(query, query.toTarget());
    if (result != null) {
      return result;
    }

    result = performQueryUsingRemoteKeys(query, remoteKeys, lastLimboFreeSnapshotVersion);
    if (result != null) {
      return result;
    }

    return executeFullCollectionScan(query);
  }

  /**
   * Performs an indexed query that evaluates the query based on a collection's persisted index
   * values. Returns {@code null} if an index is not available.
   */
  private @Nullable ImmutableSortedMap<DocumentKey, Document> performQueryUsingIndex(
      Query query, Target target) {
    if (query.matchesAllDocuments()) {
      // Don't use index queries that can be executed by scanning the collection.
      return null;
    }

    IndexType indexType = indexManager.getIndexType(target);

    if (indexType.equals(IndexType.NONE)) {
      // The target cannot be served from any index.
      return null;
    }

    if (indexType.equals(IndexType.PARTIAL)) {
      // We cannot apply a limit for targets that are served using a partial index.
      // If a partial index will be used to serve the target, the query may return a superset of
      // documents that match the target (e.g. if the index doesn't include all the target's
      // filters), or may return the correct set of documents in the wrong order (e.g. if the index
      // doesn't include a segment for one of the orderBys). Therefore a limit should not be applied
      // in such cases.
      query = query.limitToFirst(Target.NO_LIMIT);
      target = query.toTarget();
    }

    List<DocumentKey> keys = indexManager.getDocumentsMatchingTarget(target);
    hardAssert(keys != null, "index manager must return results for partial and full indexes.");

    ImmutableSortedMap<DocumentKey, Document> indexedDocuments =
        localDocumentsView.getDocuments(keys);<commit_msg>QueryEngine clean up (#3646)<commit_after>// Copyright 2018 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.firebase.firestore.local;

import static com.google.firebase.firestore.util.Assert.hardAssert;
import static com.google.firebase.firestore.util.Util.values;

import com.google.firebase.database.collection.ImmutableSortedMap;
import com.google.firebase.database.collection.ImmutableSortedSet;
import com.google.firebase.firestore.core.Query;
import com.google.firebase.firestore.core.Target;
import com.google.firebase.firestore.local.IndexManager.IndexType;
import com.google.firebase.firestore.model.Document;
import com.google.firebase.firestore.model.DocumentKey;
import com.google.firebase.firestore.model.FieldIndex;
import com.google.firebase.firestore.model.FieldIndex.IndexOffset;
import com.google.firebase.firestore.model.SnapshotVersion;
import com.google.firebase.firestore.util.Logger;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import javax.annotation.Nullable;

/**
 * The Firestore query engine.
 *
 * <p>Firestore queries can be executed in three modes. The Query Engine determines what mode to use
 * based on what data is persisted. The mode only determines the runtime complexity of the query -
 * the result set is equivalent across all implementations.
 *
 * <p>The Query engine will use indexed-based execution if a user has configured any index that can
 * be used to execute query (via {@link FirebaseFirestore#setIndexConfiguration}). Otherwise, the
 * engine will try to optimize the query by re-using a previously persisted query result. If that is
 * not possible, the query will be executed via a full collection scan.
 *
 * <p>Index-based execution is the default when available. The query engine supports partial indexed
 * execution and merges the result from the index lookup with documents that have not yet been
 * indexed. The index evaluation matches the backend's format and as such, the SDK can use indexing
 * for all queries that the backend supports.
 *
 * <p>If no index exists, the query engine tries to take advantage of the target document mapping in
 * the TargetCache. These mappings exists for all queries that have been synced with the backend at
 * least once and allow the query engine to only read documents that previously matched a query plus
 * any documents that were edited after the query was last listened to.
 *
 * <p>There are some cases where this specific optimization is not guaranteed to produce the same
 * results as full collection scans. In these cases, query processing falls back to full scans.
 * These cases are:
 *
 * <ol>
 *   <li>Limit queries where a document that matched the query previously no longer matches the
 *       query.
 *   <li>Limit queries where a document edit may cause the document to sort below another document
 *       that is in the local cache.
 *   <li>Queries that have never been CURRENT or free of limbo documents.
 * </ol>
 */
public class QueryEngine {
  private static final String LOG_TAG = "QueryEngine";

  private LocalDocumentsView localDocumentsView;
  private IndexManager indexManager;
  private boolean initialized;

  public void initialize(LocalDocumentsView localDocumentsView, IndexManager indexManager) {
    this.localDocumentsView = localDocumentsView;
    this.indexManager = indexManager;
    this.initialized = true;
  }

  public ImmutableSortedMap<DocumentKey, Document> getDocumentsMatchingQuery(
      Query query,
      SnapshotVersion lastLimboFreeSnapshotVersion,
      ImmutableSortedSet<DocumentKey> remoteKeys) {
    hardAssert(initialized, "initialize() not called");

    ImmutableSortedMap<DocumentKey, Document> result = performQueryUsingIndex(query);
    if (result != null) {
      return result;
    }

    result = performQueryUsingRemoteKeys(query, remoteKeys, lastLimboFreeSnapshotVersion);
    if (result != null) {
      return result;
    }

    return executeFullCollectionScan(query);
  }

  /**
   * Performs an indexed query that evaluates the query based on a collection's persisted index
   * values. Returns {@code null} if an index is not available.
   */
  private @Nullable ImmutableSortedMap<DocumentKey, Document> performQueryUsingIndex(Query query) {
    if (query.matchesAllDocuments()) {
      // Don't use index queries that can be executed by scanning the collection.
      return null;
    }

    Target target = query.toTarget();
    IndexType indexType = indexManager.getIndexType(target);

    if (indexType.equals(IndexType.NONE)) {
      // The target cannot be served from any index.
      return null;
    }

    if (indexType.equals(IndexType.PARTIAL)) {
      // We cannot apply a limit for targets that are served using a partial index.
      // If a partial index will be used to serve the target, the query may return a superset of
      // documents that match the target (e.g. if the index doesn't include all the target's
      // filters), or may return the correct set of documents in the wrong order (e.g. if the index
      // doesn't include a segment for one of the orderBys). Therefore a limit should not be applied
      // in such cases.
      query = query.limitToFirst(Target.NO_LIMIT);
      target = query.toTarget();
    }

    List<DocumentKey> keys = indexManager.getDocumentsMatchingTarget(target);
    hardAssert(keys != null, "index manager must return results for partial and full indexes.");

    ImmutableSortedMap<DocumentKey, Document> indexedDocuments =
        localDocumentsView.getDocuments(keys);
{'fraction_non_alphanumeric': 0.07251971090670171, 'fraction_numerical': 0.0016425755584756898, 'mean_word_length': 3.9339546191247976, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1468121', 'n_tokens_mistral': 3158, 'n_tokens_neox': 3047, 'n_words': 1309}