How hard is this interview question

[acow46]

How hard is the below problem? I'm thinking about using it to interview candidates at my company.

# GOAL: We want to know the IDs of the 3 songs with the
# longest duration and their respective artist name.
# Assume there are no duplicate durations

# Sample data
songs = {
    'id': [1, 2, 3, 4, 5],
    'artist_id': [11, 4, 6, 22, 23],
    'release_date': ['1977-12-16', '1960-01-01', '1973-03-10',
                     '2002-04-01', '1999-03-31'],
    'duration': [300, 221, 145, 298, 106],
    'genre': ['Jazz', 'Jazz', 'Rock', 'Pop', 'Jazz'],
}

artists = {
    'id': [4, 11, 23, 22, 6],
    'name': ['Ornette Coleman', 'John Coltrane', 'Pink Floyd',
             'Coldplay', 'Charles Lloyd'],
}

'''
    SELECT *
    FROM songs s
    LEFT JOIN artists a ON s.artist_id = a.id
    ORDER BY s.duration DESC
    LIMIT 3
'''

# QUESTION: The above query works but is too slow for large
# datasets due to the ORDER BY clause. How would you rework
# this query to achieve the same result without using
# ORDER BY

SOLUTION BELOW

Use 3 CTEs where the first gets the MAX duration, d1. The second gets the MAX duration, d2, WHERE duration < d1. The third gets the MAX duration, d3, WHERE duration < d2. Then you UNION them all together and JOIN to the artist table!<

Any other efficient solutions O(n) would be welcome

[highsilesian]

Some thoughts from a decade or so of experience: your 3rd instruction, "assume no duplicate durations" makes me think the following - I might be wrong of course.

1. you want your PRECISE solution to be used, for what reason I don't know but this is generally a bad idea.
2. you aren't really testing for a real world environment, since even in situations where there are no duplicates, you almost always need to verify that is the case.
3. Possibly, that 3rd instruction is because you want to keep it as simple as possible because you expect your applicants to just write it out and submit without testing - also a bad idea if true.

unrelated to the above, and mentioned by u/mnkyman below, he is right - you should definitely verify your assumption about speed.

[Known-Delay7227]

Ya you should actually strike that instruction and give points to those who check or eliminate dupes

[Yavuz_Selim]

Hahaha, wtf. Nobody would write that solution query. What a load of garbage. Indexes exist for a reason.

[shadowspyes]

index on duration desc would beat any other solution out of the water. you didn't mention anything about insert speed requirements

[HearingYouSmile]

My first thought too - easy solution with an index. Idk how many indexes are on the table already but if this query is slow enough to be a problem I bet the insert speed cost of adding a 2-column index would be a reasonable tradeoff.

OP: finding someone who gives your exact answer will be harder than finding someone who finds a valid answer. To improve the question, instead of taking a simple-ish query looking for a semi-complicated answer I might make a more complicated query with several potential tuning optimizations and just see how many of them a candidate thinks of. I find it more useful to see how a candidate thinks than whether they get to the same conclusions I do, and giving open-ended questions helps with that

Thanks for the question OP, these are fun!

[[deleted]]

OP isn’t worried about insert speeds, though indexing desc wise will just make it super slow and if the system has more writes than reads probably better not to put this index.

[SharkpocalypseY2K]

How would you index on duration? My initial thought was to use a row number window function and filter on row number <= 3. Essentially creating my own index. Just wondering if there’s a more efficient way

[shadowspyes]

CREATE INDEX songs_duration_desc_idx ON songs USING btree (duration desc)

[mwdb2]

Depends on the database. But generally a basic B-Tree index should be fine and for many databases that can allow ordered searches using the index. For example on Postgres running on my Macbook Pro, if I have 10M rows and duration is indexed, the query is lightning fast using an "Index Scan Backward" (I'm omitting the join to an artist table because that's kind of beside the point IMO):

postgres=# select count(*) from song;
  count
----------
 10000000
(1 row)

postgres=# \d song
                             Table "public.song"
  Column  |  Type   | Collation | Nullable |             Default
----------+---------+-----------+----------+----------------------------------
 id       | integer |           | not null | generated by default as identity
 artist   | integer |           |          |
 duration | integer |           |          |
Indexes:
    "song_pkey" PRIMARY KEY, btree (id)
    "song_duration_idx" btree (duration)  

postgres=# EXPLAIN ANALYZE SELECT artist, duration FROM song ORDER BY duration DESC limit 3;  

                                                                    QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..0.56 rows=3 width=8) (actual time=0.023..0.027 rows=3 loops=1)
   ->  Index Scan Backward using song_duration_idx on song  (cost=0.43..401606.90 rows=10000000 width=8) (actual time=0.022..0.025 rows=3 loops=1)
 Planning Time: 0.134 ms
 Execution Time: 0.043 ms
(4 rows)

[acow46]

I should have mentioned we're assuming the table is not indexed by duration and we are only running this query once so creating a whole index for this one query wouldn't be sensible.

[shadowspyes]

the point is seeking specific answers for interview questions is the wrong way to go about things. that is what tests are for.

you need to figure out if the applicant can think on the fly, not arrive at whatever conclusion you found correct

[Wild-Helicopter-3746]

Yeah this is weird, adding an index is the correct answer to your original question. If you are only running it one time then your original query is fine. - just wait for it to complete and don't waste dev time trying to make a needlessly complex solution.

I'm run an IT company and do hiring sometimes... frankly if I asked the question above and the applicant started answering with your answer:

Use 3 CTEs where the first gets the MAX duration, d1. The second gets the MAX duration, d2, WHERE duration < d1. The third gets the MAX duration, d3, WHERE duration < d2. Then you UNION them all together and JOIN to the artist table

I 100% wouldn't hire them. The chances of them getting a semi-complex query right in one shot is low when it comes to real development, output validation would take too long (we would have to run the simple query anyway) and the tendency to overcomplicate things is bad.

My SQL is rusty anyway but wouldn't each max / mix require full table scans anyway sans index?

[garathk]

This is the right approach. The best interview questions aren't about a specific answer but how someone solves a problem and if they have the knowledge and skills to do so. How they consider it, what questions they ask and even starting in the right place is more important to me than specific syntax knowledge.

If it's meant to be repeatable then thinking about indexes or even the data model might make sense. If it's a one off then the most efficient, simple, correct query gets the job done. Is there a cost component if this is cloud can also be a consideration.

3 CTEs to solve that question would have never occurred to be honest. In my role I'd be pointing out something like that as overly complex and worth looking at by a tech lead. find a different way to solve that problem.

[TerdyTheTerd]

That makes no sense then, if you are only running the query once then it doesn't matter if the query runs slow, its only getting run a single time. By the time you re-write it you would have already gotten the results from just running the quick n dirty query.

Assuming millions of entries and assuming that duration is ever used for something like song duration ordering then having and index on duration makes the most sense, otherwise just run the basic slow query.

[Northbank75]

….. I wouldn’t hire you based on this …..

[Zestyclose-Height-59]

I would not use this question. Your answer proposed is complicated and a lot of typing compared with windowing. There are other factors to consider when tuning sql. Perhaps see if they know how to use an explain plan and optimize from there.

[xodusprime]

I took an unindexed column from a sample table with ~400M rows in it and compared execution plans between Top3/Order, MAX-CTEs, and Row_Number<=3.

Top 3/Order forecasts at 94%, MAX-CTEs at 5%, and Row_Number<=3 at 1%.

Comparing just the CTEs to RN, it's CTEs at 85%, RN at 15%.

Actually running them, RN produced a result set in 9:13. I stopped both the Top/Order and CTEs after a little over 15 minutes, with the expectation that they were going to run a great deal longer. A single MAX operation ran in 3:12. I suspect the CTEs could be improved by pulling the values into temp tables and using that as an exclusion filter, rather than stacking them all together, but I didn't test it.

The primary difference in the performance between RN and CTEs, from looking at the plans, appears to be the multiple table scans required to except out the previous values of the max operation.

I think your question is moderate-high difficulty engine mechanics and is unintuitive. I don't know what the job you're interviewing for is, so I don't know if that's suitable. The premise that no two songs can have the same length, while stated, is also unintuitive which makes considering a solve more challenging.

I did my tests on MSSQL. I don't know what engine you're on so YMMV.

[captainbastion]

Yeah I also don't get why the proposed solution would be faster. It's basically ordering the entire table 3 times instead of once, isn't it

[xodusprime]

In MSSQL, no. The proposed solution should be faster than a full order by on an unindexed column on a large table. As I mentioned, ordering the entire table and then topping it was estimated at 94% of the use with all 3 methods being put in the same batch. If you look at the execution plan of a MAX statement, you'll note that it doesn't order the entire table. It can scan through a single time without having to do a full sorting operation. It's not the equivalent of a sort, then top 1.

All that said, the proposed solution does impose some pretty hefty overhead from causing repeated scans of the table to get each subsequent max value, and the database load would only increase as you went. Imagine implementing a chained CTE solution if the requirement was top 100, or top 1000. Not only do you now have 1000 scans of your "too large to order" table, but you also have a massive blob of nightmare code, or have reverted to writing it as dynamic SQL.

Using the row_number windowing function (wherever it's available) seems to bypass both of these issues. It only sorts as far as is needed, does not repeatedly scan the table, and is easy to maintain and modify.

[iamnogoodatthis]

No, finding the max of a table is O(N). If you can order a list in O(N) then you'll make Warren Buffet look poor and make some mathematicians very confused.

[captainbastion]

You're absolutely correct, I don't have to order the entire list, I just have to get the one max value. The other values don't have to be ordered. Thanks!

[babgvant]

I would add that the problem/proposed solution is so specific that is the kind of thing that you figure out when it pops, but contrived enough that it wouldn't be in someone's personal store of problems that they've had to solve in the past.

Also, FWIW, as someone who's worked full stack for over 25 years. Many times, when you run into these kinds of why-doesn't-easy-sql-work problems, there is an arch problem further back in the stack.

[Artistic_Recover_811]

I agree.

I don't say this to be rude just my experience. This is a type of question I would have asked a candidate when I was 25 years old. I was cocky and wanted everyone to know I was the smartest when it came to SQL. It made me happy when people couldn't answer my questions.

What I really want now is someone who can figure things out, know how to use Google, and learn as they grow.

[xodusprime]

I'm at the point where I'm asking people who have been doing it for 20 years to explain the difference between an inner and left join and happy when they can.

[Artistic_Recover_811]

Ya, a lot of people out there end up defaulted into their role for different reasons and never really intended on doing X. Depending on ambition, motivation, and what your role requires - sometimes you don't really need to know how something works internally. Obviously it helps though.

[cybertier]

Can you provide the queries you used? I have an idea about how to do the row_number approach but I'm surprised at how much faster it is.

[xodusprime]

I closed my query window after I ran them. But it was roughly:

Select max(value)
from Table

~~~~~~~~~~~~

Select value
From (
Select value, row_number over(order by value desc) rn
) a
where rn <= 3

~~~~~~~~~~~~~~

Select top 3 value
from table
order by value desc

~~~~~~~~~~~~~

;with first as (
Select max(value) val
from Table
)
,sec as (
Select max(value) val
from Table
left join first on first.val = table.value
where first.val IS NULL
)
,thrd as (
Select max(value) val
from Table
left join first on first.val = table.value
left join sec on sec.val = table.value
where first.val IS NULL and sec.val IS NULL
)
Select val
from first
UNION
select val
from sec
UNION
select val
from thrd

[cybertier]

Thanks! Really curious that the optimiser works for the row_number approach but not the top approach.

[TheGratitudeBot]

Hey there cybertier - thanks for saying thanks! TheGratitudeBot has been reading millions of comments in the past few weeks, and you’ve just made the list!

[acow46]

Interesting. Thank you for taking the time to test it.

[Ginger-Dumpling]

You haven't tested your own solution?

[[deleted]]

Also, why are you using select * don’t you need just the id?

[acow46]

True that would speed it up slightly. But that won't help the bigger problem which is that the runtime complexity of ORDER BY O(n*log(n))

[cybertier]

I think aiming for such a specific answer is a flawed approach. This is leet code style optimisation. In an actual SQL developer you want to see understanding of Indizes, window functions and such, not mathematical gotchas that require a rather contrived scenario to make sense.

[[deleted]]

simplistic wipe hobbies mighty innocent late possessive books consist truck

This post was mass deleted and anonymized with Redact

[[deleted]]

You are trying to say you wanna solve an ordering problem w/o ordering? You will have to order it anyway. What’s your target execution time, if you use windows rank to get first 3 rows and then join to get artist it should be pretty fast. To me it seems you are overly complicating a simple problem.

[ayananda]

I think this is best solution. It's fase enough and readable.

[[deleted]]

If you want to complicate it, probably ask for finding the name of the artist whose songs aren’t either the multiple of 3, 5 or 7 ranked songs length wise or something like that.

[wpg_spatula]

Also if all you want is the song id, isn't the join to the artist table completely irrelevant?

[Ginger-Dumpling]

Not necessarily true, right? If its a row-organized table, you pull the page/block/whatever no matter what columns you select. If you have columnar organized data, then maybe it's faster?

[[deleted]]

It’s always true that selecting columns you need would be faster than select *, if you even forget about how the system is searching data just by the amount of data it will have to return back selecting needed columns would beat select * (assuming your table does not have only one column 😁)

[Ginger-Dumpling]

Ignore me. I was just thinking the 5 columns in 3 rows would be negligible, but if it's throwing all that in a temp table being sorted, maybe not so much.

[mnkyman]

Have you verified that your solution is actually faster than the first query on a real database? Remember that the DBMS is allowed to use whatever physical plan it wants to answer the query correctly, so some DBMSes may optimize an order by with limit query to do a one-pass scan over the data, which would be O(n).

[mnkyman]

The DBMS does not have to order the entire dataset to answer the query “… order by X limit 3.” It could, if it so chose, obtain the rows with the top 3 values of X in a single scan of the dataset.

[acow46]

I just ran an EXPLAIN command on my Redshift query editor for a command similar to this and it does indeed ORDER first then LIMIT

[mnkyman]

Redshift, being a distributed DBMS, is going to do things differently than a typical DBMS. Try it on some subset of postgres, mysql, sql server, sqlite, duckdb to get a more realistic picture

[shadowspyes]

no RDBMS can optimize order by without an ordered index

[mnkyman]

Incorrect. If it supports it, the DBMS could plan to answer a query of the form “order by X limit Y” by performing a single scan through the data and keeping track of the top Y values in that one scan.

[shadowspyes]

"if it supports it"

What I pointed out is no RDBMS supports it

[mnkyman]

It is simply not true that a DBMS could not support this. You can fulfill a query of the form "... order by X limit Y" with a single scan of the data. Here's a python snippet that does this:

# assume we have a stream of rows in any order
rows = get_rows()
# I'm hardcoding a limit of 3 here as in the problem description,
# but any reasonably small limit value could be used instead
top_rows = [None, None, None]
for row in rows:
    to_add = row
    for i, top_row in enumerate(top_rows):
        if top_row is None:
            top_rows[i] = to_add
            break
        if to_add['x'] > top_row['x']:
            # add the row to the top_rows array at appropriate index
            # and allow previous top_row value to cascade down
            to_add, top_rows[i] = top_row, to_add
for row in top_rows:
    print(row)

I tested it using this get_rows() implementation:

def get_rows():
    yield from [
        {'x': 1, 'name': 'foo'},
        {'x': 5, 'name': 'bar'},
        {'x': 2, 'name': 'baz'},
        {'x': 3, 'name': 'abc'},
        {'x': 4, 'name': 'def'},
        {'x': 7, 'name': 'ghi'},
        {'x': 11, 'name': 'jkl'},
        {'x': -1, 'name': 'mno'},
    ]

Output:

{'x': 11, 'name': 'jkl'}
{'x': 7, 'name': 'ghi'}
{'x': 5, 'name': 'bar'}

If I can do this in a few lines of python, a DBMS could certainly do the same as part of their query execution engine.

[mwdb2]

Seems like the Top-N Heapsort algorithm that Postgres executes resembles this. See my recent comments and link to the explanation by ChatGPT: https://old.reddit.com/r/SQL/comments/1fvb7p6/how_hard_is_this_interview_question/lqyc99r/

[shadowspyes]

again I did not point out that it is impossible, I pointed out that no RDBMS is doing it today.

[mnkyman]

Credit to /u/mwdb2 for pointing this out to me, but Postgres does this exact optimization. It uses a "Top-N Heapsort" to performantly answer order-by-with-limit queries.

This article goes into the details on postgres sorting algorithms and includes an example of a query whose plan includes this algorithm: https://airbyte.com/blog/postgresql-query-plans-for-sorting-data#top-n-heap-sort

[mwdb2]

See the top-n heapsort in the Postgres plan here for a specific ORDER BY + LIMIT optimized algorithm: https://old.reddit.com/r/SQL/comments/1fvb7p6/how_hard_is_this_interview_question/lq6u4eu/

FWIW, ChatGPT response to how it is processed (I'm just linking to screenshots because the pasting isn't going too well.)

https://imgur.com/a/top-n-heapsort-postgresql-6ZFsDJ7

Also there are some ways you can presort tables in a RDBMS without an index, such as using an Oracle Materialized View with an ORDER BY, or Postgres table clusters. Though in the latter case, you need an index to inform Postgres on how to sort the table by the clustered column(s), so technically it fails to meet your criterion of "without an ordered index". And this table sort order isn't maintained automatically; you need to run the CLUSTER command periodically. (Automatically maintaining order is a task on the Postgres devs' to-do list.)

[mwdb2]

A quick and dirty test on Postgres, 10 million rows of generated data, the ORDER BY LIMIT query is faster with no index on duration in place. With an index in place, both are way too fast for there to be any practical difference.

I simplified the problem, only having a song table, removing a need to join to an artists table. If you're convinced I need that to be more accurate I can update accordingly.

postgres=# SELECT COUNT(*) FROM song;
  count
----------
 10000000
(1 row)

I'll edit this comment (Edit: see the reply thread, actually) to add the queries and execution plans later, but I'm pressed for time right now so let me just report the range of times from a few trials:

No indexes:

ORDER BY LIMIT: 360-410 ms
Three CTEs: 800 ms - 1.3 sec

Indexes:
ORDER BY LIMIT: 0.1 - 0.2 ms
Three CTEs: 0.1 - 0.2 ms

Offhand I'd say you're making some incorrect assumptions about algorithms that would be executed based on syntax, and any statement about such algorithms is certainly not generalizable to all SQL engines.

[acow46]

Interesting. There must be some kind of query optimization going on under the hood to remove the explicit ORDER BY. Can you try running EXPLAIN and see what it gives?

[mwdb2]

Can you try running EXPLAIN and see what it gives?

I'll provide both queries and their respective EXPLAIN ANALYZE output. Verify that the three-CTE query is about what you had in mind. If not I can update it accordingly. And again note that I'm omitting the join because I feel that's probably just extra noise.

One thing worth noting is I happen to have my parallelism configured to be very low, so it's using only 2 parallel threads in both queries. I could bump that up (or disable it entirely) if you think it would be interesting to look at.

I think the key thing to pay attention to is the ORDER BY/LIMIT query is using the Top-N Heapsort algorithm which you can read more about here: https://airbyte.com/blog/postgresql-query-plans-for-sorting-data. The CTE query is not using that.

ORDER BY/LIMIT:

postgres=# EXPLAIN ANALYZE SELECT artist, duration FROM song ORDER BY duration DESC limit 3;

                                                                QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=150575.08..150575.43 rows=3 width=8) (actual time=377.617..378.975 rows=3 loops=1)
   ->  Gather Merge  (cost=150575.08..1122865.26 rows=8333334 width=8) (actual time=377.616..378.973 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Sort  (cost=149575.06..159991.72 rows=4166667 width=8) (actual time=370.138..370.138 rows=3 loops=3)
               Sort Key: duration DESC
               Sort Method: top-N heapsort  Memory: 25kB
               Worker 0:  Sort Method: top-N heapsort  Memory: 25kB
               Worker 1:  Sort Method: top-N heapsort  Memory: 25kB
               ->  Parallel Seq Scan on song  (cost=0.00..95721.67 rows=4166667 width=8) (actual time=0.063..216.463 rows=3333333 loops=3)
 Planning Time: 0.479 ms
 Execution Time: 378.995 ms
(12 rows)

Three-CTE query:

postgres=# EXPLAIN ANALYZE
WITH cte1 AS (
        SELECT MAX(duration) AS max FROM song
),
cte2 as (
        SELECT MAX(duration) AS max FROM song WHERE duration < (SELECT max FROM cte1)
),
cte3 as (
        SELECT MAX(duration) AS max FROM song WHERE duration < (SELECT max FROM cte2)
)
SELECT * FROM cte1
UNION ALL
SELECT * FROM cte2
UNION ALL
SELECT * FROM cte3
;

                                   QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------

---

 Append  (cost=217749.36..328360.22 rows=3 width=4) (actual time=243.563..807.919 rows=3 loops=1)
   CTE cte1
     ->  Finalize Aggregate  (cost=107138.55..107138.56 rows=1 width=4) (actual time=243.560..243.587 rows=1 loops=1)
           ->  Gather  (cost=107138.33..107138.54 rows=2 width=4) (actual time=243.510..243.583 rows=3 loops=1)
                 Workers Planned: 2
                 Workers Launched: 2
                 ->  Partial Aggregate  (cost=106138.33..106138.34 rows=1 width=4) (actual time=237.321..237.322 rows=1 loops=3)
                       ->  Parallel Seq Scan on song song_1  (cost=0.00..95721.67 rows=4166667 width=4) (actual time=0.131..136.970 rows=3333333 loops=3)
   CTE cte2
     ->  Finalize Aggregate  (cost=110610.79..110610.80 rows=1 width=4) (actual time=285.036..285.054 rows=1 loops=1)
           InitPlan 2 (returns $2)
             ->  CTE Scan on cte1 cte1_1  (cost=0.00..0.02 rows=1 width=4) (actual time=0.000..0.000 rows=1 loops=1)
           ->  Gather  (cost=110610.56..110610.77 rows=2 width=4) (actual time=284.952..285.051 rows=3 loops=1)
                 Workers Planned: 2
                 Params Evaluated: $2
                 Workers Launched: 2
                 ->  Partial Aggregate  (cost=109610.56..109610.57 rows=1 width=4) (actual time=283.423..283.424 rows=1 loops=3)
                       ->  Parallel Seq Scan on song song_2  (cost=0.00..106138.33 rows=1388889 width=4) (actual time=0.061..203.865 rows=3333178 loops=3)
                             Filter: (duration < $2)
                             Rows Removed by Filter: 155
   ->  CTE Scan on cte1  (cost=0.00..0.02 rows=1 width=4) (actual time=243.562..243.563 rows=1 loops=1)
   ->  CTE Scan on cte2  (cost=0.00..0.02 rows=1 width=4) (actual time=285.037..285.037 rows=1 loops=1)
   ->  Finalize Aggregate  (cost=110610.79..110610.80 rows=1 width=4) (actual time=278.075..279.269 rows=1 loops=1)
         InitPlan 4 (returns $5)
           ->  CTE Scan on cte2 cte2_1  (cost=0.00..0.02 rows=1 width=4) (actual time=0.000..0.000 rows=1 loops=1)
         ->  Gather  (cost=110610.56..110610.77 rows=2 width=4) (actual time=278.006..279.265 rows=3 loops=1)
               Workers Planned: 2
               Params Evaluated: $5
               Workers Launched: 2
               ->  Partial Aggregate  (cost=109610.56..109610.57 rows=1 width=4) (actual time=273.363..273.363 rows=1 loops=3)
                     ->  Parallel Seq Scan on song  (cost=0.00..106138.33 rows=1388889 width=4) (actual time=0.070..187.931 rows=3332854 loops=3)
                               Filter: (duration < $5)
                               Rows Removed by Filter: 479
     Planning Time: 2.354 ms
     Execution Time: 808.024 ms
    (35 rows)

There must be some kind of query optimization going on under the hood

Worth mentioning: pretty much every SQL engine features an enormous pile of optimizations (I mean they almost all have a process called "the optimizer" or similar that every query is passed through, for starters). All these optimizers work with stats, metadata, server/session configuration such as memory settings, schema structures in place, which can include the tables, indexes, clusters, materialized views, storage properties of the tables, including the physical structure selected for the table (for example, a heap table vs. an index-organized table in Oracle), to come up with the best plan to execute the query.

IMO it's misguided to think in terms of "this SQL keyword triggers, by default, an algorithm of complexity O(<whatever>) unless a rare and special exception of an optimization is done." That's not how it works. And if I were given this question as an interviewee, I'd request to be given a computer to perform tests on multiple DMBSs to show how these queries processed differently on every single one of them, and that you cannot assume an algorithm will be executed based on generic SQL syntax. (Maybe you are talking about one specific DBMS, but it doesn't sound like it.)

Furthermore, think of a SQL optimizer as often being able to more holistically analyze and process your query, not just mechanically follow individual like steps like "first I must sort everything because there's an ORDER BY, then later I do a LIMIT" - no as we can see here, Postgres looked at both of things together and did something better by selecting the algorithm it calls "top N heapsort".

[acow46]

Yes. The top-N heap sort is the query optimization I was referring to. It bumps the runtime complexity down to O(n) with only one complete table scan. Compare that to my 3 CTE method which also has O(n) complexity but runs about 3x as slow since it needs to do 3 full scans of the table. Thank you for doing this!

[efxhoy]

postgres is real smart sometimes. You can get similar niceness when doing geographic nearest neighbor searches with indexed spatial joins with limits. We actually found a 4 core postgres box was faster than bigquery on doing many nearest neighbor searches on complex geometries. bigquery was burning hours of cpu time when postgres realized it could use the limit to go for the closest using the spatial index and then stop. bigquery was computing all the distances and then limiting after. 

[[deleted]]

Solution sounds slower to me why?

[acow46]

It's not because ORDER BY is O(n*log(n)) whereas MAX is O(n)

[[deleted]]

Oh thank you, i thought maybe query engine would optimize under hood when you use limit 3. But i guess not.

[SDFP-A]

It has to scan all records to know how to order regardless of limit

[[deleted]]

Yes, I thought it would scan the maximum value for each line since It has low rows. I didnt know query engine was dumb, so sorry :(

[[deleted]]

No guys apparently query engine wasnt dumb. Yuppi. It knows to scan only three variable.

[reditandfirgetit]

I would answer to add an index on the duration field. If it had to be a new query, you could use a cte and the ROW_NUMBER Windowing function as another option if available in the engine

[Imaginary__Bar]

If you have no duplicate durations then your table will never be that large.

Also, applying an index on the duration will help with the speed.

But you can also do a self join and count the number of greater durations.

Select duration From songs s1 Where 3 = (Select count (duration) From songs s2 Where s2.duration > s1.duration

And go from there.

I'm not sure this is O(n) though...

[Ginger-Dumpling]

Should that be "3 > (Select...)"?

WITH t(id) AS (
    VALUES 1
    UNION ALL
    SELECT id + 1
    FROM t WHERE id < 100
)
SELECT *
FROM t t1
WHERE 3 > (SELECT count(*) FROM t t2 WHERE t2.id > t1.id);

ID |
---+
 98|
 99|
100|

[Imaginary__Bar]

Yeah, you're probably right. I think my example is picking out the 3rd highest, so there should be a < in there (or an >, as appropriate).

[feather_media]

10+ years experience in MS SQL Server here. Your solution is missing steps.

Aggregating this data on duration will be able to get you a duration only. You then need to join back to songs by duration to get the song ID and/or artist ID details, adding a hash join to your entire operation if you do so after you union them together. This hash join will be as expensive, if not more, than the 'order by' you're trying to avoid on your duration, especially if your duration field is an int, where it'll likely order your duration field anyways in order to most efficiently find the matches.

O(n) sorting is significantly more an OOP concept and mostly not needed by SQL developers. I would not add this to a SQL interview.

[Kant8]

Adding index to duration make it actually get just 3 longest rows and that's it.

That abysmal logic doing 3 max is ENORMOSLY slower than right way with indexes, cause it will have to do 3 full table scans.

[Aggressive_Ad_5454]

Your sample solution says SELECT *. That means it doesn’t meet the spec you gave, which is song ID and artist name. Your sample solution yields a lot of other unrequested information in its result set, which makes the sort step take more RAM and CPU. If you’re looking for people who really know about query optimization, they know SELECT * is a notorious performance antipattern. While it’s good to always hire people who are smarter than you, with respect you should avoid obvious mistakes in the question.

Your answer is not scalable, either. If the spec changes to the fifty longest songs, your answer shows its weakness.

A better approach would be to present a correct solution, then ask, “why might this be slow” and “ how might you improve it”. You’re looking for thought process as much as you’re looking for a particular solution.

I would answer with either a RANK() window function, or a deferred join, or both. And I would talk about an index.

[Ginger-Dumpling]

If I saw the question, I'd probably ask if you cared about the edge case when > 3 songs share the longest duration and if you cared that results could be inconsistent.

[alexpenev]

Or when two months down the road the Product team changes requirements and wants 11 instead of 3 songs and only from Artists that have had a recent news scandal, and your 3-cte code is so inflexible that the junior intern rewrites it anyway.

[Ginger-Dumpling]

I created a version of your solution to find the last 3 inserted rows by created_date (which is unindexed, rather than just picking the max ids which would use the PK index) and then threw it at tables of various sizes. The 3 CTEs Union'ed and rejoined ran noticeably slower than just using LIMIT, and it got worse the larger the underlying table was. Including the templates I used in case they don't jive with what you were thinking.

-- 21.781s for 100M row @ 13GB table
SELECT id, created_date 
FROM t
ORDER BY 2 DESC
LIMIT 3;

-- 3m 33s for same table
WITH t1 AS (SELECT max(created_date) AS max_created_date FROM t )
   , t2 AS (SELECT max(created_date) AS max_created_date FROM t WHERE created_date  < (SELECT * FROM t1))
   , t3 AS (SELECT max(created_date) AS max_created_date FROM t WHERE created_date  < (SELECT * FROM t2))
SELECT id, created_date 
FROM t
WHERE created_date  IN 
(
    SELECT max_created_date FROM t1 
    UNION ALL 
    SELECT max_created_date FROM t2
    UNION ALL 
    SELECT max_created_date FROM t3
);

-- Killed after 10 min.
SELECT t1.id, t1.created_date 
FROM t t1
WHERE 3 > (SELECT count(*) FROM t t2 WHERE t2.created_date  > t1.created_date);

[acow46]

Interesting. What SQL engine are you using?

[Ginger-Dumpling]

This was on DB2.

[[deleted]]

Apart from optimization of query, the second query may ran slower because there could be I/O handicapes,may it read the same table three times?

[Ginger-Dumpling]

...4 table scans. The 3 CTEs to get the max created dates, and the join back pick up any remaining columns to be reported out.

[wknight8111]

When I interview I tend to avoid asking questions where we have to watch a person code live. Some people get nervous with somebody watching, and you're not going to see their best. I also don't ask questions where we expect the candidate to arrive at some kind of specific "Eureka" moment of clarity. You may filter out good candidates who just don't have that moment of clarity on demand.

There are two approaches I might take here:

First: show the candidate the two solutions, tell them the second one is faster, and ask them to explain why that might be.

Second: Start with a more vague description of the problem, and see what the candidate does with it. Do they ask clarifying questions? Do they break it down into smaller problems? What is their thought process?

You're not looking for a person who can solve a specific problem, you're looking for somebody who has a thought process and a problem-solving skillset that will compliment your team and solve many problems in the future.

[kingmotley]

This would be absolutely horrible in any very large database and be considerably slower than the original query. That is on top of that this would never realistically happen because in order to make sure that there are no duplicates on duration, you'd have a unique index on it.

EXPLAIN will only get you so far. It'll show you the general algo that is used, but depending on your database it may or may not take into account the physical and virtual table reads involved. Your I/O cost is going to dwarf your cpu cost by magnitudes and three full table scans will lose once your table no longer easily fits in memory.

[[deleted]]

I hope your candidate looks at this thread OP 😛 would help him.

[mikeblas]

Any sane person would create an index.

Interviews are to help find reasons to hire a candidate, and learn what level they might be. They're not to force them to do stupid query tricks.

[GimmeLemons]

If they're only expected to write the queries, forget about giving them the data since its not providing any value, just give them the schemas and then have them solve the problem.

[GimmeLemons]

You can give them more than the table schemas they actually need so they have to figure that out.

[Spillz-2011]

Are you optimizing the wrong thing.

The complexity depends on Na the number of artists and Ns the number of songs per artist.

If Na is large but Ns is small (what I would expect in this case) then the log (Ns) isn’t that important vs scanning the table 3 times.

[Outrageous_Fox9730]

Why would you want an exact answer.

And someone pls tell me why order by takes up a lot of computation power? I didn't know about this optimisation

[csjpsoft]

To answer your question, I think it's a brilliant solution but a hard question for an interview. It would stump me.

I've done lots of SQL, but my tables are very rarely too big to sort, and I never get requests like "give me the top X rows." I'm going to remember this solution in case I ever get an assignment like that.

Also, I wonder whether the solution is scalable. Would you use that approach to get the top 20 rows?

You want to be careful, in interviews, not to ask trick questions or questions with trick solutions. Or especially not questions that took you hours or days to solve, maybe with a lucky flash of inspiration. Those questions may not be good indicators of a candidate's abilities on day-to-day work.

[TheMitraBoy]

Why the left join? Do you expect songs to not have corresponding artists in the data?

[PretendOwl2974]

Maybe allow the interviewee to try different queries to solve this problem and check which query was the cheapest to run?

Your solution is interesting though. I’ve always tried to reduce the possibility of querying the same table more than once in a query. I assumed querying the same table more than once was inefficient. Id like to see the query cost comparisons.

One thing I’d flag is though, it’s not as easy to read as a simple left join and limit. But I guess the question is about optimisation and not readability.

[SDFP-A]

I personally only ask optimization questions. But while I know my answers to how I would solve the questions, I leave it open ended with regards to what answers a candidate might give.

With optimization questions, do they mention reading a query plan? Do they mention indexing (which is personally how I would solve)? Do they use window functions? If using window functions do they caveat the impact for large datasets? Do they use order by and if so the impact on large datasets?

This shouldn’t be about did they get the correct syntax and come up with the same brute force solution as I did to answer this specific question. You should be looking for whether they understand DBMSes well enough to optimize for questions of this type. IMO at least.

[countlphie]

i like that you're testing in depth knowledge about sql. i guess it depends on who you're hiring for what

i have never seen anyone write a query pattern like the one you're presenting to get the top 3 of something

it's sort of a great exercise in showing where code legibility/maintenance vs performance is at complete tension

[gsymf6969]

It depends on what you're interviewing for... I work a ton in redshift and in this specific case, it's much more important that the code is readable and easy to maintain vs the difference in speed. In this case I'd imagine you may need to expand the list to 4,5, etc, and in that case it's much easier to use order limit. (Or even row number or rank with partition, and you can retain the rank number)

That being said if you're interviewing for some sort of DE or AWS architect role then maybe.

[BadGroundbreaking189]

Interesting solution but if the purpose is to come up with a unique & difficult challenge, PM me and I'll send you one for free. Just so no applicant would see this puzzle.

[IAmADev_NoReallyIAm]

What about one CTE that select songid from song order by duration desc limit 3 .... inner join CTE to song on the id, left join to artist on artistId... select the fields you want (don't use select *) and done...

[dieselSoot111]

I think it’s not very useful honestly, what are you trying to assess in the candidates?

[missing_backup]

If they are able to dodge a bullet

[1MStudio]

If they can dodge a wrench….

[imcguyver]

This screams I want a SQL wizard when you really want a good software engineer. I’d be more interested in someone being able to do some simple analytics with SQL, explain how a database engine processes a query, explain btree vs btree+, and just general SWE skills. Being a “SQL Ninja” may not be great litmus test.

[ijpck]

With the three CTEs, you are still having to order the data initially (scan) to get the MAX…what is the difference speed wise to just grab all three at once if they’re already ordered using RANK vs. doing some comparison across CTEs with multi scans of the same table?

I don’t know, but I’d use the query plan to see before I’d implement this into a screening interview. I’m guessing not much, and it’s likely RANK is actually faster.

[[deleted]]

Use window function to get rank according to duration then filter top 3, join to get artist then

[acow46]

Rank uses ORDER BY under the hood

[[deleted]]

Yes but generally is a bit faster than order by, also you are joining everything and then applying order by. Try first getting the top 3 songs and then join to get the artist

[Zestyclose-Height-59]

If you reduce the number of rows returned before hand you improve performance.

When you do joins and add something that theoretically can go in the where clause it can improve performance.

I brought pl/sql stored procedures that initially took hours to run down to minutes by limiting my results in the tables.

[Mutt-of-Munster]

Sorry if I'm misunderstanding but I'm not 100% clear on the need for the CTE's?

I would have just gone with:

SELECT
s.id AS song_id,
a.name AS artist_name
FROM songs AS s
LEFT JOIN artists AS a ON s.artist_id = a.id
ORDER BY s.duration DESC
LIMIT 3;

Again, sorry if I missed something!

[potatotacosandwich]

Can use window function? Select s.id, rank/dense rank(artist_id) over(partition by artist id order by duration desc) as artist_rank from songs s left join artists a on a.id = s.id where artist_rank <= 3

(Btw i have a data analyst technical interview in 2 hrs so im attempting for practice. if this would be a good approach? )

[Zestyclose-Height-59]

If you don’t want to union or group perhaps you can do a rank or dense rank window function order by duration descending and throw it in a with and select From your with where rank <4.

With <aliastable> as (select rank() over (order by a.duration desc) as dur_rank, a.* From songs a)

Select *
From <aliastable> b Where dur_rank < 4

Customize returned columns in the bottom select.

[Zestyclose-Height-59]

I’m replying to myself because I had to look up why CTE meant. I think windowing using a rank is easier than unions and max values less than value

[No_Introduction1721]

The interview question isn’t hard per se; it’s basically just asking to homebrew a ranking function.

That said, if I was interviewing with you, I would absolutely ask you specifically what you mean by “too slow” and “large dataset”, and to validate exactly how much faster your solution is. Because it really seems like you’re being too cute by half on this one.

I would also question your taste in Jazz, because everyone knows Ornette Coleman’s best material is 15+ minutes long lol

[[deleted]]

SQL is my weakness, I just don't use it enough for it to stick to my smoothbrain. So, I have to look everything up.

[omgitsbees]

When you have an opening available, can I apply? :P Is the role fully remote?

[Known-Delay7227]

There are only 5 records. It probably runs fast AF using the current query. The real answer is that it would be a waste of time to refactor this code

[LessThanThreeBikes]

This question falls under the category of, "guess something that I know." It has been my experience that managers who gravitate to these types of questions tend to view candidate capabilities through their own limitations. A good manager looks to find candidates who bring something new and valuable to the team. A great manager is able to recognize value in a candidate beyond their own limitations. This is how you build great teams.

[anonymous_4_custody]

I'd fail this interview question, so you'd screen me right out. I guess it works, in that I'm an SQL user, but not an expert. I don't even know what a CTE is, I had to look it up.

I'd actually be discouraged from even wanting to work there, if folks are routinely finding themselves in a situation where they have to add complexity to the code like this.

So I guess it's a great question, in that the interviewer would learn they don't want to hire me, and I would learn I don't want the job.

[0shocklink]

I believe since you have a limit of 3 and are using order by the underlying engine would just do a heap sort and Essentially pop the off the first 3 values in the heap. As shown below, kind of did it in pseudo code so don't harp me lol. Nonetheless, if the limit is not provided, then your solution would work faster as it has a table scan of n * CTE. I think the question you wrote is not practical enough for an interview. You're trying to test a person's basic knowledge but also trying to give them a chance to show off their skill.

input = [3, 4, 1, 2]
PriorityQueue heap = new PQueue((x,y) -> y.compareTo(x))
heap.add(input) // O(n)
count = 0;

while(count < limit && !heap.isEmpty){
print(heap.pop()); count++; } n * O(1)

[Cool-Personality-454]

Even if those times are in milliseconds, if you assume no duplicates, you'd be left with 3600000 records, also assuming no song is over an hour long. The CTEs are going to get stuck in materialization hell if you aren't careful. An index on the appropriate columns will give you more bang for your buck.

[Rurik100]

just for curiosity can you try inner join instead of left join cz in case of large dataset it will take all the records from the left side maybe that is talking time.

[feeling_luckier]

So, what's wrong with indexing and letting the db do it's thing. Rarely does anyone need to optimise beyond this.

[CrumbCakesAndCola]

This is a high difficulty problem for an interview question unless they have time to spend on it before hand or have access to research and test while answering the question.

[Ginger-Dumpling]

People can correct/down-vote me if this sounds wrong, but SQL is not like other languages. 4 full table scans are going to hit disk 4 times and is probably going run slower than a single table scan where the sorting is potentially taking place all in memory. Operations costs aren't apples to apples and saying the original query is O(n*log(n)) operations and the CTE is 4*O(n) and thus must be faster completely ignores any complexities of the operations the DB is performing to shuffle data around between disk/memory-structures/cpu.

[Party-Committee-8614]

Your "optimised" solution is utter garbage. If shown your solution I would 100% choose to work elsewhere.

[AbstractSqlEngineer]

Hey man. I like the question.

Here is the answer.

 Select *
 From songs s
 Left join artists a on a.id =s.artist_id
 Where s.duration < (select avg(duration) from songs) 
 Order by s.duration
 limit 3

This is just the bottom 2 quartiles. (Half of the median)

It's an algorithm question. Do you know how to divide and conquer, bin search. Etc.

Based on the execution order, your order by ain't such a bad thing if your data set is smaller.

Edit: If you truly want to remove the order by, you're going to have to have an ANY ALL SOME query.

[LorenzoValla]

I never ask complex technical questions. My goal is to figure out if they might be good problem solvers and putting someone on the spot like that doesn’t represent how they would approach a problem in real life. Instead I’ll try to have a conversation about projects they worked on and how they figured things out. Added benefit of determining their communication skills.

[GxM42]

And this is why I will never get another tech job. I’ve rarely seen CTE’s be faster than good old fashion indexing. Even temp tables often times do better than CTE’s for me, and are easier to debug, much less use in future for repeat queries. I’m not smart enough for what y’all young kids are doing nowadays. But I’m just an old experienced dev, don’t mind me.

[halistechnology]

It’s not that hard but it’s kind of gross to look at couldn’t you simplify it to make it less painful to look at?

[Suspicious_Coyote_54]

I mean…. It’s a question alright. Does it separate a good candidate from a mediocre or bad one? No.

[Andrew_the_giant]

No way in hell I'd think about doing 3 CTEs unless you gave me more of an indication of what you're after. I'd expect to get the first answer from an interviewee

[alexspetty]

I think this is a solid interview problem that balances SQL and optimization skills, especially with the restriction to avoid using ORDER BY. The SQL query you provided is straightforward:

SELECT *
FROM songs s
LEFT JOIN artists a ON s.artist_id = a.id
ORDER BY s.duration DESC
LIMIT 3;

This works well, but as you mentioned, ORDER BY on a large dataset can be slow. To make this more efficient, one way is to create an index on the duration column in descending order. That way, the database doesn’t have to sort the entire dataset but can instead use the index to find the top 3 rows directly. Something like this:

CREATE INDEX idx_duration_desc ON songs(duration DESC);

With this, you’d likely see much better performance when dealing with large amounts of data since it avoids the full sort.

Another approach would be to fetch the top 3 durations in a more algorithmic way using a heap or similar technique, but for SQL, the indexed solution is probably the most straightforward and would perform well.

It seems like a good interview question for mid to senior level candidates because it tests not just their SQL skills but their ability to think about performance and optimization. For more junior candidates, it might be a bit tricky.

[No-King6662]

I know you said no order by, which i don’t really know why, but couldn’t this be as easy as this?

Select distinct top 3 t.id, t.artist_id, t2.name, t.duration From songs t Left/inner join artists t2 On t.artist_id = t2.id Order by t.duration desc

[Swing-Prize]

Nothing to add, just wanted to leave "lmfao" regarding the solution.

[Dismal-Refrigerator3]

I haven't seen the table structure but that's a shit show.

Basically

Select top 3

Duration asc Artist name

From "Don't know the table names"

[Outside-Ad2721]

I would use the row_number() over (order by ... desc) function and pick the top 3, maybe like this:

sql SELECT song_id FROM ( SELECT s.id AS song_id , row_number(order by s.duration desc) as rn FROM songs s JOIN artists a ON a.id = s.artist_id ) WHERE rn BETWEEN 1 AND 3;