Search code examples
sqlalgorithmsqlitedatabase-optimization

what is the minimum time Order of a query in SQL databases?

I want to know what is the minimum query time in a given SQL(specially SQLite) database(with n records). I know that full table scan is O(n) and for indexed column (and RowId) it is O(log(n)).

1st question : is there any situation that the time is smaller than O(log(n))?

2nd question : why querying on RowId (SELECT *FROM table_01 WHERE rowid='234')is also O(log(n))?? if it (RowId)is ordered from 1 to n I logically expect that SQL can immediately find the row with a given RowId

Solution

  • Finding a specific row requires a search. (Not every rowid is necessarily present, so the database needs to look.) The optimistic case, or even the average case, should be much faster than log(n), but the worst case cannot be, since it requires searching a list.