title: BigQuery - nest operations within partition in order to aggregate consecutive records from a table with 17 billion records
body: <p>I'm pretty new to SQL and BigQuery, and have been slamming my head against the wall trying to figure out a feasible solution to this problem for a week now. The two solutions that I've got don't scale.</p>
  
  <p><strong>Background</strong></p>
  
  <p>Have a BigQuery table with 17 Billion records. Each record represents one device ping. Each records contains a timestamp, an ID to identify the user, and the name of the location that received the ping.</p>
  
  <p>Take this data table, partition it by the ID and sort by timestamp. Then you have a chronologically ordered set of pings. A user may have 1 ping to location A followed by 7 to location B followed by 2 to location C, and, 2 more to A.</p>
  
  <pre><code>ID        timestamp             Location
  ABC123    2017-10-12 10:20:37   A
  ABC123    2017-10-12 11:15:21   B
  ABC123    2017-10-12 11:21:47   B
  ABC123    2017-10-12 11:25:05   B
  ABC123    2017-10-12 11:32:12   B
  ABC123    2017-10-12 11:36:24   B
  ABC123    2017-10-12 11:47:13   B
  ABC123    2017-10-12 11:59:08   B
  ABC123    2017-10-12 12:04:42   C
  ABC123    2017-10-12 17:04:52   C
  ABC123    2017-10-12 19:15:37   A
  ABC123    2017-10-12 19:18:37   A
  </code></pre>
  
  <p>What I would like to do, is take this table and produce a new one with one row per "trip". Where a trip is a group of consecutive pings, with a "first_ping" and a "last_ping" column. In the event that a trip consists of 1 ping, that timestamp is both the first and last ping.</p>
  
  <pre><code>ID        first_ping            last_ping             Location
  ABC123    2017-10-12 10:20:37   2017-10-12 10:20:37   A
  ABC123    2017-10-12 11:15:21   2017-10-12 11:59:08   B
  ABC123    2017-10-12 12:04:42   2017-10-12 17:04:52   C
  ABC123    2017-10-12 19:15:37   2017-10-12 19:18:37   A
  </code></pre>
  
  <p><strong>Attempts at a Solution</strong></p>
  
  <p><strong>Python</strong></p>
  
  <p>I've never worked with data this large, and I've always worked with Python. So my first attempt at a solution was a Python script that:</p>
  
  <ol>
  <li>Queries BQ for all the data for one ID</li>
  <li>Sorts the data by timestamp</li>
  <li>Uses the diff function on "Location" to figure out when it changes</li>
  <li>Uses cumsum() to flag all the items for each group of pings with the same value.</li>
  <li>uses df.groupby() on the cumsum() to get one row per record, and first() and last() to get the first_ping and last_ping values.</li>
  </ol>
  
  <p>This solution produces the output I need, but is not feasible for 17 billion records and 69M unique IDs. It takes about 10 seconds per ID, and that's about 190K hours of run time.</p>
  
  <p><strong>SQL</strong></p>
  
  <pre><code>WITH visitWithIsChange AS 
  (select
     *,
     LAG(location,1,'') OVER (PARTITION BY user_id ORDER BY timestamp) previous,
      CASE 
       WHEN (LAG(location,1,'') 
             OVER (PARTITION BY user_id ORDER BY timestamp)) = location
             THEN 0
             ELSE 1
       END ischange
   FROM `ping_table` ORDER BY user_id, timestamp),
   visitsWithcumsum AS (
     SELECT 
        t1.*,
        SUM(t2.ischange) AS cumulativeSum 
     FROM visitWithIsChange t1
          INNER JOIN
               visitWithIsChange t2
                 ON
                   t1.local_timestamp &gt;=t2.local_timestamp
                   AND
                   t1.user_id=t2.user_id
     GROUP BY 
       t1.local_timestamp,
       t1.user_id,
       t1.chain_id,
       t1.previous,
       t1.isChange
     ORDER BY user_id, timestamp
  )
  SELECT 
    MIN(timestamp) AS first_ping,
    MAX(local_timestamp) AS last_ping,
    user_id,
    chain_id,
  FROM visitsWithcumsum
  GROUP BY
    user_id,
    cumulativeSum,
    chain_id,
  ORDER BY user_id, first_ping
  </code></pre>
  
  <p>I know that the problem with the SQL statement is the use of ORDER BY outside of the partitions. BigQuery throws resource exceeded errors every time ORDER BY is called on more than a couple hundred thousand rows. My understanding is that this occurs because an ORDER BY statement requires all of the data being ordered to reside on one node.</p>
  
  <p><strong>Questions</strong></p>
  
  <ol>
  <li>Is it possible to use the above SQL approach, but nest all of the logic within a partition statement? Basically, partition by user_id and do all of the ordering, cumsum, etc., within that partition?</li>
  <li>Is there a better approach to solving this problem?</li>
  </ol>
  
  <p>I appreciate any and all input. I'm at a complete loss as to the best way to solve this, and feel way out of my depth.</p>