diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
index a4ca49e..86cf3d2 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
@@ -487,6 +487,25 @@
     assertThat(nc.getOriginalSubject()).isEqualTo(orig);
   }
 
+  @Test
+  public void deleteDraftPS1WithNoOtherEntities() throws Exception {
+    PushOneCommit push = pushFactory.create(db, admin.getIdent(), testRepo);
+    PushOneCommit.Result r = push.to("refs/drafts/master");
+    push = pushFactory.create(db, admin.getIdent(), testRepo,
+        PushOneCommit.SUBJECT, "b.txt", "4711", r.getChangeId());
+    r = push.to("refs/drafts/master");
+    PatchSet.Id psId = r.getPatchSetId();
+    Change.Id id = psId.getParentKey();
+
+    gApi.changes().id(r.getChangeId()).revision(1).delete();
+
+    checker.rebuildAndCheckChanges(id);
+
+    notesMigration.setAllEnabled(true);
+    ChangeNotes notes = notesFactory.create(db, project, id);
+    assertThat(notes.getPatchSets().keySet()).containsExactly(psId);
+  }
+
   private void setInvalidNoteDbState(Change.Id id) throws Exception {
     ReviewDb db = unwrapDb();
     Change c = db.changes().get(id);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeBundle.java b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeBundle.java
index 8660f42..b80b683 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeBundle.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeBundle.java
@@ -14,6 +14,7 @@
 
 package com.google.gerrit.server.notedb;
 
+import static com.google.common.base.MoreObjects.firstNonNull;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
@@ -28,6 +29,7 @@
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.LinkedListMultimap;
 import com.google.common.collect.Lists;
@@ -150,8 +152,8 @@
   }
 
 
-  private static Map<PatchSet.Id, PatchSet> patchSetMap(Iterable<PatchSet> in) {
-    Map<PatchSet.Id, PatchSet> out = new TreeMap<>(
+  private static TreeMap<PatchSet.Id, PatchSet> patchSetMap(Iterable<PatchSet> in) {
+    TreeMap<PatchSet.Id, PatchSet> out = new TreeMap<>(
         new Comparator<PatchSet.Id>() {
           @Override
           public int compare(PatchSet.Id a, PatchSet.Id b) {
@@ -244,7 +246,7 @@
 
   private final Change change;
   private final ImmutableList<ChangeMessage> changeMessages;
-  private final ImmutableMap<PatchSet.Id, PatchSet> patchSets;
+  private final ImmutableSortedMap<PatchSet.Id, PatchSet> patchSets;
   private final ImmutableMap<PatchSetApproval.Key, PatchSetApproval>
       patchSetApprovals;
   private final ImmutableMap<PatchLineComment.Key, PatchLineComment>
@@ -260,7 +262,7 @@
       Source source) {
     this.change = checkNotNull(change);
     this.changeMessages = changeMessageList(changeMessages);
-    this.patchSets = ImmutableMap.copyOf(patchSetMap(patchSets));
+    this.patchSets = ImmutableSortedMap.copyOfSorted(patchSetMap(patchSets));
     this.patchSetApprovals =
         ImmutableMap.copyOf(patchSetApprovalMap(patchSetApprovals));
     this.patchLineComments =
@@ -316,9 +318,16 @@
     return ImmutableList.copyOf(diffs);
   }
 
+  private Timestamp getFirstPatchSetTime() {
+    if (patchSets.isEmpty()) {
+      return change.getCreatedOn();
+    }
+    return patchSets.firstEntry().getValue().getCreatedOn();
+  }
+
   private Timestamp getLatestTimestamp() {
-    Ordering<Timestamp> o = Ordering.natural();
-    Timestamp ts = change.getLastUpdatedOn();
+    Ordering<Timestamp> o = Ordering.natural().nullsFirst();
+    Timestamp ts = null;
     for (ChangeMessage cm : getChangeMessages()) {
       ts = o.max(ts, cm.getWrittenOn());
     }
@@ -334,7 +343,7 @@
         ts = o.max(ts, plc.getWrittenOn());
       }
     }
-    return ts;
+    return firstNonNull(ts, change.getLastUpdatedOn());
   }
 
   private static void diffChanges(List<String> diffs, ChangeBundle bundleA,
@@ -343,13 +352,16 @@
     Change b = bundleB.change;
     String desc = a.getId().equals(b.getId()) ? describe(a.getId()) : "Changes";
 
+    boolean excludeCreatedOn = false;
     boolean excludeSubject = false;
     boolean excludeOrigSubj = false;
     boolean excludeTopic = false;
     Timestamp aUpdated = a.getLastUpdatedOn();
     Timestamp bUpdated = b.getLastUpdatedOn();
 
-
+    // Allow created timestamp in NoteDb to be either the created timestamp of
+    // the change, or the timestamp of the first remaining patch set.
+    //
     // Ignore subject if the NoteDb subject starts with the ReviewDb subject.
     // The NoteDb subject is read directly from the commit, whereas the ReviewDb
     // subject historically may have been truncated to fit in a SQL varchar
@@ -376,11 +388,15 @@
     //
     // Use max timestamp of all ReviewDb entities when comparing with NoteDb.
     if (bundleA.source == REVIEW_DB && bundleB.source == NOTE_DB) {
+      excludeCreatedOn = !timestampsDiffer(
+          bundleA, bundleA.getFirstPatchSetTime(), bundleB, b.getCreatedOn());
       excludeSubject = b.getSubject().startsWith(a.getSubject());
       excludeOrigSubj = true;
       excludeTopic = "".equals(a.getTopic()) && b.getTopic() == null;
       aUpdated = bundleA.getLatestTimestamp();
     } else if (bundleA.source == NOTE_DB && bundleB.source == REVIEW_DB) {
+      excludeCreatedOn = !timestampsDiffer(
+          bundleA, a.getCreatedOn(), bundleB, bundleB.getFirstPatchSetTime());
       excludeSubject = a.getSubject().startsWith(b.getSubject());
       excludeOrigSubj = true;
       excludeTopic = a.getTopic() == null && "".equals(b.getTopic());
@@ -390,6 +406,9 @@
     String updatedField = "lastUpdatedOn";
     List<String> exclude =
         Lists.newArrayList(updatedField, "noteDbState", "rowVersion");
+    if (excludeCreatedOn) {
+      exclude.add("createdOn");
+    }
     if (excludeSubject) {
       exclude.add("subject");
     }
@@ -402,9 +421,9 @@
     diffColumnsExcluding(diffs, Change.class, desc, bundleA, a, bundleB, b,
         exclude);
 
-    // Allow timestamps to either be exactly equal (within slop), or the NoteDb
-    // timestamp to be equal to the latest entity timestamp in the whole
-    // ReviewDb bundle (within slop).
+    // Allow last updated timestamps to either be exactly equal (within slop),
+    // or the NoteDb timestamp to be equal to the latest entity timestamp in the
+    // whole ReviewDb bundle (within slop).
     if (timestampsDiffer(bundleA, a.getLastUpdatedOn(),
           bundleB, b.getLastUpdatedOn())) {
       diffTimestamps(diffs, desc, bundleA, aUpdated, bundleB, bUpdated,
diff --git a/gerrit-server/src/test/java/com/google/gerrit/server/notedb/ChangeBundleTest.java b/gerrit-server/src/test/java/com/google/gerrit/server/notedb/ChangeBundleTest.java
index 7baaec6..03747e5 100644
--- a/gerrit-server/src/test/java/com/google/gerrit/server/notedb/ChangeBundleTest.java
+++ b/gerrit-server/src/test/java/com/google/gerrit/server/notedb/ChangeBundleTest.java
@@ -294,6 +294,41 @@
   }
 
   @Test
+  public void diffChangesIgnoresChangeTimestampIfAnyOtherEntitiesExist() {
+    Change c1 = TestChanges.newChange(
+        new Project.NameKey("project"), new Account.Id(100));
+    PatchSetApproval a = new PatchSetApproval(
+        new PatchSetApproval.Key(
+            c1.currentPatchSetId(), accountId, new LabelId("Code-Review")),
+        (short) 1,
+        TimeUtil.nowTs());
+    c1.setLastUpdatedOn(a.getGranted());
+
+    Change c2 = clone(c1);
+    c2.setLastUpdatedOn(TimeUtil.nowTs());
+
+    // ReviewDb has later lastUpdatedOn timestamp than NoteDb, allowed since
+    // NoteDb matches the latest timestamp of a non-Change entity.
+    ChangeBundle b1 = new ChangeBundle(c2, messages(), patchSets(),
+        approvals(a), comments(), REVIEW_DB);
+    ChangeBundle b2 = new ChangeBundle(c1, messages(), patchSets(),
+        approvals(a), comments(), NOTE_DB);
+    assertThat(b1.getChange().getLastUpdatedOn())
+        .isGreaterThan(b2.getChange().getLastUpdatedOn());
+    assertNoDiffs(b1, b2);
+
+    // Timestamps must actually match if Change is the only entity.
+    b1 = new ChangeBundle(c2, messages(), patchSets(), approvals(), comments(),
+        REVIEW_DB);
+    b2 = new ChangeBundle(c1, messages(), patchSets(), approvals(), comments(),
+        NOTE_DB);
+    assertDiffs(b1, b2,
+        "effective last updated time differs for Change.Id " + c1.getId()
+            + " in NoteDb vs. ReviewDb:"
+            + " {2009-09-30 17:00:06.0} != {2009-09-30 17:00:12.0}");
+  }
+
+  @Test
   public void diffChangesAllowsReviewDbSubjectToBePrefixOfNoteDbSubject()
       throws Exception {
     Change c1 = TestChanges.newChange(