From 6ab0195f11e9a0daab46babf7f894bb08b2ae9c3 Mon Sep 17 00:00:00 2001 From: Konstantin Varlamov Date: Mon, 16 Jul 2018 18:20:00 -0400 Subject: Minimize rereading of batches in FSTLocalDocumentsView documentsMatchingCollectionQuery (#1533) Previously in `documentsMatchingCollectionQuery`, write batches were read three times; in fact, all relevant batches will always be contained inside `allMutationBatchesAffectingQuery` (which is also more efficient); the other two calls were redundant. --- Firestore/Source/Local/FSTLocalDocumentsView.mm | 99 ++++++---------------- .../core/src/firebase/firestore/model/base_path.h | 10 +++ 2 files changed, 36 insertions(+), 73 deletions(-) diff --git a/Firestore/Source/Local/FSTLocalDocumentsView.mm b/Firestore/Source/Local/FSTLocalDocumentsView.mm index 4337879..ee27ef7 100644 --- a/Firestore/Source/Local/FSTLocalDocumentsView.mm +++ b/Firestore/Source/Local/FSTLocalDocumentsView.mm @@ -70,8 +70,12 @@ NS_ASSUME_NONNULL_BEGIN // Internal version of documentForKey: which allows reusing `batches`. - (nullable FSTMaybeDocument *)documentForKey:(const DocumentKey &)key inBatches:(NSArray *)batches { - FSTMaybeDocument *_Nullable remoteDoc = [self.remoteDocumentCache entryForKey:key]; - return [self localDocument:remoteDoc key:key inBatches:batches]; + FSTMaybeDocument *_Nullable document = [self.remoteDocumentCache entryForKey:key]; + for (FSTMutationBatch *batch in batches) { + document = [batch applyTo:document documentKey:key]; + } + + return document; } - (FSTMaybeDocumentDictionary *)documentsForKeys:(const DocumentKeySet &)keys { @@ -110,37 +114,34 @@ NS_ASSUME_NONNULL_BEGIN } - (FSTDocumentDictionary *)documentsMatchingCollectionQuery:(FSTQuery *)query { - // Query the remote documents and overlay mutations. - // TODO(mikelehen): There may be significant overlap between the mutations affecting these - // remote documents and the allMutationBatchesAffectingQuery mutations. Consider optimizing. __block FSTDocumentDictionary *results = [self.remoteDocumentCache documentsMatchingQuery:query]; - results = [self localDocuments:results]; - - // Now use the mutation queue to discover any other documents that may match the query after - // applying mutations. - DocumentKeySet matchingKeys; - NSArray *matchingMutationBatches = + // Get locally persisted mutation batches. + NSArray *matchingBatches = [self.mutationQueue allMutationBatchesAffectingQuery:query]; - for (FSTMutationBatch *batch in matchingMutationBatches) { + + for (FSTMutationBatch *batch in matchingBatches) { for (FSTMutation *mutation in batch.mutations) { - // TODO(mikelehen): PERF: Check if this mutation actually affects the query to reduce work. + // Only process documents belonging to the collection. + if (!query.path.IsImmediateParentOf(mutation.key.path())) { + continue; + } - // If the key is already in the results, we can skip it. - if (![results containsKey:mutation.key]) { - matchingKeys = matchingKeys.insert(mutation.key); + FSTDocumentKey *key = static_cast(mutation.key); + // baseDoc may be nil for the documents that weren't yet written to the backend. + FSTMaybeDocument *baseDoc = results[key]; + FSTMaybeDocument *mutatedDoc = + [mutation applyTo:baseDoc baseDocument:baseDoc localWriteTime:batch.localWriteTime]; + + if ([mutatedDoc isKindOfClass:[FSTDeletedDocument class]]) { + results = [results dictionaryByRemovingObjectForKey:key]; + } else if ([mutatedDoc isKindOfClass:[FSTDocument class]]) { + results = [results dictionaryBySettingObject:(FSTDocument *)mutatedDoc forKey:key]; + } else { + HARD_FAIL("Unknown document: %s", mutatedDoc); } } } - // Now add in results for the matchingKeys. - FSTMaybeDocumentDictionary *matchingKeysDocs = [self documentsForKeys:matchingKeys]; - [matchingKeysDocs - enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTMaybeDocument *doc, BOOL *stop) { - if ([doc isKindOfClass:[FSTDocument class]]) { - results = [results dictionaryBySettingObject:(FSTDocument *)doc forKey:key]; - } - }]; - // Finally, filter out any documents that don't actually match the query. Note that the extra // reference here prevents ARC from deallocating the initial unfiltered results while we're // enumerating them. @@ -155,54 +156,6 @@ NS_ASSUME_NONNULL_BEGIN return results; } -/** - * Takes a remote document and applies local mutations to generate the local view of the - * document. - * - * @param document The base remote document to apply mutations to. - * @param documentKey The key of the document (necessary when remoteDocument is nil). - */ -- (nullable FSTMaybeDocument *)localDocument:(nullable FSTMaybeDocument *)document - key:(const DocumentKey &)documentKey - inBatches:(NSArray *)batches { - for (FSTMutationBatch *batch in batches) { - document = [batch applyTo:document documentKey:documentKey]; - } - - return document; -} - -/** - * Takes a set of remote documents and applies local mutations to generate the local view of - * the documents. - * - * @param documents The base remote documents to apply mutations to. - * @return The local view of the documents. - */ -- (FSTDocumentDictionary *)localDocuments:(FSTDocumentDictionary *)documents { - __block DocumentKeySet keySet; - [documents - enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTDocument *doc, BOOL *stop) { - keySet = keySet.insert(doc.key); - }]; - NSArray *batches = - [self.mutationQueue allMutationBatchesAffectingDocumentKeys:keySet]; - - __block FSTDocumentDictionary *result = documents; - [documents enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTDocument *remoteDocument, - BOOL *stop) { - FSTMaybeDocument *mutatedDoc = [self localDocument:remoteDocument key:key inBatches:batches]; - if ([mutatedDoc isKindOfClass:[FSTDeletedDocument class]]) { - result = [result dictionaryByRemovingObjectForKey:key]; - } else if ([mutatedDoc isKindOfClass:[FSTDocument class]]) { - result = [result dictionaryBySettingObject:(FSTDocument *)mutatedDoc forKey:key]; - } else { - HARD_FAIL("Unknown document: %s", mutatedDoc); - } - }]; - return result; -} - @end NS_ASSUME_NONNULL_END diff --git a/Firestore/core/src/firebase/firestore/model/base_path.h b/Firestore/core/src/firebase/firestore/model/base_path.h index 7608829..31aaebb 100644 --- a/Firestore/core/src/firebase/firestore/model/base_path.h +++ b/Firestore/core/src/firebase/firestore/model/base_path.h @@ -139,6 +139,16 @@ class BasePath { return size() <= rhs.size() && std::equal(begin(), end(), rhs.begin()); } + /** + * Returns true if the given argument is a direct child of this path. + * + * Empty path is a parent of any path that consists of a single segment. + */ + bool IsImmediateParentOf(const T& potential_child) const { + return size() + 1 == potential_child.size() && + std::equal(begin(), end(), potential_child.begin()); + } + bool operator==(const BasePath& rhs) const { return segments_ == rhs.segments_; } -- cgit v1.2.3