diff --git a/Android.bp b/Android.bp
index bfd01ac..dcabf2e 100644
--- a/Android.bp
+++ b/Android.bp
@@ -9410,6 +9410,18 @@
 // GN: //src/trace_processor/db/overlays:overlays
 filegroup {
     name: "perfetto_src_trace_processor_db_overlays_overlays",
+    srcs: [
+        "src/trace_processor/db/overlays/null_overlay.cc",
+        "src/trace_processor/db/overlays/storage_overlay.cc",
+    ],
+}
+
+// GN: //src/trace_processor/db/overlays:unittests
+filegroup {
+    name: "perfetto_src_trace_processor_db_overlays_unittests",
+    srcs: [
+        "src/trace_processor/db/overlays/null_overlay_unittest.cc",
+    ],
 }
 
 // GN: //src/trace_processor/db/storage:storage
@@ -12064,6 +12076,7 @@
         ":perfetto_src_trace_processor_containers_unittests",
         ":perfetto_src_trace_processor_db_db",
         ":perfetto_src_trace_processor_db_overlays_overlays",
+        ":perfetto_src_trace_processor_db_overlays_unittests",
         ":perfetto_src_trace_processor_db_storage_storage",
         ":perfetto_src_trace_processor_db_storage_unittests",
         ":perfetto_src_trace_processor_db_unittests",
diff --git a/BUILD b/BUILD
index 5e43586..f9a1035 100644
--- a/BUILD
+++ b/BUILD
@@ -1277,6 +1277,9 @@
 perfetto_filegroup(
     name = "src_trace_processor_db_overlays_overlays",
     srcs = [
+        "src/trace_processor/db/overlays/null_overlay.cc",
+        "src/trace_processor/db/overlays/null_overlay.h",
+        "src/trace_processor/db/overlays/storage_overlay.cc",
         "src/trace_processor/db/overlays/storage_overlay.h",
         "src/trace_processor/db/overlays/types.h",
     ],
diff --git a/protos/perfetto/common/trace_stats.proto b/protos/perfetto/common/trace_stats.proto
index 4e6d455..bbee8f9 100644
--- a/protos/perfetto/common/trace_stats.proto
+++ b/protos/perfetto/common/trace_stats.proto
@@ -20,7 +20,7 @@
 
 // Statistics for the internals of the tracing service.
 //
-// Next id: 17.
+// Next id: 19.
 message TraceStats {
   // From TraceBuffer::Stats.
   //
diff --git a/protos/perfetto/trace/perfetto_trace.proto b/protos/perfetto/trace/perfetto_trace.proto
index e886311..1681cd9 100644
--- a/protos/perfetto/trace/perfetto_trace.proto
+++ b/protos/perfetto/trace/perfetto_trace.proto
@@ -3240,7 +3240,7 @@
 
 // Statistics for the internals of the tracing service.
 //
-// Next id: 17.
+// Next id: 19.
 message TraceStats {
   // From TraceBuffer::Stats.
   //
diff --git a/src/tools/proto_merger/proto_file_serializer.cc b/src/tools/proto_merger/proto_file_serializer.cc
index dca5a07..c94a101 100644
--- a/src/tools/proto_merger/proto_file_serializer.cc
+++ b/src/tools/proto_merger/proto_file_serializer.cc
@@ -70,8 +70,11 @@
 
   std::string output;
   output += " [";
-  for (const auto& option : options) {
-    output += option.key + " = " + option.value;
+  size_t n = options.size();
+  for (size_t i = 0; i < n; i++) {
+    output += options[i].key + " = " + options[i].value;
+    if (i != n - 1)
+      output += ", ";
   }
   output += "]";
   return output;
diff --git a/src/trace_processor/BUILD.gn b/src/trace_processor/BUILD.gn
index 6ff25a9..04814a6 100644
--- a/src/trace_processor/BUILD.gn
+++ b/src/trace_processor/BUILD.gn
@@ -268,6 +268,7 @@
     ":top_level_unittests",
     "containers:unittests",
     "db:unittests",
+    "db/overlays:unittests",
     "db/storage:unittests",
     "importers/android_bugreport:unittests",
     "importers/common:unittests",
diff --git a/src/trace_processor/db/overlays/BUILD.gn b/src/trace_processor/db/overlays/BUILD.gn
index c1d50d8..f0b3e72 100644
--- a/src/trace_processor/db/overlays/BUILD.gn
+++ b/src/trace_processor/db/overlays/BUILD.gn
@@ -12,13 +12,30 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+import("../../../../gn/perfetto_tp_tables.gni")
+import("../../../../gn/test.gni")
+
 source_set("overlays") {
   sources = [
+    "null_overlay.cc",
+    "null_overlay.h",
+    "storage_overlay.cc",
     "storage_overlay.h",
     "types.h",
   ]
   deps = [
     "../../../../gn:default_deps",
+    "../../../base",
     "../../containers",
   ]
 }
+
+perfetto_unittest_source_set("unittests") {
+  testonly = true
+  sources = [ "null_overlay_unittest.cc" ]
+  deps = [
+    ":overlays",
+    "../../../../gn:default_deps",
+    "../../../../gn:gtest_and_gmock",
+  ]
+}
diff --git a/src/trace_processor/db/overlays/null_overlay.cc b/src/trace_processor/db/overlays/null_overlay.cc
new file mode 100644
index 0000000..c5f5f66
--- /dev/null
+++ b/src/trace_processor/db/overlays/null_overlay.cc
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include "src/trace_processor/db/overlays/null_overlay.h"
+#include "perfetto/ext/base/flat_hash_map.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace overlays {
+
+using Range = RowMap::Range;
+
+StorageRange NullOverlay::MapToStorageRange(TableRange t_range) const {
+  uint32_t start = non_null_->CountSetBits(t_range.range.start);
+  uint32_t end = non_null_->CountSetBits(t_range.range.end);
+
+  return StorageRange({Range(start, end)});
+}
+
+TableBitVector NullOverlay::MapToTableBitVector(StorageBitVector s_bv) const {
+  BitVector res = non_null_->Copy();
+  res.UpdateSetBits(s_bv.bv);
+  return {std::move(res)};
+}
+
+BitVector NullOverlay::IsStorageLookupRequired(
+    OverlayOp op,
+    const TableIndexVector& t_iv) const {
+  PERFETTO_DCHECK(t_iv.indices.size() <= non_null_->size());
+
+  if (op != OverlayOp::kOther)
+    return BitVector();
+
+  BitVector in_storage(static_cast<uint32_t>(t_iv.indices.size()), false);
+
+  // For each index in TableIndexVector check whether this index is in storage.
+  for (uint32_t i = 0; i < t_iv.indices.size(); ++i) {
+    if (non_null_->IsSet(t_iv.indices[i]))
+      in_storage.Set(i);
+  }
+
+  return in_storage;
+}
+
+StorageIndexVector NullOverlay::MapToStorageIndexVector(
+    TableIndexVector t_iv_with_idx_in_storage) const {
+  PERFETTO_DCHECK(t_iv_with_idx_in_storage.indices.size() <=
+                  non_null_->CountSetBits());
+
+  std::vector<uint32_t> storage_index_vector;
+  storage_index_vector.reserve(t_iv_with_idx_in_storage.indices.size());
+  for (auto t_idx : t_iv_with_idx_in_storage.indices) {
+    storage_index_vector.push_back(non_null_->CountSetBits(t_idx));
+  }
+
+  return StorageIndexVector({std::move(storage_index_vector)});
+}
+
+BitVector NullOverlay::IndexSearch(
+    OverlayOp op,
+    const TableIndexVector& t_iv_overlay_idx) const {
+  if (op == OverlayOp::kOther)
+    return BitVector();
+
+  BitVector res(static_cast<uint32_t>(t_iv_overlay_idx.indices.size()), false);
+  if (op == OverlayOp::kIsNull) {
+    for (uint32_t i = 0; i < res.size(); ++i) {
+      if (!non_null_->IsSet(t_iv_overlay_idx.indices[i]))
+        res.Set(i);
+    }
+    return res;
+  }
+
+  PERFETTO_DCHECK(op == OverlayOp::kIsNotNull);
+  for (uint32_t i = 0; i < res.size(); ++i) {
+    if (non_null_->IsSet(t_iv_overlay_idx.indices[i]))
+      res.Set(i);
+  }
+  return res;
+}
+
+CostEstimatePerRow NullOverlay::EstimateCostPerRow(OverlayOp op) const {
+  // TODO(b/283763282): Replace with benchmarked data.
+  CostEstimatePerRow res;
+
+  // Two |BitVector::CountSetBits| calls.
+  res.to_storage_range = 100;
+
+  // Cost of |BitVector::UpdateSetBits|
+  res.to_table_bit_vector = 100;
+
+  if (op == OverlayOp::kOther) {
+    // Cost of |BitVector::IsSet| and |BitVector::Set|
+    res.is_storage_search_required = 10;
+
+    // Cost of iterating all set bits and looping the index vector divided by
+    // number of indices.
+    res.map_to_storage_index_vector = 100;
+
+    // Won't be called.
+    res.index_search = 0;
+  } else {
+    // Cost of creating trivial BitVector.
+    res.is_storage_search_required = 0;
+
+    // Won't be called
+    res.map_to_storage_index_vector = 0;
+
+    // Cost of calling |BitVector::IsSet|
+    res.index_search = 10;
+  }
+
+  return res;
+}
+
+}  // namespace overlays
+}  // namespace trace_processor
+}  // namespace perfetto
diff --git a/src/trace_processor/db/overlays/null_overlay.h b/src/trace_processor/db/overlays/null_overlay.h
new file mode 100644
index 0000000..93da2c0
--- /dev/null
+++ b/src/trace_processor/db/overlays/null_overlay.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_DB_OVERLAYS_NULL_OVERLAY_H_
+#define SRC_TRACE_PROCESSOR_DB_OVERLAYS_NULL_OVERLAY_H_
+
+#include "src/trace_processor/db/overlays/storage_overlay.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace overlays {
+
+// Introduces the layer of nullability - spreads out the storage with nulls
+// using BitVector.
+class NullOverlay : public StorageOverlay {
+ public:
+  explicit NullOverlay(BitVector* null) : non_null_(std::move(null)) {}
+
+  StorageRange MapToStorageRange(TableRange) const override;
+
+  TableBitVector MapToTableBitVector(StorageBitVector) const override;
+
+  BitVector IsStorageLookupRequired(OverlayOp,
+                                    const TableIndexVector&) const override;
+
+  StorageIndexVector MapToStorageIndexVector(TableIndexVector) const override;
+
+  BitVector IndexSearch(OverlayOp, const TableIndexVector&) const override;
+
+  CostEstimatePerRow EstimateCostPerRow(OverlayOp) const override;
+
+ private:
+  // Non null data in the overlay.
+  BitVector* non_null_;
+};
+
+}  // namespace overlays
+}  // namespace trace_processor
+}  // namespace perfetto
+
+#endif  // SRC_TRACE_PROCESSOR_DB_OVERLAYS_NULL_OVERLAY_H_
diff --git a/src/trace_processor/db/overlays/null_overlay_unittest.cc b/src/trace_processor/db/overlays/null_overlay_unittest.cc
new file mode 100644
index 0000000..6f80eba
--- /dev/null
+++ b/src/trace_processor/db/overlays/null_overlay_unittest.cc
@@ -0,0 +1,129 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include "src/trace_processor/db/overlays/null_overlay.h"
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace overlays {
+namespace {
+
+TEST(NullOverlay, MapToStorageRangeOutsideBoundary) {
+  BitVector bv{0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0};
+  NullOverlay overlay(&bv);
+  StorageRange r = overlay.MapToStorageRange({RowMap::Range(1, 6)});
+
+  ASSERT_EQ(r.range.start, 0u);
+  ASSERT_EQ(r.range.end, 2u);
+}
+
+TEST(NullOverlay, MapToStorageRangeOnBoundary) {
+  BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
+  NullOverlay overlay(&bv);
+  StorageRange r = overlay.MapToStorageRange({RowMap::Range(3, 8)});
+
+  ASSERT_EQ(r.range.start, 1u);
+  ASSERT_EQ(r.range.end, 4u);
+}
+
+TEST(NullOverlay, MapToTableBitVector) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  BitVector storage_bv{0, 1, 0, 1};
+  TableBitVector table_bv =
+      overlay.MapToTableBitVector({std::move(storage_bv)});
+
+  ASSERT_EQ(table_bv.bv.CountSetBits(), 2u);
+  ASSERT_TRUE(table_bv.bv.IsSet(2));
+  ASSERT_TRUE(table_bv.bv.IsSet(6));
+}
+
+TEST(NullOverlay, IsStorageLookupRequiredNullOp) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{0, 2, 4, 6};
+  BitVector lookup_bv =
+      overlay.IsStorageLookupRequired(OverlayOp::kIsNull, {table_idx});
+
+  ASSERT_EQ(lookup_bv.size(), 0u);
+}
+
+TEST(NullOverlay, IsStorageLookupRequiredOtherOp) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{0, 2, 4, 6};
+  BitVector lookup_bv =
+      overlay.IsStorageLookupRequired(OverlayOp::kOther, {table_idx});
+
+  ASSERT_EQ(lookup_bv.size(), 4u);
+  ASSERT_EQ(lookup_bv.CountSetBits(), 2u);
+  ASSERT_TRUE(lookup_bv.IsSet(1));
+  ASSERT_TRUE(lookup_bv.IsSet(3));
+}
+
+TEST(NullOverlay, MapToStorageIndexVector) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{1, 5, 2};
+  StorageIndexVector storage_iv = overlay.MapToStorageIndexVector({table_idx});
+
+  std::vector<uint32_t> res{0, 2, 1};
+  ASSERT_EQ(storage_iv.indices, res);
+}
+
+TEST(NullOverlay, IndexSearchOtherOp) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{0, 3, 4};
+  BitVector idx_search_bv = overlay.IndexSearch(OverlayOp::kOther, {table_idx});
+
+  ASSERT_EQ(idx_search_bv.size(), 0u);
+}
+
+TEST(NullOverlay, IndexSearchIsNullOp) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{0, 3, 4};
+  BitVector idx_search_bv =
+      overlay.IndexSearch(OverlayOp::kIsNull, {table_idx});
+
+  ASSERT_EQ(idx_search_bv.size(), 3u);
+  ASSERT_EQ(idx_search_bv.CountSetBits(), 3u);
+}
+
+TEST(NullOverlay, IndexSearchIsNotNullOp) {
+  BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
+  NullOverlay overlay(&bv);
+
+  std::vector<uint32_t> table_idx{0, 3, 4};
+  BitVector idx_search_bv =
+      overlay.IndexSearch(OverlayOp::kIsNotNull, {table_idx});
+
+  ASSERT_EQ(idx_search_bv.size(), 3u);
+  ASSERT_EQ(idx_search_bv.CountSetBits(), 0u);
+}
+
+}  // namespace
+}  // namespace overlays
+}  // namespace trace_processor
+}  // namespace perfetto
diff --git a/src/trace_processor/db/overlays/storage_overlay.cc b/src/trace_processor/db/overlays/storage_overlay.cc
new file mode 100644
index 0000000..56897f2
--- /dev/null
+++ b/src/trace_processor/db/overlays/storage_overlay.cc
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include "src/trace_processor/db/overlays/storage_overlay.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace overlays {
+
+StorageOverlay::~StorageOverlay() = default;
+
+}  // namespace overlays
+}  // namespace trace_processor
+}  // namespace perfetto