title: How to improve the performance of traversing a large dataset
body: <p>I want to improve the logic for my task that is defined as following, the tasks is implemented in Python 3 with Django framwork:</p>
  <p>The source data is onboard to our system, the Job entity defines what involves to fully process a source,
  Job_instance defines the instance of Job. The requirement is as following:</p>
  <ol>
  <li>Given the source name, find the latest onboard date that has all jobs of the source being processed.</li>
  <li>Also output the overall status of job being processed</li>
  </ol>
  <p>The entity relationship and table structure:</p>
  <ol>
  <li>&quot;Job&quot; - this is an entity defines what involves to process a source ingested from external party. a source is divided into parts that can be processed into multiple jobs. table structure:</li>
  </ol>
  <div class="s-table-container">
  <table class="s-table">
  <thead>
  <tr>
  <th>Field name</th>
  <th>description</th>
  <th>type</th>
  </tr>
  </thead>
  <tbody>
  <tr>
  <td>id</td>
  <td>id of job</td>
  <td>int</td>
  </tr>
  <tr>
  <td>name</td>
  <td>name of job</td>
  <td>string</td>
  </tr>
  <tr>
  <td>source</td>
  <td>name of source</td>
  <td>string</td>
  </tr>
  </tbody>
  </table>
  </div>
  <ol start="2">
  <li>&quot;Job_instance&quot; - this is instance of the job that has been executed in our system.</li>
  </ol>
  <div class="s-table-container">
  <table class="s-table">
  <thead>
  <tr>
  <th>Field name</th>
  <th>description</th>
  <th>type</th>
  </tr>
  </thead>
  <tbody>
  <tr>
  <td>id</td>
  <td>id of job instance</td>
  <td>int</td>
  </tr>
  <tr>
  <td>job_id</td>
  <td>id of job</td>
  <td>int</td>
  </tr>
  <tr>
  <td>period</td>
  <td>date string the source has been onboard to our system</td>
  <td>string</td>
  </tr>
  <tr>
  <td>updated_timestamp</td>
  <td>last execution time and date for the job</td>
  <td>timestamp</td>
  </tr>
  <tr>
  <td>status</td>
  <td>the status of the instance after run has been proceeded, can be one of any, e.g: success, failed, finished, created etc</td>
  <td>string</td>
  </tr>
  </tbody>
  </table>
  </div>
  <p>The overall status of jobs processed shows as &quot;Success&quot; when all the job_instance of each job running successfully, otherwise it shows as &quot;Failure&quot;</p>
  <p>My current logic:</p>
  <ol>
  <li><p>Get list of jobs from source name and cached job_ids with boolean as a map.</p>
  <pre><code>job_ids = Job.objects.filter(Q(name__icontains=source)
  ).values_list('id', flat=True)
  
  &quot;&quot;&quot; Combine all Job Ids into one restriction &quot;&quot;&quot;
  &quot;&quot;&quot; Constructing where clause to match all job ids &quot;&quot;&quot;
  ids_filter = Q()
  for job_id in job_ids:
      ids_filter = ids_filter | Q(job__id=job_id)
  </code></pre>
  </li>
  <li><p>Get list of job instances from job ids and sort it by period and update_timestamp in descending order( this is done from database)</p>
  <pre><code>completed_status_filter = Q()
  &quot;&quot;&quot; Only check job instances that have been completed &quot;&quot;&quot;
  for status in [status_dict.get('Failed'), status_dict.get('Finished')]:
      completed_status_filter = completed_status_filter | Q(
          status__exact=status)
  
  &quot;&quot;&quot; Find Finished or Failed job instances for job ids &quot;&quot;&quot;
  &quot;&quot;&quot; and sort by period_code and updated timestamp by decending order &quot;&quot;&quot;
  job_instances = JobInstance.objects \
      .filter(ids_filter, completed_status_filter) \
      .values('id', 'job__id', 'period_code', 'update_timestamp', 'status') \
      .exclude(period_code='Ad Hoc') \
      .order_by('-period_code', '-update_timestamp')
  </code></pre>
  </li>
  <li><p>Created a period to list of job_instances map.</p>
  <pre><code>def get_period_code_instances_map(self, job_instances):
      period_code_instance_map = {}
      for instance in job_instances.iterator():
         instances =period_code_instance_map.get(instance['period_code'])
         if not instances:
           existing_instances = list()
           period_code_instance_map[instance['period_code']] \
              = existing_instances
          existing_instances.append(instance)
         else:
          instances.append(instance)
  
     return period_code_instance_map
  </code></pre>
  </li>
  <li><p>Traversing the map as following:</p>
  <pre><code>def get_last_period_code_at_curated(
      self, period_code_instances_map, job_ids, status_dict):
  
  target_period = None
  job_ids_verification_map = dict((key, False) for key in job_ids)
  &quot;&quot;&quot; Traverse instances ran on the same period_code &quot;&quot;&quot;
  for period_code, instances in period_code_instances_map.items():
      for instance in instances:
          job_id = instance['job__id']
          &quot;&quot;&quot; Set to True if job has not been visited&quot;&quot;&quot;
          if not job_ids_verification_map.get(job_id):
              job_ids_verification_map[job_id] = True
  
      &quot;&quot;&quot; If job id has not been visited after traversing &quot;&quot;&quot;
      &quot;&quot;&quot; reset job_id verifcation map &quot;&quot;&quot;
      if any(not checked for checked in job_ids_verification_map.values()):
          job_ids_verification_map = dict(
              (key, False) for key in job_ids)
      else:
          target_period = period_code
          break
  
  result = JobInstanceLatestPeriodCodeForSource()
  if not target_period:
      return result
  
  &quot;&quot;&quot; Once period_code is found, get the timestamp from 1st instance &quot;&quot;&quot;
  &quot;&quot;&quot; Evaluate status by check all statuses in instances &quot;&quot;&quot;
  instances = period_code_instances_map[target_period]
  result.period_code = target_period
  result.update_timestamp = instances[0]['update_timestamp']
  failed_status = status_dict.get('Failed')
  if any(instance['status'] == failed_status for instance in instances):
      result.status = 'Failed'
  else:
      result.status = 'Finished'
  
  return result
  </code></pre>
  <p>a. Iterate all job instance in the period to find if all jobs have been run. Here i used the job_id and boolean map to track which job has been visited for the period.</p>
  <p>b. If all jobs have been run in the period, then the period is found. otherwise, keep traversing the map.</p>
  </li>
  <li><p>When period is found, iterate the job instance list from the map again to find the overall status.</p>
  </li>
  </ol>
  <p>Limitation:</p>
  <ul>
  <li>Since the list of job_instances can be quite big( &gt; 1 million entries), I have used iterator to create the map when going through data from database. But any optimization suggestion is welcome.</li>
  <li>Is there any more efficient way on time/space to find the period code. I found i have to use nested for loop to traversing, which gives me O(n2).</li>
  </ul>
  <p>Thanks in advance</p>