Daria Ivanova Daria Ivanova - 1 month ago 9
SQL Question

Is there any difference between time complexity of the following sql queries that have to

I am working with the tables using Oracle Express. The table Employees has the fields Employee`s First_Name, Last_Name and his/her Hire_Date. My goal is to retrieve the data who from the employees was hired first.

I wrote these tho queries and I started to think about their complexity. I assume that the first one has the complexity of an O(n logn)and the second one has an O(n^2). This is only my assumption (I`m very new to programming) and I am not sure at all. Can you please explain me how the complexity of these queries is being exactly defined?

SELECT *
FROM
(
SELECT Hire_Date, First_Name, Last_Name
FROM Employees
ORDER BY Hire_Date
)
WHERE ROWNUM <= 1

SELECT *
FROM Employees
WHERE Hire_Date =
(
SELECT MIN(Hire_Date)
FROM Employees
)

Answer

First, if you are new to programming, you need to understand that the two queries are different. The first returns one row. The second returns at least one row.

That suggests that the execution plans will be different.

Under normal circumstances, if you needed to do this work, then you would have an index on Employees(Hire_Date). If so, the two would have very similar performance. The first would start returning the records in sorted order using the index and then stop at the first one. The second would do an index lookup to get the min. And then another to get the record(s) that match.

Without an index, the first would probably be O(n log n) because of the sort. The second would be O(n) -- one scan for the subquery and one for the outer query (these are not nested, so the complexity is linear). However, Oracle may have some optimizations, particularly for the first case.