Computational SQL Query Complexity

Question

If I have a table of, say, blog posts with columns such as post_id and author_id, and I used SQL "SELECT * FROM post_table where author_id = 34", what would be the computational complexity of this query? Will it just scan each line and check if it has the correct author id, O (n), or does something more efficient?

I’m just curious because I’m in a situation where I could either look for an SQL database with this data, or download an xml file with a list of messages, and search through them, I was wondering what would be faster.

Answer 1

There are two main ways to make such a simple request.

First, you need to perform a full table scan. This will have O (n) performance.

The second is finding the value in the index, loading the page, and returning the results. Index scan should be O (log (n)). The page load should be O (1).

With a more complex query, it would be difficult to make such a general statement. But any SQL engine will usually take one of these two paths. Oh, there is a third option if the table is split by author_id, but you are probably not interested in this.

However, the strength of the database is not in these details. He is in memory management. The database will cache data and indexes in memory, so you do not need to re-read the data pages. The database will use several processors and several disks, so you do not need to encode it. The database retains all consistency in the face of updates and deletions.

Regarding your specific question. If the data is in the database, search there. Downloading all the data in an xml file and then doing a memory search requires a lot of overhead. You would only like to do this if the connection to your database is slow and you make a lot of such queries.

Answer 2

Look at the EXPLAIN command. It shows you what the database actually does when it executes a given SELECT query.