Semi-join Subquery Optimizations - Source

Revision: 124642
User: Sergei Petrunia
Date: 2023-03-26 20:51

<<toc>>

MariaDB has a set of optimizations specifically targeted at //semi-join subqueries//.

== What is a Semi-Join Subquery

A semi-join subquery has a form of

<<code lang='sql'>>
SELECT ... FROM outer_tables WHERE expr IN (SELECT ... FROM inner_tables ...) AND ...
<</code>>

that is, the subquery is an IN-subquery and it is located in the WHERE clause. The most important part here is

//with semi-join subquery, we're only interested in records of outer_tables that have matches in the subquery//

Let's see why this is important. Consider a semi-join subquery:

<<code lang='sql'>>
select * from Country 
where 
  Continent='Europe' and 
  Country.Code in (select City.country 
                   from City 
                   where City.Population>1*1000*1000);
<</code>>

One can execute it "naturally", by starting from countries in Europe and checking if they have populous Cities:

The semi-join property also allows "backwards" execution: we can start from big cities, and check which countries they are in:

To contrast, let's change the subquery to be non-semi-join:

<<code lang='sql'>>
select * from Country 
where 
   Country.Continent='Europe' and 
   (Country.Code in (select City.country 
                   from City where City.Population>1*1000*1000) 
    or Country.SurfaceArea > 100*1000  -- Added this part
   );
<</code>>

It is still possible to start from countries, and then check
* if a country has any big cities
* if it has a large surface area:

The opposite, city-to-country way is not possible. This is not a semi-join.

=== Difference from Inner Joins

Semi-join operations are similar to regular relational joins. There is a difference though: with semi-joins, you don't care how many matches an inner table has for an outer row. In the above countries-with-big-cities example, Germany will be returned once, even if it has three cities with populations of more than one million each.

== Semi-Join Optimizations in MariaDB

MariaDB uses semi-join optimizations to run IN subqueries.The optimizations are enabled by default. You can disable them by turning off their [[server-system-variables#optimizer_switch|optimizer_switch]] like so:

<<code lang='sql'>>
SET optimizer_switch='semijoin=off'
<</code>>

MariaDB has five different semi-join execution strategies:

* [[table-pullout-optimization|Table pullout optimization]]
* [[firstmatch-strategy|FirstMatch execution strategy]]
* [[semi-join-materialization-strategy|Semi-join Materialization execution strategy]]
* [[loosescan-strategy|LooseScan execution strategy]]
* [[duplicateweedout-strategy|DuplicateWeedout execution strategy]]

== See Also

* [[what-is-mariadb-53|What is MariaDB 5.3]]
* [[subquery-optimizations-map|Subquery Optimizations Map]]
* [[http://s.petrunia.net/blog/?p=35|"Observations about subquery use cases"]] blog post
* [[http://en.wikipedia.org/wiki/Semijoin|http://en.wikipedia.org/wiki/Semijoin]]

Content reproduced on this site is the property of its respective owners, and this content is not reviewed in advance by MariaDB. The views, information and opinions expressed by this content do not necessarily represent those of MariaDB or any other party.

Semi-join Subquery Optimizations - Source

Products

Services

Pricing

Resources

About Us

Download MariaDB