Python FastAPI pagination with cursor-based keyset navigation

<p>My API returns large datasets and offset-based pagination becomes slow at high page numbers. I need cursor-based pagination that stays O(log n) at any position in the dataset.</p>

<p>Keyset pagination with opaque cursors:</p> <div class="highlight"><pre><span></span><code><span class="kn">import</span><span class="w"> </span><span class="nn">base64</span> <span class="kn">import</span><span class="w"> </span><span class="nn">json</span> <span class="kn">from</span><span class="w"> </span><span class="nn">datetime</span><span class="w"> </span><span class="kn">import</span> <span class="n">datetime</span> <span class="kn">from</span><span class="w"> </span><span class="nn">pydantic</span><span class="w"> </span><span class="kn">import</span> <span class="n">BaseModel</span> <span class="k">def</span><span class="w"> </span><span class="nf">encode_cursor</span><span class="p">(</span><span class="n">created_at</span><span class="p">:</span> <span class="n">datetime</span><span class="p">,</span> <span class="nb">id</span><span class="p">:</span> <span class="nb">str</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="nb">str</span><span class="p">:</span> <span class="k">return</span> <span class="n">base64</span><span class="o">.</span><span class="n">urlsafe_b64encode</span><span class="p">(</span> <span class="n">json</span><span class="o">.</span><span class="n">dumps</span><span class="p">({</span><span class="s1">'ts'</span><span class="p">:</span> <span class="n">created_at</span><span class="o">.</span><span class="n">isoformat</span><span class="p">(),</span> <span class="s1">'id'</span><span class="p">:</span> <span class="nb">id</span><span class="p">})</span><span class="o">.</span><span class="n">encode</span><span class="p">()</span> <span class="p">)</span><span class="o">.</span><span class="n">decode</span><span class="p">()</span> <span class="k">def</span><span class="w"> </span><span class="nf">decode_cursor</span><span class="p">(</span><span class="n">cursor</span><span class="p">:</span> <span class="nb">str</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="nb">tuple</span><span class="p">[</span><span class="n">datetime</span><span class="p">,</span> <span class="nb">str</span><span class="p">]:</span> <span class="n">data</span> <span class="o">=</span> <span class="n">json</span><span class="o">.</span><span class="n">loads</span><span class="p">(</span><span class="n">base64</span><span class="o">.</span><span class="n">urlsafe_b64decode</span><span class="p">(</span><span class="n">cursor</span><span class="p">))</span> <span class="k">return</span> <span class="n">datetime</span><span class="o">.</span><span class="n">fromisoformat</span><span class="p">(</span><span class="n">data</span><span class="p">[</span><span class="s1">'ts'</span><span class="p">]),</span> <span class="n">data</span><span class="p">[</span><span class="s1">'id'</span><span class="p">]</span> <span class="k">class</span><span class="w"> </span><span class="nc">PagedResponse</span><span class="p">(</span><span class="n">BaseModel</span><span class="p">):</span> <span class="n">items</span><span class="p">:</span> <span class="nb">list</span> <span class="n">next_cursor</span><span class="p">:</span> <span class="nb">str</span> <span class="o">|</span> <span class="kc">None</span> <span class="n">has_more</span><span class="p">:</span> <span class="nb">bool</span> <span class="k">async</span> <span class="k">def</span><span class="w"> </span><span class="nf">list_keyset</span><span class="p">(</span> <span class="n">session</span><span class="p">:</span> <span class="n">AsyncSession</span><span class="p">,</span> <span class="n">limit</span><span class="p">:</span> <span class="nb">int</span> <span class="o">=</span> <span class="mi">20</span><span class="p">,</span> <span class="n">cursor</span><span class="p">:</span> <span class="nb">str</span> <span class="o">|</span> <span class="kc">None</span> <span class="o">=</span> <span class="kc">None</span> <span class="p">)</span> <span class="o">-&gt;</span> <span class="n">PagedResponse</span><span class="p">:</span> <span class="n">query</span> <span class="o">=</span> <span class="n">select</span><span class="p">(</span><span class="n">Trace</span><span class="p">)</span><span class="o">.</span><span class="n">order_by</span><span class="p">(</span><span class="n">Trace</span><span class="o">.</span><span class="n">created_at</span><span class="o">.</span><span class="n">desc</span><span class="p">(),</span> <span class="n">Trace</span><span class="o">.</span><span class="n">id</span><span class="o">.</span><span class="n">desc</span><span class="p">())</span> <span class="k">if</span> <span class="n">cursor</span><span class="p">:</span> <span class="n">ts</span><span class="p">,</span> <span class="n">last_id</span> <span class="o">=</span> <span class="n">decode_cursor</span><span class="p">(</span><span class="n">cursor</span><span class="p">)</span> <span class="n">query</span> <span class="o">=</span> <span class="n">query</span><span class="o">.</span><span class="n">where</span><span class="p">(</span> <span class="p">(</span><span class="n">Trace</span><span class="o">.</span><span class="n">created_at</span> <span class="o">&lt;</span> <span class="n">ts</span><span class="p">)</span> <span class="o">|</span> <span class="p">((</span><span class="n">Trace</span><span class="o">.</span><span class="n">created_at</span> <span class="o">==</span> <span class="n">ts</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">(</span><span class="n">Trace</span><span class="o">.</span><span class="n">id</span> <span class="o">&lt;</span> <span class="n">last_id</span><span class="p">))</span> <span class="p">)</span> <span class="n">result</span> <span class="o">=</span> <span class="k">await</span> <span class="n">session</span><span class="o">.</span><span class="n">execute</span><span class="p">(</span><span class="n">query</span><span class="o">.</span><span class="n">limit</span><span class="p">(</span><span class="n">limit</span> <span class="o">+</span> <span class="mi">1</span><span class="p">))</span> <span class="c1"># Fetch one extra</span> <span class="n">items</span> <span class="o">=</span> <span class="n">result</span><span class="o">.</span><span class="n">scalars</span><span class="p">()</span><span class="o">.</span><span class="n">all</span><span class="p">()</span> <span class="n">has_more</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">items</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">limit</span> <span class="n">items</span> <span class="o">=</span> <span class="n">items</span><span class="p">[:</span><span class="n">limit</span><span class="p">]</span> <span class="n">next_cursor</span> <span class="o">=</span> <span class="n">encode_cursor</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">created_at</span><span class="p">,</span> <span class="nb">str</span><span class="p">(</span><span class="n">items</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">id</span><span class="p">))</span> <span class="k">if</span> <span class="n">has_more</span> <span class="k">else</span> <span class="kc">None</span> <span class="k">return</span> <span class="n">PagedResponse</span><span class="p">(</span><span class="n">items</span><span class="o">=</span><span class="n">items</span><span class="p">,</span> <span class="n">next_cursor</span><span class="o">=</span><span class="n">next_cursor</span><span class="p">,</span> <span class="n">has_more</span><span class="o">=</span><span class="n">has_more</span><span class="p">)</span> </code></pre></div> <p>Key points: - Keyset pagination is O(log n) regardless of position -- offsets are O(n) - Sort by (timestamp, id) -- pure timestamp sort is non-deterministic for same-second rows - Encode cursor as opaque base64 -- clients should not parse it - Fetch limit+1 to detect has_more without a COUNT query</p>