diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp
--- a/clang-tools-extra/clangd/ClangdServer.cpp
+++ b/clang-tools-extra/clangd/ClangdServer.cpp
@@ -525,11 +525,11 @@
 void ClangdServer::findTypeHierarchy(PathRef File, Position Pos, int Resolve,
                                      TypeHierarchyDirection Direction,
                                      Callback<Optional<TypeHierarchyItem>> CB) {
-  auto Action = [Pos, Resolve, Direction](decltype(CB) CB,
-                                          Expected<InputsAndAST> InpAST) {
+  auto Action = [Pos, Resolve, Direction, this](decltype(CB) CB,
+                                                Expected<InputsAndAST> InpAST) {
     if (!InpAST)
       return CB(InpAST.takeError());
-    CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction));
+    CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction, Index));
   };
 
   WorkScheduler.runWithAST("Type Hierarchy", File, Bind(Action, std::move(CB)));
diff --git a/clang-tools-extra/clangd/XRefs.h b/clang-tools-extra/clangd/XRefs.h
--- a/clang-tools-extra/clangd/XRefs.h
+++ b/clang-tools-extra/clangd/XRefs.h
@@ -67,7 +67,8 @@
 /// Get type hierarchy information at \p Pos.
 llvm::Optional<TypeHierarchyItem>
 getTypeHierarchy(ParsedAST &AST, Position Pos, int Resolve,
-                 TypeHierarchyDirection Direction);
+                 TypeHierarchyDirection Direction,
+                 const SymbolIndex *Index = nullptr);
 
 } // namespace clangd
 } // namespace clang
diff --git a/clang-tools-extra/clangd/XRefs.cpp b/clang-tools-extra/clangd/XRefs.cpp
--- a/clang-tools-extra/clangd/XRefs.cpp
+++ b/clang-tools-extra/clangd/XRefs.cpp
@@ -871,6 +871,65 @@
   return THI;
 }
 
+static Optional<TypeHierarchyItem>
+symbolIDToTypeHierarchyItem(const SymbolID &ID, const SymbolIndex *Index) {
+  LookupRequest Request;
+  Request.IDs.insert(ID);
+  Optional<TypeHierarchyItem> Result;
+  Index->lookup(Request, [&Result](const Symbol &S) {
+    TypeHierarchyItem THI;
+    THI.name = S.Name;
+    THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
+    THI.deprecated = (S.Flags & Symbol::Deprecated);
+    Position Start, End;
+    auto &CD = S.Definition ? S.Definition : S.CanonicalDeclaration;
+    Start.line = CD.Start.line();
+    Start.character = CD.Start.column();
+    End.line = CD.End.line();
+    End.character = CD.End.column();
+    // TODO: How to get entire range like in declToTypeHierarchyItem()?
+    THI.range = {Start, End};
+    THI.selectionRange = {Start, End};
+    // TODO: Reuse code between here and getWorkspaceSymbols().
+    auto Uri = URI::parse(CD.FileURI);
+    if (!Uri) {
+      log("Type hierarchy: Could not parse URI '{0}' for symbol '{1}'.",
+          CD.FileURI, S.Name);
+      return;
+    }
+    // TODO: Pass in ClangdServer::WorkspaceRoot as a HintPath.
+    StringRef HintPath;
+    auto Path = URI::resolve(*Uri, HintPath);
+    if (!Path) {
+      log("Type hierarchy: Could not resolve path for URI '{0}' for symbol "
+          "'{1}'.",
+          Uri->toString(), S.Name);
+      return;
+    }
+    THI.uri = URIForFile::canonicalize(*Path, HintPath);
+
+    Result = std::move(THI);
+  });
+  return Result;
+}
+
+static void fillSubTypes(const SymbolID &ID,
+                         std::vector<TypeHierarchyItem> &SubTypes,
+                         const SymbolIndex *Index, int Levels) {
+  Index->relations(ID, RelationKind::Subtype,
+                   [Index, Levels, &SubTypes](const SymbolID &Sub) {
+                     if (Optional<TypeHierarchyItem> ChildSym =
+                             symbolIDToTypeHierarchyItem(Sub, Index)) {
+                       if (Levels > 1) {
+                         ChildSym->children.emplace();
+                         fillSubTypes(Sub, *ChildSym->children, Index,
+                                      Levels - 1);
+                       }
+                       SubTypes.emplace_back(std::move(*ChildSym));
+                     }
+                   });
+}
+
 static Optional<TypeHierarchyItem> getTypeAncestors(const CXXRecordDecl &CXXRD,
                                                     ASTContext &ASTCtx) {
   Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
@@ -885,7 +944,6 @@
       Result->parents->emplace_back(std::move(*ParentSym));
     }
   }
-
   return Result;
 }
 
@@ -950,15 +1008,26 @@
 
 llvm::Optional<TypeHierarchyItem>
 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
-                 TypeHierarchyDirection Direction) {
+                 TypeHierarchyDirection Direction, const SymbolIndex *Index) {
   const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
   if (!CXXRD)
     return llvm::None;
 
   Optional<TypeHierarchyItem> Result =
       getTypeAncestors(*CXXRD, AST.getASTContext());
-  // TODO: Resolve type descendants if direction is Children or Both,
-  //       and ResolveLevels > 0.
+
+  if ((Direction == TypeHierarchyDirection::Children ||
+       Direction == TypeHierarchyDirection::Both) &&
+      ResolveLevels > 0) {
+    Result->children.emplace();
+
+    if (Index) {
+      if (Optional<SymbolID> ID = getSymbolID(CXXRD)) {
+        fillSubTypes(*ID, *Result->children, Index, ResolveLevels);
+      }
+    }
+  }
+
   return Result;
 }
 
diff --git a/clang-tools-extra/clangd/index/Background.cpp b/clang-tools-extra/clangd/index/Background.cpp
--- a/clang-tools-extra/clangd/index/Background.cpp
+++ b/clang-tools-extra/clangd/index/Background.cpp
@@ -316,12 +316,14 @@
     llvm::StringRef Path = FileIt.getKey();
     SymbolSlab::Builder Syms;
     RefSlab::Builder Refs;
+    RelationSlab::Builder Relations; // TODO: Populate.
     for (const auto *S : FileIt.second.Symbols)
       Syms.insert(*S);
     for (const auto *R : FileIt.second.Refs)
       Refs.insert(RefToIDs[R], *R);
     auto SS = llvm::make_unique<SymbolSlab>(std::move(Syms).build());
     auto RS = llvm::make_unique<RefSlab>(std::move(Refs).build());
+    auto RelS = llvm::make_unique<RelationSlab>(std::move(Relations).build());
     auto IG = llvm::make_unique<IncludeGraph>(
         getSubGraph(URI::create(Path), Index.Sources.getValue()));
     // We need to store shards before updating the index, since the latter
@@ -330,6 +332,7 @@
       IndexFileOut Shard;
       Shard.Symbols = SS.get();
       Shard.Refs = RS.get();
+      Shard.Relations = RelS.get();
       Shard.Sources = IG.get();
 
       if (auto Error = IndexStorage->storeShard(Path, Shard))
@@ -347,7 +350,8 @@
       // This can override a newer version that is added in another thread, if
       // this thread sees the older version but finishes later. This should be
       // rare in practice.
-      IndexedSymbols.update(Path, std::move(SS), std::move(RS));
+      IndexedSymbols.update(Path, std::move(SS), std::move(RS),
+                            std::move(RelS));
     }
   }
 }
@@ -557,8 +561,13 @@
       auto RS = SI.Shard->Refs
                     ? llvm::make_unique<RefSlab>(std::move(*SI.Shard->Refs))
                     : nullptr;
+      auto RelS =
+          SI.Shard->Relations
+              ? llvm::make_unique<RelationSlab>(std::move(*SI.Shard->Relations))
+              : nullptr;
       IndexedFileDigests[SI.AbsolutePath] = SI.Digest;
-      IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS));
+      IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS),
+                            std::move(RelS));
     }
   }
 
diff --git a/clang-tools-extra/clangd/index/FileIndex.h b/clang-tools-extra/clangd/index/FileIndex.h
--- a/clang-tools-extra/clangd/index/FileIndex.h
+++ b/clang-tools-extra/clangd/index/FileIndex.h
@@ -60,7 +60,8 @@
   /// Updates all symbols and refs in a file.
   /// If either is nullptr, corresponding data for \p Path will be removed.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
-              std::unique_ptr<RefSlab> Refs);
+              std::unique_ptr<RefSlab> Refs,
+              std::unique_ptr<RelationSlab> Relations);
 
   // The index keeps the symbols alive.
   std::unique_ptr<SymbolIndex>
@@ -74,6 +75,8 @@
   llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSymbols;
   /// Stores the latest ref snapshots for all active files.
   llvm::StringMap<std::shared_ptr<RefSlab>> FileToRefs;
+  /// Stores the latest relation snapshots for all active files.
+  llvm::StringMap<std::shared_ptr<RelationSlab>> FileToRelations;
 };
 
 /// This manages symbols from files and an in-memory index on all symbols.
@@ -119,10 +122,12 @@
   SwapIndex MainFileIndex;
 };
 
+using SlabTuple = std::tuple<SymbolSlab, RefSlab, RelationSlab>;
+
 /// Retrieves symbols and refs of local top level decls in \p AST (i.e.
 /// `AST.getLocalTopLevelDecls()`).
 /// Exposed to assist in unit tests.
-std::pair<SymbolSlab, RefSlab> indexMainDecls(ParsedAST &AST);
+SlabTuple indexMainDecls(ParsedAST &AST);
 
 /// Idex declarations from \p AST and macros from \p PP that are declared in
 /// included headers.
diff --git a/clang-tools-extra/clangd/index/FileIndex.cpp b/clang-tools-extra/clangd/index/FileIndex.cpp
--- a/clang-tools-extra/clangd/index/FileIndex.cpp
+++ b/clang-tools-extra/clangd/index/FileIndex.cpp
@@ -27,10 +27,10 @@
 namespace clang {
 namespace clangd {
 
-static std::pair<SymbolSlab, RefSlab>
-indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
-             llvm::ArrayRef<Decl *> DeclsToIndex,
-             const CanonicalIncludes &Includes, bool IsIndexMainAST) {
+static SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+                              llvm::ArrayRef<Decl *> DeclsToIndex,
+                              const CanonicalIncludes &Includes,
+                              bool IsIndexMainAST) {
   SymbolCollector::Options CollectorOpts;
   CollectorOpts.CollectIncludePath = true;
   CollectorOpts.Includes = &Includes;
@@ -64,15 +64,18 @@
 
   auto Syms = Collector.takeSymbols();
   auto Refs = Collector.takeRefs();
+  auto Relations = Collector.takeRelations();
   vlog("index AST for {0} (main={1}): \n"
        "  symbol slab: {2} symbols, {3} bytes\n"
-       "  ref slab: {4} symbols, {5} refs, {6} bytes",
+       "  ref slab: {4} symbols, {5} refs, {6} bytes\n"
+       "  relations slab: {7} symbols, {8} relations, {9} bytes",
        FileName, IsIndexMainAST, Syms.size(), Syms.bytes(), Refs.size(),
-       Refs.numRefs(), Refs.bytes());
-  return {std::move(Syms), std::move(Refs)};
+       Refs.numRefs(), Refs.bytes(), Relations.size(), Relations.numRelations(),
+       Relations.bytes());
+  return {std::move(Syms), std::move(Refs), std::move(Relations)};
 }
 
-std::pair<SymbolSlab, RefSlab> indexMainDecls(ParsedAST &AST) {
+SlabTuple indexMainDecls(ParsedAST &AST) {
   return indexSymbols(AST.getASTContext(), AST.getPreprocessorPtr(),
                       AST.getLocalTopLevelDecls(), AST.getCanonicalIncludes(),
                       /*IsIndexMainAST=*/true);
@@ -83,13 +86,13 @@
   std::vector<Decl *> DeclsToIndex(
       AST.getTranslationUnitDecl()->decls().begin(),
       AST.getTranslationUnitDecl()->decls().end());
-  return indexSymbols(AST, std::move(PP), DeclsToIndex, Includes,
-                      /*IsIndexMainAST=*/false)
-      .first;
+  return std::get<0>(indexSymbols(AST, std::move(PP), DeclsToIndex, Includes,
+                                  /*IsIndexMainAST=*/false));
 }
 
 void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols,
-                         std::unique_ptr<RefSlab> Refs) {
+                         std::unique_ptr<RefSlab> Refs,
+                         std::unique_ptr<RelationSlab> Relations) {
   std::lock_guard<std::mutex> Lock(Mutex);
   if (!Symbols)
     FileToSymbols.erase(Path);
@@ -99,18 +102,25 @@
     FileToRefs.erase(Path);
   else
     FileToRefs[Path] = std::move(Refs);
+  if (!Relations)
+    FileToRelations.erase(Path);
+  else
+    FileToRelations[Path] = std::move(Relations);
 }
 
 std::unique_ptr<SymbolIndex>
 FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle) {
   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
+  std::vector<std::shared_ptr<RelationSlab>> RelationSlabs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto &FileAndSymbols : FileToSymbols)
       SymbolSlabs.push_back(FileAndSymbols.second);
     for (const auto &FileAndRefs : FileToRefs)
       RefSlabs.push_back(FileAndRefs.second);
+    for (const auto &FileAndRelations : FileToRelations)
+      RelationSlabs.push_back(FileAndRelations.second);
   }
   std::vector<const Symbol *> AllSymbols;
   std::vector<Symbol> SymsStorage;
@@ -166,20 +176,51 @@
     }
   }
 
+  std::vector<SymbolID>
+      RelationsStorage; // Continguous ranges for each RelationKey.
+  llvm::DenseMap<RelationKey, llvm::ArrayRef<SymbolID>> AllRelations;
+  {
+    llvm::DenseMap<RelationKey, llvm::SmallVector<SymbolID, 4>> MergedRelations;
+    size_t Count = 0;
+    for (const auto &RelationSlab : RelationSlabs) {
+      for (const auto &E : *RelationSlab) {
+        MergedRelations[E.first].append(E.second.begin(), E.second.end());
+        Count += E.second.size();
+      }
+    }
+    RelationsStorage.reserve(Count);
+    AllRelations.reserve(MergedRelations.size());
+    for (auto &E : MergedRelations) {
+      auto &Relations = E.second;
+      // Sorting isn't required, but yields more stable results over rebuilds.
+      llvm::sort(Relations);
+      llvm::copy(Relations, back_inserter(RelationsStorage));
+      AllRelations.try_emplace(
+          E.first,
+          llvm::ArrayRef<SymbolID>(
+              &RelationsStorage[RelationsStorage.size() - Relations.size()],
+              Relations.size()));
+    }
+  }
+
   size_t StorageSize =
       RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
   for (const auto &Slab : SymbolSlabs)
     StorageSize += Slab->bytes();
   for (const auto &RefSlab : RefSlabs)
     StorageSize += RefSlab->bytes();
+  for (const auto &RelationSlab : RelationSlabs)
+    StorageSize += RelationSlab->bytes();
 
   // Index must keep the slabs and contiguous ranges alive.
   switch (Type) {
   case IndexType::Light:
     return llvm::make_unique<MemIndex>(
         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
+        std::move(AllRelations),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
-                        std::move(RefsStorage), std::move(SymsStorage)),
+                        std::move(RelationSlabs), std::move(RefsStorage),
+                        std::move(SymsStorage), std::move(RelationsStorage)),
         StorageSize);
   case IndexType::Heavy:
     return llvm::make_unique<dex::Dex>(
@@ -200,9 +241,9 @@
                                std::shared_ptr<Preprocessor> PP,
                                const CanonicalIncludes &Includes) {
   auto Symbols = indexHeaderSymbols(AST, std::move(PP), Includes);
-  PreambleSymbols.update(Path,
-                         llvm::make_unique<SymbolSlab>(std::move(Symbols)),
-                         llvm::make_unique<RefSlab>());
+  PreambleSymbols.update(
+      Path, llvm::make_unique<SymbolSlab>(std::move(Symbols)),
+      llvm::make_unique<RefSlab>(), llvm::make_unique<RelationSlab>());
   PreambleIndex.reset(
       PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
                                  DuplicateHandling::PickOne));
@@ -211,8 +252,9 @@
 void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
   auto Contents = indexMainDecls(AST);
   MainFileSymbols.update(
-      Path, llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
-      llvm::make_unique<RefSlab>(std::move(Contents.second)));
+      Path, llvm::make_unique<SymbolSlab>(std::move(std::get<0>(Contents))),
+      llvm::make_unique<RefSlab>(std::move(std::get<1>(Contents))),
+      llvm::make_unique<RelationSlab>(std::move(std::get<2>(Contents))));
   MainFileIndex.reset(
       MainFileSymbols.buildIndex(IndexType::Light, DuplicateHandling::PickOne));
 }
diff --git a/clang-tools-extra/clangd/index/Index.h b/clang-tools-extra/clangd/index/Index.h
--- a/clang-tools-extra/clangd/index/Index.h
+++ b/clang-tools-extra/clangd/index/Index.h
@@ -43,9 +43,7 @@
     void setColumn(uint32_t Column);
     uint32_t column() const { return Column; }
 
-    bool hasOverflow() const {
-      return Line >= MaxLine || Column >= MaxColumn;
-    }
+    bool hasOverflow() const { return Line >= MaxLine || Column >= MaxColumn; }
 
     static constexpr uint32_t MaxLine = (1 << 20) - 1;
     static constexpr uint32_t MaxColumn = (1 << 12) - 1;
@@ -247,11 +245,13 @@
   SymbolFlag Flags = SymbolFlag::None;
   /// FIXME: also add deprecation message and fixit?
 };
-inline Symbol::SymbolFlag  operator|(Symbol::SymbolFlag A, Symbol::SymbolFlag  B) {
+inline Symbol::SymbolFlag operator|(Symbol::SymbolFlag A,
+                                    Symbol::SymbolFlag B) {
   return static_cast<Symbol::SymbolFlag>(static_cast<uint8_t>(A) |
                                          static_cast<uint8_t>(B));
 }
-inline Symbol::SymbolFlag &operator|=(Symbol::SymbolFlag &A, Symbol::SymbolFlag B) {
+inline Symbol::SymbolFlag &operator|=(Symbol::SymbolFlag &A,
+                                      Symbol::SymbolFlag B) {
   return A = A | B;
 }
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
@@ -432,6 +432,71 @@
   size_t NumRefs = 0;
 };
 
+enum class RelationKind { Subtype };
+
+struct RelationKey {
+  SymbolID Symbol;
+  RelationKind Kind;
+
+  bool operator==(const RelationKey &Other) const {
+    return Symbol == Other.Symbol && Kind == Other.Kind;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const RelationKey &Key) {
+    return llvm::hash_combine(Key.Symbol, static_cast<int>(Key.Kind));
+  }
+};
+
+class RelationSlab {
+public:
+  using value_type = std::pair<RelationKey, llvm::ArrayRef<SymbolID>>;
+  using const_iterator = std::vector<value_type>::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &&Slab) = default;
+  RelationSlab &operator=(RelationSlab &&RHS) = default;
+
+  const_iterator begin() const { return Relations.begin(); }
+  const_iterator end() const { return Relations.end(); }
+  size_t size() const { return Relations.size(); }
+  size_t numRelations() const { return NumRelations; }
+  bool empty() const { return Relations.empty(); }
+
+  size_t bytes() const {
+    return sizeof(*this) + Arena.getTotalMemory() +
+           sizeof(value_type) * Relations.size();
+  }
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.
+  class Builder {
+  public:
+    Builder() {}
+    // Adds a relation to the slab. Deep copy: Strings will be owned by the
+    // slab.
+    void insert(const RelationKey &Key, const SymbolID &S);
+    // Consumes the builder to finalize the slab.
+    RelationSlab build() &&;
+
+  private:
+    llvm::BumpPtrAllocator Arena;
+    llvm::DenseMap<RelationKey, std::vector<SymbolID>> Relations;
+  };
+
+private:
+  RelationSlab(std::vector<value_type> Relations, llvm::BumpPtrAllocator Arena,
+               size_t NumRelations)
+      : Arena(std::move(Arena)), Relations(std::move(Relations)),
+        NumRelations(NumRelations) {}
+
+  llvm::BumpPtrAllocator Arena;
+  std::vector<value_type> Relations;
+  // Number of all relations.
+  size_t NumRelations = 0;
+};
+
 struct FuzzyFindRequest {
   /// \brief A query string for the fuzzy find. This is matched against symbols'
   /// un-qualified identifiers and should not contain qualifiers like "::".
@@ -512,6 +577,10 @@
   virtual void refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
+  virtual void
+  relations(const SymbolID &ID, RelationKind Kind,
+            llvm::function_ref<void(const SymbolID &)> Callback) const = 0;
+
   /// Returns estimated size of index (in bytes).
   // FIXME(kbobyrev): Currently, this only returns the size of index itself
   // excluding the size of actual symbol slab index refers to. We should include
@@ -535,6 +604,9 @@
               llvm::function_ref<void(const Symbol &)>) const override;
   void refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  void relations(const SymbolID &, RelationKind,
+                 llvm::function_ref<void(const SymbolID &)>) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
@@ -546,4 +618,30 @@
 } // namespace clangd
 } // namespace clang
 
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::RelationKey> {
+  static inline clang::clangd::RelationKey getEmptyKey() {
+    return {DenseMapInfo<clang::clangd::SymbolID>::getEmptyKey(),
+            clang::clangd::RelationKind::Subtype};
+  }
+
+  static inline clang::clangd::RelationKey getTombstoneKey() {
+    return {DenseMapInfo<clang::clangd::SymbolID>::getTombstoneKey(),
+            clang::clangd::RelationKind::Subtype};
+  }
+
+  static unsigned getHashValue(const clang::clangd::RelationKey &Key) {
+    return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::clangd::RelationKey &LHS,
+                      const clang::clangd::RelationKey &RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
diff --git a/clang-tools-extra/clangd/index/Index.cpp b/clang-tools-extra/clangd/index/Index.cpp
--- a/clang-tools-extra/clangd/index/Index.cpp
+++ b/clang-tools-extra/clangd/index/Index.cpp
@@ -158,6 +158,28 @@
   return RefSlab(std::move(Result), std::move(Arena), NumRefs);
 }
 
+void RelationSlab::Builder::insert(const RelationKey &Key, const SymbolID &S) {
+  Relations[Key].push_back(S);
+}
+
+RelationSlab RelationSlab::Builder::build() && {
+  // Reallocate relations on the arena to reduce waste and indirections when
+  // reading.
+  std::vector<std::pair<RelationKey, llvm::ArrayRef<SymbolID>>> Result;
+  Result.reserve(Relations.size());
+  size_t NumRelations = 0;
+  for (auto &Entry : Relations) {
+    auto &Rels = Entry.second;
+
+    NumRelations += Rels.size();
+    auto *Array = Arena.Allocate<SymbolID>(Rels.size());
+    std::uninitialized_copy(Rels.begin(), Rels.end(), Array);
+    Result.emplace_back(Entry.first,
+                        llvm::ArrayRef<SymbolID>(Array, Rels.size()));
+  }
+  return RelationSlab(std::move(Result), std::move(Arena), NumRelations);
+}
+
 void SwapIndex::reset(std::unique_ptr<SymbolIndex> Index) {
   // Keep the old index alive, so we don't destroy it under lock (may be slow).
   std::shared_ptr<SymbolIndex> Pin;
@@ -210,6 +232,11 @@
                      llvm::function_ref<void(const Ref &)> CB) const {
   return snapshot()->refs(R, CB);
 }
+void SwapIndex::relations(const SymbolID &ID, RelationKind Kind,
+                          llvm::function_ref<void(const SymbolID &)> CB) const {
+  return snapshot()->relations(ID, Kind, CB);
+}
+
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
diff --git a/clang-tools-extra/clangd/index/MemIndex.h b/clang-tools-extra/clangd/index/MemIndex.h
--- a/clang-tools-extra/clangd/index/MemIndex.h
+++ b/clang-tools-extra/clangd/index/MemIndex.h
@@ -20,26 +20,31 @@
 public:
   MemIndex() = default;
   // All symbols and refs must outlive this index.
-  template <typename SymbolRange, typename RefRange>
-  MemIndex(SymbolRange &&Symbols, RefRange &&Refs) {
+  template <typename SymbolRange, typename RefRange, typename RelationRange>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations) {
     for (const Symbol &S : Symbols)
       Index[S.ID] = &S;
     for (const std::pair<SymbolID, llvm::ArrayRef<Ref>> &R : Refs)
       this->Refs.try_emplace(R.first, R.second.begin(), R.second.end());
+    for (const std::pair<RelationKey, llvm::ArrayRef<SymbolID>> &R : Relations)
+      this->Relations.try_emplace(R.first, R.second.begin(), R.second.end());
   }
   // Symbols are owned by BackingData, Index takes ownership.
-  template <typename SymbolRange, typename RefRange, typename Payload>
-  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, Payload &&BackingData,
-           size_t BackingDataSize)
+  template <typename SymbolRange, typename RefRange, typename RelationRange,
+            typename Payload>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
+           Payload &&BackingData, size_t BackingDataSize)
       : MemIndex(std::forward<SymbolRange>(Symbols),
-                 std::forward<RefRange>(Refs)) {
+                 std::forward<RefRange>(Refs),
+                 std::forward<RelationRange>(Relations)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
     this->BackingDataSize = BackingDataSize;
   }
 
   /// Builds an index from slabs. The index takes ownership of the data.
-  static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs);
+  static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs,
+                                            RelationSlab Relations);
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
@@ -51,6 +56,10 @@
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  void
+  relations(const SymbolID &ID, RelationKind Kind,
+            llvm::function_ref<void(const SymbolID &)> Callback) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
@@ -58,6 +67,7 @@
   llvm::DenseMap<SymbolID, const Symbol *> Index;
   // A map from symbol ID to symbol refs, support query by IDs.
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
+  llvm::DenseMap<RelationKey, llvm::ArrayRef<SymbolID>> Relations;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
diff --git a/clang-tools-extra/clangd/index/MemIndex.cpp b/clang-tools-extra/clangd/index/MemIndex.cpp
--- a/clang-tools-extra/clangd/index/MemIndex.cpp
+++ b/clang-tools-extra/clangd/index/MemIndex.cpp
@@ -15,11 +15,14 @@
 namespace clang {
 namespace clangd {
 
-std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
+std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
+                                             RelationSlab Relations) {
   // Store Slab size before it is moved.
   const auto BackingDataSize = Slab.bytes() + Refs.bytes();
-  auto Data = std::make_pair(std::move(Slab), std::move(Refs));
-  return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data),
+  auto Data =
+      std::make_tuple(std::move(Slab), std::move(Refs), std::move(Relations));
+  return llvm::make_unique<MemIndex>(std::get<0>(Data), std::get<1>(Data),
+                                     std::get<2>(Data), std::move(Data),
                                      BackingDataSize);
 }
 
@@ -83,6 +86,17 @@
   }
 }
 
+void MemIndex::relations(
+    const SymbolID &ID, RelationKind Kind,
+    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  auto Rels = Relations.find({ID, Kind});
+  if (Rels == Relations.end())
+    return;
+  for (const auto &S : Rels->second) {
+    Callback(S);
+  }
+}
+
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
 }
diff --git a/clang-tools-extra/clangd/index/Merge.h b/clang-tools-extra/clangd/index/Merge.h
--- a/clang-tools-extra/clangd/index/Merge.h
+++ b/clang-tools-extra/clangd/index/Merge.h
@@ -42,6 +42,8 @@
               llvm::function_ref<void(const Symbol &)>) const override;
   void refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  void relations(const SymbolID &, RelationKind,
+                 llvm::function_ref<void(const SymbolID &)>) const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
diff --git a/clang-tools-extra/clangd/index/Merge.cpp b/clang-tools-extra/clangd/index/Merge.cpp
--- a/clang-tools-extra/clangd/index/Merge.cpp
+++ b/clang-tools-extra/clangd/index/Merge.cpp
@@ -118,6 +118,14 @@
   });
 }
 
+void MergedIndex::relations(
+    const SymbolID &ID, RelationKind Kind,
+    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  // TODO: Implement properly.
+  Static->relations(ID, Kind, Callback);
+  Dynamic->relations(ID, Kind, Callback);
+}
+
 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If
 // neither is preferred, this returns false.
 bool prefer(const SymbolLocation &L, const SymbolLocation &R) {
diff --git a/clang-tools-extra/clangd/index/Serialization.h b/clang-tools-extra/clangd/index/Serialization.h
--- a/clang-tools-extra/clangd/index/Serialization.h
+++ b/clang-tools-extra/clangd/index/Serialization.h
@@ -39,6 +39,7 @@
 struct IndexFileIn {
   llvm::Optional<SymbolSlab> Symbols;
   llvm::Optional<RefSlab> Refs;
+  llvm::Optional<RelationSlab> Relations;
   // Keys are URIs of the source files.
   llvm::Optional<IncludeGraph> Sources;
 };
@@ -49,6 +50,7 @@
 struct IndexFileOut {
   const SymbolSlab *Symbols = nullptr;
   const RefSlab *Refs = nullptr;
+  const RelationSlab *Relations = nullptr;
   // Keys are URIs of the source files.
   const IncludeGraph *Sources = nullptr;
   // TODO: Support serializing Dex posting lists.
@@ -57,7 +59,8 @@
   IndexFileOut() = default;
   IndexFileOut(const IndexFileIn &I)
       : Symbols(I.Symbols ? I.Symbols.getPointer() : nullptr),
-        Refs(I.Refs ? I.Refs.getPointer() : nullptr) {}
+        Refs(I.Refs ? I.Refs.getPointer() : nullptr),
+        Relations(I.Relations ? I.Relations.getPointer() : nullptr) {}
 };
 // Serializes an index file.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const IndexFileOut &O);
diff --git a/clang-tools-extra/clangd/index/Serialization.cpp b/clang-tools-extra/clangd/index/Serialization.cpp
--- a/clang-tools-extra/clangd/index/Serialization.cpp
+++ b/clang-tools-extra/clangd/index/Serialization.cpp
@@ -558,6 +558,7 @@
 
   SymbolSlab Symbols;
   RefSlab Refs;
+  RelationSlab Relations; // TODO: Populate.
   {
     trace::Span Tracer("ParseIndex");
     if (auto I = readIndexFile(Buffer->get()->getBuffer())) {
@@ -565,6 +566,8 @@
         Symbols = std::move(*I->Symbols);
       if (I->Refs)
         Refs = std::move(*I->Refs);
+      if (I->Relations)
+        Relations = std::move(*I->Relations);
     } else {
       llvm::errs() << "Bad Index: " << llvm::toString(I.takeError()) << "\n";
       return nullptr;
@@ -573,15 +576,18 @@
 
   size_t NumSym = Symbols.size();
   size_t NumRefs = Refs.numRefs();
+  size_t NumRelations = Relations.numRelations();
 
   trace::Span Tracer("BuildIndex");
   auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs))
-                      : MemIndex::build(std::move(Symbols), std::move(Refs));
+                      : MemIndex::build(std::move(Symbols), std::move(Refs),
+                                        std::move(Relations));
   vlog("Loaded {0} from {1} with estimated memory usage {2} bytes\n"
        "  - number of symbols: {3}\n"
-       "  - number of refs: {4}\n",
+       "  - number of refs: {4}\n"
+       "  - numnber of relations: {5}",
        UseDex ? "Dex" : "MemIndex", SymbolFilename,
-       Index->estimateMemoryUsage(), NumSym, NumRefs);
+       Index->estimateMemoryUsage(), NumSym, NumRefs, NumRelations);
   return Index;
 }
 
diff --git a/clang-tools-extra/clangd/index/SymbolCollector.h b/clang-tools-extra/clangd/index/SymbolCollector.h
--- a/clang-tools-extra/clangd/index/SymbolCollector.h
+++ b/clang-tools-extra/clangd/index/SymbolCollector.h
@@ -108,11 +108,13 @@
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
   RefSlab takeRefs() { return std::move(Refs).build(); }
+  RelationSlab takeRelations() { return std::move(Relations).build(); }
 
   void finish() override;
 
 private:
-  const Symbol *addDeclaration(const NamedDecl &, SymbolID, bool IsMainFileSymbol);
+  const Symbol *addDeclaration(const NamedDecl &, SymbolID,
+                               bool IsMainFileSymbol);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
 
   // All Symbols collected from the AST.
@@ -121,6 +123,8 @@
   // Only symbols declared in preamble (from #include) and referenced from the
   // main file will be included.
   RefSlab::Builder Refs;
+  // All relations collected from the AST.
+  RelationSlab::Builder Relations;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
diff --git a/clang-tools-extra/clangd/index/SymbolCollector.cpp b/clang-tools-extra/clangd/index/SymbolCollector.cpp
--- a/clang-tools-extra/clangd/index/SymbolCollector.cpp
+++ b/clang-tools-extra/clangd/index/SymbolCollector.cpp
@@ -14,6 +14,7 @@
 #include "Logger.h"
 #include "SourceCode.h"
 #include "URI.h"
+#include "XRefs.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
@@ -201,7 +202,7 @@
 // the first seen declaration as canonical declaration is not a good enough
 // heuristic.
 bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) {
-  const auto& SM = ND.getASTContext().getSourceManager();
+  const auto &SM = ND.getASTContext().getSourceManager();
   return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
          isa<TagDecl>(&ND) &&
          !SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getLocation()));
@@ -323,8 +324,8 @@
 
   // ND is the canonical (i.e. first) declaration. If it's in the main file,
   // then no public declaration was visible, so assume it's main-file only.
-  bool IsMainFileOnly = SM.isWrittenInMainFile(SM.getExpansionLoc(
-    ND->getBeginLoc()));
+  bool IsMainFileOnly =
+      SM.isWrittenInMainFile(SM.getExpansionLoc(ND->getBeginLoc()));
   if (!shouldCollectSymbol(*ND, *ASTCtx, Opts, IsMainFileOnly))
     return true;
   // Do not store references to main-file symbols.
@@ -513,8 +514,7 @@
   FilesToIndexCache.clear();
 }
 
-const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
-                                              SymbolID ID,
+const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
                                               bool IsMainFileOnly) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
@@ -612,6 +612,19 @@
           getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.Definition = *DefLoc;
   Symbols.insert(S);
+
+  // Store subtype relations.
+  const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(&ND);
+  if (!RD)
+    return;
+  for (const Decl *Parent : typeParents(RD)) {
+    if (auto ID = getSymbolID(Parent)) {
+      // We are a subtype to each of our parents.
+      llvm::errs() << "Recording subtype relationship from " << *ID << " to "
+                   << S.ID << "\n";
+      Relations.insert({*ID, RelationKind::Subtype}, S.ID);
+    }
+  }
 }
 
 } // namespace clangd
diff --git a/clang-tools-extra/clangd/index/YAMLSerialization.cpp b/clang-tools-extra/clangd/index/YAMLSerialization.cpp
--- a/clang-tools-extra/clangd/index/YAMLSerialization.cpp
+++ b/clang-tools-extra/clangd/index/YAMLSerialization.cpp
@@ -29,14 +29,18 @@
 
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol::IncludeHeaderWithReferences)
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Ref)
+LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::SymbolID)
 
 namespace {
 using RefBundle =
     std::pair<clang::clangd::SymbolID, std::vector<clang::clangd::Ref>>;
+using RelationBundle =
+    std::pair<clang::clangd::RelationKey, std::vector<clang::clangd::SymbolID>>;
 // This is a pale imitation of std::variant<Symbol, RefBundle>
 struct VariantEntry {
   llvm::Optional<clang::clangd::Symbol> Symbol;
   llvm::Optional<RefBundle> Refs;
+  llvm::Optional<RelationBundle> Relations;
 };
 // A class helps YAML to serialize the 32-bit encoded position (Line&Column),
 // as YAMLIO can't directly map bitfields.
@@ -51,6 +55,7 @@
 
 using clang::clangd::Ref;
 using clang::clangd::RefKind;
+using clang::clangd::RelationKind;
 using clang::clangd::Symbol;
 using clang::clangd::SymbolID;
 using clang::clangd::SymbolLocation;
@@ -271,6 +276,34 @@
   }
 };
 
+struct NormalizedRelationKind {
+  NormalizedRelationKind(IO &) {}
+  NormalizedRelationKind(IO &, RelationKind O) {
+    Kind = static_cast<uint8_t>(O);
+  }
+
+  RelationKind denormalize(IO &) { return static_cast<RelationKind>(Kind); }
+
+  uint8_t Kind = 0;
+};
+
+template <> struct MappingTraits<SymbolID> {
+  static void mapping(IO &IO, SymbolID &ID) {
+    MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(IO, ID);
+    IO.mapRequired("ID", NSymbolID->HexString);
+  }
+};
+
+template <> struct MappingTraits<RelationBundle> {
+  static void mapping(IO &IO, RelationBundle &Relations) {
+    MappingNormalization<NormalizedRelationKind, RelationKind> NKind(
+        IO, Relations.first.Kind);
+    IO.mapRequired("Symbol", Relations.first.Symbol);
+    IO.mapRequired("Kind", NKind->Kind);
+    IO.mapRequired("Relations", Relations.second);
+  }
+};
+
 template <> struct MappingTraits<VariantEntry> {
   static void mapping(IO &IO, VariantEntry &Variant) {
     if (IO.mapTag("!Symbol", Variant.Symbol.hasValue())) {
@@ -281,6 +314,10 @@
       if (!IO.outputting())
         Variant.Refs.emplace();
       MappingTraits<RefBundle>::mapping(IO, *Variant.Refs);
+    } else if (IO.mapTag("!Relations", Variant.Relations.hasValue())) {
+      if (!IO.outputting())
+        Variant.Relations.emplace();
+      MappingTraits<RelationBundle>::mapping(IO, *Variant.Relations);
     }
   }
 };
@@ -304,11 +341,18 @@
       Entry.Refs = Sym;
       Yout << Entry;
     }
+  if (O.Relations)
+    for (auto &E : *O.Relations) {
+      VariantEntry Entry;
+      Entry.Relations = E;
+      Yout << Entry;
+    }
 }
 
 llvm::Expected<IndexFileIn> readYAML(llvm::StringRef Data) {
   SymbolSlab::Builder Symbols;
   RefSlab::Builder Refs;
+  RelationSlab::Builder Relations;
   llvm::BumpPtrAllocator
       Arena; // store the underlying data of Position::FileURI.
   llvm::UniqueStringSaver Strings(Arena);
@@ -325,12 +369,16 @@
     if (Variant.Refs)
       for (const auto &Ref : Variant.Refs->second)
         Refs.insert(Variant.Refs->first, Ref);
+    if (Variant.Relations)
+      for (const auto &Relation : Variant.Relations->second)
+        Relations.insert(Variant.Relations->first, Relation);
     Yin.nextDocument();
   }
 
   IndexFileIn Result;
   Result.Symbols.emplace(std::move(Symbols).build());
   Result.Refs.emplace(std::move(Refs).build());
+  Result.Relations.emplace(std::move(Relations).build());
   return std::move(Result);
 }
 
diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h
--- a/clang-tools-extra/clangd/index/dex/Dex.h
+++ b/clang-tools-extra/clangd/index/dex/Dex.h
@@ -72,6 +72,10 @@
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  void
+  relations(const SymbolID &ID, RelationKind Kind,
+            llvm::function_ref<void(const SymbolID &)> Callback) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
diff --git a/clang-tools-extra/clangd/index/dex/Dex.cpp b/clang-tools-extra/clangd/index/dex/Dex.cpp
--- a/clang-tools-extra/clangd/index/dex/Dex.cpp
+++ b/clang-tools-extra/clangd/index/dex/Dex.cpp
@@ -259,6 +259,11 @@
     }
 }
 
+void Dex::relations(const SymbolID &ID, RelationKind Kind,
+                    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  // TODO: Implement.
+}
+
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
diff --git a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
--- a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
+++ b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
@@ -85,7 +85,7 @@
   SymbolSlab::Builder Slab;
   for (const auto &Sym : Symbols)
     Slab.insert(Sym);
-  return MemIndex::build(std::move(Slab).build(), RefSlab());
+  return MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
 }
 
 CodeCompleteResult completions(ClangdServer &Server, llvm::StringRef TestCode,
@@ -999,6 +999,9 @@
   void refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override {}
 
+  void relations(const SymbolID &, RelationKind,
+                 llvm::function_ref<void(const SymbolID &)>) const override {}
+
   // This is incorrect, but IndexRequestCollector is not an actual index and it
   // isn't used in production code.
   size_t estimateMemoryUsage() const override { return 0; }
diff --git a/clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp b/clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
--- a/clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
+++ b/clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
@@ -71,7 +71,6 @@
   return true;
 }
 
-
 // Helper function to make tests shorter.
 Position pos(int line, int character) {
   Position Res;
@@ -316,7 +315,7 @@
     Sym.IncludeHeaders.emplace_back(S.IncludeHeader, 1);
     Slab.insert(Sym);
   }
-  return MemIndex::build(std::move(Slab).build(), RefSlab());
+  return MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
 }
 
 TEST(IncludeFixerTest, IncompleteType) {
@@ -372,7 +371,8 @@
 
   SymbolSlab::Builder Slab;
   Slab.insert(Sym);
-  auto Index = MemIndex::build(std::move(Slab).build(), RefSlab());
+  auto Index =
+      MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(TU.build().getDiagnostics(),
@@ -589,4 +589,3 @@
 } // namespace
 } // namespace clangd
 } // namespace clang
-
diff --git a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp
--- a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp
+++ b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp
@@ -82,7 +82,7 @@
   FileSymbols FS;
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty());
 
-  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"));
+  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"), nullptr);
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*FS.buildIndex(IndexType::Light), SymbolID("1")),
@@ -91,8 +91,8 @@
 
 TEST(FileSymbolsTest, Overlap) {
   FileSymbols FS;
-  FS.update("f1", numSlab(1, 3), nullptr);
-  FS.update("f2", numSlab(3, 5), nullptr);
+  FS.update("f1", numSlab(1, 3), nullptr, nullptr);
+  FS.update("f2", numSlab(3, 5), nullptr, nullptr);
   for (auto Type : {IndexType::Light, IndexType::Heavy})
     EXPECT_THAT(runFuzzyFind(*FS.buildIndex(Type), ""),
                 UnorderedElementsAre(QName("1"), QName("2"), QName("3"),
@@ -111,8 +111,8 @@
   auto X2 = symbol("x");
   X2.Definition.FileURI = "file:///x2";
 
-  FS.update("f1", OneSymboSlab(X1), nullptr);
-  FS.update("f2", OneSymboSlab(X2), nullptr);
+  FS.update("f1", OneSymboSlab(X1), nullptr, nullptr);
+  FS.update("f2", OneSymboSlab(X2), nullptr, nullptr);
   for (auto Type : {IndexType::Light, IndexType::Heavy})
     EXPECT_THAT(
         runFuzzyFind(*FS.buildIndex(Type, DuplicateHandling::Merge), "x"),
@@ -124,14 +124,14 @@
   FileSymbols FS;
 
   SymbolID ID("1");
-  FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"));
+  FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"), nullptr);
 
   auto Symbols = FS.buildIndex(IndexType::Light);
   EXPECT_THAT(runFuzzyFind(*Symbols, ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")}));
 
-  FS.update("f1", nullptr, nullptr);
+  FS.update("f1", nullptr, nullptr, nullptr);
   auto Empty = FS.buildIndex(IndexType::Light);
   EXPECT_THAT(runFuzzyFind(*Empty, ""), IsEmpty());
   EXPECT_THAT(getRefs(*Empty, ID), ElementsAre());
diff --git a/clang-tools-extra/unittests/clangd/IndexTests.cpp b/clang-tools-extra/unittests/clangd/IndexTests.cpp
--- a/clang-tools-extra/unittests/clangd/IndexTests.cpp
+++ b/clang-tools-extra/unittests/clangd/IndexTests.cpp
@@ -77,8 +77,9 @@
   auto Token = std::make_shared<int>();
   std::weak_ptr<int> WeakToken = Token;
 
-  SwapIndex S(llvm::make_unique<MemIndex>(
-      SymbolSlab(), RefSlab(), std::move(Token), /*BackingDataSize=*/0));
+  SwapIndex S(llvm::make_unique<MemIndex>(SymbolSlab(), RefSlab(),
+                                          RelationSlab(), std::move(Token),
+                                          /*BackingDataSize=*/0));
   EXPECT_FALSE(WeakToken.expired());      // Current MemIndex keeps it alive.
   S.reset(llvm::make_unique<MemIndex>()); // Now the MemIndex is destroyed.
   EXPECT_TRUE(WeakToken.expired());       // So the token is too.
@@ -90,12 +91,13 @@
   FuzzyFindRequest Req;
   Req.Query = "2";
   Req.AnyScope = true;
-  MemIndex I(Symbols, RefSlab());
+  MemIndex I(Symbols, RefSlab(), RelationSlab());
   EXPECT_THAT(match(I, Req), ElementsAre("2"));
 }
 
 TEST(MemIndexTest, MemIndexLimitedNumMatches) {
-  auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab());
+  auto I =
+      MemIndex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.AnyScope = true;
@@ -110,7 +112,7 @@
 TEST(MemIndexTest, FuzzyMatch) {
   auto I = MemIndex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      RefSlab());
+      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.AnyScope = true;
@@ -120,8 +122,8 @@
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
-  auto I =
-      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.AnyScope = true;
@@ -129,8 +131,8 @@
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
-  auto I =
-      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
@@ -139,7 +141,8 @@
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   auto I = MemIndex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab(),
+      RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
@@ -148,7 +151,8 @@
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   auto I = MemIndex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab(),
+      RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::", "b::"};
@@ -156,7 +160,8 @@
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
-  auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
@@ -164,7 +169,8 @@
 }
 
 TEST(MemIndexTest, IgnoreCases) {
-  auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns::"};
@@ -172,7 +178,8 @@
 }
 
 TEST(MemIndexTest, Lookup) {
-  auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(),
+                           RelationSlab());
   EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::abc", "ns::xyz"));
@@ -182,8 +189,10 @@
 }
 
 TEST(MergeIndexTest, Lookup) {
-  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
+                           RelationSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
+                           RelationSlab());
   MergedIndex M(I.get(), J.get());
   EXPECT_THAT(lookup(M, SymbolID("ns::A")), UnorderedElementsAre("ns::A"));
   EXPECT_THAT(lookup(M, SymbolID("ns::B")), UnorderedElementsAre("ns::B"));
@@ -197,8 +206,10 @@
 }
 
 TEST(MergeIndexTest, FuzzyFind) {
-  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
+                           RelationSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req),
diff --git a/clang-tools-extra/unittests/clangd/TestTU.cpp b/clang-tools-extra/unittests/clangd/TestTU.cpp
--- a/clang-tools-extra/unittests/clangd/TestTU.cpp
+++ b/clang-tools-extra/unittests/clangd/TestTU.cpp
@@ -65,7 +65,9 @@
 
 std::unique_ptr<SymbolIndex> TestTU::index() const {
   auto AST = build();
-  auto Idx = llvm::make_unique<FileIndex>(/*UseDex=*/true);
+  // UseDex is temporarily set to false so we can test subtypes support
+  // before implementing it in Dex.
+  auto Idx = llvm::make_unique<FileIndex>(/*UseDex=*/false);
   Idx->updatePreamble(Filename, AST.getASTContext(), AST.getPreprocessorPtr(),
                       AST.getCanonicalIncludes());
   Idx->updateMain(Filename, AST);
diff --git a/clang-tools-extra/unittests/clangd/XRefsTests.cpp b/clang-tools-extra/unittests/clangd/XRefsTests.cpp
--- a/clang-tools-extra/unittests/clangd/XRefsTests.cpp
+++ b/clang-tools-extra/unittests/clangd/XRefsTests.cpp
@@ -1759,6 +1759,87 @@
   EXPECT_THAT(typeParents(Child3), ElementsAre());
 }
 
+SymbolID findSymbolIDByName(llvm::StringRef Name, SymbolIndex *Index) {
+  SymbolID Result;
+  FuzzyFindRequest Request;
+  Request.Query = Name;
+  Request.AnyScope = true;
+  Request.Limit = 1;
+  int ResultCount = 0;
+  Index->fuzzyFind(Request, [&](const Symbol &S) {
+    Result = S.ID;
+    ++ResultCount;
+  });
+  EXPECT_EQ(1, ResultCount);
+  return Result;
+}
+
+std::vector<SymbolID> collectSubtypes(SymbolID Type, SymbolIndex *Index) {
+  std::vector<SymbolID> Result;
+  llvm::errs() << "Querying subtypes of " << Type << "\n";
+  Index->relations(Type, RelationKind::Subtype,
+                   [&Result](const SymbolID &ID) { Result.push_back(ID); });
+  return Result;
+}
+
+TEST(Subtypes, SimpleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent {
+  int a;
+};
+
+struct Child1 : Parent {
+  int b;
+};
+
+struct Child2 : Child1 {
+  int c;
+};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+  SymbolID Child1 = findSymbolIDByName("Child1", Index.get());
+  SymbolID Child2 = findSymbolIDByName("Child2", Index.get());
+
+  EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child1));
+  EXPECT_THAT(collectSubtypes(Child1, Index.get()), ElementsAre(Child2));
+}
+
+TEST(Subtypes, MultipleInheritance) {
+  Annotations Source(R"cpp(
+struct Parent1 {
+  int a;
+};
+
+struct Parent2 {
+  int b;
+};
+
+struct Parent3 : Parent2 {
+  int c;
+};
+
+struct Child : Parent1, Parent3 {
+  int d;
+};
+)cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto Index = TU.index();
+
+  SymbolID Parent1 = findSymbolIDByName("Parent1", Index.get());
+  SymbolID Parent2 = findSymbolIDByName("Parent2", Index.get());
+  SymbolID Parent3 = findSymbolIDByName("Parent3", Index.get());
+  SymbolID Child = findSymbolIDByName("Child", Index.get());
+
+  EXPECT_THAT(collectSubtypes(Parent1, Index.get()), ElementsAre(Child));
+  EXPECT_THAT(collectSubtypes(Parent2, Index.get()), ElementsAre(Parent3));
+  EXPECT_THAT(collectSubtypes(Parent3, Index.get()), ElementsAre(Child));
+}
+
 // Parts of getTypeHierarchy() are tested in more detail by the
 // FindRecordTypeAt.* and TypeParents.* tests above. This test exercises the
 // entire operation.