Un algoritmo per implementare l'ORDER BY di SQL con TOP / LIMIT o OFFSET / FETCH

1

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.

    
posta david.pfx 26.09.2014 - 06:58
fonte

0 risposte

Leggi altre domande sui tag