title: Computing a moving maximum in BigQuery
body: <p>Given a BigQuery table with some ordering, and some numbers, I'd like to compute a "moving maximum" of the numbers -- similar to a moving average, but for a maximum instead.  From <a href="https://stackoverflow.com/questions/24590796/trying-to-calculate-ema-exponential-moving-average-using-bigquery">Trying to calculate EMA (exponential moving average) using BigQuery</a> it seems like the best way to do this is by using <code>LEAD()</code> and then doing the aggregation myself.  (<a href="https://stackoverflow.com/questions/12763404/bigquery-moving-average">Bigquery moving average</a> suggests essentially a <code>CROSS JOIN</code>, but that seems like it would be quite slow, given the size of the data.)</p>
  
  <p>Ideally, I might be able to just return a single repeated field, rather than 20 individual fields, from the inner query, and then use normal aggregation over the repeated field, but I haven't figured out a way to do that, so I'm stuck with rolling my own aggregation.  While this is easy enough for a sum or average, computing the max inline is pretty tricky, and I haven't figured out a good way to do it.</p>
  
  <p>(The examples below are of course somewhat contrived in order to use public datasets.  They also do the rolling max over 3 elements, whereas I'd like to do it for around 20.  I'm already generating the query programmatically, so making it short isn't a big issue.)</p>
  
  <p>One approach is to do the following:</p>
  
  <pre><code>SELECT word,
    (CASE
      WHEN word_count &gt;= word_count_1 AND word_count &gt;= word_count_2 THEN word_count
      WHEN word_count_1 &gt;= word_count AND word_count_1 &gt;= word_count_2 THEN word_count_1
      ELSE word_count_2 END
      ) AS max_count
  FROM (
    SELECT word, word_count,
      LEAD(word_count, 1) OVER (ORDER BY word) AS word_count_1,
      LEAD(word_count, 2) OVER (ORDER BY word) AS word_count_2,
    FROM [publicdata:samples.shakespeare]
    WHERE corpus = 'macbeth'
  )
  </code></pre>
  
  <p>This is O(n^2), but it at least works.  I could also do a nested chain of <code>IF</code>s, like this:</p>
  
  <pre><code>SELECT word,
    IF(word_count &gt;= word_count_1,
      IF(word_count &gt;= word_count_2, word_count, word_count_2),
      IF(word_count_1 &gt;= word_count_2, word_count_1, word_count_2)) AS max_count
  FROM ...
  </code></pre>
  
  <p>This is O(n) to evaluate, but the query size is exponential in n, so I don't think it's a good option; certainly it would surpass the BigQuery query size limit for n=20.  I could also do n nested queries:</p>
  
  <pre><code>SELECT word,
    IF(word_count_2 &gt;= max_count, word_count_2, max_count) AS max_count
  FROM (
    SELECT word,
      IF(word_count_1 &gt;= word_count, word_count_1, word_count) AS max_count
    FROM ...
  )
  </code></pre>
  
  <p>It seems like doing 20 nested queries might not be a great idea performance-wise, though.</p>
  
  <p>Is there a good way to do this kind of query?  If not, am I correct that for n around 20, the first is the least bad?</p>