Index: clang-tools-extra/trunk/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/MemIndex.cpp
+++ clang-tools-extra/trunk/clangd/index/MemIndex.cpp
@@ -11,6 +11,7 @@
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
 
 namespace clang {
 namespace clangd {
@@ -28,6 +29,7 @@
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
+  trace::Span Tracer("MemIndex fuzzyFind");
 
   TopN<std::pair<float, const Symbol *>> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
@@ -47,13 +49,16 @@
       if (Top.push({*Score * quality(*Sym), Sym}))
         More = true; // An element with smallest score was discarded.
   }
-  for (const auto &Item : std::move(Top).items())
+  auto Results = std::move(Top).items();
+  SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
+  for (const auto &Item : Results)
     Callback(*Item.second);
   return More;
 }
 
 void MemIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("MemIndex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())
@@ -63,6 +68,7 @@
 
 void MemIndex::refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("MemIndex refs");
   for (const auto &ReqID : Req.IDs) {
     auto SymRefs = Refs.find(ReqID);
     if (SymRefs == Refs.end())
Index: clang-tools-extra/trunk/clangd/index/Merge.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/Merge.cpp
+++ clang-tools-extra/trunk/clangd/index/Merge.cpp
@@ -9,6 +9,7 @@
 
 #include "Merge.h"
 #include "Logger.h"
+#include "Trace.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
@@ -38,19 +39,31 @@
      //    a) if it's not in the dynamic slab, yield it directly
      //    b) if it's in the dynamic slab, merge it and yield the result
      //  3) now yield all the dynamic symbols we haven't processed.
+     trace::Span Tracer("MergedIndex fuzzyFind");
      bool More = false; // We'll be incomplete if either source was.
      SymbolSlab::Builder DynB;
-     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) { DynB.insert(S); });
+     unsigned DynamicCount = 0;
+     unsigned StaticCount = 0;
+     unsigned MergedCount = 0;
+     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
+       ++DynamicCount;
+       DynB.insert(S);
+     });
      SymbolSlab Dyn = std::move(DynB).build();
 
      DenseSet<SymbolID> SeenDynamicSymbols;
      More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
        auto DynS = Dyn.find(S.ID);
+       ++StaticCount;
        if (DynS == Dyn.end())
          return Callback(S);
+       ++MergedCount;
        SeenDynamicSymbols.insert(S.ID);
        Callback(mergeSymbol(*DynS, S));
      });
+     SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
+     SPAN_ATTACH(Tracer, "static", StaticCount);
+     SPAN_ATTACH(Tracer, "merged", MergedCount);
      for (const Symbol &S : Dyn)
        if (!SeenDynamicSymbols.count(S.ID))
          Callback(S);
@@ -60,6 +73,7 @@
   void
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const override {
+    trace::Span Tracer("MergedIndex lookup");
     SymbolSlab::Builder B;
 
     Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
@@ -80,6 +94,7 @@
 
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override {
+    trace::Span Tracer("MergedIndex refs");
     // We don't want duplicated refs from the static/dynamic indexes,
     // and we can't reliably duplicate them because offsets may differ slightly.
     // We consider the dynamic index authoritative and report all its refs,
Index: clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
+++ clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
@@ -12,6 +12,7 @@
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
 #include "llvm/ADT/StringSet.h"
 #include <algorithm>
 #include <queue>
@@ -139,6 +140,8 @@
                     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
+  // FIXME: attach the query tree to the trace span.
+  trace::Span Tracer("Dex fuzzyFind");
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
 
@@ -228,6 +231,7 @@
 
 void Dex::lookup(const LookupRequest &Req,
                  llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("Dex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
@@ -237,6 +241,7 @@
 
 void Dex::refs(const RefsRequest &Req,
                llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("Dex refs");
   log("refs is not implemented.");
 }