Can databases use data structures/algorithms to respond to arbitrary queries?

Question

Let's say that I am interested in discovering the smallest 5 numbers in a set of numbers.

In SQL, this would work:

select number
from (
    select number, 
        row_number() over(order by number asc) as order_
    from my_table
) ranking
where order_ <= 5;

Alternatively, I could use the Quickselect algorithm (in my language of choice), to solve this problem, returning data in O(N) time.

Is the SQL engine using a similar optimum/near-optimum algorithm to solve this problem? Here is an execution plan in a SQL Server 2017 DB:

My interpretation is that it's taking a brute-force approach (read data, sort, compute order_, filter). With a non-clustered index on number, the table scan switches to an index scan, but otherwise, it's still the same operation.

Are there examples of databases (SQL or otherwise) where

1. The database is aware of specific patterns of queries and tries to use a data structure/algorithm to respond to the query (similar to how a human would handle it)?
2. The database provides options for humans to nudge the engine towards specific types of algorithms/data structures?

What prevents us from being able to describe queries and have a database engine figure out a near-optimal approach to solve the query?

I have a feeling that I am glossing over practical challenges that an RDBMS actually robustly handles. For instance, ACID compliance, handling data that won't fit in memory, etc make it indispensable. Implementing a binary-tree data structure + traversal on data that doesn't fit in RAM might be too niche and too complex to be useful in a general setting?

Answer 1

Full disclosure: I've written the sort subsystem for a commercial database server, albeit not a SQL one.

Database servers will use every trick you can think of, and a lot you haven't thought of, to speed up operations such as sorting. But it can only do so much if you give it an overly complex query.

Query optimisers are not magic, any more than compilers are. A compiler could, in theory, optimise sin(x)*sin(x) + cos(x)*cos(x) to 1.0, but most would agree that detecting cases like this is not a good use of a compiler developer's time. Similarly, you should think very hard about how you sort XML documents by title; you don't want to have to parse the XML on every SELECT query.

You could have expressed the query like this (apologies for the capital letters; I'm in the habit for SQL):

SELECT number
FROM my_table
ORDER BY number asc
LIMIT 5;

This is much simpler, and it gives the query optimiser more to work with. I'd be very interested in seeing what plan you got.

Query optimisers never work in a vacuum. They always take into account whatever context they can. So, for example, if my_table is a small table, then the optimiser will often reason, quite correctly, that it should just do a dumb thing with low constant factors.

Assuming that isn't the case, then with the simplified query, a modern DBMS will probably take an approach like this:

• If there is an index on the number field, it will try very hard to use an index scan. The query will then take sublinear time in the size of the table. I encourage you to try it. This is probably the number one thing you can do if you need high performance on a query of this kind.
• Otherwise, it will likely implement it with a single pass over the table, using a 5-element min-heap to form the result set. Like quickselect, this is still linear in the size of the table, but it's "quickheap" instead.

Answer 2

No, your database will not detect the semantics of your query.

What they do do, and in excruciating depth, is do their darndest to execute your query as fast (or as efficient, depending on settings) as possible. Also, these kinds of operations are the bread and butter of the DB - everything from the hardware level up will be optimized fully to perform these operations as quickly as possible within the RDBMS.

In your particular case, there is no conceivable way for the RDBMS to do it differently. There is no generic syntax for specifying a "quickselect"-like operation in SQL. In other cases, sub-queries can and routinely are optimized together with their parents, but due to your construction with the analytic function (which you presumably picked like this for the purpose of this question, it is a little more complex than needed), I would not expect the RDBMS to figure it out.

Still. The big carrot for doing it in SQL instead of in your code is that this saves you from transferring an arbitrarily large amount of data over a possibly slow network - and not only the network, but the full stack ending behind the DB library of your application, in your actual code, including coding and recoding, validation etc.. This alone is, in my experience, almost always worth it for significant amounts of data (and for insignificant amounts it usually doesn't matter either way).

While the operation is $O(n\log n)$ in the DB, the constants may still make it faster or even much faster than $O(n)$ in your application, if it takes long to transfer all the data to it. Especially if you start scaling - imagine not only having to transfer lots of data to one application, but to many - you can easily hit a network bottleneck which is out of your control to remove; while bottlenecks on your RDBMS server are usually much more under your control (or you can throw indexes, materialized views etc. at the problem, restructure your SQL, optimize RAM usage and so on).

On your concrete questions:

The database is aware of specific patterns of queries and tries to use a data structure/algorithm to respond to the query (similar to how a human would handle it)?

No, it cannot usually sense complex patterns. But what they do have are the so-called "statistics" - i.e., histograms about the contents of their tables and indexes. Each time the RDBMS needs to process a SQL statement, it creates an "execution plan" which takes all these statistics, and of course also all available algorithms, data structures and such into account.

In the distant past, RDBMS would instead use rule-based plans which were pretty stupid. But with the statistics-based approach, if all goes well (and for regular statements on a well-tuned system, that's mostly a given in a modern RDBMS) then at the end of the day it comes up with a solution equal or better to what a human can do, simply because it usually has more information.

Exceptions to that rule are where good DBAs or DB-centric devs shine and make their money.

The database provides options for humans to nudge the engine towards specific types of algorithms/data-structures?

Sure. At least the RDBMSses I know (foremost Oracle) give the human a plethora of options; both through creating specialized indexes and other structures, and through setting different options on all the data structurs; through tuning system settings (relative sizes of RAM buffers for different things; different weights on preferring certain algorithms or solutions); and finally through so-called "hints" in individual SQL queries with a non-SQL meta-language.

What prevents us from being able to describe queries and have a database engine figure out a near-optimal approach to solve the query?

Nothing is preventing us, and that is the way it should work. That's what SQL is all about - while one may naively assume that SQL is an instruction of how to work, it is most definitely not. A RDBMS is free to interpret it and plan the actuall work in whichever way it sees fit, and the art is to formulate the SQL in a way which is letting the execution planner do its job (i.e., to avoid something like in your example which pretty much shoe-horns it into a specific, non-optimal solution), but then to get out of its way.