7 ms·

How Does the SQL Server Query Optimizer Work?

86 points by xameeramir 10y ago

adamnemecek 10y ago
If this tickles you fancy, you should check out this site http://use-the-index-luke.com http://use-the-index-luke.com or a book by the same author https://www.amazon.com/Performance-Explained-Everything-Developers-about/dp/3950307826/ref=as_li_ss_tl?ie=UTF8&qid=1484664477&sr=8-1&keywords=Sql+performance&linkCode=ll1&tag=akhn-20&linkId=c4b9565b49e6d7df8926ea4b2c38638d https://www.amazon.com/Performance-Explained-Everything-Deve... He goes into great detail to explain how exactly SQL indices work and how to leverage this to write queries.
arnon 10y ago
There's very little actual data here... Oracle has a bit more data on their website.. https://docs.oracle.com/database/121/TGSQL/tgsql_optcncpt.htm#TGSQL94983 https://docs.oracle.com/database/121/TGSQL/tgsql_optcncpt.ht...
- smcl 10y ago
  I think "SQL Server Database Engine" refers to MS SQL here, I'm not sure how useful the Oracle stuff is for MS SQL Server (I have never used Oracle)
  - arnon 10y ago
    They all operate the same way give or take
rusanu 10y ago
I have a blog article that covers a bit more details: http://rusanu.com/2013/08/01/understanding-how-sql-server-executes-a-query/ http://rusanu.com/2013/08/01/understanding-how-sql-server-ex...
- swasheck 10y ago
  I remember the first time that I read this. I still reference it many years later.
morgo 10y ago
I have a guide that shows the equivalent for MySQL. It's kind of split between these two pages: http://www.unofficialmysqlguide.com/introduction.html http://www.unofficialmysqlguide.com/introduction.html http://www.unofficialmysqlguide.com/server-architecture.html http://www.unofficialmysqlguide.com/server-architecture.html
psi-squared 10y ago
There's a really nice article about the Postgres query optimizer, which goes into much more detail about the algorithms used (it's likely that at least the basic ideas are shared with SQL server, though I can't say for sure). I really like the exposition in this: http://jinchengli.me/post/postgres-query-opt/ http://jinchengli.me/post/postgres-query-opt/
- crench 10y ago
  thanks for that!
- Someone 10y ago
  There’s also https://www.sqlite.org/optoverview.html https://www.sqlite.org/optoverview.html and (more detailed) https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html for SQLite.
- quizotic 10y ago
  As a "newer" engine, SQL Server has a couple of tricks that aren't found in most other systems, including intra-query parallelism across multiple threads. This capability requires occasional reshuffling of data between threads, which makes SQL Servers internals a little more like a distributed DBMS (think Netezza/Teradata) than the wonderful, but ancient, Postgres. All of which means that SQL Server has a larger palette of execution options and some different optimization decisions than PG.
protomyth 10y ago
The reality is that, even after more than 30 years of research, query optimizers are highly complex pieces of software which still face some technical challenges. Yep. It still amazes me how queries can go from absolutely great to scanning tables with a row added in the wrong place. WITH RECOMPILE still scares the heck out of me. It can really help when distributions change, but it can also kill your performance with a bad query plan choice. It addition to the hint show, you can also force certain indexes. This didn't seem to be as big a problem on SQL Server as its parent code Sybase ASE. Sybase made some really, really bad choices on big tables. No amount of optimization will fix a bad schema design. This is also a field where talking to people about how you built your machines and where the indexes are located can make a world of difference. If you cannot have the whole database on the fastest storage, then at lest put the indexes there.
- swasheck 10y ago
  > It still amazes me how queries can go from absolutely great to scanning tables with a row added in the wrong place. I think that this is a bit of an oversimplification, though I understand the sentiment. Statistics skew is one of the primary reasons for such a dramatic shift in query planning and adding a row can create such a problem if you're already at some sort of skew tipping point and that one row pushes you over the edge. It would be nice to know more about where the edge is and how to plan to ensure you don't drive your application's/server's performance off the cliff, though.
  - protomyth 10y ago
    > I think that this is a bit of an oversimplification, though I understand the sentiment. No, it really isn't. Cache / Memory isn't a sliding scale, and once you exceed it you fall off the cliff. Databases queries can fall off a cliff if you exceed your memory. I've watched a query that was executing in a couple of seconds drop into many minutes territory because it had to start paging. There is a real machine with limited memory running your queries and it has been my experience that warnings are rare.
    - 10y ago
atombender 10y ago
Tangentially, I've always wondered why databases today still aren't capable of being self-tuning. In 2016 we're still manually creating indexes, and databases still use the exact same physical data structures for everything they store, no matter if they're storing 1,000 rows or 1 billion. The problem isn't too dissimilar from the challenge that tracing profilers try to solve. One key difference, of course, is that dynamically adapting the physical storage strategy to usage patterns is relative expensive, resource-wise. But not every problem needs to be solved for those users with 1 billion rows. I would argue that most applications — web apps, anyway — have datasets that are large enough to optimize, yet still small enough that a dynamic, self-tuning system could be entirely feasible. The resource problem can be mitigated in several ways. One is to off-load processing horizontally, so while a master is chugging away, a slave is building a table using a different strategy. Another is to simply perform expensive optimizatons during off-peak hours. Also, I find it interesting that databases also still operate in a mode where reads and writes happen in the same physical store. I have an idea for a database that separates the two: You have the transactional, highly consistent, non-horizontally-scalable OLTP-style "transaction store" where a client carefully constructs reads and writes against the absolute truth, but where reads aren't super efficient; and then you have the "query store" which is a read-only, highly replicated and sharded set of mirrors that uses highly optimized data structures that are created on demand based on the topology of the data and usage patterns (in particular, the same data can potentially be indexed in multiple ways (B-tree, compressed columns, etc.) until the profiler finds the best strategy). The mirrors' replication should be tunable so that some "hot" subsets can be immediately consistent, and others can use slower batch transfers to reduce lock contention on updates. Right now, when people build scalable systems, they often apply this design by putting the truth in PostgreSQL or whatever, and then indexing it into Elasticsearch or Solr. But there are huge benefits to combining the two into a single, unified system.
- jws 10y ago
  Back in the mid '90s Digital's RDB (an early SQL database) had a companion product, Rdb Expert, which would analyze a live database over a period of time and make a script to set up its indices (ordered and hashed) and table placement rules to optimize a database. It wasn't as good as a really good expert, but it was at least a 90% solution. As I recall it was pretty good at getting a tuple and its one to many associated tuples into the same disk page so you needed fewer disk reads to access data. These were disks that were capable of about 35 seeks per second, so it really mattered. (The drive I'm thinking of is the RA90. 1.2GB in a half of a 6U or so space. 32kg. 280 watts.)
mozumder 10y ago
Is there a Postgres equivalent to reoptimize prepared statements?
- quizotic 10y ago
  I think you can just prepare them again, no? Of course the onus is then on poor you to know when that might make sense because of changes to the referenced tables. Though postgres is so incredibly open, you could probably do that with a trigger or a hook into analyze or vacuum or copy-from.
  - anarazel 10y ago
    Prepared statements are re-planned on use if the underlying statistics change.
    - quizotic 10y ago
      Ah. Thank you for the correction!

86 points by xameeramir 10y ago

If this tickles you fancy, you should check out this site http://use-the-index-luke.com http://use-the-index-luke.com or a book by the same author https://www.amazon.com/Performance-Explained-Everything-Developers-about/dp/3950307826/ref=as_li_ss_tl?ie=UTF8&qid=1484664477&sr=8-1&keywords=Sql+performance&linkCode=ll1&tag=akhn-20&linkId=c4b9565b49e6d7df8926ea4b2c38638d https://www.amazon.com/Performance-Explained-Everything-Deve... He goes into great detail to explain how exactly SQL indices work and how to leverage this to write queries.

arnon 10y ago

There's very little actual data here... Oracle has a bit more data on their website.. https://docs.oracle.com/database/121/TGSQL/tgsql_optcncpt.htm#TGSQL94983 https://docs.oracle.com/database/121/TGSQL/tgsql_optcncpt.ht...

smcl 10y ago
I think "SQL Server Database Engine" refers to MS SQL here, I'm not sure how useful the Oracle stuff is for MS SQL Server (I have never used Oracle)
- arnon 10y ago
  They all operate the same way give or take

rusanu 10y ago

I have a blog article that covers a bit more details: http://rusanu.com/2013/08/01/understanding-how-sql-server-executes-a-query/ http://rusanu.com/2013/08/01/understanding-how-sql-server-ex...

swasheck 10y ago
I remember the first time that I read this. I still reference it many years later.

morgo 10y ago

I have a guide that shows the equivalent for MySQL. It's kind of split between these two pages: http://www.unofficialmysqlguide.com/introduction.html http://www.unofficialmysqlguide.com/introduction.html http://www.unofficialmysqlguide.com/server-architecture.html http://www.unofficialmysqlguide.com/server-architecture.html

psi-squared 10y ago

There's a really nice article about the Postgres query optimizer, which goes into much more detail about the algorithms used (it's likely that at least the basic ideas are shared with SQL server, though I can't say for sure). I really like the exposition in this: http://jinchengli.me/post/postgres-query-opt/ http://jinchengli.me/post/postgres-query-opt/

crench 10y ago
thanks for that!
Someone 10y ago
There’s also https://www.sqlite.org/optoverview.html https://www.sqlite.org/optoverview.html and (more detailed) https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html for SQLite.
quizotic 10y ago
As a "newer" engine, SQL Server has a couple of tricks that aren't found in most other systems, including intra-query parallelism across multiple threads. This capability requires occasional reshuffling of data between threads, which makes SQL Servers internals a little more like a distributed DBMS (think Netezza/Teradata) than the wonderful, but ancient, Postgres. All of which means that SQL Server has a larger palette of execution options and some different optimization decisions than PG.

protomyth 10y ago

The reality is that, even after more than 30 years of research, query optimizers are highly complex pieces of software which still face some technical challenges. Yep. It still amazes me how queries can go from absolutely great to scanning tables with a row added in the wrong place. WITH RECOMPILE still scares the heck out of me. It can really help when distributions change, but it can also kill your performance with a bad query plan choice. It addition to the hint show, you can also force certain indexes. This didn't seem to be as big a problem on SQL Server as its parent code Sybase ASE. Sybase made some really, really bad choices on big tables. No amount of optimization will fix a bad schema design. This is also a field where talking to people about how you built your machines and where the indexes are located can make a world of difference. If you cannot have the whole database on the fastest storage, then at lest put the indexes there.

swasheck 10y ago
> It still amazes me how queries can go from absolutely great to scanning tables with a row added in the wrong place. I think that this is a bit of an oversimplification, though I understand the sentiment. Statistics skew is one of the primary reasons for such a dramatic shift in query planning and adding a row can create such a problem if you're already at some sort of skew tipping point and that one row pushes you over the edge. It would be nice to know more about where the edge is and how to plan to ensure you don't drive your application's/server's performance off the cliff, though.
- protomyth 10y ago
  > I think that this is a bit of an oversimplification, though I understand the sentiment. No, it really isn't. Cache / Memory isn't a sliding scale, and once you exceed it you fall off the cliff. Databases queries can fall off a cliff if you exceed your memory. I've watched a query that was executing in a couple of seconds drop into many minutes territory because it had to start paging. There is a real machine with limited memory running your queries and it has been my experience that warnings are rare.
  - 10y ago

atombender 10y ago

Tangentially, I've always wondered why databases today still aren't capable of being self-tuning. In 2016 we're still manually creating indexes, and databases still use the exact same physical data structures for everything they store, no matter if they're storing 1,000 rows or 1 billion. The problem isn't too dissimilar from the challenge that tracing profilers try to solve. One key difference, of course, is that dynamically adapting the physical storage strategy to usage patterns is relative expensive, resource-wise. But not every problem needs to be solved for those users with 1 billion rows. I would argue that most applications — web apps, anyway — have datasets that are large enough to optimize, yet still small enough that a dynamic, self-tuning system could be entirely feasible. The resource problem can be mitigated in several ways. One is to off-load processing horizontally, so while a master is chugging away, a slave is building a table using a different strategy. Another is to simply perform expensive optimizatons during off-peak hours. Also, I find it interesting that databases also still operate in a mode where reads and writes happen in the same physical store. I have an idea for a database that separates the two: You have the transactional, highly consistent, non-horizontally-scalable OLTP-style "transaction store" where a client carefully constructs reads and writes against the absolute truth, but where reads aren't super efficient; and then you have the "query store" which is a read-only, highly replicated and sharded set of mirrors that uses highly optimized data structures that are created on demand based on the topology of the data and usage patterns (in particular, the same data can potentially be indexed in multiple ways (B-tree, compressed columns, etc.) until the profiler finds the best strategy). The mirrors' replication should be tunable so that some "hot" subsets can be immediately consistent, and others can use slower batch transfers to reduce lock contention on updates. Right now, when people build scalable systems, they often apply this design by putting the truth in PostgreSQL or whatever, and then indexing it into Elasticsearch or Solr. But there are huge benefits to combining the two into a single, unified system.

jws 10y ago
Back in the mid '90s Digital's RDB (an early SQL database) had a companion product, Rdb Expert, which would analyze a live database over a period of time and make a script to set up its indices (ordered and hashed) and table placement rules to optimize a database. It wasn't as good as a really good expert, but it was at least a 90% solution. As I recall it was pretty good at getting a tuple and its one to many associated tuples into the same disk page so you needed fewer disk reads to access data. These were disks that were capable of about 35 seeks per second, so it really mattered. (The drive I'm thinking of is the RA90. 1.2GB in a half of a 6U or so space. 32kg. 280 watts.)

mozumder 10y ago

Is there a Postgres equivalent to reoptimize prepared statements?

quizotic 10y ago
I think you can just prepare them again, no? Of course the onus is then on poor you to know when that might make sense because of changes to the referenced tables. Though postgres is so incredibly open, you could probably do that with a trigger or a hook into analyze or vacuum or copy-from.
- anarazel 10y ago
  Prepared statements are re-planned on use if the underlying statistics change.
  - quizotic 10y ago
    Ah. Thank you for the correction!