diff --git a/frontend/afe/rpc_interface.py b/frontend/afe/rpc_interface.py
index aa575b6..39c3c98 100644
--- a/frontend/afe/rpc_interface.py
+++ b/frontend/afe/rpc_interface.py
@@ -1185,6 +1185,48 @@
     return image
 
 
+def get_host_queue_entries_by_insert_time(
+    insert_time_after=None, insert_time_before=None, **filter_data):
+    """Like get_host_queue_entries, but using the insert index table.
+
+    @param insert_time_after: A lower bound on insert_time
+    @param insert_time_before: An upper bound on insert_time
+    @returns A sequence of nested dictionaries of host and job information.
+    """
+    assert insert_time_after is not None or insert_time_before is not None, \
+      ('Caller to get_host_queue_entries_by_insert_time must provide either'
+       ' insert_time_after or insert_time_before.')
+    # Get insert bounds on the index of the host queue entries.
+    if insert_time_after:
+        query = models.HostQueueEntryStartTimes.objects.filter(
+            # Note: '-insert_time' means descending. We want the largest
+            # insert time smaller than the insert time.
+            insert_time__lte=insert_time_after).order_by('-insert_time')
+        try:
+            constraint = query[0].highest_hqe_id
+            if 'id__gte' in filter_data:
+                constraint = max(constraint, filter_data['id__gte'])
+            filter_data['id__gte'] = constraint
+        except IndexError:
+            pass
+
+    # Get end bounds.
+    if insert_time_before:
+        query = models.HostQueueEntryStartTimes.objects.filter(
+            insert_time__gte=insert_time_before).order_by('insert_time')
+        try:
+            constraint = query[0].highest_hqe_id
+            if 'id__lte' in filter_data:
+                constraint = min(constraint, filter_data['id__lte'])
+            filter_data['id__lte'] = constraint
+        except IndexError:
+            pass
+
+    return rpc_utils.prepare_rows_as_nested_dicts(
+            models.HostQueueEntry.query_objects(filter_data),
+            ('host', 'job'))
+
+
 def get_host_queue_entries(start_time=None, end_time=None, **filter_data):
     """\
     @returns A sequence of nested dictionaries of host and job information.
diff --git a/frontend/afe/rpc_interface_unittest.py b/frontend/afe/rpc_interface_unittest.py
index b2b8881..8ff9cbd 100755
--- a/frontend/afe/rpc_interface_unittest.py
+++ b/frontend/afe/rpc_interface_unittest.py
@@ -323,6 +323,89 @@
         self.assertEquals(entry2['started_on'], '2009-01-03 00:00:00')
 
 
+    def _create_hqes_and_start_time_index_entries(self):
+        shard = models.Shard.objects.create(hostname='shard')
+        job = self._create_job(shard=shard, control_file='foo')
+        HqeStatus = models.HostQueueEntry.Status
+
+        models.HostQueueEntry(
+            id=1, job=job, started_on='2017-01-01',
+            status=HqeStatus.QUEUED).save()
+        models.HostQueueEntry(
+            id=2, job=job, started_on='2017-01-02',
+            status=HqeStatus.QUEUED).save()
+        models.HostQueueEntry(
+            id=3, job=job, started_on='2017-01-03',
+            status=HqeStatus.QUEUED).save()
+
+        models.HostQueueEntryStartTimes(
+            insert_time='2017-01-03', highest_hqe_id=3).save()
+        models.HostQueueEntryStartTimes(
+            insert_time='2017-01-02', highest_hqe_id=2).save()
+        models.HostQueueEntryStartTimes(
+            insert_time='2017-01-01', highest_hqe_id=1).save()
+
+    def test_get_host_queue_entries_by_insert_time(self):
+        """Check the insert_time_after and insert_time_before constraints."""
+        self._create_hqes_and_start_time_index_entries()
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_after='2017-01-01')
+        self.assertEquals(len(hqes), 3)
+
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_after='2017-01-02')
+        self.assertEquals(len(hqes), 2)
+
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_after='2017-01-03')
+        self.assertEquals(len(hqes), 1)
+
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-01')
+        self.assertEquals(len(hqes), 1)
+
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-02')
+        self.assertEquals(len(hqes), 2)
+
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-03')
+        self.assertEquals(len(hqes), 3)
+
+
+    def test_get_host_queue_entries_by_insert_time_with_missing_index_row(self):
+        """Shows that the constraints are approximate.
+
+        The query may return rows which are actually outside of the bounds
+        given, if the index table does not have an entry for the specific time.
+        """
+        self._create_hqes_and_start_time_index_entries()
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2016-12-01')
+        self.assertEquals(len(hqes), 1)
+
+    def test_get_hqe_by_insert_time_with_before_and_after(self):
+        self._create_hqes_and_start_time_index_entries()
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-02',
+            insert_time_after='2017-01-02')
+        self.assertEquals(len(hqes), 1)
+
+    def test_get_hqe_by_insert_time_and_id_constraint(self):
+        self._create_hqes_and_start_time_index_entries()
+        # The time constraint is looser than the id constraint, so the time
+        # constraint should take precedence.
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-02',
+            id__lte=1)
+        self.assertEquals(len(hqes), 1)
+
+        # Now make the time constraint tighter than the id constraint.
+        hqes = rpc_interface.get_host_queue_entries_by_insert_time(
+            insert_time_before='2017-01-01',
+            id__lte=42)
+        self.assertEquals(len(hqes), 1)
+
     def test_view_invalid_host(self):
         # RPCs used by View Host page should work for invalid hosts
         self._create_job_helper(hosts=[1])