What is a runtime complexity of this sql query?

I would like to know how fast is SELECT * FROM user_table WHERE email = '[e-mail]' is this O(1) or O(n)?

how does sql search for a particular row?

Answer

If there is no index on “email” column, the search complexity is O(N).

If there was hash-based index on an “email” column, then the search could be performed in O(1).

However in real DB engines the indices are usually tree-based (as they enable quick search not for equality only, but also for “greater/less than” conditions). For binary trees the search complexity is O(log N) so in most cases index on “email” column results in this.