Como você não controla o algoritmo selecionado, não há como saber diretamente. No entanto, sem índices, um SELECT deve ser O(n) (uma varredura de tabela deve inspecionar todos os registros, o que significa que será dimensionado com o tamanho da tabela).

Com um índice, um SELECT é provavelmente O(log(n)) (embora dependa do algoritmo usado para indexação e das propriedades dos próprios dados, se isso for verdade para qualquer tabela real). Para determinar seus resultados para qualquer tabela ou consulta, você precisa recorrer à criação de perfil de dados do mundo real para ter certeza.

O INSERT sem índices deve ser muito rápido (próximo de O(1)), enquanto o UPDATE precisa encontrar os registros primeiro e, portanto, será mais lento (um pouco) do que o SELECT que o leva até lá.

INSERT com índices provavelmente estará novamente no patamar de O(log(n^2)) quando a árvore de índices precisar ser rebalanceada, mais próxima de O(log(n)) caso contrário. A mesma lentidão ocorrerá com um UPDATE se afetar as linhas indexadas, além dos custos de SELECT.

Todas as apostas são canceladas quando você está falando sobre JOIN na mistura:você terá que criar um perfil e usar suas ferramentas de estimativa de consulta de bancos de dados para obter uma leitura sobre isso. Observe também que, se esta consulta for crítica para o desempenho, você deve re profile de tempos em tempos, pois os algoritmos usados ​​pelo seu otimizador de consulta serão alterados à medida que o carregamento de dados for alterado.

Outra coisa a ter em mente... big-O não fala sobre custos fixos para cada transação. Para mesas menores, estes são provavelmente mais altos do que os custos reais de trabalho. Como exemplo:os custos de configuração, desmontagem e comunicação de uma consulta de rede cruzada para uma única linha certamente serão mais do que a pesquisa de um registro indexado em uma pequena tabela.

Por causa disso, descobri que poder agrupar um grupo de consultas relacionadas em um lote pode ter um impacto muito maior no desempenho do que qualquer otimização que fiz no banco de dados propriamente dito.