3 ms·
How is it n^2? I can see how the DB would need to scan the index from the left side to arrive at the correct offset value O(n). But once it gets there, it shou
by srcreigh 5y ago
How is it n^2?
I can see how the DB would need to scan the index from the left side to arrive at the correct offset value O(n). But once it gets there, it should be able to load 15 rows from primary storage.
(FWIW in postgres the primary key index is a secondary index.)
I do agree that "deferred join" is no better than the first option in theory.
How does your point #3 work? It seems to assume the DB tries to guess how many rows are in a single page in order to implement OFFSET. This seems like an obvious bug that would be long fixed.
- advisedwang 5y agoit's N^2 if the client is scanning through all the records. With N records and page size P, with p=N/P pages: the client does list?page=1 then list?page=2 ... list?page=p. the server then does scans P records for the first client request, 2P for the second up to pP=N. The total record scanned is (1+2+...N/P)P = (1+N/P)(N/P)1/2*P ~ O(N^2)