title: Improve throughput of ndb query over large data
body: <p>I am trying to perform some data processing in a GAE application over data that is stored in the Datastore. The bottleneck point is the throughput in which the query returns entities and I wonder how to improve the query's performance.</p>
  
  <p>What I do in general:</p>
  
  <ul>
  <li>everything works in a task queue, so we have plenty of time (10 minute deadline).</li>
  <li>I run a query over the ndb entities in order to select which entities need to be processed.</li>
  <li>as the query returns results, I group entities in batches of, say, 1000 and send them to another task queue for further processing.</li>
  <li>the stored data is going to be large (say 500K-1M entities) and there is a chance that the 10 minutes deadline is not enough. Therefore, when the task is reaching the taskqueue deadline, I spawn a new task. This means I need an ndb.Cursor in order to continue the query from where it stopped.</li>
  </ul>
  
  <p>The problem is the rate in which the query returns entities. I have tried several approaches and observed the following performance (which is too slow for my app):</p>
  
  <p><strong>Use fetch_page() in a while loop.</strong></p>
  
  <p>The code is straightforward</p>
  
  <pre><code>while has_more and theres_more_time:
   entities, cursor, more = query.fetch_page(1000, ...)
   send_to_process_queue(entities)
   has_more = more and cursor
  </code></pre>
  
  <p>With this approach, it takes 25-30 seconds to process 10K entities. Roughly speaking, that is 20K entities per minute. I tried changing the page size or the class of the frontend instance; neither made any difference in performance.</p>
  
  <p><strong>Segment the data and fire multiple fetch_page_async() in parallel.</strong> </p>
  
  <p><a href="https://stackoverflow.com/questions/11509368/best-practice-to-query-large-number-of-ndb-entities-from-datastore">This approach is taken from here (approach C)</a></p>
  
  <p>The overall performance remains the same as above. I tried with various number of segments (from 2 to 10) in order to have 2-10 parallel fetch_async() calls. In all cases, the overall time remained the same. The more parallel fetch_page_async() are called, the longer it takes for each one to complete. I also tried with 20 parallel fetches and it got worse. Changing the page size or the fronted instance class did not have and impact either.</p>
  
  <p><strong>Fetch everything with a single fetch() call.</strong> </p>
  
  <p>Now this is the least suitable approach (if not unsuitable at all) as the instance may run out of memory, plus I don't get a cursor in case I need to spawn to another task (in fact I won't even have the ability to do so, the task will simply exceed the deadline). I tried this out of curiosity in order to see how it performs and I observed the best performance! It took 8-10 seconds for 10K entities, which is roughly be 60K entities per minute. Now that is approx. 3 times faster than fetch_page(). I wonder why this happens.</p>
  
  <p><strong>Use query.iter() in a single loop.</strong> </p>
  
  <p>This is match like the first approach. This will make use of the query iterator's underlying generator, plus I can obtain a cursor from the iterator in case I need to spawn a new task, so it suits me. With the query iterator, it fetched 10K entities in 16-18 seconds, which is approx. 36-40K entities per minute. The iterator is 30% faster than fetch_page, but much slower that fetch().</p>
  
  <p>For all the above approaches, I tried F1 and F4 frontend instances without any difference in Datastore performance. I also tried to change the batch_size parameter in the queries, still without any change. </p>
  
  <p>A first question is why do fetch(), fetch_page() and iter() behave so differently and how to make either fetch_page() or iter() do equally well as fetch()? And then another critical question is whether these throughputs (20-60K entities per minute, depending on api call) are the best we can do in GAE.</p>
  
  <p>I 'm aware of the MapReduce API but I think it doesn't suit me. AFAIK, the MapReduce API doesn't support queries and I don't want to scan all the Datastore entities (it's will be too costly and slow - the query may return only a few results). Last, but not least, I have to stick to GAE. Resorting to another platform is not an option for me. So the question really is how to optimize the ndb query.</p>
  
  <p>Any suggestions?</p>