Esiste un algoritmo generale per implementare SQL ORDER BY con OFFSET / LIMIT in modo più efficiente rispetto all'ordinamento di tutti i record?
L'algoritmo per un semplice TOP x è abbastanza semplice. Richiede un passaggio completo attraverso i dati, ma solo i record x devono essere ordinati. La complessità ammortizzata è O (n), per un insieme di n righe, assumendo x è molto minore di n.
Quindi l'approccio ingenuo di OFFSET y LIMIT z sarebbe di trattarlo come TOP (y + z) e quindi restituire solo le righe z. Questo sarebbe O (n) se y + z è piccolo, e qualcosa come O (nlog (n / 2)) se y + z è la metà di n. [I valori più grandi vengono gestiti invertendo il senso dell'ordine.]
Vedo che una variante dell'ordinamento di selezione può trovare il valore mediano in O (n), ma non sono stato in grado di definire un algoritmo per questo particolare problema.