Poiché non controlli l'algoritmo selezionato, non c'è modo di saperlo direttamente. Tuttavia, senza indici un SELECT dovrebbe essere O(n) (una scansione della tabella deve ispezionare ogni record, il che significa che verrà ridimensionato in base alle dimensioni della tabella).
Con un indice un SELECT è probabilmente O(log(n)) (sebbene dipenda dall'algoritmo utilizzato per l'indicizzazione e dalle proprietà dei dati stessi se ciò vale per qualsiasi tabella reale). Per determinare i tuoi risultati per qualsiasi tabella o query devi ricorrere alla profilazione dei dati del mondo reale per essere sicuro.
INSERT senza indici dovrebbe essere molto veloce (vicino a O(1)) mentre UPDATE deve prima trovare i record e quindi sarà più lento (leggermente) rispetto a SELECT che ti porta lì.
INSERT con gli indici sarà probabilmente di nuovo nel campo di gioco di O(log(n^2)) quando l'albero degli indici deve essere ribilanciato, altrimenti più vicino a O(log(n)). Lo stesso rallentamento si verificherà con un UPDATE se interessa le righe indicizzate, oltre ai costi SELECT.
Tutte le scommesse sono annullate quando parli di JOIN nel mix:dovrai profilare e utilizzare gli strumenti di stima delle query del tuo database per leggerlo. Tieni inoltre presente che se questa query è critica per le prestazioni dovresti ricercare profilo di volta in volta poiché gli algoritmi utilizzati da Query Optimizer cambieranno al variare del caricamento dei dati.
Un'altra cosa da tenere a mente... big-O non ti dice dei costi fissi per ogni transazione. Per i tavoli più piccoli questi sono probabilmente superiori ai costi di lavoro effettivi. Ad esempio:i costi di configurazione, smontaggio e comunicazione di una query su più reti per una singola riga saranno sicuramente più della ricerca di un record indicizzato in una piccola tabella.
Per questo motivo ho scoperto che essere in grado di raggruppare un gruppo di query correlate in un batch può avere un impatto molto maggiore sulle prestazioni rispetto a qualsiasi ottimizzazione che ho fatto al database vero e proprio.
