Why GitHub Cannot Paginate Through Millions of Repositories - Deep Pagination Explained

GitHub's search API imposes a limit of 1000 results per page, returning an error message when attempting to request beyond this limit. To understand why this happens, one must delve into the mechanics of pagination and database indexing. Pagination typically involves querying a database for a specific set of records, often using a "LIMIT" and "OFFSET" clause. However, this approach can be inefficient, especially when dealing with large result sets.

The issue arises from how database indexes are built. A sorted column is backed by a B-tree, which is optimized for sequential access of rows. While this makes ORDER BY operations fast, it doesn't offer a shortcut for retrieving a record at a specific position. Instead, the database must sequentially scan through the rows, starting from the beginning, until it reaches the desired position. This results in a time complexity of O(offset), meaning the time taken increases linearly with the offset value.

In the case of GitHub's API, when a request is made for a page beyond the first thousand results, the API returns a 422 status code, indicating that only the first 1000 search results are available. This is not due to rate limiting or a bug, but rather a design choice to prevent excessive resource usage and potential performance degradation. The same issue is observed in other systems that use similar pagination mechanisms, resulting in long wait times for requests with high offsets.

To mitigate this problem, some developers turn to "cursor pagination," which uses the result of the previous request to fetch the next set of records. This approach is generally more efficient, as it avoids the need to sequentially scan through large portions of the dataset. By using cursor pagination, developers can significantly reduce the time required to retrieve paginated results, especially when dealing with large databases.