5 ms·

How query optimisation looks like? Does it optimize on the SQL or algorithm level?

• BenoitP 2y ago
  It describes all the way the SQL could be executed, then choses the faster plan. For example: if you're looking for the user row with user_id xx, do you read the full table then filter it (you have to look at all the rows)? Or do you use the dedicated data structure to do so (an index will enable to do it in the logarithm of the number of rows)? A lot more can be done: choosing the join order, choosing the join strategies, pushing the filter predicates at the source, etc. That's the vast topic of SQL optimization.
  • abhishekjha 2y ago
    Is there a more general reading for software engineers? Seems like jumping right into the code can be a bit overwhelming if you have no background on the topic.
    • orlp 2y ago
      Not exactly reading but I would recommend the database engineering courses by Andy Pavlo that are freely available on YouTube.
    • jmgimeno 2y ago
      PostgreSQL Query Optimization: The Ultimate Guide to Building Efficient Queries, by Henrietta Dombrovskaya and Boris Novikov Anna Bailliekova, published by Apress in 2021.
      • rotifer 2y ago
        You may discover this if you go to the Apress site, but there is a second edition [1] out. [1] https://hdombrovskaya.wordpress.com/2024/01/11/the-optimization-book-second-edition-is-here/ https://hdombrovskaya.wordpress.com/2024/01/11/the-optimizat...
    • sbuttgereit 2y ago
      Always worth a mention: https://use-the-index-luke.com/ https://use-the-index-luke.com/ Markus Winand (the website's author) has also written a book on the subject targeted at software developers which is decent for non-DBA level knowledge.
    • whiterknight 2y ago
      https://www.sqlite.org/queryplanner.html https://www.sqlite.org/queryplanner.html
• magicalhippo 2y ago
  For the databases I've used, which excludes PostgreSQL, most optimization happens on algorithmic level, that is, selecting the best algorithms to use for a given query and in what order to execute them. From what I gather this is mostly because various different SQL queries might get transformed into the same "instructions", or execution plan, but also because SQL semantics doesn't leave much room for language-level optimizations. As a sibling comment noted, an important decision is if you can replace a full table scan with an index lookup or index scan instead. For example, if you need to do a full table scan, and do significant computation per row to determine if a row should be included in the result set, the optimizer might change the full table scan with a parallel table scan then merge the results from each parallel task. When writing performant code for a compiler, you'll want to know how your compilers optimizer transforms the source code to machine instructions, so you prefer writing code the optimizer handles well and avoid writing code the optimizer outputs slower machine instructions for. After all the optimizer is programmed to detect certain patterns and transform them. Same thing with a query optimizer and its execution plan. You'll have to learn which patterns the query optimizer in the database you're using can handle and generate efficient execution plans for.
  • Sesse__ 2y ago
    Postgres is a fairly standard System R implementation. You convert your SQL into a join tree with some operations at the end, and then try various access paths and their combinations.
• mdavidn 2y ago
  At a very high level, the query planner's goal is to minimize the cost of reading data from disk. It gathers pre-computed column statistics, like counts of rows and distinct values, to estimate the number of rows a query is likely to match. It uses this information to order joins and choose indexes, among other things. Joins can be accomplished with several different algorithms, like hashing or looping or merging. The cheapest option depends on factors like whether one side fits in working memory or whether both sides are already sorted, e.g. thanks to index scans.
• paulddraper 2y ago
  The query optimization chooses what algorithms provide the results requested by the SQL.