diff options
| author | Igor Babaev <igor@askmonty.org> | 2010-08-31 09:34:21 -0700 |
|---|---|---|
| committer | Igor Babaev <igor@askmonty.org> | 2010-08-31 09:34:21 -0700 |
| commit | 94cfcbd9dffdfe5e38dd29c542738de85beaeb06 (patch) | |
| tree | dca2c84e183cce7a4a08cc82ac696adfc9c244a8 | |
| parent | 02c040dd5c26cbc97ae30776638463c36d96a938 (diff) | |
| download | mariadb-git-94cfcbd9dffdfe5e38dd29c542738de85beaeb06.tar.gz | |
The main patch for MWL#128: Implement Block Nested Loop Hash Join.
32 files changed, 4273 insertions, 1631 deletions
diff --git a/mysql-test/include/index_merge2.inc b/mysql-test/include/index_merge2.inc index 32a176630ad..a6a7a4b2ae1 100644 --- a/mysql-test/include/index_merge2.inc +++ b/mysql-test/include/index_merge2.inc @@ -123,6 +123,7 @@ analyze table t1; select count(*) from t1; --replace_column 9 REF +--replace_result i2,i1 i1,i2 explain select count(*) from t1 where key1a = 2 and key1b is null and key2a = 2 and key2b is null; @@ -130,6 +131,7 @@ select count(*) from t1 where key1a = 2 and key1b is null and key2a = 2 and key2b is null; --replace_column 9 REF +--replace_result i3,i1 i1,i3 explain select count(*) from t1 where key1a = 2 and key1b is null and key3a = 2 and key3b is null; diff --git a/mysql-test/r/join_cache.result b/mysql-test/r/join_cache.result index 5437538023c..22ec45e6d25 100644..100755 --- a/mysql-test/r/join_cache.result +++ b/mysql-test/r/join_cache.result @@ -1,5 +1,8 @@ DROP TABLE IF EXISTS t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11; DROP DATABASE IF EXISTS world; +set @save_optimizer_switch=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set names utf8; CREATE DATABASE world; use world; @@ -827,6 +830,626 @@ INDEX (Percentage) show variables like 'join_buffer_size'; Variable_name Value join_buffer_size 131072 +set join_cache_level=3; +show variables like 'join_cache_level'; +Variable_name Value +join_cache_level 3 +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 SIMPLE City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +Name Name +Vientiane Laos +Riga Latvia +Daugavpils Latvia +Maseru Lesotho +Beirut Lebanon +Tripoli Lebanon +Monrovia Liberia +Tripoli Libyan Arab Jamahiriya +Bengasi Libyan Arab Jamahiriya +Misrata Libyan Arab Jamahiriya +Vilnius Lithuania +Kaunas Lithuania +Klaipeda Lithuania +?iauliai Lithuania +Panevezys Lithuania +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where +1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where; Using join buffer +1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +Name Name Language +Leiden Netherlands Dutch +La Matanza Argentina Spanish +Lomas de Zamora Argentina Spanish +La Plata Argentina Spanish +Lanús Argentina Spanish +Las Heras Argentina Spanish +La Rioja Argentina Spanish +Liège Belgium Dutch +La Paz Bolivia Spanish +Londrina Brazil Portuguese +Limeira Brazil Portuguese +Lages Brazil Portuguese +Luziânia Brazil Portuguese +Lauro de Freitas Brazil Portuguese +Linhares Brazil Portuguese +London United Kingdom English +Liverpool United Kingdom English +Leeds United Kingdom English +Leicester United Kingdom English +Luton United Kingdom English +Los Angeles Chile Spanish +La Serena Chile Spanish +La Romana Dominican Republic Spanish +Loja Ecuador Spanish +Luxor Egypt Arabic +Las Palmas de Gran Canaria Spain Spanish +L´Hospitalet de Llobregat Spain Spanish +Leganés Spain Spanish +León Spain Spanish +Logroño Spain Spanish +Lleida (Lérida) Spain Spanish +Le-Cap-Haïtien Haiti Haiti Creole +La Ceiba Honduras Spanish +Livorno Italy Italian +Latina Italy Italian +Lecce Italy Italian +La Spezia Italy Italian +Linz Austria German +London Canada English +Laval Canada English +Longueuil Canada English +Lanzhou China Chinese +Luoyang China Chinese +Liuzhou China Chinese +Liaoyang China Chinese +Liupanshui China Chinese +Liaoyuan China Chinese +Lianyungang China Chinese +Leshan China Chinese +Linyi China Chinese +Luzhou China Chinese +Laiwu China Chinese +Liaocheng China Chinese +Laizhou China Chinese +Linfen China Chinese +Liangcheng China Chinese +Longkou China Chinese +Langfang China Chinese +Liu´an China Chinese +Longjing China Chinese +Lengshuijiang China Chinese +Laiyang China Chinese +Longyan China Chinese +Linhe China Chinese +Leiyang China Chinese +Loudi China Chinese +Luohe China Chinese +Linqing China Chinese +Laohekou China Chinese +Linchuan China Chinese +Lhasa China Chinese +Lianyuan China Chinese +Liyang China Chinese +Liling China Chinese +Linhai China Chinese +Larisa Greece Greek +La Habana Cuba Spanish +Lilongwe Malawi Chichewa +León Mexico Spanish +La Paz Mexico Spanish +La Paz Mexico Spanish +Lázaro Cárdenas Mexico Spanish +Lagos de Moreno Mexico Spanish +Lerdo Mexico Spanish +Los Cabos Mexico Spanish +Lerma Mexico Spanish +Las Margaritas Mexico Spanish +Lashio (Lasho) Myanmar Burmese +Lalitapur Nepal Nepali +León Nicaragua Spanish +Lambaré Paraguay Spanish +Lima Peru Spanish +Lisboa Portugal Portuguese +Lódz Poland Polish +Lublin Poland Polish +Legnica Poland Polish +Lyon France French +Le Havre France French +Lille France French +Le Mans France French +Limoges France French +Linköping Sweden Swedish +Lund Sweden Swedish +Leipzig Germany German +Lübeck Germany German +Ludwigshafen am Rhein Germany German +Leverkusen Germany German +Lünen Germany German +Lahti Finland Finnish +Lausanne Switzerland German +Latakia Syria Arabic +Luchou Taiwan Min +Lungtan Taiwan Min +Liberec Czech Republic Czech +Lviv Ukraine Ukrainian +Lugansk Ukraine Ukrainian +Lutsk Ukraine Ukrainian +Lysyt?ansk Ukraine Ukrainian +Lower Hutt New Zealand English +Lida Belarus Belorussian +Los Teques Venezuela Spanish +Lipetsk Russian Federation Russian +Ljubertsy Russian Federation Russian +Leninsk-Kuznetski Russian Federation Russian +Long Xuyen Vietnam Vietnamese +Los Angeles United States English +Las Vegas United States English +Long Beach United States English +Lexington-Fayette United States English +Louisville United States English +Lincoln United States English +Lubbock United States English +Little Rock United States English +Laredo United States English +Lakewood United States English +Lansing United States English +Lancaster United States English +Lafayette United States English +Lowell United States English +Livonia United States English +EXPLAIN +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +Name +Vientiane +Riga +Daugavpils +Maseru +Beirut +Tripoli +Monrovia +Tripoli +Bengasi +Misrata +Vilnius +Kaunas +Klaipeda +?iauliai +Panevezys +EXPLAIN +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +FROM Country LEFT JOIN CountryLanguage ON +(CountryLanguage.Country=Country.Code AND Language='English') +WHERE +Country.Population > 10000000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country ALL NULL NULL NULL NULL 239 Using where +1 SIMPLE CountryLanguage eq_ref PRIMARY PRIMARY 33 world.Country.Code,const 1 Using where; Using join buffer +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +FROM Country LEFT JOIN CountryLanguage ON +(CountryLanguage.Country=Country.Code AND Language='English') +WHERE +Country.Population > 10000000; +Name IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +Australia 81.2 +United Kingdom 97.3 +Canada 60.4 +United States 86.2 +Zimbabwe 2.2 +Japan 0.1 +South Africa 8.5 +Malaysia 1.6 +Afghanistan NULL +Netherlands NULL +Algeria NULL +Angola NULL +Argentina NULL +Bangladesh NULL +Belgium NULL +Brazil NULL +Burkina Faso NULL +Chile NULL +Ecuador NULL +Egypt NULL +Spain NULL +Ethiopia NULL +Philippines NULL +Ghana NULL +Guatemala NULL +Indonesia NULL +India NULL +Iraq NULL +Iran NULL +Italy NULL +Yemen NULL +Yugoslavia NULL +Cambodia NULL +Cameroon NULL +Kazakstan NULL +Kenya NULL +China NULL +Colombia NULL +Congo, The Democratic Republic of the NULL +North Korea NULL +South Korea NULL +Greece NULL +Cuba NULL +Madagascar NULL +Malawi NULL +Mali NULL +Morocco NULL +Mexico NULL +Mozambique NULL +Myanmar NULL +Nepal NULL +Niger NULL +Nigeria NULL +Côte d?Ivoire NULL +Pakistan NULL +Peru NULL +Poland NULL +France NULL +Romania NULL +Germany NULL +Saudi Arabia NULL +Somalia NULL +Sri Lanka NULL +Sudan NULL +Syria NULL +Taiwan NULL +Tanzania NULL +Thailand NULL +Czech Republic NULL +Turkey NULL +Uganda NULL +Ukraine NULL +Hungary NULL +Uzbekistan NULL +Belarus NULL +Venezuela NULL +Russian Federation NULL +Vietnam NULL +show variables like 'join_buffer_size'; +Variable_name Value +join_buffer_size 131072 +set join_cache_level=4; +show variables like 'join_cache_level'; +Variable_name Value +join_cache_level 4 +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 SIMPLE City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +Name Name +Vientiane Laos +Riga Latvia +Daugavpils Latvia +Maseru Lesotho +Beirut Lebanon +Tripoli Lebanon +Monrovia Liberia +Tripoli Libyan Arab Jamahiriya +Bengasi Libyan Arab Jamahiriya +Misrata Libyan Arab Jamahiriya +Vilnius Lithuania +Kaunas Lithuania +Klaipeda Lithuania +?iauliai Lithuania +Panevezys Lithuania +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where +1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where; Using join buffer +1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +Name Name Language +Leiden Netherlands Dutch +La Matanza Argentina Spanish +Lomas de Zamora Argentina Spanish +La Plata Argentina Spanish +Lanús Argentina Spanish +Las Heras Argentina Spanish +La Rioja Argentina Spanish +Liège Belgium Dutch +La Paz Bolivia Spanish +Londrina Brazil Portuguese +Limeira Brazil Portuguese +Lages Brazil Portuguese +Luziânia Brazil Portuguese +Lauro de Freitas Brazil Portuguese +Linhares Brazil Portuguese +London United Kingdom English +Liverpool United Kingdom English +Leeds United Kingdom English +Leicester United Kingdom English +Luton United Kingdom English +Los Angeles Chile Spanish +La Serena Chile Spanish +La Romana Dominican Republic Spanish +Loja Ecuador Spanish +Luxor Egypt Arabic +Las Palmas de Gran Canaria Spain Spanish +L´Hospitalet de Llobregat Spain Spanish +Leganés Spain Spanish +León Spain Spanish +Logroño Spain Spanish +Lleida (Lérida) Spain Spanish +Le-Cap-Haïtien Haiti Haiti Creole +La Ceiba Honduras Spanish +Livorno Italy Italian +Latina Italy Italian +Lecce Italy Italian +La Spezia Italy Italian +Linz Austria German +London Canada English +Laval Canada English +Longueuil Canada English +Lanzhou China Chinese +Luoyang China Chinese +Liuzhou China Chinese +Liaoyang China Chinese +Liupanshui China Chinese +Liaoyuan China Chinese +Lianyungang China Chinese +Leshan China Chinese +Linyi China Chinese +Luzhou China Chinese +Laiwu China Chinese +Liaocheng China Chinese +Laizhou China Chinese +Linfen China Chinese +Liangcheng China Chinese +Longkou China Chinese +Langfang China Chinese +Liu´an China Chinese +Longjing China Chinese +Lengshuijiang China Chinese +Laiyang China Chinese +Longyan China Chinese +Linhe China Chinese +Leiyang China Chinese +Loudi China Chinese +Luohe China Chinese +Linqing China Chinese +Laohekou China Chinese +Linchuan China Chinese +Lhasa China Chinese +Lianyuan China Chinese +Liyang China Chinese +Liling China Chinese +Linhai China Chinese +Larisa Greece Greek +La Habana Cuba Spanish +Lilongwe Malawi Chichewa +León Mexico Spanish +La Paz Mexico Spanish +La Paz Mexico Spanish +Lázaro Cárdenas Mexico Spanish +Lagos de Moreno Mexico Spanish +Lerdo Mexico Spanish +Los Cabos Mexico Spanish +Lerma Mexico Spanish +Las Margaritas Mexico Spanish +Lashio (Lasho) Myanmar Burmese +Lalitapur Nepal Nepali +León Nicaragua Spanish +Lambaré Paraguay Spanish +Lima Peru Spanish +Lisboa Portugal Portuguese +Lódz Poland Polish +Lublin Poland Polish +Legnica Poland Polish +Lyon France French +Le Havre France French +Lille France French +Le Mans France French +Limoges France French +Linköping Sweden Swedish +Lund Sweden Swedish +Leipzig Germany German +Lübeck Germany German +Ludwigshafen am Rhein Germany German +Leverkusen Germany German +Lünen Germany German +Lahti Finland Finnish +Lausanne Switzerland German +Latakia Syria Arabic +Luchou Taiwan Min +Lungtan Taiwan Min +Liberec Czech Republic Czech +Lviv Ukraine Ukrainian +Lugansk Ukraine Ukrainian +Lutsk Ukraine Ukrainian +Lysyt?ansk Ukraine Ukrainian +Lower Hutt New Zealand English +Lida Belarus Belorussian +Los Teques Venezuela Spanish +Lipetsk Russian Federation Russian +Ljubertsy Russian Federation Russian +Leninsk-Kuznetski Russian Federation Russian +Long Xuyen Vietnam Vietnamese +Los Angeles United States English +Las Vegas United States English +Long Beach United States English +Lexington-Fayette United States English +Louisville United States English +Lincoln United States English +Lubbock United States English +Little Rock United States English +Laredo United States English +Lakewood United States English +Lansing United States English +Lancaster United States English +Lafayette United States English +Lowell United States English +Livonia United States English +EXPLAIN +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +Name +Vientiane +Riga +Daugavpils +Maseru +Beirut +Tripoli +Monrovia +Tripoli +Bengasi +Misrata +Vilnius +Kaunas +Klaipeda +?iauliai +Panevezys +EXPLAIN +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +FROM Country LEFT JOIN CountryLanguage ON +(CountryLanguage.Country=Country.Code AND Language='English') +WHERE +Country.Population > 10000000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country ALL NULL NULL NULL NULL 239 Using where +1 SIMPLE CountryLanguage eq_ref PRIMARY PRIMARY 33 world.Country.Code,const 1 Using where; Using join buffer +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +FROM Country LEFT JOIN CountryLanguage ON +(CountryLanguage.Country=Country.Code AND Language='English') +WHERE +Country.Population > 10000000; +Name IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) +Australia 81.2 +United Kingdom 97.3 +Canada 60.4 +United States 86.2 +Zimbabwe 2.2 +Japan 0.1 +South Africa 8.5 +Malaysia 1.6 +Afghanistan NULL +Netherlands NULL +Algeria NULL +Angola NULL +Argentina NULL +Bangladesh NULL +Belgium NULL +Brazil NULL +Burkina Faso NULL +Chile NULL +Ecuador NULL +Egypt NULL +Spain NULL +Ethiopia NULL +Philippines NULL +Ghana NULL +Guatemala NULL +Indonesia NULL +India NULL +Iraq NULL +Iran NULL +Italy NULL +Yemen NULL +Yugoslavia NULL +Cambodia NULL +Cameroon NULL +Kazakstan NULL +Kenya NULL +China NULL +Colombia NULL +Congo, The Democratic Republic of the NULL +North Korea NULL +South Korea NULL +Greece NULL +Cuba NULL +Madagascar NULL +Malawi NULL +Mali NULL +Morocco NULL +Mexico NULL +Mozambique NULL +Myanmar NULL +Nepal NULL +Niger NULL +Nigeria NULL +Côte d?Ivoire NULL +Pakistan NULL +Peru NULL +Poland NULL +France NULL +Romania NULL +Germany NULL +Saudi Arabia NULL +Somalia NULL +Sri Lanka NULL +Sudan NULL +Syria NULL +Taiwan NULL +Tanzania NULL +Thailand NULL +Czech Republic NULL +Turkey NULL +Uganda NULL +Ukraine NULL +Hungary NULL +Uzbekistan NULL +Belarus NULL +Venezuela NULL +Russian Federation NULL +Vietnam NULL +show variables like 'join_buffer_size'; +Variable_name Value +join_buffer_size 131072 set join_cache_level=5; show variables like 'join_cache_level'; Variable_name Value @@ -1015,14 +1638,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -1330,14 +1945,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -1645,14 +2252,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -1960,14 +2559,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -2091,6 +2682,434 @@ set join_buffer_size=256; show variables like 'join_buffer_size'; Variable_name Value join_buffer_size 256 +set join_cache_level=3; +show variables like 'join_cache_level'; +Variable_name Value +join_cache_level 3 +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 SIMPLE City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +Name Name +Vientiane Laos +Riga Latvia +Daugavpils Latvia +Maseru Lesotho +Beirut Lebanon +Tripoli Lebanon +Monrovia Liberia +Tripoli Libyan Arab Jamahiriya +Bengasi Libyan Arab Jamahiriya +Misrata Libyan Arab Jamahiriya +Vilnius Lithuania +Kaunas Lithuania +Klaipeda Lithuania +?iauliai Lithuania +Panevezys Lithuania +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where +1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where; Using join buffer +1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +Name Name Language +Leiden Netherlands Dutch +La Matanza Argentina Spanish +Lomas de Zamora Argentina Spanish +La Plata Argentina Spanish +Lanús Argentina Spanish +Las Heras Argentina Spanish +La Rioja Argentina Spanish +Liège Belgium Dutch +La Paz Bolivia Spanish +Londrina Brazil Portuguese +Limeira Brazil Portuguese +Lages Brazil Portuguese +Luziânia Brazil Portuguese +Lauro de Freitas Brazil Portuguese +Linhares Brazil Portuguese +London United Kingdom English +Liverpool United Kingdom English +Leeds United Kingdom English +Leicester United Kingdom English +Luton United Kingdom English +Los Angeles Chile Spanish +La Serena Chile Spanish +La Romana Dominican Republic Spanish +Loja Ecuador Spanish +Luxor Egypt Arabic +Las Palmas de Gran Canaria Spain Spanish +L´Hospitalet de Llobregat Spain Spanish +Leganés Spain Spanish +León Spain Spanish +Logroño Spain Spanish +Lleida (Lérida) Spain Spanish +Le-Cap-Haïtien Haiti Haiti Creole +La Ceiba Honduras Spanish +Livorno Italy Italian +Latina Italy Italian +Lecce Italy Italian +La Spezia Italy Italian +Linz Austria German +London Canada English +Laval Canada English +Longueuil Canada English +Lanzhou China Chinese +Luoyang China Chinese +Liuzhou China Chinese +Liaoyang China Chinese +Liupanshui China Chinese +Liaoyuan China Chinese +Lianyungang China Chinese +Leshan China Chinese +Linyi China Chinese +Luzhou China Chinese +Laiwu China Chinese +Liaocheng China Chinese +Laizhou China Chinese +Linfen China Chinese +Liangcheng China Chinese +Longkou China Chinese +Langfang China Chinese +Liu´an China Chinese +Longjing China Chinese +Lengshuijiang China Chinese +Laiyang China Chinese +Longyan China Chinese +Linhe China Chinese +Leiyang China Chinese +Loudi China Chinese +Luohe China Chinese +Linqing China Chinese +Laohekou China Chinese +Linchuan China Chinese +Lhasa China Chinese +Lianyuan China Chinese +Liyang China Chinese +Liling China Chinese +Linhai China Chinese +Larisa Greece Greek +La Habana Cuba Spanish +Lilongwe Malawi Chichewa +León Mexico Spanish +La Paz Mexico Spanish +La Paz Mexico Spanish +Lázaro Cárdenas Mexico Spanish +Lagos de Moreno Mexico Spanish +Lerdo Mexico Spanish +Los Cabos Mexico Spanish +Lerma Mexico Spanish +Las Margaritas Mexico Spanish +Lashio (Lasho) Myanmar Burmese +Lalitapur Nepal Nepali +León Nicaragua Spanish +Lambaré Paraguay Spanish +Lima Peru Spanish +Lisboa Portugal Portuguese +Lódz Poland Polish +Lublin Poland Polish +Legnica Poland Polish +Lyon France French +Le Havre France French +Lille France French +Le Mans France French +Limoges France French +Linköping Sweden Swedish +Lund Sweden Swedish +Leipzig Germany German +Lübeck Germany German +Ludwigshafen am Rhein Germany German +Leverkusen Germany German +Lünen Germany German +Lahti Finland Finnish +Lausanne Switzerland German +Latakia Syria Arabic +Luchou Taiwan Min +Lungtan Taiwan Min +Liberec Czech Republic Czech +Lviv Ukraine Ukrainian +Lugansk Ukraine Ukrainian +Lutsk Ukraine Ukrainian +Lysyt?ansk Ukraine Ukrainian +Lower Hutt New Zealand English +Lida Belarus Belorussian +Los Teques Venezuela Spanish +Lipetsk Russian Federation Russian +Ljubertsy Russian Federation Russian +Leninsk-Kuznetski Russian Federation Russian +Long Xuyen Vietnam Vietnamese +Los Angeles United States English +Las Vegas United States English +Long Beach United States English +Lexington-Fayette United States English +Louisville United States English +Lincoln United States English +Lubbock United States English +Little Rock United States English +Laredo United States English +Lakewood United States English +Lansing United States English +Lancaster United States English +Lafayette United States English +Lowell United States English +Livonia United States English +EXPLAIN +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +Name +Vientiane +Riga +Daugavpils +Maseru +Beirut +Tripoli +Monrovia +Tripoli +Bengasi +Misrata +Vilnius +Kaunas +Klaipeda +?iauliai +Panevezys +set join_cache_level=4; +show variables like 'join_cache_level'; +Variable_name Value +join_cache_level 4 +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 SIMPLE City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name FROM City,Country +WHERE City.Country=Country.Code AND +Country.Name LIKE 'L%' AND City.Population > 100000; +Name Name +Vientiane Laos +Riga Latvia +Daugavpils Latvia +Maseru Lesotho +Beirut Lebanon +Tripoli Lebanon +Monrovia Liberia +Tripoli Libyan Arab Jamahiriya +Bengasi Libyan Arab Jamahiriya +Misrata Libyan Arab Jamahiriya +Vilnius Lithuania +Kaunas Lithuania +Klaipeda Lithuania +?iauliai Lithuania +Panevezys Lithuania +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where +1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where; Using join buffer +1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT City.Name, Country.Name, CountryLanguage.Language +FROM City,Country,CountryLanguage +WHERE City.Country=Country.Code AND +CountryLanguage.Country=Country.Code AND +City.Name LIKE 'L%' AND Country.Population > 3000000 AND +CountryLanguage.Percentage > 50; +Name Name Language +Leiden Netherlands Dutch +La Matanza Argentina Spanish +Lomas de Zamora Argentina Spanish +La Plata Argentina Spanish +Lanús Argentina Spanish +Las Heras Argentina Spanish +La Rioja Argentina Spanish +Liège Belgium Dutch +La Paz Bolivia Spanish +Londrina Brazil Portuguese +Limeira Brazil Portuguese +Lages Brazil Portuguese +Luziânia Brazil Portuguese +Lauro de Freitas Brazil Portuguese +Linhares Brazil Portuguese +London United Kingdom English +Liverpool United Kingdom English +Leeds United Kingdom English +Leicester United Kingdom English +Luton United Kingdom English +Los Angeles Chile Spanish +La Serena Chile Spanish +La Romana Dominican Republic Spanish +Loja Ecuador Spanish +Luxor Egypt Arabic +Las Palmas de Gran Canaria Spain Spanish +L´Hospitalet de Llobregat Spain Spanish +Leganés Spain Spanish +León Spain Spanish +Logroño Spain Spanish +Lleida (Lérida) Spain Spanish +Le-Cap-Haïtien Haiti Haiti Creole +La Ceiba Honduras Spanish +Livorno Italy Italian +Latina Italy Italian +Lecce Italy Italian +La Spezia Italy Italian +Linz Austria German +London Canada English +Laval Canada English +Longueuil Canada English +Lanzhou China Chinese +Luoyang China Chinese +Liuzhou China Chinese +Liaoyang China Chinese +Liupanshui China Chinese +Liaoyuan China Chinese +Lianyungang China Chinese +Leshan China Chinese +Linyi China Chinese +Luzhou China Chinese +Laiwu China Chinese +Liaocheng China Chinese +Laizhou China Chinese +Linfen China Chinese +Liangcheng China Chinese +Longkou China Chinese +Langfang China Chinese +Liu´an China Chinese +Longjing China Chinese +Lengshuijiang China Chinese +Laiyang China Chinese +Longyan China Chinese +Linhe China Chinese +Leiyang China Chinese +Loudi China Chinese +Luohe China Chinese +Linqing China Chinese +Laohekou China Chinese +Linchuan China Chinese +Lhasa China Chinese +Lianyuan China Chinese +Liyang China Chinese +Liling China Chinese +Linhai China Chinese +Larisa Greece Greek +La Habana Cuba Spanish +Lilongwe Malawi Chichewa +León Mexico Spanish +La Paz Mexico Spanish +La Paz Mexico Spanish +Lázaro Cárdenas Mexico Spanish +Lagos de Moreno Mexico Spanish +Lerdo Mexico Spanish +Los Cabos Mexico Spanish +Lerma Mexico Spanish +Las Margaritas Mexico Spanish +Lashio (Lasho) Myanmar Burmese +Lalitapur Nepal Nepali +León Nicaragua Spanish +Lambaré Paraguay Spanish +Lima Peru Spanish +Lisboa Portugal Portuguese +Lódz Poland Polish +Lublin Poland Polish +Legnica Poland Polish +Lyon France French +Le Havre France French +Lille France French +Le Mans France French +Limoges France French +Linköping Sweden Swedish +Lund Sweden Swedish +Leipzig Germany German +Lübeck Germany German +Ludwigshafen am Rhein Germany German +Leverkusen Germany German +Lünen Germany German +Lahti Finland Finnish +Lausanne Switzerland German +Latakia Syria Arabic +Luchou Taiwan Min +Lungtan Taiwan Min +Liberec Czech Republic Czech +Lviv Ukraine Ukrainian +Lugansk Ukraine Ukrainian +Lutsk Ukraine Ukrainian +Lysyt?ansk Ukraine Ukrainian +Lower Hutt New Zealand English +Lida Belarus Belorussian +Los Teques Venezuela Spanish +Lipetsk Russian Federation Russian +Ljubertsy Russian Federation Russian +Leninsk-Kuznetski Russian Federation Russian +Long Xuyen Vietnam Vietnamese +Los Angeles United States English +Las Vegas United States English +Long Beach United States English +Lexington-Fayette United States English +Louisville United States English +Lincoln United States English +Lubbock United States English +Little Rock United States English +Laredo United States English +Lakewood United States English +Lansing United States English +Lancaster United States English +Lafayette United States English +Lowell United States English +Livonia United States English +EXPLAIN +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR +1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +SELECT Name FROM City +WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND +City.Population > 100000; +Name +Vientiane +Riga +Daugavpils +Maseru +Beirut +Tripoli +Monrovia +Tripoli +Bengasi +Misrata +Vilnius +Kaunas +Klaipeda +?iauliai +Panevezys set join_cache_level=5; show variables like 'join_cache_level'; Variable_name Value @@ -2279,14 +3298,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -2501,14 +3512,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -2723,14 +3726,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -2945,14 +3940,6 @@ Lancaster United States English Lafayette United States English Lowell United States English Livonia United States English -# !!!NB igor: after backporting the SJ code the following should return -# EXPLAIN -# SELECT Name FROM City -# WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND -# City.Population > 100000; -# id select_type table type possible_keys key key_len ref rows Extra -# 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR -# 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -3038,7 +4025,7 @@ Ho Chi Minh City Vietnam New York United States Los Angeles United States set join_cache_level=8; -set join_buffer_size=256; +set join_buffer_size=384; EXPLAIN SELECT City.Name, Country.Name FROM City,Country WHERE City.Country=Country.Code AND City.Population > 3000000; @@ -3059,36 +4046,36 @@ Cairo Egypt Jakarta Indonesia Delhi India Calcutta [Kolkata] India -Mumbai (Bombay) India Chennai (Madras) India +Mumbai (Bombay) India Baghdad Iraq Teheran Iran Tokyo Japan Jokohama [Yokohama] Japan Peking China Chongqing China -Shanghai China +Tianjin China Wuhan China Harbin China Shenyang China -Kanton [Guangzhou] China -Tianjin China +Shanghai China Chengdu China +Kanton [Guangzhou] China Santafé de Bogotá Colombia Kinshasa Congo, The Democratic Republic of the -Seoul South Korea Pusan South Korea +Seoul South Korea Ciudad de México Mexico Rangoon (Yangon) Myanmar -Karachi Pakistan Lahore Pakistan +Karachi Pakistan Lima Peru Berlin Germany Riyadh Saudi Arabia Singapore Singapore Bangkok Thailand -Ankara Turkey Istanbul Turkey +Ankara Turkey St Petersburg Russian Federation Moscow Russian Federation Ho Chi Minh City Vietnam @@ -3593,7 +4580,7 @@ id select_type table type possible_keys key key_len ref rows Extra select * from t1 left join t2 on (1=0) where a=40; a b 40 NULL -set join_cache_level=1; +set join_cache_level=0; explain select * from t1 left join t2 on (1=0); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 ALL NULL NULL NULL NULL 3 @@ -3714,6 +4701,7 @@ INSERT INTO t3(a,b) VALUES (4,30), (4,40), (4,50), (4,60), (4,70), (4,80), (5,30), (5,40), (5,50), (5,60), (5,70), (5,80), (7,30), (7,40), (7,50), (7,60), (7,70), (7,80); +set join_cache_level=0; SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b) WHERE t1.a=t2.a; @@ -3755,7 +4743,7 @@ a a a b b val 2 2 2 70 70 0 2 2 2 80 80 0 DROP INDEX idx ON t3; -set join_cache_level=4; +set join_cache_level=2; EXPLAIN SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b) @@ -3997,9 +4985,9 @@ WHERE t1.id1=t5.id1 AND t1.id2=t5.id2 and t4.id2=t1.id2 AND t5.enum2='Active' AND t3.id4=t2.id4 AND t2.id3=t1.id3 AND t3.text1<'D'; id1 num3 text1 id4 id3 dummy 228172702 14 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2567095402 2667134182 0 +228172702 134 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2567095402 2667134182 0 228172702 15 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2567095402 2667134182 0 228172702 3 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2567095402 2667134182 0 -228172702 134 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2567095402 2667134182 0 228808822 61 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 13 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 60 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 @@ -4007,23 +4995,23 @@ id1 num3 text1 id4 id3 dummy 228808822 3 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 4 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 6 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 -228808822 17 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 -228808822 50 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 18 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 1 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 3 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 4 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 +228808822 17 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 +228808822 50 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 826928662 935693782 0 228808822 89 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 19 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 +228808822 9 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 84 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 14 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 -228808822 9 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 1 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 10 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 26 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 -228808822 4 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 3 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 1 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 +228808822 4 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 3 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 28 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 228808822 62 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 2381969632 2482416112 0 @@ -4185,3 +5173,4 @@ a b 2 2 set join_cache_level=default; drop table t1,t2,t3; +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/r/join_nested_jcl6.result b/mysql-test/r/join_nested_jcl6.result index 0b83bd7cd6e..5aea6ba74c3 100644..100755 --- a/mysql-test/r/join_nested_jcl6.result +++ b/mysql-test/r/join_nested_jcl6.result @@ -1,3 +1,6 @@ +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value @@ -1854,3 +1857,4 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/r/join_outer_jcl6.result b/mysql-test/r/join_outer_jcl6.result index 854fc725845..1347866745b 100644..100755 --- a/mysql-test/r/join_outer_jcl6.result +++ b/mysql-test/r/join_outer_jcl6.result @@ -1,3 +1,6 @@ +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value @@ -1317,3 +1320,4 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/r/optimizer_switch.result b/mysql-test/r/optimizer_switch.result index 6bccefe54be..118eeaa094c 100644..100755 --- a/mysql-test/r/optimizer_switch.result +++ b/mysql-test/r/optimizer_switch.result @@ -4,19 +4,19 @@ # select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='index_merge=off,index_merge_union=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='index_merge_union=on'; select @@optimizer_switch; @@optimizer_switch -index_merge=off,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=off,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,index_merge_sort_union=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=off,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=off,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch=4; ERROR 42000: Variable 'optimizer_switch' can't be set to the value of '4' set optimizer_switch=NULL; @@ -43,57 +43,57 @@ set optimizer_switch=default; set optimizer_switch='index_merge=off,index_merge_union=off,default'; select @@optimizer_switch; @@optimizer_switch -index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=off,index_merge_union=off,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch=default; select @@global.optimizer_switch; @@global.optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set @@global.optimizer_switch=default; select @@global.optimizer_switch; @@global.optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on # # Check index_merge's @@optimizer_switch flags # select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on BUG#37120 optimizer_switch allowable values not according to specification select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,materialization=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,semijoin=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,loosescan=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,semijoin=off,materialization=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,materialization=off,semijoin=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=on,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,semijoin=off,materialization=off,loosescan=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,semijoin=off,loosescan=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch='default,materialization=off,loosescan=off'; select @@optimizer_switch; @@optimizer_switch -index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on +index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_condition_pushdown=on,firstmatch=on,loosescan=off,materialization=off,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,outer_join_with_cache=off,semijoin_with_cache=off,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on set optimizer_switch=default; diff --git a/mysql-test/r/select_jcl6.result b/mysql-test/r/select_jcl6.result index ff09e79a511..7ea2744d69b 100644..100755 --- a/mysql-test/r/select_jcl6.result +++ b/mysql-test/r/select_jcl6.result @@ -1,3 +1,6 @@ +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value @@ -4790,3 +4793,4 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/r/subselect3.result b/mysql-test/r/subselect3.result index 665bb9a2bde..a947aecb326 100644..100755 --- a/mysql-test/r/subselect3.result +++ b/mysql-test/r/subselect3.result @@ -1,4 +1,5 @@ drop table if exists t0, t1, t2, t3, t4, t5, t11, t12, t21, t22; +set @save_optimizer_switch=@@optimizer_switch; create table t1 (oref int, grp int, ie int) ; insert into t1 (oref, grp, ie) values (1, 1, 1), @@ -1046,7 +1047,7 @@ select (select max(Y.a) from t1 Y where a in (select a from t1 Z) and a < X.a) a subq NULL 0 -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t1; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); @@ -1107,7 +1108,7 @@ a 17 18 19 -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; explain select * from (select a from t0) X where a in (select a from t1); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY <derived2> ALL NULL NULL NULL NULL 11 @@ -1153,7 +1154,7 @@ show status like 'Created_tmp_disk_tables'; Variable_name Value Created_tmp_disk_tables 1 set @save_max_heap_table_size=@@max_heap_table_size; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); @@ -1203,7 +1204,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 2 Start temporary 1 PRIMARY t1 ALL NULL NULL NULL NULL 2 Using where; End temporary; Using join buffer drop table t1; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; create table t1 (a int); insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); create table t2 as select * from t1; @@ -1285,7 +1286,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY subselect2 eq_ref unique_key unique_key 10 func 1 2 SUBQUERY t2 ALL NULL NULL NULL NULL 100 set @@optimizer_search_depth=@save_optimizer_search_depth; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1, t2; create table t0 (a decimal(4,2)); insert into t0 values (10.24), (22.11); @@ -1426,3 +1427,4 @@ CALL p1; ERROR 42S22: Unknown column 'f1' in 'where clause' DROP PROCEDURE p1; DROP TABLE t1, t2; +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/r/subselect3_jcl6.result b/mysql-test/r/subselect3_jcl6.result index d25ca436311..ad6ef5dc325 100644..100755 --- a/mysql-test/r/subselect3_jcl6.result +++ b/mysql-test/r/subselect3_jcl6.result @@ -1,8 +1,12 @@ +set @save_optimizer_switch=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value join_cache_level 6 drop table if exists t0, t1, t2, t3, t4, t5, t11, t12, t21, t22; +set @save_optimizer_switch=@@optimizer_switch; create table t1 (oref int, grp int, ie int) ; insert into t1 (oref, grp, ie) values (1, 1, 1), @@ -1051,7 +1055,7 @@ select (select max(Y.a) from t1 Y where a in (select a from t1 Z) and a < X.a) a subq NULL 0 -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t1; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); @@ -1112,7 +1116,7 @@ a 17 18 19 -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; explain select * from (select a from t0) X where a in (select a from t1); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY <derived2> ALL NULL NULL NULL NULL 11 @@ -1158,7 +1162,7 @@ show status like 'Created_tmp_disk_tables'; Variable_name Value Created_tmp_disk_tables 1 set @save_max_heap_table_size=@@max_heap_table_size; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); @@ -1208,7 +1212,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 2 Start temporary 1 PRIMARY t1 ALL NULL NULL NULL NULL 2 Using where; End temporary; Using join buffer drop table t1; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; create table t1 (a int); insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); create table t2 as select * from t1; @@ -1290,7 +1294,7 @@ id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY subselect2 eq_ref unique_key unique_key 10 func 1 2 SUBQUERY t2 ALL NULL NULL NULL NULL 100 set @@optimizer_search_depth=@save_optimizer_search_depth; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1, t2; create table t0 (a decimal(4,2)); insert into t0 values (10.24), (22.11); @@ -1431,7 +1435,9 @@ CALL p1; ERROR 42S22: Unknown column 'f1' in 'where clause' DROP PROCEDURE p1; DROP TABLE t1, t2; +set @@optimizer_switch=@save_optimizer_switch; set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/r/subselect_sj.result b/mysql-test/r/subselect_sj.result index 648a066f185..066d29d941f 100644..100755 --- a/mysql-test/r/subselect_sj.result +++ b/mysql-test/r/subselect_sj.result @@ -1,4 +1,5 @@ drop table if exists t0, t1, t2, t3, t4, t10, t11, t12; +set @save_optimizer_switch=@@optimizer_switch; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); create table t1(a int, b int); @@ -322,7 +323,8 @@ INSERT INTO WORKS VALUES ('E3','P2',20); INSERT INTO WORKS VALUES ('E4','P2',20); INSERT INTO WORKS VALUES ('E4','P4',40); INSERT INTO WORKS VALUES ('E4','P5',80); -set optimizer_switch='default,materialization=off'; +set optimizer_switch=@save_optimizer_switch; +set optimizer_switch='materialization=off'; explain SELECT EMPNUM, EMPNAME FROM STAFF WHERE EMPNUM IN @@ -344,7 +346,7 @@ E1 Alice E2 Betty E3 Carmen E4 Don -set optimizer_switch='default'; +set optimizer_switch=@save_optimizer_switch; drop table STAFF,WORKS,PROJ; # End of bug#45191 # @@ -450,7 +452,7 @@ COUNT(*) drop table t1, t2; drop view v1; drop procedure p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; # End of bug#46744 Bug#46797 "Crash in fix_semijoin_strategies_for_picked_join_order @@ -601,7 +603,7 @@ v1field DROP TABLE t1,t2; DROP VIEW v1,v2; DROP PROCEDURE p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; # End of BUG#48834 Bug#49097 subquery with view generates wrong result with @@ -1075,3 +1077,4 @@ DROP TABLE t1; DROP TABLE t2; DROP TABLE t3; # End of Bug#48623 +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/r/subselect_sj2_jcl6.result b/mysql-test/r/subselect_sj2_jcl6.result index 67215d1715e..e497263ed4a 100644..100755 --- a/mysql-test/r/subselect_sj2_jcl6.result +++ b/mysql-test/r/subselect_sj2_jcl6.result @@ -1,3 +1,6 @@ +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value @@ -733,3 +736,4 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/r/subselect_sj_jcl6.result b/mysql-test/r/subselect_sj_jcl6.result index 5af207432ff..ce8270ae563 100644..100755 --- a/mysql-test/r/subselect_sj_jcl6.result +++ b/mysql-test/r/subselect_sj_jcl6.result @@ -1,8 +1,12 @@ +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; set join_cache_level=6; show variables like 'join_cache_level'; Variable_name Value join_cache_level 6 drop table if exists t0, t1, t2, t3, t4, t10, t11, t12; +set @save_optimizer_switch=@@optimizer_switch; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); create table t1(a int, b int); @@ -326,7 +330,8 @@ INSERT INTO WORKS VALUES ('E3','P2',20); INSERT INTO WORKS VALUES ('E4','P2',20); INSERT INTO WORKS VALUES ('E4','P4',40); INSERT INTO WORKS VALUES ('E4','P5',80); -set optimizer_switch='default,materialization=off'; +set optimizer_switch=@save_optimizer_switch; +set optimizer_switch='materialization=off'; explain SELECT EMPNUM, EMPNAME FROM STAFF WHERE EMPNUM IN @@ -348,7 +353,7 @@ E1 Alice E2 Betty E3 Carmen E4 Don -set optimizer_switch='default'; +set optimizer_switch=@save_optimizer_switch; drop table STAFF,WORKS,PROJ; # End of bug#45191 # @@ -454,7 +459,7 @@ COUNT(*) drop table t1, t2; drop view v1; drop procedure p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; # End of bug#46744 Bug#46797 "Crash in fix_semijoin_strategies_for_picked_join_order @@ -605,7 +610,7 @@ v1field DROP TABLE t1,t2; DROP VIEW v1,v2; DROP PROCEDURE p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; # End of BUG#48834 Bug#49097 subquery with view generates wrong result with @@ -1079,6 +1084,7 @@ DROP TABLE t1; DROP TABLE t2; DROP TABLE t3; # End of Bug#48623 +set @@optimizer_switch=@save_optimizer_switch; # # BUG#49129: Wrong result with IN-subquery with join_cache_level=6 and firstmatch=off # @@ -1114,3 +1120,4 @@ set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value join_cache_level 1 +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/t/join_cache.test b/mysql-test/t/join_cache.test index 0cb1c139161..68693fe70eb 100644..100755 --- a/mysql-test/t/join_cache.test +++ b/mysql-test/t/join_cache.test @@ -3,6 +3,10 @@ DROP TABLE IF EXISTS t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11; DROP DATABASE IF EXISTS world; --enable_warnings +set @save_optimizer_switch=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set names utf8; CREATE DATABASE world; @@ -160,7 +164,7 @@ use world; --enable_query_log show variables like 'join_buffer_size'; -set join_cache_level=5; +set join_cache_level=3; show variables like 'join_cache_level'; EXPLAIN @@ -187,14 +191,55 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +EXPLAIN +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +EXPLAIN +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) + FROM Country LEFT JOIN CountryLanguage ON + (CountryLanguage.Country=Country.Code AND Language='English') + WHERE + Country.Population > 10000000; + +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) + FROM Country LEFT JOIN CountryLanguage ON + (CountryLanguage.Country=Country.Code AND Language='English') + WHERE + Country.Population > 10000000; + +show variables like 'join_buffer_size'; +set join_cache_level=4; +show variables like 'join_cache_level'; + +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; + +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; EXPLAIN SELECT Name FROM City @@ -218,7 +263,9 @@ SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.P WHERE Country.Population > 10000000; -set join_cache_level=6; + +show variables like 'join_buffer_size'; +set join_cache_level=5; show variables like 'join_cache_level'; EXPLAIN @@ -245,14 +292,54 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +EXPLAIN +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +EXPLAIN +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) + FROM Country LEFT JOIN CountryLanguage ON + (CountryLanguage.Country=Country.Code AND Language='English') + WHERE + Country.Population > 10000000; + +SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.Percentage) + FROM Country LEFT JOIN CountryLanguage ON + (CountryLanguage.Country=Country.Code AND Language='English') + WHERE + Country.Population > 10000000; + +set join_cache_level=6; +show variables like 'join_cache_level'; + +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; + +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; EXPLAIN SELECT Name FROM City @@ -303,15 +390,6 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer - EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -361,15 +439,6 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer - EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -395,7 +464,7 @@ SELECT Country.Name, IF(ISNULL(CountryLanguage.Country), NULL, CountryLanguage.P set join_buffer_size=256; show variables like 'join_buffer_size'; -set join_cache_level=5; +set join_cache_level=3; show variables like 'join_cache_level'; EXPLAIN @@ -422,14 +491,41 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +EXPLAIN +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +set join_cache_level=4; +show variables like 'join_cache_level'; + +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; + +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; EXPLAIN SELECT Name FROM City @@ -440,7 +536,7 @@ SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND City.Population > 100000; -set join_cache_level=6; +set join_cache_level=5; show variables like 'join_cache_level'; EXPLAIN @@ -467,14 +563,41 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer +EXPLAIN +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +SELECT Name FROM City + WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND + City.Population > 100000; + +set join_cache_level=6; +show variables like 'join_cache_level'; + +EXPLAIN +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +SELECT City.Name, Country.Name FROM City,Country + WHERE City.Country=Country.Code AND + Country.Name LIKE 'L%' AND City.Population > 100000; + +EXPLAIN +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; + +SELECT City.Name, Country.Name, CountryLanguage.Language + FROM City,Country,CountryLanguage + WHERE City.Country=Country.Code AND + CountryLanguage.Country=Country.Code AND + City.Name LIKE 'L%' AND Country.Population > 3000000 AND + CountryLanguage.Percentage > 50; EXPLAIN SELECT Name FROM City @@ -512,15 +635,6 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer - EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -557,15 +671,6 @@ SELECT City.Name, Country.Name, CountryLanguage.Language City.Name LIKE 'L%' AND Country.Population > 3000000 AND CountryLanguage.Percentage > 50; ---echo # !!!NB igor: after backporting the SJ code the following should return ---echo # EXPLAIN ---echo # SELECT Name FROM City ---echo # WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND ---echo # City.Population > 100000; ---echo # id select_type table type possible_keys key key_len ref rows Extra ---echo # 1 PRIMARY Country range PRIMARY,Name Name 52 NULL 10 Using index condition; Using MRR ---echo # 1 PRIMARY City ref Population,Country Country 3 world.Country.Code 18 Using where; Using join buffer - EXPLAIN SELECT Name FROM City WHERE City.Country IN (SELECT Code FROM Country WHERE Country.Name LIKE 'L%') AND @@ -587,7 +692,7 @@ SELECT City.Name, Country.Name FROM City,Country WHERE City.Country=Country.Code AND City.Population > 3000000; set join_cache_level=8; -set join_buffer_size=256; +set join_buffer_size=384; --replace_column 9 # EXPLAIN @@ -997,7 +1102,7 @@ select * from t1 left join t2 on (1=0); explain select * from t1 left join t2 on (1=0) where a=40; select * from t1 left join t2 on (1=0) where a=40; -set join_cache_level=1; +set join_cache_level=0; explain select * from t1 left join t2 on (1=0); set join_cache_level=default; @@ -1131,6 +1236,8 @@ INSERT INTO t3(a,b) VALUES (5,30), (5,40), (5,50), (5,60), (5,70), (5,80), (7,30), (7,40), (7,50), (7,60), (7,70), (7,80); +set join_cache_level=0; + SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b) WHERE t1.a=t2.a; @@ -1148,7 +1255,7 @@ SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val WHERE t1.a=t2.a; DROP INDEX idx ON t3; -set join_cache_level=4; +set join_cache_level=2; EXPLAIN SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val @@ -1847,3 +1954,5 @@ select t1.* from t1,t2,t3; set join_cache_level=default; drop table t1,t2,t3; + +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/t/join_nested_jcl6.test b/mysql-test/t/join_nested_jcl6.test index caa656ecd87..5737cfe115f 100644..100755 --- a/mysql-test/t/join_nested_jcl6.test +++ b/mysql-test/t/join_nested_jcl6.test @@ -2,6 +2,10 @@ # Run join_nested.test with BKA enabled # +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -93,3 +97,5 @@ DROP TABLE t5,t6,t7,t8; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/t/join_outer_jcl6.test b/mysql-test/t/join_outer_jcl6.test index 16543296f27..be98e7503ad 100644..100755 --- a/mysql-test/t/join_outer_jcl6.test +++ b/mysql-test/t/join_outer_jcl6.test @@ -2,6 +2,10 @@ # Run join_outer.test with BKA enabled # +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -9,3 +13,5 @@ show variables like 'join_cache_level'; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/t/select_jcl6.test b/mysql-test/t/select_jcl6.test index 3247ab6e343..9f9a3a40e0f 100644..100755 --- a/mysql-test/t/select_jcl6.test +++ b/mysql-test/t/select_jcl6.test @@ -2,6 +2,10 @@ # Run select.test with BKA enabled # +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -9,3 +13,5 @@ show variables like 'join_cache_level'; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/mysql-test/t/subselect3.test b/mysql-test/t/subselect3.test index a621c4c776c..2a5aa1c5429 100644..100755 --- a/mysql-test/t/subselect3.test +++ b/mysql-test/t/subselect3.test @@ -2,6 +2,8 @@ drop table if exists t0, t1, t2, t3, t4, t5, t11, t12, t21, t22; --enable_warnings +set @save_optimizer_switch=@@optimizer_switch; + # # 1. Subquery with GROUP/HAVING # @@ -888,7 +890,7 @@ set @@optimizer_switch='firstmatch=off'; explain select (select max(Y.a) from t1 Y where a in (select a from t1 Z) and a < X.a) as subq from t1 X; select (select max(Y.a) from t1 Y where a in (select a from t1 Z) and a < X.a) as subq from t1 X; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t1; @@ -906,7 +908,7 @@ select * from t1 where 2 in (select a from t0); set @@optimizer_switch='default,materialization=off'; explain select * from t1 where 2 in (select a from t0); select * from t1 where 2 in (select a from t0); -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; # @@ -952,7 +954,7 @@ flush status; select count(*) from t0 A, t0 B, t0 C, t0 D where D.a in (select a from t1 E); show status like 'Created_tmp_disk_tables'; set @save_max_heap_table_size=@@max_heap_table_size; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1; # @@ -990,7 +992,7 @@ create table t1 (a decimal); insert into t1 values (1),(2); explain select * from t1 where a in (select a from t1); drop table t1; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; # # SJ-Materialization-scan for non-first table @@ -1051,7 +1053,7 @@ set @save_optimizer_search_depth=@@optimizer_search_depth; set @@optimizer_search_depth=63; explain select * from t1 where (a,b) in (select a,b from t2); set @@optimizer_search_depth=@save_optimizer_search_depth; -set @@optimizer_switch=default; +set @@optimizer_switch=@save_optimizer_switch; drop table t0, t1, t2; @@ -1181,3 +1183,6 @@ ALTER TABLE t2 CHANGE COLUMN f1 my_column INT; CALL p1; DROP PROCEDURE p1; DROP TABLE t1, t2; + +# The following command must be the last one the file +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/t/subselect3_jcl6.test b/mysql-test/t/subselect3_jcl6.test index 9ee23288d99..6d9611f83f3 100644..100755 --- a/mysql-test/t/subselect3_jcl6.test +++ b/mysql-test/t/subselect3_jcl6.test @@ -2,6 +2,10 @@ # Run subselect3.test with BKA enabled # +set @save_optimizer_switch=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -9,3 +13,5 @@ show variables like 'join_cache_level'; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/t/subselect_sj.test b/mysql-test/t/subselect_sj.test index 33f3e936482..783429ed836 100644..100755 --- a/mysql-test/t/subselect_sj.test +++ b/mysql-test/t/subselect_sj.test @@ -5,6 +5,8 @@ drop table if exists t0, t1, t2, t3, t4, t10, t11, t12; --enable_warnings +set @save_optimizer_switch=@@optimizer_switch; + # # 1. Subqueries that are converted into semi-joins # @@ -224,7 +226,8 @@ INSERT INTO WORKS VALUES ('E4','P2',20); INSERT INTO WORKS VALUES ('E4','P4',40); INSERT INTO WORKS VALUES ('E4','P5',80); -set optimizer_switch='default,materialization=off'; +set optimizer_switch=@save_optimizer_switch; +set optimizer_switch='materialization=off'; explain SELECT EMPNUM, EMPNAME FROM STAFF @@ -240,7 +243,7 @@ WHERE EMPNUM IN WHERE PNUM IN (SELECT PNUM FROM PROJ)); -set optimizer_switch='default'; +set optimizer_switch=@save_optimizer_switch; drop table STAFF,WORKS,PROJ; @@ -359,7 +362,7 @@ drop table t1, t2; drop view v1; drop procedure p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; --echo # End of bug#46744 @@ -526,7 +529,7 @@ DROP TABLE t1,t2; DROP VIEW v1,v2; DROP PROCEDURE p1; -set SESSION optimizer_switch='default'; +set SESSION optimizer_switch=@save_optimizer_switch; --echo # End of BUG#48834 @@ -935,3 +938,6 @@ DROP TABLE t2; DROP TABLE t3; --echo # End of Bug#48623 + +# The following command must be the last one the file +set @@optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/t/subselect_sj2_jcl6.test b/mysql-test/t/subselect_sj2_jcl6.test index 202ea139e5f..5292a56f266 100644..100755 --- a/mysql-test/t/subselect_sj2_jcl6.test +++ b/mysql-test/t/subselect_sj2_jcl6.test @@ -2,6 +2,10 @@ # Run subselect_sj2.test with BKA enabled # +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -9,3 +13,6 @@ show variables like 'join_cache_level'; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch_jcl6; + diff --git a/mysql-test/t/subselect_sj_jcl6.test b/mysql-test/t/subselect_sj_jcl6.test index f821e1864be..27c864fc699 100644..100755 --- a/mysql-test/t/subselect_sj_jcl6.test +++ b/mysql-test/t/subselect_sj_jcl6.test @@ -2,6 +2,10 @@ # Run subselect_sj.test with BKA enabled # +set @save_optimizer_switch_jcl6=@@optimizer_switch; +set @@optimizer_switch='semijoin_with_cache=on'; +set @@optimizer_switch='outer_join_with_cache=on'; + set join_cache_level=6; show variables like 'join_cache_level'; @@ -37,3 +41,5 @@ drop table t0, t1, t2; set join_cache_level=default; show variables like 'join_cache_level'; + +set @@optimizer_switch=@save_optimizer_switch_jcl6; diff --git a/sql/handler.h b/sql/handler.h index e12048da18c..62ed49b7cdd 100644 --- a/sql/handler.h +++ b/sql/handler.h @@ -1211,6 +1211,8 @@ typedef struct st_range_seq_if bool (*skip_index_tuple) (range_seq_t seq, char *range_info); } RANGE_SEQ_IF; +typedef bool (*SKIP_INDEX_TUPLE_FUNC) (range_seq_t seq, char *range_info); + class COST_VECT { public: diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h index ba60bab9b50..987bce5a3fd 100644..100755 --- a/sql/mysql_priv.h +++ b/sql/mysql_priv.h @@ -571,12 +571,17 @@ protected: #define OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE 512 #define OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN 1024 #define OPTIMIZER_SWITCH_SUBQUERY_CACHE (1<<11) +#define OPTIMIZER_SWITCH_OUTER_JOIN_WITH_CACHE (1<<12) +#define OPTIMIZER_SWITCH_SEMIJOIN_WITH_CACHE (1<<13) +#define OPTIMIZER_SWITCH_JOIN_CACHE_INCREMENTAL (1<<14) +#define OPTIMIZER_SWITCH_JOIN_CACHE_HASHED (1<<15) +#define OPTIMIZER_SWITCH_JOIN_CACHE_BKA (1<<16) #ifdef DBUG_OFF -# define OPTIMIZER_SWITCH_LAST (1<<12) +# define OPTIMIZER_SWITCH_LAST (1<<17) #else -# define OPTIMIZER_SWITCH_TABLE_ELIMINATION (1<<12) -# define OPTIMIZER_SWITCH_LAST (1<<13) +# define OPTIMIZER_SWITCH_TABLE_ELIMINATION (1<<17) +# define OPTIMIZER_SWITCH_LAST (1<<18) #endif #ifdef DBUG_OFF @@ -592,7 +597,10 @@ protected: OPTIMIZER_SWITCH_SEMIJOIN | \ OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\ OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN|\ - OPTIMIZER_SWITCH_SUBQUERY_CACHE) + OPTIMIZER_SWITCH_SUBQUERY_CACHE | \ + OPTIMIZER_SWITCH_JOIN_CACHE_INCREMENTAL | \ + OPTIMIZER_SWITCH_JOIN_CACHE_HASHED | \ + OPTIMIZER_SWITCH_JOIN_CACHE_BKA) #else # define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \ OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \ @@ -606,7 +614,10 @@ protected: OPTIMIZER_SWITCH_SEMIJOIN | \ OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE|\ OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN|\ - OPTIMIZER_SWITCH_SUBQUERY_CACHE) + OPTIMIZER_SWITCH_SUBQUERY_CACHE | \ + OPTIMIZER_SWITCH_JOIN_CACHE_INCREMENTAL | \ + OPTIMIZER_SWITCH_JOIN_CACHE_HASHED | \ + OPTIMIZER_SWITCH_JOIN_CACHE_BKA) #endif /* diff --git a/sql/mysqld.cc b/sql/mysqld.cc index 1593a584454..db8f3e12ac3 100644..100755 --- a/sql/mysqld.cc +++ b/sql/mysqld.cc @@ -308,6 +308,11 @@ static const char *optimizer_switch_names[]= "partial_match_rowid_merge", "partial_match_table_scan", "subquery_cache", + "outer_join_with_cache", + "semijoin_with_cache", + "join_cache_incremental", + "join_cache_hashed", + "join_cache_bka", #ifndef DBUG_OFF "table_elimination", #endif @@ -329,6 +334,11 @@ static const unsigned int optimizer_switch_names_len[]= sizeof("partial_match_rowid_merge") - 1, sizeof("partial_match_table_scan") - 1, sizeof("subquery_cache") - 1, + sizeof("outer_join_with_cache") - 1, + sizeof("semijoin_with_cache") - 1, + sizeof("join_cache_incremental") - 1, + sizeof("join_cache_hashed") - 1, + sizeof("join_cache_bka") - 1, #ifndef DBUG_OFF sizeof("table_elimination") - 1, #endif @@ -415,7 +425,10 @@ static const char *optimizer_switch_str="index_merge=on,index_merge_union=on," "semijoin=on," "partial_match_rowid_merge=on," "partial_match_table_scan=on," - "subquery_cache=on" + "subquery_cache=on," + "join_cache_incremental=on," + "join_cache_hashed=on," + "join_cache_bka=on" #ifndef DBUG_OFF ",table_elimination=on"; #else @@ -5865,7 +5878,8 @@ enum options_mysqld OPT_DELAYED_INSERT_LIMIT, OPT_DELAYED_QUEUE_SIZE, OPT_FLUSH_TIME, OPT_FT_MIN_WORD_LEN, OPT_FT_BOOLEAN_SYNTAX, OPT_FT_MAX_WORD_LEN, OPT_FT_QUERY_EXPANSION_LIMIT, OPT_FT_STOPWORD_FILE, - OPT_INTERACTIVE_TIMEOUT, OPT_JOIN_BUFF_SIZE, OPT_JOIN_CACHE_LEVEL, + OPT_INTERACTIVE_TIMEOUT, OPT_JOIN_BUFF_SIZE, + OPT_JOIN_BUFF_SPACE_LIMIT, OPT_JOIN_CACHE_LEVEL, OPT_KEY_BUFFER_SIZE, OPT_KEY_CACHE_BLOCK_SIZE, OPT_KEY_CACHE_DIVISION_LIMIT, OPT_KEY_CACHE_AGE_THRESHOLD, OPT_KEY_CACHE_PARTITIONS, @@ -6958,11 +6972,17 @@ log and this option does nothing anymore.", (uchar**) &max_system_variables.net_interactive_timeout, 0, GET_ULONG, REQUIRED_ARG, NET_WAIT_TIMEOUT, 1, LONG_TIMEOUT, 0, 1, 0}, {"join_buffer_size", OPT_JOIN_BUFF_SIZE, - "The size of the buffer that is used for full joins.", + "The size of the buffer that is used for joins.", (uchar**) &global_system_variables.join_buff_size, (uchar**) &max_system_variables.join_buff_size, 0, GET_ULONG, REQUIRED_ARG, 128*1024L, 128+MALLOC_OVERHEAD, (longlong) ULONG_MAX, MALLOC_OVERHEAD, 128, 0}, + {"join_buffer_space_limit", OPT_JOIN_BUFF_SPACE_LIMIT, + "The limit of the space for all join buffers used by a query.", + (uchar**) &global_system_variables.join_buff_space_limit, + (uchar**) &max_system_variables.join_buff_space_limit, 0, GET_ULL, + REQUIRED_ARG, 8*128*1024L, 2048+MALLOC_OVERHEAD, (longlong) ULONGLONG_MAX, + MALLOC_OVERHEAD, 2048, 0}, {"join_cache_level", OPT_JOIN_CACHE_LEVEL, "Controls what join operations can be executed with join buffers. Odd numbers are used for plain join buffers while even numbers are used for linked buffers", (uchar**) &global_system_variables.join_cache_level, @@ -7235,7 +7255,8 @@ The minimum value for this variable is 4096.", "index_merge_union, index_merge_sort_union, index_merge_intersection, " "index_condition_pushdown, firstmatch, loosescan, materialization, " "semijoin, partial_match_rowid_merge, partial_match_table_scan, " - "subquery_cache" + "subquery_cache, outer_join_with_cache, semijoin_with_cache, " + "join_cache_incremental, join_cache_hashed, join_cache_bka" #ifndef DBUG_OFF ", table_elimination" #endif diff --git a/sql/opt_subselect.h b/sql/opt_subselect.h index e9b93085aea..9de12774dec 100644..100755 --- a/sql/opt_subselect.h +++ b/sql/opt_subselect.h @@ -199,7 +199,8 @@ public: double records= rows2double(s->table->file->stats.records); /* The cost is entire index scan cost (divided by 2) */ - double read_time= s->table->file->keyread_read_time(key, 1, records); + double read_time= + s->table->file->keyread_read_time(key, 1, (ha_rows) records); /* Now find out how many different keys we will get (for now we diff --git a/sql/set_var.cc b/sql/set_var.cc index 56ebdbcade1..45c2aab03ab 100644..100755 --- a/sql/set_var.cc +++ b/sql/set_var.cc @@ -319,6 +319,9 @@ static sys_var_thd_ulong sys_interactive_timeout(&vars, "interactive_timeout", &SV::net_interactive_timeout); static sys_var_thd_ulong sys_join_buffer_size(&vars, "join_buffer_size", &SV::join_buff_size); +static sys_var_thd_ulonglong sys_join_buffer_space_limit(&vars, + "join_buffer_space_limit", + &SV::join_buff_space_limit); static sys_var_thd_ulong sys_join_cache_level(&vars, "join_cache_level", &SV::join_cache_level); static sys_var_key_buffer_size sys_key_buffer_size(&vars, "key_buffer_size"); @@ -4045,7 +4048,7 @@ bool sys_var_thd_optimizer_switch:: symbolic_mode_representation(THD *thd, ulonglong val, LEX_STRING *rep) { - char buff[STRING_BUFFER_USUAL_SIZE*8]; + char buff[STRING_BUFFER_USUAL_SIZE*18]; String tmp(buff, sizeof(buff), &my_charset_latin1); int i; ulonglong bit; diff --git a/sql/sql_class.h b/sql/sql_class.h index 53f03de5efc..4852023dbf9 100644..100755 --- a/sql/sql_class.h +++ b/sql/sql_class.h @@ -376,6 +376,7 @@ struct system_variables ulonglong max_heap_table_size; ulonglong tmp_table_size; ulonglong long_query_time; + ulonglong join_buff_space_limit; ha_rows select_limit; ha_rows max_join_size; ulong auto_increment_increment, auto_increment_offset; diff --git a/sql/sql_join_cache.cc b/sql/sql_join_cache.cc index e9923c3c983..b61adbf8d79 100644..100755 --- a/sql/sql_join_cache.cc +++ b/sql/sql_join_cache.cc @@ -57,7 +57,7 @@ The function ignores the fields 'blob_length' and 'ofset' of the descriptor. - RETURN + RETURN VALUE the length of the field */ @@ -98,7 +98,7 @@ uint add_flag_field_to_join_cache(uchar *str, uint length, CACHE_FIELD **field) descriptor while 'descr_ptr' points to the position right after the last added pointer. - RETURN + RETURN VALUE the total length of the added fields */ @@ -152,7 +152,7 @@ uint add_table_data_fields_to_join_cache(JOIN_TAB *tab, The function sets 'with_match_flag' on if 'join_tab' needs a match flag i.e. if it is the first inner table of an outer join or a semi-join. - RETURN + RETURN VALUE none */ @@ -171,7 +171,7 @@ void JOIN_CACHE::calc_record_fields() for ( ; tab < join_tab ; tab++) { - calc_used_field_length(join->thd, tab); + tab->calc_used_field_length(FALSE); flag_fields+= test(tab->used_null_fields || tab->used_uneven_bit_fields); flag_fields+= test(tab->table->maybe_null); fields+= tab->used_fields; @@ -184,6 +184,72 @@ void JOIN_CACHE::calc_record_fields() fields+= flag_fields; } + +/* + Collect information on join key arguments + + SYNOPSIS + collect_info_on_key_args() + + DESCRIPTION + The function traverses the ref expressions that are used to access the + joined table join_tab. For each table 'tab' whose fields are to be stored + in the join buffer of the cache the function finds the fields from 'tab' + that occur in the ref expressions and marks these fields in the bitmap + tab->table->tmp_set. The function counts the number of them stored + in this cache and the total number of them stored in the previous caches + and saves the results of the counting in 'local_key_arg_fields' and 'external_key_arg_fields' respectively. + + NOTES + The function does not do anything if no key is used to join the records + from join_tab. + + RETURN VALUE + none +*/ + +void JOIN_CACHE::collect_info_on_key_args() +{ + JOIN_TAB *tab; + JOIN_CACHE *cache; + local_key_arg_fields= 0; + external_key_arg_fields= 0; + + if (!is_key_access()) + return; + + TABLE_REF *ref= &join_tab->ref; + cache= this; + do + { + for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++) + { + uint key_args; + bitmap_clear_all(&tab->table->tmp_set); + for (uint i= 0; i < ref->key_parts; i++) + { + Item *ref_item= ref->items[i]; + if (!(tab->table->map & ref_item->used_tables())) + continue; + ref_item->walk(&Item::add_field_to_set_processor, 1, + (uchar *) tab->table); + } + if ((key_args= bitmap_bits_set(&tab->table->tmp_set))) + { + if (cache == this) + local_key_arg_fields+= key_args; + else + external_key_arg_fields+= key_args; + } + } + cache= cache->prev_cache; + } + while (cache); + + return; +} + + /* Allocate memory for descriptors and pointers to them associated with the cache @@ -195,23 +261,22 @@ void JOIN_CACHE::calc_record_fields() and the array of pointers to the field descriptors used to copy join record data from record buffers into the join buffer and backward. Some pointers refer to the field descriptor associated - with previous caches. They are placed at the beginning of the - array of pointers and its total number is specified by the parameter - 'external fields'. - The pointer of the first array is assigned to field_descr and the - number of elements is precalculated by the function calc_record_fields. + with previous caches. They are placed at the beginning of the array + of pointers and its total number is stored in external_key_arg_fields. + The pointer of the first array is assigned to field_descr and the number + of the elements in it is precalculated by the function calc_record_fields. The allocated arrays are adjacent. NOTES The memory is allocated in join->thd->memroot - RETURN + RETURN VALUE pointer to the first array */ -int JOIN_CACHE::alloc_fields(uint external_fields) +int JOIN_CACHE::alloc_fields() { - uint ptr_cnt= external_fields+blobs+1; + uint ptr_cnt= external_key_arg_fields+blobs+1; uint fields_size= sizeof(CACHE_FIELD)*fields; field_descr= (CACHE_FIELD*) sql_alloc(fields_size + sizeof(CACHE_FIELD*)*ptr_cnt); @@ -219,6 +284,7 @@ int JOIN_CACHE::alloc_fields(uint external_fields) return (field_descr == NULL); } + /* Create descriptors of the record flag fields stored in the join buffer @@ -252,7 +318,7 @@ int JOIN_CACHE::alloc_fields(uint external_fields) The function sets the value of 'length' to the total length of the flag fields. - RETURN + RETURN VALUE none */ @@ -295,17 +361,144 @@ void JOIN_CACHE::create_flag_fields() /* + Create descriptors of the fields used to build access keys to the joined table + + SYNOPSIS + create_key_arg_fields() + + DESCRIPTION + The function creates descriptors of the record fields stored in the join + buffer that are used to build access keys to the joined table. These + fields are put into the buffer ahead of other records fields stored in + the buffer. Such placement helps to optimize construction of access keys. + For each field that is used to build access keys to the joined table but + is stored in some other join cache buffer the function saves a pointer + to the the field descriptor. The array of such pointers are placed in the + the join cache structure just before the array of pointers to the + blob fields blob_ptr. + Any field stored in a join cache buffer that is used to construct keys + to access tables associated with other join caches is called a referenced + field. It receives a unique number that is saved by the function in the + member 'referenced_field_no' of the CACHE_FIELD descriptor for the field. + This number is used as index to the array of offsets to the referenced + fields that are saved and put in the join cache buffer after all record + fields. + The function also finds out whether that the keys to access join_tab + can be considered as embedded and, if so, sets the flag 'use_emb_key' in + this join cache appropriately. + + NOTES. + When a key to access the joined table 'join_tab' is constructed the array + of pointers to the field descriptors for the external fields is looked + through. For each of this pointers we find out in what previous key cache + the referenced field is stored. The value of 'referenced_field_no' + provides us with the index into the array of offsets for referenced + fields stored in the join cache. The offset read by the the index allows + us to read the field without reading all other fields of the record + stored the join cache buffer. This optimizes the construction of keys + to access 'join_tab' when some key arguments are stored in the previous + join caches. + + NOTES + The function does not do anything if no key is used to join the records + from join_tab. + + RETURN VALUE + none +*/ +void JOIN_CACHE::create_key_arg_fields() +{ + JOIN_TAB *tab; + JOIN_CACHE *cache; + + if (!is_key_access()) + return; + + /* + Save pointers to the cache fields in previous caches + that are used to build keys for this key access. + */ + cache= this; + uint ext_key_arg_cnt= external_key_arg_fields; + CACHE_FIELD *copy; + CACHE_FIELD **copy_ptr= blob_ptr; + while (ext_key_arg_cnt) + { + cache= cache->prev_cache; + for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++) + { + CACHE_FIELD *copy_end; + MY_BITMAP *key_read_set= &tab->table->tmp_set; + /* key_read_set contains the bitmap of tab's fields referenced by ref */ + if (bitmap_is_clear_all(key_read_set)) + continue; + copy_end= cache->field_descr+cache->fields; + for (copy= cache->field_descr+cache->flag_fields; copy < copy_end; copy++) + { + /* + (1) - when we store rowids for DuplicateWeedout, they have + copy->field==NULL + */ + if (copy->field && // (1) + copy->field->table == tab->table && + bitmap_is_set(key_read_set, copy->field->field_index)) + { + *copy_ptr++= copy; + ext_key_arg_cnt--; + if (!copy->referenced_field_no) + { + /* + Register the referenced field 'copy': + - set the offset number in copy->referenced_field_no, + - adjust the value of the flag 'with_length', + - adjust the values of 'pack_length' and + of 'pack_length_with_blob_ptrs'. + */ + copy->referenced_field_no= ++cache->referenced_fields; + if (!cache->with_length) + { + cache->with_length= TRUE; + uint sz= cache->get_size_of_rec_length(); + cache->base_prefix_length+= sz; + cache->pack_length+= sz; + cache->pack_length_with_blob_ptrs+= sz; + } + cache->pack_length+= cache->get_size_of_fld_offset(); + cache->pack_length_with_blob_ptrs+= cache->get_size_of_fld_offset(); + } + } + } + } + } + /* After this 'blob_ptr' shall not be be changed */ + blob_ptr= copy_ptr; + + /* Now create local fields that are used to build ref for this key access */ + copy= field_descr+flag_fields; + for (tab= join_tab-tables; tab < join_tab ; tab++) + { + length+= add_table_data_fields_to_join_cache(tab, &tab->table->tmp_set, + &data_field_count, ©, + &data_field_ptr_count, + ©_ptr); + } + + use_emb_key= check_emb_key_usage(); + + return; +} + + +/* Create descriptors of all remaining data fields stored in the join buffer SYNOPSIS create_remaining_fields() - all_read_fields indicates that descriptors for all read data fields - are to be created DESCRIPTION The function creates descriptors for all remaining data fields of a - record from the join buffer. If the parameter 'all_read_fields' is - true the function creates fields for all read record fields that + record from the join buffer. If the value returned by is_key_access() is + false the function creates fields for all read record fields that comprise the partial join record joined with join_tab. Otherwise, for each table tab, the set of the read fields for which the descriptors have to be added is determined as the difference between all read fields @@ -315,7 +508,7 @@ void JOIN_CACHE::create_flag_fields() the added fields. NOTES - If 'all_read_fields' is false the function modifies the value of + If is_key_access() returns true the function modifies the value of tab->table->tmp_set for a each table whose fields are stored in the cache. The function calls the method Field::fill_cache_field to figure out the type of the cache field and the maximal length of its representation @@ -327,13 +520,14 @@ void JOIN_CACHE::create_flag_fields() contains the number of the pointers to such descriptors having been stored up to the moment. - RETURN + RETURN VALUE none */ -void JOIN_CACHE:: create_remaining_fields(bool all_read_fields) +void JOIN_CACHE:: create_remaining_fields() { JOIN_TAB *tab; + bool all_read_fields= !is_key_access(); CACHE_FIELD *copy= field_descr+flag_fields+data_field_count; CACHE_FIELD **copy_ptr= blob_ptr+data_field_ptr_count; @@ -372,6 +566,7 @@ void JOIN_CACHE:: create_remaining_fields(bool all_read_fields) } + /* Calculate and set all cache constants @@ -389,7 +584,7 @@ void JOIN_CACHE:: create_remaining_fields(bool all_read_fields) making a dicision whether more records should be added into the join buffer or not. - RETURN + RETURN VALUE none */ @@ -424,6 +619,8 @@ void JOIN_CACHE::set_constants() size_of_rec_ofs= offset_size(buff_size); size_of_rec_len= blobs ? size_of_rec_ofs : offset_size(len); size_of_fld_ofs= size_of_rec_len; + base_prefix_length= (with_length ? size_of_rec_len : 0) + + (prev_cache ? prev_cache->get_size_of_rec_offset() : 0); /* The size of the offsets for referenced fields will be added later. The values of 'pack_length' and 'pack_length_with_blob_ptrs' are adjusted @@ -437,92 +634,293 @@ void JOIN_CACHE::set_constants() /* - Allocate memory for a join buffer + Get maximum total length of all affixes of a record in the join cache buffer SYNOPSIS - alloc_buffer() + get_record_max_affix_length() DESCRIPTION - The function allocates a lump of memory for the cache join buffer. The - size of the allocated memory is 'buff_size' bytes. - - RETURN - 0 - if the memory has been successfully allocated - 1 - otherwise + The function calculates the maximum possible total length of all affixes + of a record in the join cache buffer, that is made of: + - the length of all prefixes used in this cache, + - the length of the match flag if it's needed + - the total length of the maximum possible offsets to the fields of + a record in the buffer. + + RETURN VALUE + The maximum total length of all affixes of a record in the join buffer +*/ + +uint JOIN_CACHE::get_record_max_affix_length() +{ + uint len= get_prefix_length() + + test(with_match_flag) + + size_of_fld_ofs * data_field_count; + return len; +} + + +/* + Get the minimum possible size of the cache join buffer + + SYNOPSIS + get_min_join_buffer_size() + + DESCRIPTION + At the first its invocation for the cache the function calculates the + minimum possible size of the join buffer of the cache. This value depends + on the minimal number of records 'min_records' to be stored in the join + buffer. The number is supposed to be determined by the procedure that + chooses the best access path to the joined table join_tab in the execution + plan. After the calculation of the interesting size the function saves it + in the field 'min_buff_size' in order to use it directly at the next + invocations of the function. + + NOTES + Currently the number of minimal records is just set to 1. + + RETURN VALUE + The minimal possible size of the join buffer of this cache */ -int JOIN_CACHE::alloc_buffer() +ulong JOIN_CACHE::get_min_join_buffer_size() { - buff= (uchar*) my_malloc(buff_size, MYF(0)); - return buff == NULL; -} - + if (!min_buff_size) + { + ulong len= 0; + for (JOIN_TAB *tab= join_tab-tables; tab < join_tab; tab++) + len+= tab->get_max_used_fieldlength(); + len+= get_record_max_affix_length() + get_max_key_addon_space_per_record(); + ulong min_sz= len*min_records; + ulong add_sz= 0; + for (uint i=0; i < min_records; i++) + add_sz+= join_tab_scan->aux_buffer_incr(i+1); + avg_aux_buffer_incr= add_sz/min_records; + min_sz+= add_sz; + min_sz+= pack_length_with_blob_ptrs; + min_buff_size= min_sz; + } + return min_buff_size; +} + /* - Initialize a BNL cache + Get the maximum possible size of the cache join buffer SYNOPSIS - init() + get_max_join_buffer_size() DESCRIPTION - The function initializes the cache structure. It supposed to be called - right after a constructor for the JOIN_CACHE_BNL. - The function allocates memory for the join buffer and for descriptors of - the record fields stored in the buffer. + At the first its invocation for the cache the function calculates the + maximum possible size of join buffer for the cache. This value does not + exceed the estimate of the number of records 'max_records' in the partial + join that joins tables from the first one through join_tab. This value + is also capped off by the value of join_tab->join_buffer_size_limit, if it + has been set a to non-zero value, and by the value of the system parameter + join_buffer_size - otherwise. After the calculation of the interesting size + the function saves the value in the field 'max_buff_size' in order to use + it directly at the next invocations of the function. NOTES - The code of this function should have been included into the constructor - code itself. However the new operator for the class JOIN_CACHE_BNL would - never fail while memory allocation for the join buffer is not absolutely - unlikely to fail. That's why this memory allocation has to be placed in a - separate function that is called in a couple with a cache constructor. - It is quite natural to put almost all other constructor actions into - this function. - - RETURN - 0 initialization with buffer allocations has been succeeded - 1 otherwise + Currently the value of join_tab->join_buffer_size_limit is initialized + to 0 and is never reset. + + RETURN VALUE + The maximum possible size of the join buffer of this cache */ -int JOIN_CACHE_BNL::init() +ulong JOIN_CACHE::get_max_join_buffer_size() { - DBUG_ENTER("JOIN_CACHE::init"); + if (!max_buff_size) + { + ulong max_sz; + ulong min_sz= get_min_join_buffer_size(); + ulong len= 0; + for (JOIN_TAB *tab= join_tab-tables; tab < join_tab; tab++) + len+= tab->get_used_fieldlength(); + len+= get_record_max_affix_length(); + avg_record_length= len; + len+= get_max_key_addon_space_per_record() + avg_aux_buffer_incr; + space_per_record= len; + + ulong limit_sz= join->thd->variables.join_buff_size; + if (join_tab->join_buffer_size_limit) + set_if_smaller(limit_sz, join_tab->join_buffer_size_limit); + if (limit_sz / max_records > space_per_record) + max_sz*= space_per_record * max_records; + else + max_sz= limit_sz; + max_sz+= pack_length_with_blob_ptrs; + set_if_smaller(max_sz, limit_sz); + set_if_bigger(max_sz, min_sz); + max_buff_size= max_sz; + } + return max_buff_size; +} + - calc_record_fields(); +/* + Allocate memory for a join buffer - if (alloc_fields(0)) - DBUG_RETURN(1); + SYNOPSIS + alloc_buffer() - create_flag_fields(); + DESCRIPTION + The function allocates a lump of memory for the cache join buffer. + Initially the function sets the size of the buffer buff_size equal to + the value returned by get_max_join_buffer_size(). If the total size of + the space intended to be used for the join buffers employed by the + tables from the first one through join_tab exceeds the value of the + system parameter join_buff_space_limit, then the function first tries + to shrink the used buffers to make the occupied space fit the maximum + memory allowed to be used for all join buffers in total. After + this the function tries to allocate a join buffer for join_tab. + If it fails to do so, it decrements the requested size of the join + buffer, shrinks proportionally the join buffers used for the previous + tables and tries to allocate a buffer for join_tab. In the case of a + failure the function repeats its attempts with smaller and smaller + requested sizes of the buffer, but not more than 4 times. - create_remaining_fields(TRUE); + RETURN VALUE + 0 if the memory has been successfully allocated + 1 otherwise +*/ - set_constants(); +int JOIN_CACHE::alloc_buffer() +{ + JOIN_TAB *tab; + JOIN_CACHE *cache; + ulonglong curr_buff_space_sz= 0; + ulonglong curr_min_buff_space_sz= 0; + ulonglong join_buff_space_limit= + join->thd->variables.join_buff_space_limit; + buff= NULL; + min_buff_size= 0; + max_buff_size= 0; + min_records= 1; + max_records= join_tab->records; + set_if_bigger(max_records, 1); + min_buff_size= get_min_join_buffer_size(); + buff_size= get_max_join_buffer_size(); + for (tab= join->join_tab+join->const_tables; tab <= join_tab; tab++) + { + cache= tab->cache; + if (cache) + { + curr_min_buff_space_sz+= cache->get_min_join_buffer_size(); + curr_buff_space_sz+= cache->get_join_buffer_size(); + } + } - if (alloc_buffer()) - DBUG_RETURN(1); - - reset(TRUE); + if (curr_min_buff_space_sz > join_buff_space_limit || + curr_buff_space_sz > join_buff_space_limit && + join->shrink_join_buffers(join_tab, curr_buff_space_sz, + join_buff_space_limit)) + goto fail; + + for (ulong buff_size_decr= (buff_size-min_buff_size)/4 + 1; ; ) + { + ulong next_buff_size; - DBUG_RETURN(0); + if ((buff= (uchar*) my_malloc(buff_size, MYF(0)))) + break; + + next_buff_size= buff_size > buff_size_decr ? buff_size-buff_size_decr : 0; + if (next_buff_size < min_buff_size || + join->shrink_join_buffers(join_tab, curr_buff_space_sz, + curr_buff_space_sz-buff_size_decr)) + goto fail; + buff_size= next_buff_size; + + curr_buff_space_sz= 0; + for (tab= join->join_tab+join->const_tables; tab <= join_tab; tab++) + { + cache= tab->cache; + if (cache) + curr_buff_space_sz+= cache->get_join_buffer_size(); + } + } + return 0; + +fail: + buff_size= 0; + return 1; } + +/* + Shrink the size if the cache join buffer in a given ratio + + SYNOPSIS + shrink_join_buffer_in_ratio() + n nominator of the ratio to shrink the buffer in + d denominator if the ratio + + DESCRIPTION + The function first deallocates the join buffer of the cache. Then + it allocates a buffer that is (n/d) times smaller. + + RETURN VALUE + FALSE on success with allocation of the smaller join buffer + TRUE otherwise +*/ + +bool JOIN_CACHE::shrink_join_buffer_in_ratio(ulonglong n, ulonglong d) +{ + ulonglong next_buff_size; + if (n < d) + return FALSE; + next_buff_size= (ulonglong) ((double) buff_size / n * d); + set_if_smaller(next_buff_size, min_buff_size); + buff_size= next_buff_size; + return realloc_buffer(); +} + + +/* + Reallocate the join buffer of a join cache + + SYNOPSIS + realloc_buffer() + + DESCRITION + The function reallocates the join buffer of the join cache. After this + it resets the buffer for writing. + + NOTES + The function assumes that buff_size contains the new value for the join + buffer size. + + RETURN VALUE + 0 if the buffer has been successfully reallocated + 1 otherwise +*/ + +int JOIN_CACHE::realloc_buffer() +{ + int rc; + free(); + rc= test(!(buff= (uchar*) my_malloc(buff_size, MYF(0)))); + reset(TRUE); + return rc; +} + /* - Initialize a BKA cache + Initialize a join cache SYNOPSIS init() DESCRIPTION - The function initializes the cache structure. It supposed to be called - right after a constructor for the JOIN_CACHE_BKA. + The function initializes the join cache structure. It supposed to be called + by init methods for classes derived from the JOIN_CACHE. The function allocates memory for the join buffer and for descriptors of the record fields stored in the buffer. NOTES The code of this function should have been included into the constructor - code itself. However the new operator for the class JOIN_CACHE_BKA would + code itself. However the new operator for the class JOIN_CACHE would never fail while memory allocation for the join buffer is not absolutely unlikely to fail. That's why this memory allocation has to be placed in a separate function that is called in a couple with a cache constructor. @@ -534,139 +932,36 @@ int JOIN_CACHE_BNL::init() 1 otherwise */ -int JOIN_CACHE_BKA::init() +int JOIN_CACHE::init() { - JOIN_TAB *tab; - JOIN_CACHE *cache; - local_key_arg_fields= 0; - external_key_arg_fields= 0; - DBUG_ENTER("JOIN_CACHE_BKA::init"); + DBUG_ENTER("JOIN_CACHE::init"); calc_record_fields(); - /* Mark all fields that can be used as arguments for this key access */ - TABLE_REF *ref= &join_tab->ref; - cache= this; - do - { - /* - Traverse the ref expressions and find the occurrences of fields in them for - each table 'tab' whose fields are to be stored in the 'cache' join buffer. - Mark these fields in the bitmap tab->table->tmp_set. - For these fields count the number of them stored in this cache and the - total number of them stored in the previous caches. Save the result - of the counting 'in local_key_arg_fields' and 'external_key_arg_fields' - respectively. - */ - for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++) - { - uint key_args; - bitmap_clear_all(&tab->table->tmp_set); - for (uint i= 0; i < ref->key_parts; i++) - { - Item *ref_item= ref->items[i]; - if (!(tab->table->map & ref_item->used_tables())) - continue; - ref_item->walk(&Item::add_field_to_set_processor, 1, - (uchar *) tab->table); - } - if ((key_args= bitmap_bits_set(&tab->table->tmp_set))) - { - if (cache == this) - local_key_arg_fields+= key_args; - else - external_key_arg_fields+= key_args; - } - } - cache= cache->prev_cache; - } - while (cache); + collect_info_on_key_args(); - if (alloc_fields(external_key_arg_fields)) + if (alloc_fields()) DBUG_RETURN(1); create_flag_fields(); - - /* - Save pointers to the cache fields in previous caches - that are used to build keys for this key access. - */ - cache= this; - uint ext_key_arg_cnt= external_key_arg_fields; - CACHE_FIELD *copy; - CACHE_FIELD **copy_ptr= blob_ptr; - while (ext_key_arg_cnt) - { - cache= cache->prev_cache; - for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++) - { - CACHE_FIELD *copy_end; - MY_BITMAP *key_read_set= &tab->table->tmp_set; - /* key_read_set contains the bitmap of tab's fields referenced by ref */ - if (bitmap_is_clear_all(key_read_set)) - continue; - copy_end= cache->field_descr+cache->fields; - for (copy= cache->field_descr+cache->flag_fields; copy < copy_end; copy++) - { - /* - (1) - when we store rowids for DuplicateWeedout, they have - copy->field==NULL - */ - if (copy->field && // (1) - copy->field->table == tab->table && - bitmap_is_set(key_read_set, copy->field->field_index)) - { - *copy_ptr++= copy; - ext_key_arg_cnt--; - if (!copy->referenced_field_no) - { - /* - Register the referenced field 'copy': - - set the offset number in copy->referenced_field_no, - - adjust the value of the flag 'with_length', - - adjust the values of 'pack_length' and - of 'pack_length_with_blob_ptrs'. - */ - copy->referenced_field_no= ++cache->referenced_fields; - cache->with_length= TRUE; - cache->pack_length+= cache->get_size_of_fld_offset(); - cache->pack_length_with_blob_ptrs+= cache->get_size_of_fld_offset(); - } - } - } - } - } - /* After this 'blob_ptr' shall not be be changed */ - blob_ptr= copy_ptr; - - /* Now create local fields that are used to build ref for this key access */ - copy= field_descr+flag_fields; - for (tab= join_tab-tables; tab < join_tab ; tab++) - { - length+= add_table_data_fields_to_join_cache(tab, &tab->table->tmp_set, - &data_field_count, ©, - &data_field_ptr_count, - ©_ptr); - } - use_emb_key= check_emb_key_usage(); + create_key_arg_fields(); - create_remaining_fields(FALSE); + create_remaining_fields(); set_constants(); if (alloc_buffer()) DBUG_RETURN(1); - - reset(TRUE); + + reset(TRUE); DBUG_RETURN(0); -} +} /* Check the possibility to read the access keys directly from the join buffer - SYNOPSIS check_emb_key_usage() @@ -693,13 +988,21 @@ int JOIN_CACHE_BKA::init() we still do not consider them embedded. In the future we'll expand the the class of keys which we identify as embedded. - RETURN - TRUE - key values will be considered as embedded, - FALSE - otherwise. + NOTES + The function returns FALSE if no key is used to join the records + from join_tab. + + RETURN VALUE + TRUE key values will be considered as embedded, + FALSE otherwise. */ -bool JOIN_CACHE_BKA::check_emb_key_usage() +bool JOIN_CACHE::check_emb_key_usage() { + + if (!is_key_access()) + return FALSE; + uint i; Item *item; KEY_PART_INFO *key_part; @@ -800,110 +1103,6 @@ bool JOIN_CACHE_BKA::check_emb_key_usage() /* - Calculate the increment of the MRR buffer for a record write - - SYNOPSIS - aux_buffer_incr() - - DESCRIPTION - This implementation of the virtual function aux_buffer_incr determines - for how much the size of the MRR buffer should be increased when another - record is added to the cache. - - RETURN - the increment of the size of the MRR buffer for the next record -*/ - -uint JOIN_CACHE_BKA::aux_buffer_incr() -{ - uint incr= 0; - TABLE_REF *ref= &join_tab->ref; - TABLE *tab= join_tab->table; - uint rec_per_key= tab->key_info[ref->key].rec_per_key[ref->key_parts-1]; - set_if_bigger(rec_per_key, 1); - if (records == 1) - incr= ref->key_length + tab->file->ref_length; - incr+= tab->file->stats.mrr_length_per_rec * rec_per_key; - return incr; -} - - -/* - Check if the record combination matches the index condition - - SYNOPSIS - JOIN_CACHE_BKA::skip_index_tuple() - rseq Value returned by bka_range_seq_init() - range_info MRR range association data - - DESCRIPTION - This function is invoked from MRR implementation to check if an index - tuple matches the index condition. It is used in the case where the index - condition actually depends on both columns of the used index and columns - from previous tables. - - Accessing columns of the previous tables requires special handling with - BKA. The idea of BKA is to collect record combinations in a buffer and - then do a batch of ref access lookups, i.e. by the time we're doing a - lookup its previous-records-combination is not in prev_table->record[0] - but somewhere in the join buffer. - - We need to get it from there back into prev_table(s)->record[0] before we - can evaluate the index condition, and that's why we need this function - instead of regular IndexConditionPushdown. - - NOTE - Possible optimization: - Before we unpack the record from a previous table - check if this table is used in the condition. - If so then unpack the record otherwise skip the unpacking. - This should be done by a special virtual method - get_partial_record_by_pos(). - - RETURN - 0 The record combination satisfies the index condition - 1 Otherwise -*/ - -bool JOIN_CACHE_BKA::skip_index_tuple(range_seq_t rseq, char *range_info) -{ - DBUG_ENTER("JOIN_CACHE_BKA::skip_index_tuple"); - JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; - cache->get_record_by_pos((uchar*)range_info); - DBUG_RETURN(!join_tab->cache_idx_cond->val_int()); -} - - -/* - Check if the record combination matches the index condition - - SYNOPSIS - bka_skip_index_tuple() - rseq Value returned by bka_range_seq_init() - range_info MRR range association data - - DESCRIPTION - This is wrapper for JOIN_CACHE_BKA::skip_index_tuple method, - see comments there. - - NOTE - This function is used as a RANGE_SEQ_IF::skip_index_tuple callback. - - RETURN - 0 The record combination satisfies the index condition - 1 Otherwise -*/ - -static -bool bka_skip_index_tuple(range_seq_t rseq, char *range_info) -{ - DBUG_ENTER("bka_skip_index_tuple"); - JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; - DBUG_RETURN(cache->skip_index_tuple(rseq, range_info)); -} - - -/* Write record fields and their required offsets into the join cache buffer SYNOPSIS @@ -942,9 +1141,8 @@ bool bka_skip_index_tuple(range_seq_t rseq, char *range_info) The 'last_rec_blob_data_is_in_rec_buff' is set on if the blob data remains in the record buffers and not copied to the join buffer. It may happen only to the blob data from the last record added into the cache. - - - RETURN + + RETURN VALUE length of the written record data */ @@ -963,7 +1161,7 @@ uint JOIN_CACHE::write_record_data(uchar * link, bool *is_full) len= pack_length; /* Make an adjustment for the size of the auxiliary buffer if there is any */ - uint incr= aux_buffer_incr(); + uint incr= aux_buffer_incr(records); ulong rem= rem_space(); aux_buff_size+= len+incr < rem ? incr : rem; @@ -1158,7 +1356,7 @@ uint JOIN_CACHE::write_record_data(uchar * link, bool *is_full) - the size of the auxiliary buffer is reset to 0, - the flag 'last_rec_blob_data_is_in_rec_buff' is set to 0. - RETURN + RETURN VALUE none */ @@ -1176,6 +1374,7 @@ void JOIN_CACHE::reset(bool for_writing) } } + /* Add a record into the join buffer: the default implementation @@ -1190,7 +1389,7 @@ void JOIN_CACHE::reset(bool for_writing) The implementation assumes that the function get_curr_link() will return exactly the pointer to this matched record. - RETURN + RETURN VALUE TRUE if it has been decided that it should be the last record in the join buffer, FALSE otherwise @@ -1227,9 +1426,9 @@ bool JOIN_CACHE::put_record() point to the beginning of the first field of the record in the join buffer. - RETURN - TRUE - there are no more records to read from the join buffer - FALSE - otherwise + RETURN VALUE + TRUE there are no more records to read from the join buffer + FALSE otherwise */ bool JOIN_CACHE::get_record() @@ -1268,7 +1467,7 @@ bool JOIN_CACHE::get_record() from the the join buffers of the previous caches. The fields are read into the corresponding record buffers. - RETURN + RETURN VALUE none */ @@ -1299,7 +1498,7 @@ void JOIN_CACHE::get_record_by_pos(uchar *rec_ptr) rec_ptr. If the match flag in placed one of the previous buffers the function first reaches the linked record fields in this buffer. - RETURN + RETURN VALUE TRUE if the match flag is set on FALSE otherwise */ @@ -1319,6 +1518,28 @@ bool JOIN_CACHE::get_match_flag_by_pos(uchar *rec_ptr) /* + Calculate the increment of the auxiliary buffer for a record write + + SYNOPSIS + aux_buffer_incr() + recno the number of the record the increment to be calculated for + + DESCRIPTION + This function calls the aux_buffer_incr the method of the + companion member join_tab_scan to calculate the growth of the + auxiliary buffer when the recno-th record is added to the + join_buffer of this cache. + + RETURN VALUE + the number of bytes in the increment +*/ + +uint JOIN_CACHE::aux_buffer_incr(ulong recno) +{ + return join_tab_scan->aux_buffer_incr(recno); +} + +/* Read all flag and data fields of a record from the join buffer SYNOPSIS @@ -1332,8 +1553,8 @@ bool JOIN_CACHE::get_match_flag_by_pos(uchar *rec_ptr) The function increments the value of 'pos' by the length of the read data. - RETURN - (-1) - if there is no more records in the join buffer + RETURN VALUE + (-1) if there is no more records in the join buffer length of the data read from the join buffer - otherwise */ @@ -1371,7 +1592,7 @@ uint JOIN_CACHE::read_all_record_fields() The function increments the value of 'pos' by the length of the read data. - RETURN + RETURN VALUE length of the data read from the join buffer */ @@ -1406,7 +1627,7 @@ uint JOIN_CACHE::read_flag_fields() The function increments the value of 'pos' by the length of the read data. - RETURN + RETURN VALUE length of the data read from the join buffer */ @@ -1486,7 +1707,7 @@ uint JOIN_CACHE::read_record_field(CACHE_FIELD *copy, bool blob_in_rec_buff) values. Otherwise *len is supposed to provide this value that has been obtained earlier. - RETURN + RETURN VALUE TRUE 'copy' points to a data descriptor of this join cache FALSE otherwise */ @@ -1533,7 +1754,7 @@ bool JOIN_CACHE::read_referenced_field(CACHE_FIELD *copy, Skip record from join buffer if its match flag is on: default implementation SYNOPSIS - skip_record_if_match() + skip_recurrent_match() DESCRIPTION This default implementation of the virtual function skip_record_if_match @@ -1541,12 +1762,12 @@ bool JOIN_CACHE::read_referenced_field(CACHE_FIELD *copy, If the record is skipped the value of 'pos' is set to points to the position right after the record. - RETURN - TRUE - the match flag is on and the record has been skipped - FALSE - the match flag is off + RETURN VALUE + TRUE the match flag is on and the record has been skipped + FALSE the match flag is off */ -bool JOIN_CACHE::skip_record_if_match() +bool JOIN_CACHE::skip_recurrent_match() { DBUG_ASSERT(with_length); uint offset= size_of_rec_len; @@ -1617,7 +1838,7 @@ void JOIN_CACHE::restore_last_record() that have matches, after which null complementing extension for all unmatched records from the join buffer are generated. - RETURN + RETURN VALUE return one of enum_nested_loop_state, except NESTED_LOOP_NO_MORE_ROWS. */ @@ -1711,16 +1932,16 @@ finish: } -/* - Using BNL find matches from the next table for records from the join buffer +/* + Find matches from the next table for records from the join buffer SYNOPSIS join_matching_records() skip_last do not look for matches for the last partial join record DESCRIPTION - The function retrieves all rows of the join_tab table and check whether - they match partial join records from the join buffer. If a match is found + The function retrieves rows of the join_tab table and checks whether they + match partial join records from the join buffer. If a match is found the function will call the sub_select function trying to look for matches for the remaining join operations. This function currently is called only from the function join_records. @@ -1729,25 +1950,44 @@ finish: the future processing in the caller function. NOTES + If employed by BNL or BNLH join algorithms the function performs a full + scan of join_tab for each refill of the join buffer. If BKA or BKAH + algorithms are used then the function iterates only over those records + from join_tab that can be accessed by keys built over records in the join + buffer. To apply a proper method of iteration the function just calls + virtual iterator methods (open, next, close) of the member join_tab_scan. + The member can be either of the JOIN_TAB_SCAN or JOIN_TAB_SCAN_MMR type. + The class JOIN_TAB_SCAN provides the iterator methods for BNL/BNLH join + algorithms. The class JOIN_TAB_SCAN_MRR provides the iterator methods + for BKA/BKAH join algorithms. + When the function looks for records from the join buffer that would + match a record from join_tab it iterates either over all records in + the buffer or only over selected records. If BNL join operation is + performed all records are checked for the match. If BNLH or BKAH + algorithm is employed to join join_tab then the function looks only + through the records with the same join key as the record from join_tab. + With the BKA join algorithm only one record from the join buffer is checked + for a match for any record from join_tab. To iterate over the candidates + for a match the virtual function get_next_candidate_for_match is used, + while the virtual function prepare_look_for_matches is called to prepare + for such iteration proccess. + + NOTES The function produces all matching extensions for the records in the - join buffer following the path of the Blocked Nested Loops algorithm. + join buffer following the path of the employed blocked algorithm. When an outer join operation is performed all unmatched records from the join buffer must be extended by null values. The function 'join_null_complements' serves this purpose. - RETURN - return one of enum_nested_loop_state. + RETURN VALUE + return one of enum_nested_loop_state */ -enum_nested_loop_state JOIN_CACHE_BNL::join_matching_records(bool skip_last) +enum_nested_loop_state JOIN_CACHE::join_matching_records(bool skip_last) { - uint cnt; int error; - JOIN_TAB *tab; - READ_RECORD *info; enum_nested_loop_state rc= NESTED_LOOP_OK; bool check_only_first_match= join_tab->check_only_first_match(); - SQL_SELECT *select= join_tab->cache_select; join_tab->table->null_row= 0; @@ -1771,25 +2011,12 @@ enum_nested_loop_state JOIN_CACHE_BNL::join_matching_records(bool skip_last) join_tab->select->quick= 0; } - for (tab= join->join_tab; tab != join_tab ; tab++) - { - tab->status= tab->table->status; - tab->table->status= 0; - } - - /* Start retrieving all records of the joined table */ - if ((error= join_init_read_record(join_tab))) - { - rc= error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR; + /* Prepare to retrieve all records of the joined table */ + if ((error= join_tab_scan->open())) goto finish; - } - info= &join_tab->read_record; - do + while (!(error= join_tab_scan->next())) { - if (join_tab->keep_current_rowid) - join_tab->table->file->position(join_tab->table->record[0]); - if (join->thd->killed) { /* The user has aborted the execution of the query */ @@ -1797,56 +2024,41 @@ enum_nested_loop_state JOIN_CACHE_BNL::join_matching_records(bool skip_last) rc= NESTED_LOOP_KILLED; goto finish; } - int err= 0; - if (rc == NESTED_LOOP_OK) - update_virtual_fields(join_tab->table); - - /* - Do not look for matches if the last read record of the joined table - does not meet the conditions that have been pushed to this table - */ - if (rc == NESTED_LOOP_OK && - (!select || (err= select->skip_record(join->thd)) != 0)) - { - if (err < 0) - return NESTED_LOOP_ERROR; - rc= NESTED_LOOP_OK; - //psergey3-merge: todo: check if all other places in this file - // should have the - // skip_record(...) <0 --> return error - // code. - - /* Prepare to read records from the join buffer */ - reset(FALSE); - - /* Read each record from the join buffer and look for matches */ - for (cnt= records - test(skip_last) ; cnt; cnt--) - { - /* - If only the first match is needed and it has been already found for - the next record read from the join buffer then the record is skipped. - */ - if (!check_only_first_match || !skip_record_if_match()) - { - get_record(); - rc= generate_full_extensions(get_curr_rec()); - if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS) - goto finish; - } + if (join_tab->keep_current_rowid) + join_tab->table->file->position(join_tab->table->record[0]); + + /* Prepare to read matching candidates from the join buffer */ + if (prepare_look_for_matches(skip_last)) + continue; + + uchar *rec_ptr; + /* Read each possible candidate from the buffer and look for matches */ + while ((rec_ptr= get_next_candidate_for_match())) + { + /* + If only the first match is needed, and, it has been already found for + the next record read from the join buffer, then the record is skipped. + */ + if (!(check_only_first_match && + skip_recurrent_candidate_for_match(rec_ptr))) + { + read_next_candidate_for_match(rec_ptr); + rc= generate_full_extensions(rec_ptr); + if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS) + goto finish; } } - } while (!(error= info->read_record(info))); + } - if (error > 0) // Fatal error - rc= NESTED_LOOP_ERROR; -finish: - for (tab= join->join_tab; tab != join_tab ; tab++) - tab->table->status= tab->status; +finish: + if (error) + rc= error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR; + join_tab_scan->close(); return rc; } - + /* Set match flag for a record in join buffer if it has not been set yet @@ -1981,7 +2193,7 @@ enum_nested_loop_state JOIN_CACHE::generate_full_extensions(uchar *rec_ptr) inline bool JOIN_CACHE::check_match(uchar *rec_ptr) { /* Check whether pushdown conditions are satisfied */ - if (join_tab->select && join_tab->select->skip_record(join->thd) < 1) + if (join_tab->select && join_tab->select->skip_record(join->thd) <= 0) return FALSE; if (!join_tab->is_last_inner_table()) @@ -2011,7 +2223,7 @@ inline bool JOIN_CACHE::check_match(uchar *rec_ptr) */ for (JOIN_TAB *tab= first_inner; tab <= join_tab; tab++) { - if (tab->select && tab->select->skip_record(join->thd) < 1) + if (tab->select && tab->select->skip_record(join->thd) <= 0) return FALSE; } } @@ -2042,7 +2254,7 @@ inline bool JOIN_CACHE::check_match(uchar *rec_ptr) NOTES The same implementation of the virtual method join_null_complements - is used for JOIN_CACHE_BNL and JOIN_CACHE_BKA. + is used for BNL/BNLH/BKA/BKA join algorthm. RETURN return one of enum_nested_loop_state. @@ -2074,7 +2286,7 @@ enum_nested_loop_state JOIN_CACHE::join_null_complements(bool skip_last) goto finish; } /* Just skip the whole record if a match for it has been already found */ - if (!is_first_inner || !skip_record_if_match()) + if (!is_first_inner || !skip_recurrent_match()) { get_record(); /* The outer row is complemented by nulls for each inner table */ @@ -2082,7 +2294,7 @@ enum_nested_loop_state JOIN_CACHE::join_null_complements(bool skip_last) mark_as_null_row(join_tab->table); /* Check all pushdown conditions attached to the inner table */ join_tab->first_unmatched->found= 1; - if (join_tab->select && join_tab->select->skip_record(join->thd) < 1) + if (join_tab->select && join_tab->select->skip_record(join->thd) <= 0) continue; if (is_last_inner) { @@ -2092,7 +2304,7 @@ enum_nested_loop_state JOIN_CACHE::join_null_complements(bool skip_last) set_match_flag_if_none(first_upper, get_curr_rec()); for (JOIN_TAB* tab= first_upper; tab <= join_tab; tab++) { - if (tab->select && tab->select->skip_record(join->thd) < 1) + if (tab->select && tab->select->skip_record(join->thd) <= 0) goto next; } first_upper= first_upper->first_upper; @@ -2114,477 +2326,87 @@ finish: return rc; } - -/* - Initialize retrieval of range sequence for BKA algorithm - - SYNOPSIS - bka_range_seq_init() - init_params pointer to the BKA join cache object - n_ranges the number of ranges obtained - flags combination of HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY - - DESCRIPTION - The function interprets init_param as a pointer to a JOIN_CACHE_BKA - object. The function prepares for an iteration over the join keys - built for all records from the cache join buffer. - - NOTE - This function are used only as a callback function. - - RETURN - init_param value that is to be used as a parameter of bka_range_seq_next() -*/ - -static -range_seq_t bka_range_seq_init(void *init_param, uint n_ranges, uint flags) -{ - DBUG_ENTER("bka_range_seq_init"); - JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) init_param; - cache->reset(0); - DBUG_RETURN((range_seq_t) init_param); -} - - -/* - Get the key over the next record from the join buffer used by BKA - - SYNOPSIS - bka_range_seq_next() - seq the value returned by bka_range_seq_init - range OUT reference to the next range - - DESCRIPTION - The function interprets seq as a pointer to a JOIN_CACHE_BKA - object. The function returns a pointer to the range descriptor - for the key built over the next record from the join buffer. - - NOTE - This function are used only as a callback function. - - RETURN - 0 ok, the range structure filled with info about the next key - 1 no more ranges -*/ - -static -uint bka_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) -{ - DBUG_ENTER("bka_range_seq_next"); - JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; - TABLE_REF *ref= &cache->join_tab->ref; - key_range *start_key= &range->start_key; - if ((start_key->length= cache->get_next_key((uchar **) &start_key->key))) - { - start_key->keypart_map= (1 << ref->key_parts) - 1; - start_key->flag= HA_READ_KEY_EXACT; - range->end_key= *start_key; - range->end_key.flag= HA_READ_AFTER_KEY; - range->ptr= (char *) cache->get_curr_rec(); - range->range_flag= EQ_RANGE; - DBUG_RETURN(0); - } - DBUG_RETURN(1); -} - - -/* - Check whether range_info orders to skip the next record from BKA buffer - - SYNOPSIS - bka_range_seq_skip_record() - seq value returned by bka_range_seq_init() - range_info information about the next range - rowid [NOT USED] rowid of the record to be checked - - - DESCRIPTION - The function interprets seq as a pointer to a JOIN_CACHE_BKA object. - The function interprets seq as a pointer to the JOIN_CACHE_BKA_UNIQUE - object. The function returns TRUE if the record with this range_info - is to be filtered out from the stream of records returned by - multi_range_read_next(). - - NOTE - This function are used only as a callback function. - - RETURN - 1 record with this range_info is to be filtered out from the stream - of records returned by multi_range_read_next() - 0 the record is to be left in the stream -*/ - -static -bool bka_range_seq_skip_record(range_seq_t rseq, char *range_info, uchar *rowid) -{ - DBUG_ENTER("bka_range_seq_skip_record"); - JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; - bool res= cache->get_match_flag_by_pos((uchar *) range_info); - DBUG_RETURN(res); -} - -/* - Using BKA find matches from the next table for records from the join buffer +/* + Initialize a hashed join cache SYNOPSIS - join_matching_records() - skip_last do not look for matches for the last partial join record + init() DESCRIPTION - This function can be used only when the table join_tab can be accessed - by keys built over the fields of previous join tables. - The function retrieves all partial join records from the join buffer and - for each of them builds the key value to access join_tab, performs index - look-up with this key and selects matching records yielded by this look-up - If a match is found the function will call the sub_select function trying - to look for matches for the remaining join operations. - This function currently is called only from the function join_records. - It's assumed that this function is always called with the skip_last - parameter equal to false. - - NOTES - The function produces all matching extensions for the records in the - join buffer following the path of the Batched Key Access algorithm. - When an outer join operation is performed all unmatched records from - the join buffer must be extended by null values. The function - join_null_complements serves this purpose. - The Batched Key Access algorithm assumes that key accesses are batched. - In other words it assumes that, first, either keys themselves or the - corresponding rowids (primary keys) are accumulated in a buffer, then - data rows from join_tab are fetched for all of them. When a row is - fetched it is always returned with a reference to the key by which it - has been accessed. - When key values are batched we can save on the number of the server - requests for index lookups. For the remote engines, like NDB cluster, it - essentially reduces the number of round trips between the server and - the engine when performing a join operation. - When the rowids for the keys are batched we can optimize the order - in what we fetch the data for this rowids. The performance benefits of - this optimization can be significant for such engines as MyISAM, InnoDB. - What is exactly batched are hidden behind implementations of - MRR handler interface that is supposed to be appropriately chosen - for each engine. If for a engine no specific implementation of the MRR - interface is supllied then the default implementation is used. This - implementation actually follows the path of Nested Loops Join algorithm. - In this case BKA join surely will demonstrate a worse performance than - NL join. - - RETURN - return one of enum_nested_loop_state -*/ - -enum_nested_loop_state JOIN_CACHE_BKA::join_matching_records(bool skip_last) -{ - int error; - handler *file= join_tab->table->file; - enum_nested_loop_state rc= NESTED_LOOP_OK; - uchar *rec_ptr= 0; - bool check_only_first_match= join_tab->check_only_first_match(); - - /* Set functions to iterate over keys in the join buffer */ - - RANGE_SEQ_IF seq_funcs= { bka_range_seq_init, - bka_range_seq_next, - check_only_first_match ? - bka_range_seq_skip_record : 0, - join_tab->cache_idx_cond ? - bka_skip_index_tuple : 0 }; - - /* The value of skip_last must be always FALSE when this function is called */ - DBUG_ASSERT(!skip_last); - - /* Return at once if there are no records in the join buffer */ - if (!records) - return NESTED_LOOP_OK; - - rc= init_join_matching_records(&seq_funcs, records); - if (rc != NESTED_LOOP_OK) - goto finish; - - while (!(error= file->multi_range_read_next((char **) &rec_ptr))) - { - if (join->thd->killed) - { - /* The user has aborted the execution of the query */ - join->thd->send_kill_message(); - rc= NESTED_LOOP_KILLED; - goto finish; - } - if (join_tab->keep_current_rowid) - join_tab->table->file->position(join_tab->table->record[0]); - /* - If only the first match is needed and it has been already found - for the associated partial join record then the returned candidate - is discarded. - */ - if (rc == NESTED_LOOP_OK && - (!check_only_first_match || !get_match_flag_by_pos(rec_ptr))) - { - get_record_by_pos(rec_ptr); - update_virtual_fields(join_tab->table); - rc= generate_full_extensions(rec_ptr); - if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS) - goto finish; - } - } - - if (error > 0 && error != HA_ERR_END_OF_FILE) - return NESTED_LOOP_ERROR; -finish: - return end_join_matching_records(rc); -} - - - -/* - Prepare to search for records that match records from the join buffer - - SYNOPSIS - init_join_matching_records() - seq_funcs structure of range sequence interface - ranges number of keys/ranges in the sequence - - DESCRIPTION - This function calls the multi_range_read_init function to set up - the BKA process of generating the keys from the records in the join - buffer and looking for matching records from the table to be joined. - The function passes as a parameter a structure of functions that - implement the range sequence interface. This interface is used to - enumerate all generated keys and optionally to filter the matching - records returned by the multi_range_read_next calls from the - intended invocation of the join_matching_records method. The - multi_range_read_init function also receives the parameters for - MRR buffer to be used and flags specifying the mode in which - this buffer will be functioning. - The number of keys in the sequence expected by multi_range_read_init - is passed through the parameter ranges. - - RETURN - return one of enum_nested_loop_state -*/ - -enum_nested_loop_state -JOIN_CACHE_BKA::init_join_matching_records(RANGE_SEQ_IF *seq_funcs, uint ranges) -{ - int error; - handler *file= join_tab->table->file; - enum_nested_loop_state rc= NESTED_LOOP_OK; - - join_tab->table->null_row= 0; - - - /* Dynamic range access is never used with BKA */ - DBUG_ASSERT(join_tab->use_quick != 2); - - for (JOIN_TAB *tab =join->join_tab; tab != join_tab ; tab++) - { - tab->status= tab->table->status; - tab->table->status= 0; - } - - init_mrr_buff(); + The function initializes the cache structure with a hash table in it. + The hash table will be used to store key values for the records from + the join buffer. + The function allocates memory for the join buffer and for descriptors of + the record fields stored in the buffer. + The function also initializes a hash table for record keys within the join + buffer space. - /* - Prepare to iterate over keys from the join buffer and to get - matching candidates obtained with MMR handler functions. - */ - if (!file->inited) - file->ha_index_init(join_tab->ref.key, 1); - if ((error= file->multi_range_read_init(seq_funcs, (void*) this, ranges, - mrr_mode, &mrr_buff))) - rc= error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR; + NOTES VALUE + The function is supposed to be called by the init methods of the classes + derived from JOIN_CACHE_HASHED. - return rc; -} - - -/* - Finish searching for records that match records from the join buffer - - SYNOPSIS - end_join_matching_records() - rc return code passed by the join_matching_records function - - DESCRIPTION - This function perform final actions on searching for all matches for - the records from the join buffer and building all full join extensions - of the records with these matches. - RETURN - return code rc passed to the function as a parameter + 0 initialization with buffer allocations has been succeeded + 1 otherwise */ -enum_nested_loop_state -JOIN_CACHE_BKA::end_join_matching_records(enum_nested_loop_state rc) +int JOIN_CACHE_HASHED::init() { - for (JOIN_TAB *tab=join->join_tab; tab != join_tab ; tab++) - tab->table->status= tab->status; - return rc; -} - - -/* - Get the key built over the next record from BKA join buffer + int rc= 0; + TABLE_REF *ref= &join_tab->ref; - SYNOPSIS - get_next_key() - key pointer to the buffer where the key value is to be placed + DBUG_ENTER("JOIN_CACHE_HASHED::init"); - DESCRIPTION - The function reads key fields from the current record in the join buffer. - and builds the key value out of these fields that will be used to access - the 'join_tab' table. Some of key fields may belong to previous caches. - They are accessed via record references to the record parts stored in the - previous join buffers. The other key fields always are placed right after - the flag fields of the record. - If the key is embedded, which means that its value can be read directly - from the join buffer, then *key is set to the beginning of the key in - this buffer. Otherwise the key is built in the join_tab->ref->key_buff. - The function returns the length of the key if it succeeds ro read it. - If is assumed that the functions starts reading at the position of - the record length which is provided for each records in a BKA cache. - After the key is built the 'pos' value points to the first position after - the current record. - The function returns 0 if the initial position is after the beginning - of the record fields for last record from the join buffer. + hash_table= 0; + key_entries= 0; - RETURN - length of the key value - if the starting value of 'pos' points to - the position before the fields for the last record, - 0 - otherwise. -*/ + key_length= ref->key_length; -uint JOIN_CACHE_BKA::get_next_key(uchar ** key) -{ - uint len; - uint32 rec_len; - uchar *init_pos; - JOIN_CACHE *cache; - - if (pos > last_rec_pos || !records) - return 0; + if ((rc= JOIN_CACHE::init())) + DBUG_RETURN (rc); - /* Any record in a BKA cache is prepended with its length */ - DBUG_ASSERT(with_length); - - /* Read the length of the record */ - rec_len= get_rec_length(pos); - pos+= size_of_rec_len; - init_pos= pos; + /* Take into account a reference to the next record in the key chain */ + pack_length+= get_size_of_rec_offset(); + pack_length_with_blob_ptrs+= get_size_of_rec_offset(); - /* Read a reference to the previous cache if any */ - if (prev_cache) - pos+= prev_cache->get_size_of_rec_offset(); + init_hash_table(); - curr_rec_pos= pos; + rec_fields_offset= get_size_of_rec_offset()+get_size_of_rec_length()+ + (prev_cache ? prev_cache->get_size_of_rec_offset() : 0); - /* Read all flag fields of the record */ - read_flag_fields(); - + data_fields_offset= 0; if (use_emb_key) { - /* An embedded key is taken directly from the join buffer */ - *key= pos; - len= emb_key_length; - } - else - { - /* Read key arguments from previous caches if there are any such fields */ - if (external_key_arg_fields) - { - uchar *rec_ptr= curr_rec_pos; - uint key_arg_count= external_key_arg_fields; - CACHE_FIELD **copy_ptr= blob_ptr-key_arg_count; - for (cache= prev_cache; key_arg_count; cache= cache->prev_cache) - { - uint len= 0; - DBUG_ASSERT(cache); - rec_ptr= cache->get_rec_ref(rec_ptr); - while (!cache->referenced_fields) - { - cache= cache->prev_cache; - DBUG_ASSERT(cache); - rec_ptr= cache->get_rec_ref(rec_ptr); - } - while (key_arg_count && - cache->read_referenced_field(*copy_ptr, rec_ptr, &len)) - { - copy_ptr++; - --key_arg_count; - } - } - } - - /* - Read the other key arguments from the current record. The fields for - these arguments are always first in the sequence of the record's fields. - */ - CACHE_FIELD *copy= field_descr+flag_fields; - CACHE_FIELD *copy_end= copy+local_key_arg_fields; - bool blob_in_rec_buff= blob_data_is_in_rec_buff(curr_rec_pos); + CACHE_FIELD *copy= field_descr; + CACHE_FIELD *copy_end= copy+flag_fields; for ( ; copy < copy_end; copy++) - read_record_field(copy, blob_in_rec_buff); - - /* Build the key over the fields read into the record buffers */ - TABLE_REF *ref= &join_tab->ref; - cp_buffer_from_ref(join->thd, join_tab->table, ref); - *key= ref->key_buff; - len= ref->key_length; - } - - pos= init_pos+rec_len; + data_fields_offset+= copy->length; + } - return len; -} + DBUG_RETURN(rc); +} /* - Initialize a BKA_UNIQUE cache + Initialize the hash table of a hashed join cache SYNOPSIS - init() + init_hash_table() DESCRIPTION - The function initializes the cache structure. It supposed to be called - right after a constructor for the JOIN_CACHE_BKA_UNIQUE. - The function allocates memory for the join buffer and for descriptors of - the record fields stored in the buffer. - The function also estimates the number of hash table entries in the hash - table to be used and initializes this hash table. + The function estimates the number of hash table entries in the hash + table to be used and initializes this hash table within the join buffer + space. - NOTES - The code of this function should have been included into the constructor - code itself. However the new operator for the class JOIN_CACHE_BKA_UNIQUE - would never fail while memory allocation for the join buffer is not - absolutely unlikely to fail. That's why this memory allocation has to be - placed in a separate function that is called in a couple with a cache - constructor. - It is quite natural to put almost all other constructor actions into - this function. - - RETURN - 0 initialization with buffer allocations has been succeeded - 1 otherwise + RETURN VALUE + Currently the function always returns 0; */ -int JOIN_CACHE_BKA_UNIQUE::init() +int JOIN_CACHE_HASHED::init_hash_table() { - int rc= 0; - TABLE_REF *ref= &join_tab->ref; - - DBUG_ENTER("JOIN_CACHE_BKA_UNIQUE::init"); - hash_table= 0; key_entries= 0; - if ((rc= JOIN_CACHE_BKA::init())) - DBUG_RETURN (rc); - - key_length= ref->key_length; - - /* Take into account a reference to the next record in the key chain */ - pack_length+= get_size_of_rec_offset(); - /* Calculate the minimal possible value of size_of_key_ofs greater than 1 */ uint max_size_of_key_ofs= max(2, get_size_of_rec_offset()); for (size_of_key_ofs= 2; @@ -2595,7 +2417,10 @@ int JOIN_CACHE_BKA_UNIQUE::init() size_of_key_ofs + // reference to the next key (use_emb_key ? get_size_of_rec_offset() : key_length); - uint n= buff_size / (pack_length+key_entry_length+size_of_key_ofs); + ulong space_per_rec= avg_record_length + + avg_aux_buffer_incr + + key_entry_length+size_of_key_ofs; + uint n= buff_size / space_per_rec; /* TODO: Make a better estimate for this upper bound of @@ -2605,6 +2430,7 @@ int JOIN_CACHE_BKA_UNIQUE::init() key_entry_length+size_of_key_ofs); hash_entries= (uint) (n / 0.7); + set_if_bigger(hash_entries, 1); if (offset_size(max_n*key_entry_length) <= size_of_key_ofs) @@ -2616,27 +2442,69 @@ int JOIN_CACHE_BKA_UNIQUE::init() cleanup_hash_table(); curr_key_entry= hash_table; - pack_length+= key_entry_length; - pack_length_with_blob_ptrs+= get_size_of_rec_offset() + key_entry_length; + return 0; +} - rec_fields_offset= get_size_of_rec_offset()+get_size_of_rec_length()+ - (prev_cache ? prev_cache->get_size_of_rec_offset() : 0); - data_fields_offset= 0; - if (use_emb_key) - { - CACHE_FIELD *copy= field_descr; - CACHE_FIELD *copy_end= copy+flag_fields; - for ( ; copy < copy_end; copy++) - data_fields_offset+= copy->length; - } +/* + Reallocate the join buffer of a hashed join cache + + SYNOPSIS + realloc_buffer() - DBUG_RETURN(rc); + DESCRITION + The function reallocates the join buffer of the hashed join cache. + After this it initializes a hash table within the buffer space and + resets the join cache for writing. + + NOTES + The function assumes that buff_size contains the new value for the join + buffer size. + + RETURN VALUE + 0 if the buffer has been successfully reallocated + 1 otherwise +*/ + +int JOIN_CACHE_HASHED::realloc_buffer() +{ + int rc; + free(); + rc= test(!(buff= (uchar*) my_malloc(buff_size, MYF(0)))); + init_hash_table(); + reset(TRUE); + return rc; } +/* + Get maximum size of the additional space per record used for record keys + + SYNOPSYS + get_max_key_addon_space_per_record() + + DESCRIPTION + The function returns the size of the space occupied by one key entry + and one hash table entry. + + RETURN VALUE + maximum size of the additional space per record that is used to store + record keys in the hash table +*/ + +uint JOIN_CACHE_HASHED::get_max_key_addon_space_per_record() +{ + ulong len; + TABLE_REF *ref= &join_tab->ref; + len= (use_emb_key ? get_size_of_rec_offset() : ref->key_length) + + size_of_rec_ofs + // size of the key chain header + size_of_rec_ofs + // >= size of the reference to the next key + size_of_rec_ofs; // >= size of hash table entry + return len; +} + /* - Reset the JOIN_CACHE_BKA_UNIQUE buffer for reading/writing + Reset the buffer of a hashed join cache for reading/writing SYNOPSIS reset() @@ -2644,7 +2512,7 @@ int JOIN_CACHE_BKA_UNIQUE::init() DESCRIPTION This implementation of the virtual function reset() resets the join buffer - of the JOIN_CACHE_BKA_UNIQUE class for reading or writing. + of the JOIN_CACHE_HASHED class for reading or writing. Additionally to what the default implementation does this function cleans up the hash table allocated within the buffer. @@ -2652,7 +2520,7 @@ int JOIN_CACHE_BKA_UNIQUE::init() none */ -void JOIN_CACHE_BKA_UNIQUE::reset(bool for_writing) +void JOIN_CACHE_HASHED::reset(bool for_writing) { this->JOIN_CACHE::reset(for_writing); if (for_writing && hash_table) @@ -2660,15 +2528,16 @@ void JOIN_CACHE_BKA_UNIQUE::reset(bool for_writing) curr_key_entry= hash_table; } + /* - Add a record into the JOIN_CACHE_BKA_UNIQUE buffer + Add a record into the buffer of a hashed join cache SYNOPSIS put_record() DESCRIPTION This implementation of the virtual function put_record writes the next - matching record into the join buffer of the JOIN_CACHE_BKA_UNIQUE class. + matching record into the join buffer of the JOIN_CACHE_HASHED class. Additionally to what the default implementation does this function performs the following. It extracts from the record the key value used in lookups for matching @@ -2686,7 +2555,7 @@ void JOIN_CACHE_BKA_UNIQUE::reset(bool for_writing) FALSE otherwise */ -bool JOIN_CACHE_BKA_UNIQUE::put_record() +bool JOIN_CACHE_HASHED::put_record() { bool is_full; uchar *key; @@ -2763,7 +2632,7 @@ bool JOIN_CACHE_BKA_UNIQUE::put_record() /* - Read the next record from the JOIN_CACHE_BKA_UNIQUE buffer + Read the next record from the buffer of a hashed join cache SYNOPSIS get_record() @@ -2774,11 +2643,11 @@ bool JOIN_CACHE_BKA_UNIQUE::put_record() used to connect the records with the same key into a chain. RETURN - TRUE - there are no more records to read from the join buffer - FALSE - otherwise + TRUE there are no more records to read from the join buffer + FALSE otherwise */ -bool JOIN_CACHE_BKA_UNIQUE::get_record() +bool JOIN_CACHE_HASHED::get_record() { pos+= get_size_of_rec_offset(); return this->JOIN_CACHE::get_record(); @@ -2786,26 +2655,26 @@ bool JOIN_CACHE_BKA_UNIQUE::get_record() /* - Skip record from the JOIN_CACHE_BKA_UNIQUE join buffer if its match flag is on + Skip record from a hashed join buffer if its match flag is on SYNOPSIS - skip_record_if_match() + skip_recurrent_match() DESCRIPTION - This implementation of the virtual function skip_record_if_match does + This implementation of the virtual function skip_recurrent_match does the same as the default implementation does, but it takes into account the link element used to connect the records with the same key into a chain. RETURN - TRUE - the match flag is on and the record has been skipped - FALSE - the match flag is off + TRUE the match flag is on and the record has been skipped + FALSE the match flag is off */ -bool JOIN_CACHE_BKA_UNIQUE::skip_record_if_match() +bool JOIN_CACHE_HASHED::skip_recurrent_match() { uchar *save_pos= pos; pos+= get_size_of_rec_offset(); - if (!this->JOIN_CACHE::skip_record_if_match()) + if (!this->JOIN_CACHE::skip_recurrent_match()) { pos= save_pos; return FALSE; @@ -2834,13 +2703,13 @@ bool JOIN_CACHE_BKA_UNIQUE::skip_record_if_match() Otherwise the function returns the position where the reference to the newly created hash element for the given key is to be added. - RETURN - TRUE - the key is found in the hash table - FALSE - otherwise + RETURN VALUE + TRUE the key is found in the hash table + FALSE otherwise */ -bool JOIN_CACHE_BKA_UNIQUE::key_search(uchar *key, uint key_len, - uchar **key_ref_ptr) +bool JOIN_CACHE_HASHED::key_search(uchar *key, uint key_len, + uchar **key_ref_ptr) { bool is_found= FALSE; uint idx= get_hash_idx(key, key_length); @@ -2875,11 +2744,11 @@ bool JOIN_CACHE_BKA_UNIQUE::key_search(uchar *key, uint key_len, The function calculates an index of the hash entry in the hash table of the join buffer for the given key - RETURN + RETURN VALUE the calculated index of the hash entry for the given key. */ -uint JOIN_CACHE_BKA_UNIQUE::get_hash_idx(uchar* key, uint key_len) +uint JOIN_CACHE_HASHED::get_hash_idx(uchar* key, uint key_len) { ulong nr= 1; ulong nr2= 4; @@ -2906,11 +2775,11 @@ uint JOIN_CACHE_BKA_UNIQUE::get_hash_idx(uchar* key, uint key_len) The function cleans up the hash table in the join buffer removing all hash elements from the table. - RETURN + RETURN VALUE none */ -void JOIN_CACHE_BKA_UNIQUE:: cleanup_hash_table() +void JOIN_CACHE_HASHED:: cleanup_hash_table() { last_key_entry= hash_table; bzero(hash_table, (buff+buff_size)-hash_table); @@ -2919,64 +2788,671 @@ void JOIN_CACHE_BKA_UNIQUE:: cleanup_hash_table() /* - Initialize retrieval of range sequence for BKA_UNIQUE algorithm + Check whether all records in a key chain have their match flags set on + + SYNOPSIS + check_all_match_flags_for_key() + key_chain_ptr + + DESCRIPTION + This function retrieves records in the given circular chain and checks + whether their match flags are set on. The parameter key_chain_ptr shall + point to the position in the join buffer storing the reference to the + last element of this chain. + + RETURN + TRUE if each retrieved record has its match flag set on + FALSE otherwise +*/ + +bool JOIN_CACHE_HASHED::check_all_match_flags_for_key(uchar *key_chain_ptr) +{ + uchar *last_rec_ref_ptr= get_next_rec_ref(key_chain_ptr); + uchar *next_rec_ref_ptr= last_rec_ref_ptr; + do + { + next_rec_ref_ptr= get_next_rec_ref(next_rec_ref_ptr); + uchar *rec_ptr= next_rec_ref_ptr+rec_fields_offset; + if (!get_match_flag_by_pos(rec_ptr)) + return FALSE; + } + while (next_rec_ref_ptr != last_rec_ref_ptr); + return TRUE; +} + + +/* + Get the next key built for the records from the buffer of a hashed join cache + + SYNOPSIS + get_next_key() + key pointer to the buffer where the key value is to be placed + + DESCRIPTION + The function reads the next key value stored in the hash table of the + join buffer. Depending on the value of the use_emb_key flag of the + join cache the value is read either from the table itself or from + the record field where it occurs. + + RETURN VALUE + length of the key value - if the starting value of 'cur_key_entry' refers + to the position after that referred by the the value of 'last_key_entry', + 0 - otherwise. +*/ + +uint JOIN_CACHE_HASHED::get_next_key(uchar ** key) +{ + if (curr_key_entry == last_key_entry) + return 0; + + curr_key_entry-= key_entry_length; + + *key = use_emb_key ? get_emb_key(curr_key_entry) : curr_key_entry; + + DBUG_ASSERT(*key >= buff && *key < hash_table); + + return key_length; +} + + +/* + Initiate an iteration process over records in the joined table + + SYNOPSIS + open() + + DESCRIPTION + The function initiates the process of iteration over records from the + joined table recurrently performed by the BNL/BKLH join algorithm. + + RETURN VALUE + 0 the initiation is a success + error code otherwise +*/ + +int JOIN_TAB_SCAN::open() +{ + for (JOIN_TAB *tab= join->join_tab; tab != join_tab ; tab++) + { + tab->status= tab->table->status; + tab->table->status= 0; + } + is_first_record= TRUE; + return join_init_read_record(join_tab); +} + + +/* + Read the next record that can match while scanning the joined table + + SYNOPSIS + next() + + DESCRIPTION + The function reads the next record from the joined table that can + match some records in the buffer of the join cache 'cache'. To do + this the function calls the function that scans table records and + looks for the next one that meets the condition pushed to the + joined table join_tab. + + NOTES + The function catches the signal that kills the query. + + RETURN VALUE + 0 the next record exists and has been successfully read + error code otherwise +*/ + +int JOIN_TAB_SCAN::next() +{ + int err= 0; + int skip_rc; + READ_RECORD *info= &join_tab->read_record; + SQL_SELECT *select= join_tab->cache_select; + if (is_first_record) + is_first_record= FALSE; + else + err= info->read_record(info); + if (!err) + update_virtual_fields(join_tab->table); + while (!err && select && (skip_rc= select->skip_record(join->thd)) <= 0) + { + if (join->thd->killed || skip_rc < 0) + return 1; + /* + Move to the next record if the last retrieved record does not + meet the condition pushed to the table join_tab. + */ + err= info->read_record(info); + if (!err) + update_virtual_fields(join_tab->table); + } + return err; +} + + +/* + Perform finalizing actions for a scan over the table records + + SYNOPSIS + close() + + DESCRIPTION + The function performs the necessary restoring actions after + the table scan over the joined table has been finished. + + RETURN VALUE + none +*/ + +void JOIN_TAB_SCAN::close() +{ + for (JOIN_TAB *tab= join->join_tab; tab != join_tab ; tab++) + tab->table->status= tab->status; +} + + +/* + Prepare to iterate over the BNL join cache buffer to look for matches + + SYNOPSIS + prepare_look_for_matches() + skip_last <-> ignore the last record in the buffer + + DESCRIPTION + The function prepares the join cache for an iteration over the + records in the join buffer. The iteration is performed when looking + for matches for the record from the joined table join_tab that + has been placed into the record buffer of the joined table. + If the value of the parameter skip_last is TRUE then the last + record from the join buffer is ignored. + The function initializes the counter of the records that have been + not iterated over yet. + + RETURN VALUE + TRUE there are no records in the buffer to iterate over + FALSE otherwise +*/ + +bool JOIN_CACHE_BNL::prepare_look_for_matches(bool skip_last) +{ + if (!records) + return TRUE; + reset(FALSE); + rem_records= records-test(skip_last); + return rem_records == 0; +} + + +/* + Get next record from the BNL join cache buffer when looking for matches + + SYNOPSIS + get_next_candidate_for_match + + DESCRIPTION + This method is used for iterations over the records from the join + cache buffer when looking for matches for records from join_tab. + The methods performs the necessary preparations to read the next record + from the join buffer into the record buffer by the method + read_next_candidate_for_match, or, to skip the next record from the join + buffer by the method skip_recurrent_candidate_for_match. + This implementation of the virtual method get_next_candidate_for_match + just decrements the counter of the records that are to be iterated over + and returns the current value of the cursor 'pos' as the position of + the record to be processed. + + RETURN + pointer to the position right after the prefix of the current record + in the join buffer if the there is another record to iterate over, + 0 - otherwise. +*/ + +uchar *JOIN_CACHE_BNL::get_next_candidate_for_match() +{ + if (!rem_records) + return 0; + rem_records--; + return pos+base_prefix_length; +} + + +/* + Check whether the matching record from the BNL cache is to be skipped + + SYNOPSIS + skip_recurrent_candidate_for_match + rec_ptr pointer to the position in the join buffer right after the prefix + of the current record + + DESCRIPTION + This implementation of the virtual function just calls the + method skip_recurrent_match to check whether the record referenced by + ref_ptr has its match flag set on and, if so, just skips this record + setting the value of the cursor 'pos' to the position right after it. + + RETURN + TRUE the record referenced by rec_ptr has been skipped + FALSE otherwise +*/ + +bool JOIN_CACHE_BNL::skip_recurrent_candidate_for_match(uchar *rec_ptr) +{ + pos= rec_ptr-base_prefix_length; + return skip_recurrent_match(); +} + + +/* + Read next record from the BNL join cache buffer when looking for matches + + SYNOPSIS + read_next_candidate_for_match + rec_ptr pointer to the position in the join buffer right after the prefix + the current record. + + DESCRIPTION + This implementation of the virtual method read_next_candidate_for_match + calls the method get_record to read the record referenced by rec_ptr from + the join buffer into the record buffer. If this record refers to the + fields in the other join buffers the call of get_record ensures that + these fields are read into the corresponding record buffers as well. + This function is supposed to be called after a successful call of + the method get_next_candidate_for_match. + + RETURN VALUE + none +*/ + +void JOIN_CACHE_BNL::read_next_candidate_for_match(uchar *rec_ptr) +{ + pos= rec_ptr-base_prefix_length; + get_record(); +} + + +/* + Initialize the BNL join cache + + SYNOPSIS + init + + DESCRIPTION + The function initializes the cache structure. It is supposed to be called + right after a constructor for the JOIN_CACHE_BNL. + + NOTES + The function first constructs a companion object of the type JOIN_TAB_SCAN, + then it calls the init method of the parent class. + + RETURN VALUE + 0 initialization with buffer allocations has been succeeded + 1 otherwise +*/ + +int JOIN_CACHE_BNL::init() +{ + DBUG_ENTER("JOIN_CACHE_BNL::init"); + + if (!(join_tab_scan= new JOIN_TAB_SCAN(join, join_tab))) + DBUG_RETURN(1); + + DBUG_RETURN(JOIN_CACHE::init()); +} + + +/* + Get the chain of records from buffer matching the current candidate for join + + SYNOPSIS + get_matching_chain_by_join_key() + + DESCRIPTION + This function first build a join key for the record of join_tab that + currently is in the join buffer for this table. Then it looks for + the key entry with this key in the hash table of the join cache. + If such a key entry is found the function returns the pointer to + the head of the chain of records in the join_buffer that match this + key. + + RETURN VALUE + The pointer to the corresponding circular list of records if + the key entry with the join key is found, 0 - otherwise. +*/ + +uchar *JOIN_CACHE_BNLH::get_matching_chain_by_join_key() +{ + uchar *key_ref_ptr; + TABLE *table= join_tab->table; + TABLE_REF *ref= &join_tab->ref; + KEY *keyinfo= table->key_info+ref->key; + /* Build the join key value out of the record in the record buffer */ + key_copy(ref->key_buff, table->record[0], keyinfo, ref->key_length); + /* Look for this key in the join buffer */ + if (!key_search(ref->key_buff, ref->key_length, &key_ref_ptr)) + return 0; + return key_ref_ptr+get_size_of_key_offset(); +} + + +/* + Prepare to iterate over the BNLH join cache buffer to look for matches + + SYNOPSIS + prepare_look_for_matches() + skip_last <-> ignore the last record in the buffer + + DESCRIPTION + The function prepares the join cache for an iteration over the + records in the join buffer. The iteration is performed when looking + for matches for the record from the joined table join_tab that + has been placed into the record buffer of the joined table. + If the value of the parameter skip_last is TRUE then the last + record from the join buffer is ignored. + The function builds the hashed key from the join fields of join_tab + and uses this key to look in the hash table of the join cache for + the chain of matching records in in the join buffer. If it finds + such a chain it sets the member last_rec_ref_ptr to point to the + last link of the chain while setting the member next_rec_ref_po 0. + + RETURN VALUE + TRUE there are no matching records in the buffer to iterate over + FALSE otherwise +*/ + +bool JOIN_CACHE_BNLH::prepare_look_for_matches(bool skip_last) +{ + uchar *curr_matching_chain; + last_matching_rec_ref_ptr= next_matching_rec_ref_ptr= 0; + if (!(curr_matching_chain= get_matching_chain_by_join_key())) + return 1; + last_matching_rec_ref_ptr= get_next_rec_ref(curr_matching_chain); + return 0; +} + + +/* + Get next record from the BNLH join cache buffer when looking for matches + + SYNOPSIS + get_next_candidate_for_match + + DESCRIPTION + This method is used for iterations over the records from the join + cache buffer when looking for matches for records from join_tab. + The methods performs the necessary preparations to read the next record + from the join buffer into the record buffer by the method + read_next_candidate_for_match, or, to skip the next record from the join + buffer by the method skip_recurrent_candidate_for_match. + This implementation of the virtual method moves to the next record + in the chain of all records from the join buffer that are to be + equi-joined with the current record from join_tab. + + RETURN VALUE + pointer to the beginning of the record fields in the join buffer + if the there is another record to iterate over, 0 - otherwise. +*/ + +uchar *JOIN_CACHE_BNLH::get_next_candidate_for_match() +{ + if (next_matching_rec_ref_ptr == last_matching_rec_ref_ptr) + return 0; + next_matching_rec_ref_ptr= get_next_rec_ref(next_matching_rec_ref_ptr ? + next_matching_rec_ref_ptr : + last_matching_rec_ref_ptr); + return next_matching_rec_ref_ptr+rec_fields_offset; +} + + +/* + Check whether the matching record from the BNLH cache is to be skipped + + SYNOPSIS + skip_recurrent_candidate_for_match + rec_ptr pointer to the position in the join buffer right after + the previous record + + DESCRIPTION + This implementation of the virtual function just calls the + method get_match_flag_by_pos to check whether the record referenced + by ref_ptr has its match flag set on. + + RETURN + TRUE the record referenced by rec_ptr has its match flag set on + FALSE otherwise +*/ + +bool JOIN_CACHE_BNLH::skip_recurrent_candidate_for_match(uchar *rec_ptr) +{ + return get_match_flag_by_pos(rec_ptr); +} + + +/* + Read next record from the BNLH join cache buffer when looking for matches + + SYNOPSIS + read_next_candidate_for_match + rec_ptr pointer to the position in the join buffer right after + the previous record + + DESCRIPTION + This implementation of the virtual method read_next_candidate_for_match + calls the method get_record_by_pos to read the record referenced by rec_ptr + from the join buffer into the record buffer. If this record refers to + fields in the other join buffers the call of get_record_by_po ensures that + these fields are read into the corresponding record buffers as well. + This function is supposed to be called after a successful call of + the method get_next_candidate_for_match. + + RETURN VALUE + none +*/ + +void JOIN_CACHE_BNLH::read_next_candidate_for_match(uchar *rec_ptr) +{ + get_record_by_pos(rec_ptr); +} + + +/* + Initialize the BNLH join cache + + SYNOPSIS + init + + DESCRIPTION + The function initializes the cache structure. It is supposed to be called + right after a constructor for the JOIN_CACHE_BNLH. + + NOTES + The function first constructs a companion object of the type JOIN_TAB_SCAN, + then it calls the init method of the parent class. + + RETURN VALUE + 0 initialization with buffer allocations has been succeeded + 1 otherwise +*/ + +int JOIN_CACHE_BNLH::init() +{ + DBUG_ENTER("JOIN_CACHE_BNLH::init"); + + if (!(join_tab_scan= new JOIN_TAB_SCAN(join, join_tab))) + DBUG_RETURN(1); + + DBUG_RETURN(JOIN_CACHE_HASHED::init()); +} + + +/* + Calculate the increment of the MRR buffer for a record write + + SYNOPSIS + aux_buffer_incr() + + DESCRIPTION + This implementation of the virtual function aux_buffer_incr determines + for how much the size of the MRR buffer should be increased when another + record is added to the cache. + + RETURN VALUE + the increment of the size of the MRR buffer for the next record +*/ + +uint JOIN_TAB_SCAN_MRR::aux_buffer_incr(ulong recno) +{ + uint incr= 0; + TABLE_REF *ref= &join_tab->ref; + TABLE *tab= join_tab->table; + uint rec_per_key= tab->key_info[ref->key].rec_per_key[ref->key_parts-1]; + set_if_bigger(rec_per_key, 1); + if (recno == 1) + incr= ref->key_length + tab->file->ref_length; + incr+= tab->file->stats.mrr_length_per_rec * rec_per_key; + return incr; +} + + +/* + Initiate iteration over records returned by MRR for the current join buffer + + SYNOPSIS + open() + + DESCRIPTION + The function initiates the process of iteration over the records from + join_tab returned by the MRR interface functions for records from + the join buffer. Such an iteration is performed by the BKA/BKAH join + algorithm for each new refill of the join buffer. + The function calls the MRR handler function multi_range_read_init to + initiate this process. + + RETURN VALUE + 0 the initiation is a success + error code otherwise +*/ + +int JOIN_TAB_SCAN_MRR::open() +{ + handler *file= join_tab->table->file; + + join_tab->table->null_row= 0; + + + /* Dynamic range access is never used with BKA */ + DBUG_ASSERT(join_tab->use_quick != 2); + + for (JOIN_TAB *tab =join->join_tab; tab != join_tab ; tab++) + { + tab->status= tab->table->status; + tab->table->status= 0; + } + + init_mrr_buff(); + + /* + Prepare to iterate over keys from the join buffer and to get + matching candidates obtained with MMR handler functions. + */ + if (!file->inited) + file->ha_index_init(join_tab->ref.key, 1); + ranges= cache->get_number_of_ranges_for_mrr(); + if (!join_tab->cache_idx_cond) + range_seq_funcs.skip_index_tuple= 0; + return file->multi_range_read_init(&range_seq_funcs, (void*) cache, + ranges, mrr_mode, &mrr_buff); +} + + +/* + Read the next record returned by MRR for the current join buffer + + SYNOPSIS + next() + + DESCRIPTION + The function reads the next record from the joined table join_tab + returned by the MRR handler function multi_range_read_next for + the current refill of the join buffer. The record is read into + the record buffer used for join_tab records in join operations. + + RETURN VALUE + 0 the next record exists and has been successfully read + error code otherwise +*/ + +int JOIN_TAB_SCAN_MRR::next() +{ + char **ptr= (char **) cache->get_curr_association_ptr(); + uint rc= join_tab->table->file->multi_range_read_next(ptr) ? -1 : 0; + if (!rc) + { + DBUG_ASSERT(cache->buff <= (uchar *) (*ptr) && + (uchar *) (*ptr) < cache->end_pos); + update_virtual_fields(join_tab->table); + } + return rc; +} + + +/* + Initialize retrieval of range sequence for BKA join algorithm SYNOPSIS bka_range_seq_init() - init_params pointer to the BKA_INIQUE join cache object - n_ranges the number of ranges obtained - flags combination of HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY + init_params pointer to the BKA join cache object + n_ranges the number of ranges obtained + flags combination of MRR flags DESCRIPTION - The function interprets init_param as a pointer to a JOIN_CACHE_BKA_UNIQUE - object. The function prepares for an iteration over the unique join keys - built over the records from the cache join buffer. + The function interprets init_param as a pointer to a JOIN_CACHE_BKA + object. The function prepares for an iteration over the join keys + built for all records from the cache join buffer. NOTE This function are used only as a callback function. - RETURN - init_param value that is to be used as a parameter of - bka_unique_range_seq_next() + RETURN VALUE + init_param value that is to be used as a parameter of bka_range_seq_next() */ static -range_seq_t bka_unique_range_seq_init(void *init_param, uint n_ranges, - uint flags) +range_seq_t bka_range_seq_init(void *init_param, uint n_ranges, uint flags) { - DBUG_ENTER("bka_unique_range_seq_init"); - JOIN_CACHE_BKA_UNIQUE *cache= (JOIN_CACHE_BKA_UNIQUE *) init_param; + DBUG_ENTER("bka_range_seq_init"); + JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) init_param; cache->reset(0); DBUG_RETURN((range_seq_t) init_param); } /* - Get the key over the next record from the join buffer used by BKA_UNIQUE + Get the next range/key over records from the join buffer used by a BKA cache SYNOPSIS - bka_unique_range_seq_next() - seq value returned by bka_unique_range_seq_init() + bka_range_seq_next() + seq the value returned by bka_range_seq_init range OUT reference to the next range DESCRIPTION - The function interprets seq as a pointer to the JOIN_CACHE_BKA_UNIQUE + The function interprets seq as a pointer to a JOIN_CACHE_BKA object. The function returns a pointer to the range descriptor - for the next unique key built over records from the join buffer. + for the key built over the next record from the join buffer. NOTE This function are used only as a callback function. - RETURN - 0 ok, the range structure filled with info about the next key - 1 no more ranges + RETURN VALUE + 0 ok, the range structure filled with info about the next range/key + 1 no more ranges */ static -uint bka_unique_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) +uint bka_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) { - DBUG_ENTER("bka_unique_range_seq_next"); - JOIN_CACHE_BKA_UNIQUE *cache= (JOIN_CACHE_BKA_UNIQUE *) rseq; + DBUG_ENTER("bka_range_seq_next"); + JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; TABLE_REF *ref= &cache->join_tab->ref; key_range *start_key= &range->start_key; if ((start_key->length= cache->get_next_key((uchar **) &start_key->key))) @@ -2985,7 +3461,7 @@ uint bka_unique_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) start_key->flag= HA_READ_KEY_EXACT; range->end_key= *start_key; range->end_key.flag= HA_READ_AFTER_KEY; - range->ptr= (char *) cache->get_curr_key_chain(); + range->ptr= (char *) cache->get_curr_rec(); range->range_flag= EQ_RANGE; DBUG_RETURN(0); } @@ -2994,305 +3470,638 @@ uint bka_unique_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) /* - Check whether range_info orders to skip the next record from BKA_UNIQUE buffer + Check whether range_info orders to skip the next record from BKA buffer SYNOPSIS - bka_unique_range_seq_skip_record() - seq value returned by bka_unique_range_seq_init() + bka_range_seq_skip_record() + seq value returned by bka_range_seq_init() range_info information about the next range - rowid [NOT USED] rowid of the record to be checked (not used) + rowid [NOT USED] rowid of the record to be checked + DESCRIPTION - The function interprets seq as a pointer to the JOIN_CACHE_BKA_UNIQUE - object. The function returns TRUE if the record with this range_info - is to be filtered out from the stream of records returned by + The function interprets seq as a pointer to a JOIN_CACHE_BKA object. + The function returns TRUE if the record with this range_info + is to be filtered out from the stream of records returned by multi_range_read_next(). NOTE This function are used only as a callback function. - RETURN + RETURN VALUE 1 record with this range_info is to be filtered out from the stream of records returned by multi_range_read_next() 0 the record is to be left in the stream */ static -bool bka_unique_range_seq_skip_record(range_seq_t rseq, char *range_info, - uchar *rowid) +bool bka_range_seq_skip_record(range_seq_t rseq, char *range_info, uchar *rowid) { - DBUG_ENTER("bka_unique_range_seq_skip_record"); - JOIN_CACHE_BKA_UNIQUE *cache= (JOIN_CACHE_BKA_UNIQUE *) rseq; - bool res= cache->check_all_match_flags_for_key((uchar *) range_info); + DBUG_ENTER("bka_range_seq_skip_record"); + JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; + bool res= cache->get_match_flag_by_pos((uchar *) range_info); DBUG_RETURN(res); } - + /* - Check if the record combination matches the index condition + Check if the record combination from BKA cache matches the index condition SYNOPSIS - JOIN_CACHE_BKA_UNIQUE::skip_index_tuple() - rseq Value returned by bka_range_seq_init() - range_info MRR range association data + bka_skip_index_tuple() + rseq value returned by bka_range_seq_init() + range_info record chain for the next range/key returned by MRR DESCRIPTION - See JOIN_CACHE_BKA::skip_index_tuple(). - This function is the variant for use with - JOIN_CACHE_BKA_UNIQUE. The difference from JOIN_CACHE_BKA case is that - there may be multiple previous table record combinations that share the - same key, i.e. they map to the same MRR range. - As a consequence, we need to loop through all previous table record - combinations that match the given MRR range key range_info until we find - one that satisfies the index condition. + This is wrapper for JOIN_CACHE_BKA::skip_index_tuple method, + see comments there. NOTE - Possible optimization: - Before we unpack the record from a previous table - check if this table is used in the condition. - If so then unpack the record otherwise skip the unpacking. - This should be done by a special virtual method - get_partial_record_by_pos(). - - RETURN + This function is used as a RANGE_SEQ_IF::skip_index_tuple callback. + + RETURN VALUE 0 The record combination satisfies the index condition 1 Otherwise +*/ +static +bool bka_skip_index_tuple(range_seq_t rseq, char *range_info) +{ + DBUG_ENTER("bka_skip_index_tuple"); + JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) rseq; + DBUG_RETURN(cache->skip_index_tuple(range_info)); +} -*/ -bool JOIN_CACHE_BKA_UNIQUE::skip_index_tuple(range_seq_t rseq, char *range_info) +/* + Prepare to read the record from BKA cache matching the current joined record + + SYNOPSIS + prepare_look_for_matches() + skip_last <-> ignore the last record in the buffer (always unused here) + + DESCRIPTION + The function prepares to iterate over records in the join cache buffer + matching the record loaded into the record buffer for join_tab when + performing join operation by BKA join algorithm. With BKA algorithms the + record loaded into the record buffer for join_tab always has a direct + reference to the matching records from the join buffer. When the regular + BKA join algorithm is employed the record from join_tab can refer to + only one such record. + The function sets the counter of the remaining records from the cache + buffer that would match the current join_tab record to 1. + + RETURN VALUE + TRUE there are no records in the buffer to iterate over + FALSE otherwise +*/ + +bool JOIN_CACHE_BKA::prepare_look_for_matches(bool skip_last) { - DBUG_ENTER("JOIN_CACHE_BKA_UNIQUE::skip_index_tuple"); - JOIN_CACHE_BKA_UNIQUE *cache= (JOIN_CACHE_BKA_UNIQUE *) rseq; - uchar *last_rec_ref_ptr= cache->get_next_rec_ref((uchar*) range_info); - uchar *next_rec_ref_ptr= last_rec_ref_ptr; - do - { - next_rec_ref_ptr= cache->get_next_rec_ref(next_rec_ref_ptr); - uchar *rec_ptr= next_rec_ref_ptr + cache->rec_fields_offset; - cache->get_record_by_pos(rec_ptr); - if (join_tab->cache_idx_cond->val_int()) - DBUG_RETURN(FALSE); - } while(next_rec_ref_ptr != last_rec_ref_ptr); - DBUG_RETURN(TRUE); + if (!records) + return TRUE; + rem_records= 1; + return FALSE; } /* - Check if the record combination matches the index condition + Get the record from the BKA cache matching the current joined record SYNOPSIS - bka_unique_skip_index_tuple() - rseq Value returned by bka_range_seq_init() - range_info MRR range association data + get_next_candidate_for_match + + DESCRIPTION + This method is used for iterations over the records from the join + cache buffer when looking for matches for records from join_tab. + The method performs the necessary preparations to read the next record + from the join buffer into the record buffer by the method + read_next_candidate_for_match, or, to skip the next record from the join + buffer by the method skip_recurrent_match. + This implementation of the virtual method get_next_candidate_for_match + just decrements the counter of the records that are to be iterated over + and returns the value of curr_association as a reference to the position + of the beginning of the record fields in the buffer. + RETURN VALUE + pointer to the start of the record fields in the join buffer + if the there is another record to iterate over, 0 - otherwise. +*/ + +uchar *JOIN_CACHE_BKA::get_next_candidate_for_match() +{ + if (!rem_records) + return 0; + rem_records--; + return curr_association; +} + + +/* + Check whether the matching record from the BKA cache is to be skipped + + SYNOPSIS + skip_recurrent_candidate_for_match + rec_ptr pointer to the position in the join buffer right after + the previous record + DESCRIPTION - This is wrapper for JOIN_CACHE_BKA_UNIQUE::skip_index_tuple method, - see comments there. + This implementation of the virtual function just calls the + method get_match_flag_by_pos to check whether the record referenced + by ref_ptr has its match flag set on. - NOTE - This function is used as a RANGE_SEQ_IF::skip_index_tuple callback. - - RETURN - 0 The record combination satisfies the index condition - 1 Otherwise + RETURN VALUE + TRUE the record referenced by rec_ptr has its match flag set on + FALSE otherwise */ -static -bool bka_unique_skip_index_tuple(range_seq_t rseq, char *range_info) +bool JOIN_CACHE_BKA::skip_recurrent_candidate_for_match(uchar *rec_ptr) { - DBUG_ENTER("bka_unique_skip_index_tuple"); - JOIN_CACHE_BKA_UNIQUE *cache= (JOIN_CACHE_BKA_UNIQUE *) rseq; - DBUG_RETURN(cache->skip_index_tuple(rseq, range_info)); + return get_match_flag_by_pos(rec_ptr); } /* - Using BKA_UNIQUE find matches from the next table for records from join buffer + Read the next record from the BKA join cache buffer when looking for matches SYNOPSIS - join_matching_records() - skip_last do not look for matches for the last partial join record + read_next_candidate_for_match + rec_ptr pointer to the position in the join buffer right after + the previous record DESCRIPTION - This function can be used only when the table join_tab can be accessed - by keys built over the fields of previous join tables. - The function retrieves all keys from the hash table of the join buffer - built for partial join records from the buffer. For each of these keys - the function performs an index lookup and tries to match records yielded - by this lookup with records from the join buffer attached to the key. - If a match is found the function will call the sub_select function trying - to look for matches for the remaining join operations. - This function does not assume that matching records are necessarily - returned with references to the keys by which they were found. If the call - of the function multi_range_read_init returns flags with - HA_MRR_NO_ASSOCIATION then a search for the key built from the returned - record is carried on. The search is performed by probing in in the hash - table of the join buffer. - This function currently is called only from the function join_records. - It's assumed that this function is always called with the skip_last - parameter equal to false. - - RETURN - return one of enum_nested_loop_state + This implementation of the virtual method read_next_candidate_for_match + calls the method get_record_by_pos to read the record referenced by rec_ptr + from the join buffer into the record buffer. If this record refers to + fields in the other join buffers the call of get_record_by_po ensures that + these fields are read into the corresponding record buffers as well. + This function is supposed to be called after a successful call of + the method get_next_candidate_for_match. + + RETURN VALUE + none */ -enum_nested_loop_state -JOIN_CACHE_BKA_UNIQUE::join_matching_records(bool skip_last) +void JOIN_CACHE_BKA::read_next_candidate_for_match(uchar *rec_ptr) +{ + get_record_by_pos(rec_ptr); +} + + +/* + Initialize the BKA join cache + + SYNOPSIS + init + + DESCRIPTION + The function initializes the cache structure. It is supposed to be called + right after a constructor for the JOIN_CACHE_BKA. + + NOTES + The function first constructs a companion object of the type + JOIN_TAB_SCAN_MRR, then it calls the init method of the parent class. + + RETURN VALUE + 0 initialization with buffer allocations has been succeeded + 1 otherwise +*/ + +int JOIN_CACHE_BKA::init() { - int error; - uchar *key_chain_ptr; - handler *file= join_tab->table->file; - enum_nested_loop_state rc= NESTED_LOOP_OK; bool check_only_first_match= join_tab->check_only_first_match(); - bool no_association= test(mrr_mode & HA_MRR_NO_ASSOCIATION); - /* Set functions to iterate over keys in the join buffer */ - RANGE_SEQ_IF seq_funcs= { bka_unique_range_seq_init, - bka_unique_range_seq_next, - check_only_first_match && !no_association ? - bka_unique_range_seq_skip_record : 0, - join_tab->cache_idx_cond ? - bka_unique_skip_index_tuple : 0 }; + RANGE_SEQ_IF rs_funcs= { bka_range_seq_init, + bka_range_seq_next, + check_only_first_match ? + bka_range_seq_skip_record : 0, + bka_skip_index_tuple }; - /* The value of skip_last must be always FALSE when this function is called */ - DBUG_ASSERT(!skip_last); + DBUG_ENTER("JOIN_CACHE_BKA::init"); - /* Return at once if there are no records in the join buffer */ - if (!records) - return NESTED_LOOP_OK; - - rc= init_join_matching_records(&seq_funcs, key_entries); - if (rc != NESTED_LOOP_OK) - goto finish; + if (!(join_tab_scan= new JOIN_TAB_SCAN_MRR(join, join_tab, + mrr_mode, rs_funcs))) + DBUG_RETURN(1); - while (!(error= file->multi_range_read_next((char **) &key_chain_ptr))) - { - if (no_association) - { - uchar *key_ref_ptr; - TABLE *table= join_tab->table; - TABLE_REF *ref= &join_tab->ref; - KEY *keyinfo= table->key_info+ref->key; - /* - Build the key value out of the record returned by the call of - multi_range_read_next in the record buffer - */ - key_copy(ref->key_buff, table->record[0], keyinfo, ref->key_length); - /* Look for this key in the join buffer */ - if (!key_search(ref->key_buff, ref->key_length, &key_ref_ptr)) - continue; - key_chain_ptr= key_ref_ptr+get_size_of_key_offset(); - } + DBUG_RETURN(JOIN_CACHE::init()); +} - uchar *last_rec_ref_ptr= get_next_rec_ref(key_chain_ptr); - uchar *next_rec_ref_ptr= last_rec_ref_ptr; - do - { - next_rec_ref_ptr= get_next_rec_ref(next_rec_ref_ptr); - uchar *rec_ptr= next_rec_ref_ptr+rec_fields_offset; - if (join->thd->killed) - { - /* The user has aborted the execution of the query */ - join->thd->send_kill_message(); - rc= NESTED_LOOP_KILLED; - goto finish; - } - /* - If only the first match is needed and it has been already found - for the associated partial join record then the returned candidate - is discarded. - */ - if (rc == NESTED_LOOP_OK && - (!check_only_first_match || !get_match_flag_by_pos(rec_ptr))) - { - get_record_by_pos(rec_ptr); - update_virtual_fields(join_tab->table); - rc= generate_full_extensions(rec_ptr); - if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS) - goto finish; +/* + Get the key built over the next record from BKA join buffer + + SYNOPSIS + get_next_key() + key pointer to the buffer where the key value is to be placed + + DESCRIPTION + The function reads key fields from the current record in the join buffer. + and builds the key value out of these fields that will be used to access + the 'join_tab' table. Some of key fields may belong to previous caches. + They are accessed via record references to the record parts stored in the + previous join buffers. The other key fields always are placed right after + the flag fields of the record. + If the key is embedded, which means that its value can be read directly + from the join buffer, then *key is set to the beginning of the key in + this buffer. Otherwise the key is built in the join_tab->ref->key_buff. + The function returns the length of the key if it succeeds ro read it. + If is assumed that the functions starts reading at the position of + the record length which is provided for each records in a BKA cache. + After the key is built the 'pos' value points to the first position after + the current record. + The function returns 0 if the initial position is after the beginning + of the record fields for last record from the join buffer. + + RETURN VALUE + length of the key value - if the starting value of 'pos' points to + the position before the fields for the last record, + 0 - otherwise. +*/ + +uint JOIN_CACHE_BKA::get_next_key(uchar ** key) +{ + uint len; + uint32 rec_len; + uchar *init_pos; + JOIN_CACHE *cache; + + if (pos > last_rec_pos || !records) + return 0; + + /* Any record in a BKA cache is prepended with its length */ + DBUG_ASSERT(with_length); + + /* Read the length of the record */ + rec_len= get_rec_length(pos); + pos+= size_of_rec_len; + init_pos= pos; + + /* Read a reference to the previous cache if any */ + if (prev_cache) + pos+= prev_cache->get_size_of_rec_offset(); + + curr_rec_pos= pos; + + /* Read all flag fields of the record */ + read_flag_fields(); + + if (use_emb_key) + { + /* An embedded key is taken directly from the join buffer */ + *key= pos; + len= emb_key_length; + } + else + { + /* Read key arguments from previous caches if there are any such fields */ + if (external_key_arg_fields) + { + uchar *rec_ptr= curr_rec_pos; + uint key_arg_count= external_key_arg_fields; + CACHE_FIELD **copy_ptr= blob_ptr-key_arg_count; + for (cache= prev_cache; key_arg_count; cache= cache->prev_cache) + { + uint len= 0; + DBUG_ASSERT(cache); + rec_ptr= cache->get_rec_ref(rec_ptr); + while (!cache->referenced_fields) + { + cache= cache->prev_cache; + DBUG_ASSERT(cache); + rec_ptr= cache->get_rec_ref(rec_ptr); + } + while (key_arg_count && + cache->read_referenced_field(*copy_ptr, rec_ptr, &len)) + { + copy_ptr++; + --key_arg_count; + } } } - while (next_rec_ref_ptr != last_rec_ref_ptr); + + /* + Read the other key arguments from the current record. The fields for + these arguments are always first in the sequence of the record's fields. + */ + CACHE_FIELD *copy= field_descr+flag_fields; + CACHE_FIELD *copy_end= copy+local_key_arg_fields; + bool blob_in_rec_buff= blob_data_is_in_rec_buff(curr_rec_pos); + for ( ; copy < copy_end; copy++) + read_record_field(copy, blob_in_rec_buff); + + /* Build the key over the fields read into the record buffers */ + TABLE_REF *ref= &join_tab->ref; + cp_buffer_from_ref(join->thd, join_tab->table, ref); + *key= ref->key_buff; + len= ref->key_length; } - if (error > 0 && error != HA_ERR_END_OF_FILE) - return NESTED_LOOP_ERROR; -finish: - return end_join_matching_records(rc); + pos= init_pos+rec_len; + + return len; +} + + +/* + Check the index condition of the joined table for a record from the BKA cache + + SYNOPSIS + skip_index_tuple() + range_info pointer to the record returned by MRR + + DESCRIPTION + This function is invoked from MRR implementation to check if an index + tuple matches the index condition. It is used in the case where the index + condition actually depends on both columns of the used index and columns + from previous tables. + + NOTES + Accessing columns of the previous tables requires special handling with + BKA. The idea of BKA is to collect record combinations in a buffer and + then do a batch of ref access lookups, i.e. by the time we're doing a + lookup its previous-records-combination is not in prev_table->record[0] + but somewhere in the join buffer. + We need to get it from there back into prev_table(s)->record[0] before we + can evaluate the index condition, and that's why we need this function + instead of regular IndexConditionPushdown. + + NOTES + Possible optimization: + Before we unpack the record from a previous table + check if this table is used in the condition. + If so then unpack the record otherwise skip the unpacking. + This should be done by a special virtual method + get_partial_record_by_pos(). + + RETURN VALUE + 1 the record combination does not satisfies the index condition + 0 otherwise +*/ + +bool JOIN_CACHE_BKA::skip_index_tuple(char *range_info) +{ + DBUG_ENTER("JOIN_CACHE_BKA::skip_index_tuple"); + get_record_by_pos((uchar*)range_info); + DBUG_RETURN(!join_tab->cache_idx_cond->val_int()); } + /* - Check whether all records in a key chain have their match flags set on + Initialize retrieval of range sequence for the BKAH join algorithm + + SYNOPSIS + bkah_range_seq_init() + init_params pointer to the BKAH join cache object + n_ranges the number of ranges obtained + flags combination of MRR flags + + DESCRIPTION + The function interprets init_param as a pointer to a JOIN_CACHE_BKAH + object. The function prepares for an iteration over distinct join keys + built over the records from the cache join buffer. + + NOTE + This function are used only as a callback function. + + RETURN VALUE + init_param value that is to be used as a parameter of + bkah_range_seq_next() +*/ + +static +range_seq_t bkah_range_seq_init(void *init_param, uint n_ranges, uint flags) +{ + DBUG_ENTER("bkah_range_seq_init"); + JOIN_CACHE_BKAH *cache= (JOIN_CACHE_BKAH *) init_param; + cache->reset(0); + DBUG_RETURN((range_seq_t) init_param); +} + +/* + Get the next range/key over records from the join buffer of a BKAH cache + SYNOPSIS - check_all_match_flags_for_key() - key_chain_ptr + bkah_range_seq_next() + seq value returned by bkah_range_seq_init() + range OUT reference to the next range + + DESCRIPTION + The function interprets seq as a pointer to a JOIN_CACHE_BKAH + object. The function returns a pointer to the range descriptor + for the next unique key built over records from the join buffer. + + NOTE + This function are used only as a callback function. + + RETURN VALUE + 0 ok, the range structure filled with info about the next range/key + 1 no more ranges +*/ + +static +uint bkah_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) +{ + DBUG_ENTER("bkah_range_seq_next"); + JOIN_CACHE_BKAH *cache= (JOIN_CACHE_BKAH *) rseq; + TABLE_REF *ref= &cache->join_tab->ref; + key_range *start_key= &range->start_key; + if ((start_key->length= cache->get_next_key((uchar **) &start_key->key))) + { + start_key->keypart_map= (1 << ref->key_parts) - 1; + start_key->flag= HA_READ_KEY_EXACT; + range->end_key= *start_key; + range->end_key.flag= HA_READ_AFTER_KEY; + range->ptr= (char *) cache->get_curr_key_chain(); + range->range_flag= EQ_RANGE; + DBUG_RETURN(0); + } + DBUG_RETURN(1); +} + + +/* + Check whether range_info orders to skip the next record from BKAH join buffer + SYNOPSIS + bkah_range_seq_skip_record() + seq value returned by bkah_range_seq_init() + range_info information about the next range/key returned by MRR + rowid [NOT USED] rowid of the record to be checked (not used) + DESCRIPTION - This function retrieves records in the given circular chain and checks - whether their match flags are set on. The parameter key_chain_ptr shall - point to the position in the join buffer storing the reference to the - last element of this chain. - - RETURN - TRUE if each retrieved record has its match flag set on - FALSE otherwise + The function interprets seq as a pointer to a JOIN_CACHE_BKAH + object. The function returns TRUE if the record with this range_info + is to be filtered out from the stream of records returned by + multi_range_read_next(). + + NOTE + This function are used only as a callback function. + + RETURN VALUE + 1 record with this range_info is to be filtered out from the stream + of records returned by multi_range_read_next() + 0 the record is to be left in the stream +*/ + +static +bool bkah_range_seq_skip_record(range_seq_t rseq, char *range_info, + uchar *rowid) +{ + DBUG_ENTER("bkah_range_seq_skip_record"); + JOIN_CACHE_BKAH *cache= (JOIN_CACHE_BKAH *) rseq; + bool res= cache->check_all_match_flags_for_key((uchar *) range_info); + DBUG_RETURN(res); +} + + +/* + Check if the record combination from BKAH cache matches the index condition + + SYNOPSIS + bkah_skip_index_tuple() + rseq value returned by bka_range_seq_init() + range_info record chain for the next range/key returned by MRR + + DESCRIPTION + This is wrapper for JOIN_CACHE_BKA_UNIQUE::skip_index_tuple method, + see comments there. + + NOTE + This function is used as a RANGE_SEQ_IF::skip_index_tuple callback. + + RETURN VALUE + 0 some records from the chain satisfy the index condition + 1 otherwise */ -bool JOIN_CACHE_BKA_UNIQUE::check_all_match_flags_for_key(uchar *key_chain_ptr) +static +bool bkah_skip_index_tuple(range_seq_t rseq, char *range_info) { - uchar *last_rec_ref_ptr= get_next_rec_ref(key_chain_ptr); - uchar *next_rec_ref_ptr= last_rec_ref_ptr; - do - { - next_rec_ref_ptr= get_next_rec_ref(next_rec_ref_ptr); - uchar *rec_ptr= next_rec_ref_ptr+rec_fields_offset; - if (!get_match_flag_by_pos(rec_ptr)) - return FALSE; - } - while (next_rec_ref_ptr != last_rec_ref_ptr); - return TRUE; + DBUG_ENTER("bka_unique_skip_index_tuple"); + JOIN_CACHE_BKAH *cache= (JOIN_CACHE_BKAH *) rseq; + DBUG_RETURN(cache->skip_index_tuple(range_info)); } - -/* - Get the next key built for the records from BKA_UNIQUE join buffer + +/* + Prepare to read record from BKAH cache matching the current joined record SYNOPSIS - get_next_key() - key pointer to the buffer where the key value is to be placed + prepare_look_for_matches() + skip_last <-> ignore the last record in the buffer (always unused here) DESCRIPTION - The function reads the next key value stored in the hash table of the - join buffer. Depending on the value of the use_emb_key flag of the - join cache the value is read either from the table itself or from - the record field where it occurs. + The function prepares to iterate over records in the join cache buffer + matching the record loaded into the record buffer for join_tab when + performing join operation by BKAH join algorithm. With BKAH algorithm, if + association labels are used, then record loaded into the record buffer + for join_tab always has a direct reference to the chain of the mathing + records from the join buffer. If association labels are not used then + then the chain of the matching records is obtained by the call of the + get_key_chain_by_join_key function. + + RETURN VALUE + TRUE there are no records in the buffer to iterate over + FALSE otherwise +*/ + +bool JOIN_CACHE_BKAH::prepare_look_for_matches(bool skip_last) +{ + last_matching_rec_ref_ptr= next_matching_rec_ref_ptr= 0; + if (no_association && + (curr_matching_chain= get_matching_chain_by_join_key())) + return 1; + last_matching_rec_ref_ptr= get_next_rec_ref(curr_matching_chain); + return 0; +} - RETURN - length of the key value - if the starting value of 'cur_key_entry' refers - to the position after that referred by the the value of 'last_key_entry' - 0 - otherwise. +/* + Initialize the BKAH join cache + + SYNOPSIS + init + + DESCRIPTION + The function initializes the cache structure. It is supposed to be called + right after a constructor for the JOIN_CACHE_BKAH. + + NOTES + The function first constructs a companion object of the type + JOIN_TAB_SCAN_MRR, then it calls the init method of the parent class. + + RETURN VALUE + 0 initialization with buffer allocations has been succeeded + 1 otherwise */ -uint JOIN_CACHE_BKA_UNIQUE::get_next_key(uchar ** key) -{ - if (curr_key_entry == last_key_entry) - return 0; +int JOIN_CACHE_BKAH::init() +{ + bool check_only_first_match= join_tab->check_only_first_match(); - curr_key_entry-= key_entry_length; + no_association= test(mrr_mode & HA_MRR_NO_ASSOCIATION); - *key = use_emb_key ? get_emb_key(curr_key_entry) : curr_key_entry; + RANGE_SEQ_IF rs_funcs= { bkah_range_seq_init, + bkah_range_seq_next, + check_only_first_match && !no_association ? + bkah_range_seq_skip_record : 0, + bkah_skip_index_tuple }; - DBUG_ASSERT(*key >= buff && *key < hash_table); + DBUG_ENTER("JOIN_CACHE_BKAH::init"); - return key_length; + if (!(join_tab_scan= new JOIN_TAB_SCAN_MRR(join, join_tab, + mrr_mode, rs_funcs))) + DBUG_RETURN(1); + + DBUG_RETURN(JOIN_CACHE_HASHED::init()); } -/**************************************************************************** - * Join cache module end - ****************************************************************************/ +/* + Check the index condition of the joined table for a record from the BKA cache + + SYNOPSIS + skip_index_tuple() + range_info record chain returned by MRR + + DESCRIPTION + See JOIN_CACHE_BKA::skip_index_tuple(). + This function is the variant for use with rhe class JOIN_CACHE_BKAH. + The difference from JOIN_CACHE_BKA case is that there may be multiple + previous table record combinations that share the same key(MRR range). + As a consequence, we need to loop through the chain of all table record + combinations that match the given MRR range key range_info until we find + one that satisfies the index condition. + + NOTE + Possible optimization: + Before we unpack the record from a previous table + check if this table is used in the condition. + If so then unpack the record otherwise skip the unpacking. + This should be done by a special virtual method + get_partial_record_by_pos(). + + RETURN + 1 any record combination from the chain referred by range_info + does not satisfy the index condition + 0 otherwise + + +*/ + +bool JOIN_CACHE_BKAH::skip_index_tuple(char *range_info) +{ + uchar *last_rec_ref_ptr= get_next_rec_ref((uchar*) range_info); + uchar *next_rec_ref_ptr= last_rec_ref_ptr; + DBUG_ENTER("JOIN_CACHE_BKAH::skip_index_tuple"); + do + { + next_rec_ref_ptr= get_next_rec_ref(next_rec_ref_ptr); + uchar *rec_ptr= next_rec_ref_ptr + rec_fields_offset; + get_record_by_pos(rec_ptr); + if (join_tab->cache_idx_cond->val_int()) + DBUG_RETURN(FALSE); + } while(next_rec_ref_ptr != last_rec_ref_ptr); + DBUG_RETURN(TRUE); +} diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 2638daf4e5c..b30dc81d7d9 100644..100755 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -94,6 +94,7 @@ static void make_outerjoin_info(JOIN *join); static Item* make_cond_after_sjm(Item *root_cond, Item *cond, table_map tables, table_map sjm_tables); static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item); +static void revise_cache_usage(JOIN_TAB *join_tab); static bool make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after); static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables); static void update_depend_map(JOIN *join); @@ -1671,6 +1672,62 @@ void JOIN::restore_tmp() } +/* + Shrink join buffers used for preceding tables to reduce the occupied space + + SYNOPSIS + shrink_join_buffers() + jt table up to which the buffers are to be shrunk + curr_space the size of the space used by the buffers for tables 1..jt + needed_space the size of the space that has to be used by these buffers + + DESCRIPTION + The function makes an attempt to shrink all join buffers used for the + tables starting from the first up to jt to reduce the total size of the + space occupied by the buffers used for tables 1,...,jt from curr_space + to needed_space. + The function assumes that the buffer for the table jt has not been + allocated yet. + + RETURN + FALSE if all buffer have been successfully shrunk + TRUE otherwise +*/ + +bool JOIN::shrink_join_buffers(JOIN_TAB *jt, + ulonglong curr_space, + ulonglong needed_space) +{ + JOIN_CACHE *cache; + for (JOIN_TAB *tab= join_tab+const_tables; tab < jt; tab++) + { + cache= tab->cache; + if (cache) + { + ulong buff_size; + if (needed_space < cache->get_min_join_buffer_size()) + return TRUE; + if (cache->shrink_join_buffer_in_ratio(curr_space, needed_space)) + { + revise_cache_usage(tab); + return TRUE; + } + buff_size= cache->get_join_buffer_size(); + curr_space-= buff_size; + needed_space-= buff_size; + } + } + + cache= jt->cache; + DBUG_ASSERT(cache); + if (needed_space < cache->get_min_join_buffer_size()) + return TRUE; + cache->set_join_buffer_size(needed_space); + + return FALSE; +} + + int JOIN::reinit() { @@ -4617,7 +4674,8 @@ best_access_path(JOIN *join, if (table->covering_keys.is_set(key)) { /* we can use only index tree */ - tmp= record_count * table->file->keyread_read_time(key, 1, tmp); + tmp= record_count * + table->file->keyread_read_time(key, 1, (ha_rows) tmp); } else tmp= record_count*min(tmp,s->worst_seeks); @@ -4782,7 +4840,8 @@ best_access_path(JOIN *join, if (table->covering_keys.is_set(key)) { /* we can use only index tree */ - tmp= record_count * table->file->keyread_read_time(key, 1, tmp); + tmp= record_count * + table->file->keyread_read_time(key, 1, (ha_rows) tmp); } else tmp= record_count * min(tmp,s->worst_seeks); @@ -5848,15 +5907,15 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count, Find how much space the prevous read not const tables takes in cache. */ -void calc_used_field_length(THD *thd, JOIN_TAB *join_tab) +void JOIN_TAB::calc_used_field_length(bool max_fl) { uint null_fields,blobs,fields,rec_length; Field **f_ptr,*field; uint uneven_bit_fields; - MY_BITMAP *read_set= join_tab->table->read_set; + MY_BITMAP *read_set= table->read_set; uneven_bit_fields= null_fields= blobs= fields= rec_length=0; - for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++) + for (f_ptr=table->field ; (field= *f_ptr) ; f_ptr++) { if (bitmap_is_set(read_set, field->field_index)) { @@ -5873,24 +5932,31 @@ void calc_used_field_length(THD *thd, JOIN_TAB *join_tab) } } if (null_fields || uneven_bit_fields) - rec_length+=(join_tab->table->s->null_fields+7)/8; - if (join_tab->table->maybe_null) + rec_length+=(table->s->null_fields+7)/8; + if (table->maybe_null) rec_length+=sizeof(my_bool); - if (blobs) + if (max_fl) { - uint blob_length=(uint) (join_tab->table->file->stats.mean_rec_length- - (join_tab->table->s->reclength-rec_length)); - rec_length+=(uint) max(4,blob_length); - } + // TODO: to improve this estimate for max expected length if the record + if (blobs) + { + uint blob_length=(uint) (table->file->stats.mean_rec_length- + (table->s->reclength-rec_length)); + rec_length+=(uint) max(4,blob_length); + } + } + else + rec_length= table->file->stats.mean_rec_length; + /* psergey-todo: why we don't count here rowid that we might need to store when using DuplicateElimination? */ - join_tab->used_fields=fields; - join_tab->used_fieldlength=rec_length; - join_tab->used_blobs=blobs; - join_tab->used_null_fields= null_fields; - join_tab->used_uneven_bit_fields= uneven_bit_fields; + used_fields=fields; + used_fieldlength=rec_length; + used_blobs=blobs; + used_null_fields= null_fields; + used_uneven_bit_fields= uneven_bit_fields; } @@ -5899,16 +5965,13 @@ cache_record_length(JOIN *join,uint idx) { uint length=0; JOIN_TAB **pos,**end; - THD *thd=join->thd; for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ; pos != end ; pos++) { JOIN_TAB *join_tab= *pos; - if (!join_tab->used_fieldlength) /* Not calced yet */ - calc_used_field_length(thd, join_tab); - length+=join_tab->used_fieldlength; + length+= join_tab->get_used_fieldlength(); } return length; } @@ -7344,24 +7407,66 @@ end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) depend on: - the access method to access rows of the joined table - whether the join table is an inner table of an outer join or semi-join + - whether the optimizer switches + outer_join_with_cache, semijoin_with_cache, join_cache_incremental, + join_cache_hashed, join_cache_bka, + are set on or off - the join cache level set for the query - the join 'options'. + In any case join buffer is not used if the number of the joined table is greater than 'no_jbuf_after'. It's also never used if the value of join_cache_level is equal to 0. - The other valid settings of join_cache_level lay in the interval 1..8. - If join_cache_level==1|2 then join buffer is used only for inner joins - with 'JT_ALL' access method. - If join_cache_level==3|4 then join buffer is used for any join operation - (inner join, outer join, semi-join) with 'JT_ALL' access method. - If 'JT_ALL' access method is used to read rows of the joined table then - always a JOIN_CACHE_BNL object is employed. + If the optimizer switch outer_join_with_cache is off no join buffer is + used for outer join operations. + If the optimizer switch semijoin_with_cache is off no join buffer is used + for semi-join operations. + If the optimizer switch join_cache_incremental is off no incremental join + buffers are used. + If the optimizer switch join_cache_hashed is off then the optimizer does + not use neither BNLH algorithm, nor BKAH algorithm to perform join + operations. + + If the optimizer switch join_cache_bka is off then the optimizer does not + use neither BKA algprithm, nor BKAH algorithm to perform join operation. + The valid settings for join_cache_level lay in the interval 0..8. + If it set to 0 no join buffers are used to perform join operations. + Currently we differentiate between join caches of 8 levels: + 1 : non-incremental join cache used for BNL join algorithm + 2 : incremental join cache used for BNL join algorithm + 3 : non-incremental join cache used for BNLH join algorithm + 4 : incremental join cache used for BNLH join algorithm + 5 : non-incremental join cache used for BKA join algorithm + 6 : incremental join cache used for BKA join algorithm + 7 : non-incremental join cache used for BKAH join algorithm + 8 : incremental join cache used for BKAH join algorithm + If the value of join_cache_level is set to n then no join caches of + levels higher than n can be employed. + + If the optimizer switches outer_join_with_cache, semijoin_with_cache, + join_cache_incremental, join_cache_hashed, join_cache_bka are all on + the following rules are applied. + If join_cache_level==1|2 then join buffer is used for inner joins, outer + joins and semi-joins with 'JT_ALL' access method. In this case a + JOIN_CACHE_BNL object is employed. + If join_cache_level==3|4 and then join buffer is used for a join operation + (inner join, outer join, semi-join) with 'JT_REF'/'JT_EQREF' access method + then a JOIN_CACHE_BNLH object is employed. If an index is used to access rows of the joined table and the value of join_cache_level==5|6 then a JOIN_CACHE_BKA object is employed. If an index is used to access rows of the joined table and the value of - join_cache_level==7|8 then a JOIN_CACHE_BKA_UNIQUE object is employed. + join_cache_level==7|8 then a JOIN_CACHE_BKAH object is employed. If the value of join_cache_level is odd then creation of a non-linked join cache is forced. + + Currently for any join operation a join cache of the level of the + highest allowed and applicable level is used. + For example, if join_cache_level is set to 6 and the optimizer switch + join_cache_bka is off, while the optimizer switch join_cache_hashed is + on then for any inner join operation with JT_REF/JT_EQREF access method + to the joined table the BNLH join algorithm will be used, while for + the table accessed by the JT_ALL methods the BNL algorithm will be used. + If the function decides that a join buffer can be used to join the table 'tab' then it sets the value of tab->use_join_buffer to TRUE and assigns the selected join cache object to the field 'cache' of the previous @@ -7378,10 +7483,13 @@ end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) For a nested outer join/semi-join, currently, we either use join buffers for all inner tables or for none of them. Some engines (e.g. Falcon) currently allow to use only a join cache - of the type JOIN_CACHE_BKA_UNIQUE when the joined table is accessed through + of the type JOIN_CACHE_BKAH when the joined table is accessed through an index. For these engines setting the value of join_cache_level to 5 or 6 results in that no join buffer is used to join the table. + RETURN VALUE + cache level if cache is used, otherwise returns 0 + TODO Support BKA inside SJ-Materialization nests. When doing this, we'll need to only store sj-inner tables in the join buffer. @@ -7405,10 +7513,6 @@ end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) first_tab= join->join_tab + first_sjm_table; } #endif - - RETURN - - cache level if cache is used, otherwise returns 0 */ static @@ -7423,7 +7527,12 @@ uint check_join_cache_usage(JOIN_TAB *tab, uint bufsz= 4096; JOIN_CACHE *prev_cache=0; uint cache_level= join->thd->variables.join_cache_level; - bool force_unlinked_cache= test(cache_level & 1); + bool force_unlinked_cache= + !optimizer_flag(join->thd, OPTIMIZER_SWITCH_JOIN_CACHE_INCREMENTAL); + bool no_hashed_cache= + !optimizer_flag(join->thd, OPTIMIZER_SWITCH_JOIN_CACHE_HASHED); + bool no_bka_cache= + !optimizer_flag(join->thd, OPTIMIZER_SWITCH_JOIN_CACHE_BKA); uint i= tab - join->join_tab; *icp_other_tables_ok= TRUE; @@ -7438,16 +7547,23 @@ uint check_join_cache_usage(JOIN_TAB *tab, */ if (tab->use_quick == 2) goto no_join_cache; + + if (tab->is_inner_table_of_semi_join_with_first_match() && + !optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN_WITH_CACHE)) + goto no_join_cache; + if (tab->is_inner_table_of_outer_join() && + !optimizer_flag(join->thd, OPTIMIZER_SWITCH_OUTER_JOIN_WITH_CACHE)) + goto no_join_cache; + /* Non-linked join buffers can't guarantee one match */ - if (force_unlinked_cache && - (!tab->type == JT_ALL || cache_level <= 4) && - ((tab->is_inner_table_of_semi_join_with_first_match() && - !tab->is_single_inner_of_semi_join_with_first_match()) || - (tab->is_inner_table_of_outer_join() && - !tab->is_single_inner_of_outer_join()))) - goto no_join_cache; + if (force_unlinked_cache && + ((tab->is_inner_table_of_semi_join_with_first_match() && + !tab->is_single_inner_of_semi_join_with_first_match()) || + (tab->is_inner_table_of_outer_join() && + !tab->is_single_inner_of_outer_join()))) + goto no_join_cache; /* Don't use join buffering if we're dictated not to by no_jbuf_after (this @@ -7492,43 +7608,76 @@ uint check_join_cache_usage(JOIN_TAB *tab, switch (tab->type) { case JT_ALL: - if (cache_level <= 2 && (tab->first_inner || tab->first_sj_inner_tab)) - goto no_join_cache; + if (cache_level == 1) + prev_cache= 0; if ((options & SELECT_DESCRIBE) || (((tab->cache= new JOIN_CACHE_BNL(join, tab, prev_cache))) && !tab->cache->init())) { *icp_other_tables_ok= FALSE; - return cache_level; + return (2-test(!prev_cache)); } goto no_join_cache; case JT_SYSTEM: case JT_CONST: case JT_REF: case JT_EQ_REF: - if (cache_level <= 4) - return 0; + if (cache_level <=2 || (no_hashed_cache && no_bka_cache)) + goto no_join_cache; + flags= HA_MRR_NO_NULL_ENDPOINTS; if (tab->table->covering_keys.is_set(tab->ref.key)) flags|= HA_MRR_INDEX_ONLY; rows= tab->table->file->multi_range_read_info(tab->ref.key, 10, 20, &bufsz, &flags, &cost); - if ((rows != HA_POS_ERROR) && !(flags & HA_MRR_USE_DEFAULT_IMPL) && - (!(flags & HA_MRR_NO_ASSOCIATION) || cache_level > 6) && - ((options & SELECT_DESCRIBE) || - (((cache_level <= 6 && - (tab->cache= new JOIN_CACHE_BKA(join, tab, flags, prev_cache))) || - (cache_level > 6 && - (tab->cache= new JOIN_CACHE_BKA_UNIQUE(join, tab, flags, prev_cache))) - ) && !tab->cache->init()))) - return cache_level; + + if ((cache_level <=4 && !no_hashed_cache) || no_bka_cache || + (flags & HA_MRR_NO_ASSOCIATION) && cache_level <=6) + { + if (cache_level == 3) + prev_cache= 0; + if ((options & SELECT_DESCRIBE) || + ((tab->cache= new JOIN_CACHE_BNLH(join, tab, prev_cache)) && + !tab->cache->init())) + return (4-test(!prev_cache)); + goto no_join_cache; + } + if (cache_level > 4 && no_bka_cache) + goto no_join_cache; + + if ((flags & HA_MRR_NO_ASSOCIATION) && + (cache_level <= 6 || no_hashed_cache)) + goto no_join_cache; + + if ((rows != HA_POS_ERROR) && !(flags & HA_MRR_USE_DEFAULT_IMPL)) + { + if (cache_level <= 6 || no_hashed_cache) + { + if (cache_level == 5) + prev_cache= 0; + if ((options & SELECT_DESCRIBE) || + ((tab->cache= new JOIN_CACHE_BKA(join, tab, flags, prev_cache)) && + !tab->cache->init())) + return (6-test(!prev_cache)); + goto no_join_cache; + } + else + { + if (cache_level == 7) + prev_cache= 0; + if ((options & SELECT_DESCRIBE) || + ((tab->cache= new JOIN_CACHE_BKAH(join, tab, flags, prev_cache)) && + !tab->cache->init())) + return (8-test(!prev_cache)); + goto no_join_cache; + } + } goto no_join_cache; default : ; } no_join_cache: - if (cache_level>2) - revise_cache_usage(tab); + revise_cache_usage(tab); return 0; } @@ -7559,6 +7708,7 @@ static bool make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) { uint i; + uint jcl; bool statistics= test(!(join->select_options & SELECT_DESCRIBE)); bool sorted= 1; uint first_sjm_table= MAX_TABLES; @@ -7610,27 +7760,26 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) /* Only happens with outer joins */ tab->read_first_record= tab->type == JT_SYSTEM ? join_read_system :join_read_const; - if (check_join_cache_usage(tab, join, options, no_jbuf_after, - &icp_other_tables_ok)) + if ((jcl= check_join_cache_usage(tab, join, options, + no_jbuf_after, &icp_other_tables_ok))) { tab->use_join_cache= TRUE; tab[-1].next_select=sub_select_cache; } - else if (table->covering_keys.is_set(tab->ref.key) && !table->no_keyread) { table->key_read=1; table->file->extra(HA_EXTRA_KEYREAD); } - else + else if (!jcl || jcl > 4) push_index_cond(tab, tab->ref.key, icp_other_tables_ok); break; case JT_EQ_REF: tab->read_record.unlock_row= join_read_key_unlock_row; /* fall through */ - if (check_join_cache_usage(tab, join, options, no_jbuf_after, - &icp_other_tables_ok)) + if ((jcl= check_join_cache_usage(tab, join, options, + no_jbuf_after, &icp_other_tables_ok))) { tab->use_join_cache= TRUE; tab[-1].next_select=sub_select_cache; @@ -7641,7 +7790,7 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) table->key_read=1; table->file->extra(HA_EXTRA_KEYREAD); } - else + else if (!jcl || jcl > 4) push_index_cond(tab, tab->ref.key, icp_other_tables_ok ); break; case JT_REF_OR_NULL: @@ -7653,8 +7802,8 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) } delete tab->quick; tab->quick=0; - if (check_join_cache_usage(tab, join, options, no_jbuf_after, - &icp_other_tables_ok)) + if ((jcl= check_join_cache_usage(tab, join, options, + no_jbuf_after, &icp_other_tables_ok))) { tab->use_join_cache= TRUE; tab[-1].next_select=sub_select_cache; @@ -7662,7 +7811,7 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) if (table->covering_keys.is_set(tab->ref.key) && !table->no_keyread) table->enable_keyread(); - else + else if (!jcl || jcl > 4) push_index_cond(tab, tab->ref.key, icp_other_tables_ok); break; case JT_ALL: @@ -18308,8 +18457,8 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, item_list.push_back(new Item_string("func", strlen("func"), cs)); } /* rows */ - ha_rows rows= (sj_strategy == SJ_OPT_MATERIALIZE_SCAN)? - tab->emb_sj_nest->sj_mat_info->rows : 1; + ha_rows rows= (ha_rows) ((sj_strategy == SJ_OPT_MATERIALIZE_SCAN)? + tab->emb_sj_nest->sj_mat_info->rows : 1); item_list.push_back(new Item_int((longlong)rows, MY_INT64_NUM_DECIMAL_DIGITS)); /* filtered */ diff --git a/sql/sql_select.h b/sql/sql_select.h index 2b7fc8fd47c..251a3869d8c 100644..100755 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -220,7 +220,10 @@ typedef struct st_join_table { table_map dependent,key_dependent; uint use_quick,index; uint status; ///< Save status for cache - uint used_fields,used_fieldlength,used_blobs; + uint used_fields; + ulong used_fieldlength; + ulong max_used_fieldlength; + uint used_blobs; uint used_null_fields; uint used_rowid_fields; uint used_uneven_bit_fields; @@ -235,6 +238,7 @@ typedef struct st_join_table { ha_rows limit; TABLE_REF ref; bool use_join_cache; + ulong join_buffer_size_limit; JOIN_CACHE *cache; /* Index condition for BKA access join @@ -369,6 +373,19 @@ typedef struct st_join_table { select->cond= new_cond; return tmp_select_cond; } + void calc_used_field_length(bool max_fl); + ulong get_used_fieldlength() + { + if (!used_fieldlength) + calc_used_field_length(FALSE); + return used_fieldlength; + } + ulong get_max_used_fieldlength() + { + if (!max_used_fieldlength) + calc_used_field_length(TRUE); + return max_used_fieldlength; + } } JOIN_TAB; @@ -409,20 +426,25 @@ typedef struct st_cache_field { } CACHE_FIELD; +class JOIN_TAB_SCAN; + + /* - JOIN_CACHE is the base class to support the implementations of both - Blocked-Based Nested Loops (BNL) Join Algorithm and Batched Key Access (BKA) - Join Algorithm. The first algorithm is supported by the derived class - JOIN_CACHE_BNL, while the second algorithm is supported by the derived - class JOIN_CACHE_BKA. - These two algorithms have a lot in common. Both algorithms first - accumulate the records of the left join operand in a join buffer and - then search for matching rows of the second operand for all accumulated - records. - For the first algorithm this strategy saves on logical I/O operations: + JOIN_CACHE is the base class to support the implementations of + - Block Nested Loop (BNL) Join Algorithm, + - Block Nested Loop Hash (BNLH) Join Algorithm, + - Batched Key Access (BKA) Join Algorithm. + The first algorithm is supported by the derived class JOIN_CACHE_BNL, + the second algorithm is supported by the derived class JOIN_CACHE_BNLH, + while the third algorithm is implemented in two variant supported by + the classes JOIN_CACHE_BKA and JOIN_CACHE_BKAH. + These three algorithms have a lot in common. Each of them first accumulates + the records of the left join operand in a join buffer and then searches for + matching rows of the second operand for all accumulated records. + For the first two algorithms this strategy saves on logical I/O operations: the entire set of records from the join buffer requires only one look-through - the records provided by the second operand. - For the second algorithm the accumulation of records allows to optimize + of the records provided by the second operand. + For the third algorithm the accumulation of records allows to optimize fetching rows of the second operand from disk for some engines (MyISAM, InnoDB), or to minimize the number of round-trips between the Server and the engine nodes (NDB Cluster). @@ -470,7 +492,7 @@ protected: } /* - The total maximal length of the fields stored for a record in the cache. + The maximum total length of the fields stored for a record in the cache. For blob fields only the sizes of the blob lengths are taken into account. */ uint length; @@ -483,7 +505,7 @@ protected: /* Cardinality of the range of join tables whose fields can be put into the - cache. (A table from the range not necessarily contributes to the cache.) + cache. A table from the range not necessarily contributes to the cache. */ uint tables; @@ -507,9 +529,11 @@ protected: /* The total number of fields referenced from field descriptors for other join - caches. These fields are used to construct key values to access matching - rows with index lookups. Currently the fields can be referenced only from - descriptors for bka caches. However they may belong to a cache of any type. + caches. These fields are used to construct key values. + When BKA join algorithm is employed the constructed key values serve to + access matching rows with index lookups. + The key values are put into a hash table when the BNLH join algorithm + is employed and when BKAH is used for the join operation. */ uint referenced_fields; @@ -524,7 +548,8 @@ protected: descriptors. This number can be useful for implementations of the init methods. */ - uint data_field_ptr_count; + uint data_field_ptr_count; + /* Array of the descriptors of fields containing 'fields' elements. These are all fields that are stored for a record in the cache. @@ -560,6 +585,27 @@ protected: */ uint pack_length_with_blob_ptrs; + /* + The total size of the record base prefix. The base prefix of record may + include the following components: + - the length of the record + - the link to a record in a previous buffer. + Each record in the buffer are supplied with the same set of the components. + */ + uint base_prefix_length; + + /* + The expected length of a record in the join buffer together with + all prefixes and postfixes + */ + ulong avg_record_length; + + /* The expected size of the space per record in the auxiliary buffer */ + ulong avg_aux_buffer_incr; + + /* Expected join buffer space used for one record */ + ulong space_per_record; + /* Pointer to the beginning of the join buffer */ uchar *buff; /* @@ -567,11 +613,25 @@ protected: Part of this memory may be reserved for the auxiliary buffer. */ ulong buff_size; - /* Size of the auxiliary buffer. */ + /* The minimal join buffer size when join buffer still makes sense to use */ + ulong min_buff_size; + /* The maximum expected size if the join buffer to be used */ + ulong max_buff_size; + /* Size of the auxiliary buffer */ ulong aux_buff_size; /* The number of records put into the join buffer */ - uint records; + ulong records; + /* + The number of records in the fully refilled join buffer of + the minimal size equal to min_buff_size + */ + ulong min_records; + /* + The maximum expected number of records to be put in the join buffer + at one refill + */ + ulong max_records; /* Pointer to the current position in the join buffer. @@ -586,13 +646,13 @@ protected: uchar *end_pos; /* - Pointer to the beginning of first field of the current read/write record - from the join buffer. The value is adjusted by the get_record/put_record - functions. + Pointer to the beginning of the first field of the current read/write + record from the join buffer. The value is adjusted by the + get_record/put_record functions. */ uchar *curr_rec_pos; /* - Pointer to the beginning of first field of the last record + Pointer to the beginning of the first field of the last record from the join buffer. */ uchar *last_rec_pos; @@ -611,16 +671,55 @@ protected: In the simplest case a record link is just a pointer to the beginning of the record stored in the buffer. In a more general case a link could be a reference to an array of pointers - to records in the buffer. */ + to records in the buffer. + */ uchar *curr_rec_link; + /* + The number of fields put in the join buffer of the join cache that are + used in building keys to access the table join_tab + */ + uint local_key_arg_fields; + /* + The total number of the fields in the previous caches that are used + in building keys to access the table join_tab + */ + uint external_key_arg_fields; + + /* + This flag indicates that the key values will be read directly from the join + buffer. It will save us building key values in the key buffer. + */ + bool use_emb_key; + /* The length of an embedded key value */ + uint emb_key_length; + + /* + This object provides the methods to iterate over records of + the joined table join_tab when looking for join matches between + records from join buffer and records from join_tab. + BNL and BNLH join algorithms retrieve all records from join_tab, + while BKA/BKAH algorithm iterates only over those records from + join_tab that can be accessed by look-ups with join keys built + from records in join buffer. + */ + JOIN_TAB_SCAN *join_tab_scan; + void calc_record_fields(); - int alloc_fields(uint external_fields); + void collect_info_on_key_args(); + int alloc_fields(); void create_flag_fields(); - void create_remaining_fields(bool all_read_fields); + void create_key_arg_fields(); + void create_remaining_fields(); void set_constants(); int alloc_buffer(); + /* Shall reallocate the join buffer */ + virtual int realloc_buffer(); + + /* Check the possibility to read the access keys directly from join buffer */ + bool check_emb_key_usage(); + uint get_size_of_rec_offset() { return size_of_rec_ofs; } uint get_size_of_rec_length() { return size_of_rec_len; } uint get_size_of_fld_offset() { return size_of_fld_ofs; } @@ -642,7 +741,6 @@ protected: { store_offset(size_of_rec_ofs, ptr-size_of_rec_ofs, (ulong) (ref-buff)); } - void store_rec_length(uchar *ptr, ulong len) { store_offset(size_of_rec_len, ptr, len); @@ -655,12 +753,23 @@ protected: /* Write record fields and their required offsets into the join buffer */ uint write_record_data(uchar *link, bool *is_full); + /* Get the total length of all prefixes of a record in the join buffer */ + virtual uint get_prefix_length() { return base_prefix_length; } + /* Get maximum total length of all affixes of a record in the join buffer */ + virtual uint get_record_max_affix_length(); + + /* + Shall get maximum size of the additional space per record used for + record keys + */ + virtual uint get_max_key_addon_space_per_record() { return 0; } + /* This method must determine for how much the auxiliary buffer should be incremented when a new record is added to the join buffer. If no auxiliary buffer is needed the function should return 0. */ - virtual uint aux_buffer_incr() { return 0; } + virtual uint aux_buffer_incr(ulong recno); /* Shall calculate how much space is remaining in the join buffer */ virtual ulong rem_space() @@ -668,9 +777,6 @@ protected: return max(buff_size-(end_pos-buff)-aux_buff_size,0); } - /* Shall skip record from the join buffer if its match flag is on */ - virtual bool skip_record_if_match(); - /* Read all flag and data fields of a record from the join buffer */ uint read_all_record_fields(); @@ -683,6 +789,9 @@ protected: /* Read a referenced field from the join buffer */ bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len); + /* Shall skip record from the join buffer if its match flag is on */ + virtual bool skip_recurrent_match(); + /* True if rec_ptr points to the record whose blob data stay in record buffers @@ -692,16 +801,61 @@ protected: return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff; } - /* Find matches from the next table for records from the join buffer */ - virtual enum_nested_loop_state join_matching_records(bool skip_last)=0; + /* Find matches from the next table for records from the join buffer */ + virtual enum_nested_loop_state join_matching_records(bool skip_last); + + /* Shall set an auxiliary buffer up (currently used only by BKA joins) */ + virtual int setup_aux_buffer(HANDLER_BUFFER &aux_buff) + { + DBUG_ASSERT(0); + return 0; + } + + /* + Shall get the number of ranges in the cache buffer passed + to the MRR interface + */ + virtual uint get_number_of_ranges_for_mrr() { return 0; }; + + /* + Shall prepare to look for records from the join cache buffer that would + match the record of the joined table read into the record buffer + */ + virtual bool prepare_look_for_matches(bool skip_last)= 0; + /* + Shall return a pointer to the record from join buffer that is checked + as the next candidate for a match with the current record from join_tab. + Each implementation of this virtual function should bare in mind + that the record position it returns shall be exactly the position + passed as the parameter to the implementations of the virtual functions + skip_next_candidate_for_match and read_next_candidate_for_match. + */ + virtual uchar *get_next_candidate_for_match()= 0; + /* + Shall check whether the given record from the join buffer has its match + flag set on and, if so, skip the record in the buffer. + */ + virtual bool skip_recurrent_candidate_for_match(uchar *rec_ptr)= 0; + /* + Shall read the given record from the join buffer into the + the corresponding record buffer + */ + virtual void read_next_candidate_for_match(uchar *rec_ptr)= 0; + + /* + Shall return the location of the association label returned by + the multi_read_range_next function for the current record loaded + into join_tab's record buffer + */ + virtual uchar **get_curr_association_ptr() { return 0; }; - /* Add null complements for unmatched outer records from buffer */ + /* Add null complements for unmatched outer records from the join buffer */ virtual enum_nested_loop_state join_null_complements(bool skip_last); /* Restore the fields of the last record from the join buffer */ virtual void restore_last_record(); - /*Set match flag for a record in join buffer if it has not been set yet */ + /* Set match flag for a record in join buffer if it has not been set yet */ bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr); enum_nested_loop_state generate_full_extensions(uchar *rec_ptr); @@ -720,10 +874,26 @@ public: JOIN_CACHE *next_cache; /* Shall initialize the join cache structure */ - virtual int init()=0; + virtual int init(); + + /* Get the current size of the cache join buffer */ + ulong get_join_buffer_size() { return buff_size; } + /* Set the size of the cache join buffer to a new value */ + void set_join_buffer_size(ulong sz) { buff_size= sz; } + + /* Get the minimum possible size of the cache join buffer */ + virtual ulong get_min_join_buffer_size(); + /* Get the maximum possible size of the cache join buffer */ + virtual ulong get_max_join_buffer_size(); - /* The function shall return TRUE only for BKA caches */ - virtual bool is_key_access() { return FALSE; } + /* Shrink the size if the cache join buffer in a given ratio */ + bool shrink_join_buffer_in_ratio(ulonglong n, ulonglong d); + + /* + The function shall return TRUE only when there is a key access + to the join table + */ + virtual bool is_key_access()= 0; /* Shall reset the join buffer for reading/writing */ virtual void reset(bool for_writing); @@ -761,7 +931,7 @@ public: return (curr_rec_link ? curr_rec_link : get_curr_rec()); } - /* Join records from the join buffer with records from the next join table */ + /* Join records from the join buffer with records from the next join table */ enum_nested_loop_state join_records(bool skip_last); virtual ~JOIN_CACHE() {} @@ -772,164 +942,31 @@ public: buff= 0; } + friend class JOIN_CACHE_HASHED; friend class JOIN_CACHE_BNL; friend class JOIN_CACHE_BKA; - friend class JOIN_CACHE_BKA_UNIQUE; -}; - - -class JOIN_CACHE_BNL :public JOIN_CACHE -{ - -protected: - - /* Using BNL find matches from the next table for records from join buffer */ - enum_nested_loop_state join_matching_records(bool skip_last); - -public: - - /* - This constructor creates an unlinked BNL join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - */ - JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab) - { - join= j; - join_tab= tab; - prev_cache= next_cache= 0; - } - - /* - This constructor creates a linked BNL join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - */ - JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) - { - join= j; - join_tab= tab; - prev_cache= prev; - next_cache= 0; - if (prev) - prev->next_cache= this; - } - - /* Initialize the BNL cache */ - int init(); + friend class JOIN_TAB_SCAN; + friend class JOIN_TAB_SCAN_MRR; }; -class JOIN_CACHE_BKA :public JOIN_CACHE -{ -protected: - - /* Flag to to be passed to the MRR interface */ - uint mrr_mode; - - /* MRR buffer assotiated with this join cache */ - HANDLER_BUFFER mrr_buff; - - /* Shall initialize the MRR buffer */ - virtual void init_mrr_buff() - { - mrr_buff.buffer= end_pos; - mrr_buff.buffer_end= buff+buff_size; - } - - /* - The number of the cache fields that are used in building keys to access - the table join_tab - */ - uint local_key_arg_fields; - /* - The total number of the fields in the previous caches that are used - in building keys t access the table join_tab - */ - uint external_key_arg_fields; - - /* - This flag indicates that the key values will be read directly from the join - buffer. It will save us building key values in the key buffer. - */ - bool use_emb_key; - /* The length of an embedded key value */ - uint emb_key_length; - - /* Check the possibility to read the access keys directly from join buffer */ - bool check_emb_key_usage(); - - /* Calculate the increment of the MM buffer for a record write */ - uint aux_buffer_incr(); - - /* Using BKA find matches from the next table for records from join buffer */ - enum_nested_loop_state join_matching_records(bool skip_last); - - /* Prepare to search for records that match records from the join buffer */ - enum_nested_loop_state init_join_matching_records(RANGE_SEQ_IF *seq_funcs, - uint ranges); - - /* Finish searching for records that match records from the join buffer */ - enum_nested_loop_state end_join_matching_records(enum_nested_loop_state rc); - -public: - - /* - This constructor creates an unlinked BKA join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags) - { - join= j; - join_tab= tab; - prev_cache= next_cache= 0; - mrr_mode= flags; - } - - /* - This constructor creates a linked BKA join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the cache - object to which this cache is linked. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) - { - join= j; - join_tab= tab; - prev_cache= prev; - next_cache= 0; - if (prev) - prev->next_cache= this; - mrr_mode= flags; - } - - /* Initialize the BKA cache */ - int init(); - - bool is_key_access() { return TRUE; } - - /* Shall get the key built over the next record from the join buffer */ - virtual uint get_next_key(uchar **key); - - /* Check if the record combination matches the index condition */ - bool skip_index_tuple(range_seq_t rseq, char *range_info); -}; /* - The class JOIN_CACHE_BKA_UNIQUE supports the variant of the BKA join algorithm - that submits only distinct keys to the MRR interface. The records in the join - buffer of a cache of this class that have the same access key are linked into - a chain attached to a key entry structure that either itself contains the key - value, or, in the case when the keys are embedded, refers to its occurance in - one of the records from the chain. + The class JOIN_CACHE_HASHED is the base class for the classes + JOIN_CACHE_HASHED_BNL and JOIN_CACHE_HASHED_BKA. The first of them supports + an implementation of Block Nested Loop Hash (BNLH) Join Algorithm, + while the second is used for a variant of the BKA Join algorithm that performs + only one lookup for any records from join buffer with the same key value. + For a join cache of this class the records from the join buffer that have + the same access key are linked into a chain attached to a key entry structure + that either itself contains the key value, or, in the case when the keys are + embedded, refers to its occurrence in one of the records from the chain. To build the chains with the same keys a hash table is employed. It is placed at the very end of the join buffer. The array of hash entries is allocated - first at the very bottom of the join buffer, then go key entries. A hash entry - contains a header of the list of the key entries with the same hash value. + first at the very bottom of the join buffer, while key entries are placed + before this array. + A hash entry contains a header of the list of the key entries with the same + hash value. Each key entry is a structure of the following type: struct st_join_cache_key_entry { union { @@ -942,17 +979,10 @@ public: The references linking the records in a chain are always placed at the very beginning of the record info stored in the join buffer. The records are linked in a circular list. A new record is always added to the end of this - list. When a key is passed to the MRR interface it can be passed either with - an association link containing a reference to the header of the record chain - attached to the corresponding key entry in the hash table, or without any - association link. When the next record is returned by a call to the MRR - function multi_range_read_next without any association (because if was not - passed together with the key) then the key value is extracted from the - returned record and searched for it in the hash table. If there is any records - with such key the chain of them will be yielded as the result of this search. + list. The following picture represents a typical layout for the info stored in the - join buffer of a join cache object of the JOIN_CACHE_BKA_UNIQUE class. + join buffer of a join cache object of the JOIN_CACHE_HASHED class. buff V @@ -998,7 +1028,7 @@ public: */ -class JOIN_CACHE_BKA_UNIQUE :public JOIN_CACHE_BKA +class JOIN_CACHE_HASHED: public JOIN_CACHE { private: @@ -1023,31 +1053,34 @@ private: /* Number of hash entries in the hash table */ uint hash_entries; + + /* The position of the currently retrieved key entry in the hash table */ + uchar *curr_key_entry; + + /* The offset of the data fields from the beginning of the record fields */ + uint data_fields_offset; + + uint get_hash_idx(uchar* key, uint key_len); + + int init_hash_table(); + void cleanup_hash_table(); + +protected: + /* Number of key entries in the hash table (number of distinct keys) */ uint key_entries; /* The position of the last key entry in the hash table */ uchar *last_key_entry; - /* The position of the currently retrieved key entry in the hash table */ - uchar *curr_key_entry; - /* The offset of the record fields from the beginning of the record representation. The record representation starts with a reference to the next record in the key record chain followed by the length of the trailing record data followed by a reference to the record segment - in the previous cache, if any, followed by the record fields. + in the previous cache, if any, followed by the record fields. */ uint rec_fields_offset; - /* The offset of the data fields from the beginning of the record fields */ - uint data_fields_offset; - - uint get_hash_idx(uchar* key, uint key_len); - - void cleanup_hash_table(); - -protected: uint get_size_of_key_offset() { return size_of_key_ofs; } @@ -1101,8 +1134,8 @@ protected: void store_next_rec_ref(uchar *ref_ptr, uchar *ref) { store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); - } - + } + /* Get the position of the embedded key value for the current record pointed to by get_curr_rec(). @@ -1132,6 +1165,18 @@ protected: store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); } + /* Get the total length of all prefixes of a record in hashed join buffer */ + uint get_prefix_length() + { + return base_prefix_length + get_size_of_rec_offset(); + } + + /* + Get maximum size of the additional space per record used for + the hash table with record keys + */ + uint get_max_key_addon_space_per_record(); + /* Calculate how much space in the buffer would not be occupied by records, key entries and additional memory for the MMR buffer. @@ -1141,57 +1186,27 @@ protected: return max(last_key_entry-end_pos-aux_buff_size,0); } - /* - Initialize the MRR buffer allocating some space within the join buffer. - The entire space between the last record put into the join buffer and the - last key entry added to the hash table is used for the MRR buffer. - */ - void init_mrr_buff() - { - mrr_buff.buffer= end_pos; - mrr_buff.buffer_end= last_key_entry; - } - - /* Skip record from JOIN_CACHE_BKA_UNIQUE buffer if its match flag is on */ - bool skip_record_if_match(); - - /* Using BKA_UNIQUE find matches for records from join buffer */ - enum_nested_loop_state join_matching_records(bool skip_last); + /* Skip record from a hashed join buffer if its match flag is on */ + bool skip_recurrent_match(); /* Search for a key in the hash table of the join buffer */ bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr); -public: + /* Reallocate the join buffer of a hashed join cache */ + int realloc_buffer(); - /* - This constructor creates an unlinked BKA_UNIQUE join cache. The cache is - to be used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA_UNIQUE(JOIN *j, JOIN_TAB *tab, uint flags) - :JOIN_CACHE_BKA(j, tab, flags) {} - - /* - This constructor creates a linked BKA_UNIQUE join cache. The cache is - to be used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the cache - object to which this cache is linked. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA_UNIQUE(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) - :JOIN_CACHE_BKA(j, tab, flags, prev) {} +public: - /* Initialize the BKA_UNIQUE cache */ + /* Initialize a hashed join cache */ int init(); - /* Reset the JOIN_CACHE_BKA_UNIQUE buffer for reading/writing */ + /* Reset the buffer of a hashed join cache for reading/writing */ void reset(bool for_writing); - /* Add a record into the JOIN_CACHE_BKA_UNIQUE buffer */ + /* Add a record into the buffer of a hashed join cache */ bool put_record(); - /* Read the next record from the JOIN_CACHE_BKA_UNIQUE buffer */ + /* Read the next record from the buffer of a hashed join cache */ bool get_record(); /* @@ -1209,8 +1224,449 @@ public: get_size_of_rec_offset()); } - /* Check if the record combination matches the index condition */ - bool skip_index_tuple(range_seq_t rseq, char *range_info); +}; + + +/* + The class JOIN_TAB_SCAN is a companion class for the classes JOIN_CACHE_BNL + and JOIN_CACHE_BNLH. Actually the class implements the iterator over the + table joinded by BNL/BNLH join algorithm. + The virtual functions open, next and close are called for any iteration over + the table. The function open is called to initiate the process of the + iteration. The function next shall read the next record from the joined + table. The record is read into the record buffer of the joined table. + The record is to be matched with records from the join cache buffer. + The function close shall perform the finalizing actions for the iteration. +*/ + +class JOIN_TAB_SCAN: public Sql_alloc +{ + +private: + /* TRUE if this is the first record from the joined table to iterate over */ + bool is_first_record; + +protected: + + /* The joined table to be iterated over */ + JOIN_TAB *join_tab; + /* The join cache used to join the table join_tab */ + JOIN_CACHE *cache; + /* + Representation of the executed multi-way join through which + all needed context can be accessed. + */ + JOIN *join; + +public: + + JOIN_TAB_SCAN(JOIN *j, JOIN_TAB *tab) + { + join= j; + join_tab= tab; + cache= join_tab->cache; + } + + virtual ~JOIN_TAB_SCAN() {} + + /* + Shall calculate the increment of the auxiliary buffer for a record + write if such a buffer is used by the table scan object + */ + virtual uint aux_buffer_incr(ulong recno) { return 0; } + + /* Initiate the process of iteration over the joined table */ + virtual int open(); + /* + Shall read the next candidate for matches with records from + the join buffer. + */ + virtual int next(); + /* + Perform the finalizing actions for the process of iteration + over the joined_table. + */ + virtual void close(); + +}; + +/* + The class JOIN_CACHE_BNL is used when the BNL join algorithm is + employed to perform a join operation +*/ + +class JOIN_CACHE_BNL :public JOIN_CACHE +{ +private: + /* + The number of the records in the join buffer that have to be + checked yet for a match with the current record of join_tab + read into the record buffer. + */ + uint rem_records; + +protected: + + bool prepare_look_for_matches(bool skip_last); + + uchar *get_next_candidate_for_match(); + + bool skip_recurrent_candidate_for_match(uchar *rec_ptr); + + void read_next_candidate_for_match(uchar *rec_ptr); + +public: + + /* + This constructor creates an unlinked BNL join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. + */ + JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab) + { + join= j; + join_tab= tab; + prev_cache= next_cache= 0; + } + + /* + This constructor creates a linked BNL join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. The parameter 'prev' specifies the previous + cache object to which this cache is linked. + */ + JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) + { + join= j; + join_tab= tab; + prev_cache= prev; + next_cache= 0; + if (prev) + prev->next_cache= this; + } + + /* Initialize the BNL cache */ + int init(); + + bool is_key_access() { return FALSE; } + +}; + + +/* + The class JOIN_CACHE_BNLH is used when the BNLH join algorithm is + employed to perform a join operation +*/ + +class JOIN_CACHE_BNLH :public JOIN_CACHE_HASHED +{ + +protected: + + /* + The pointer to the last record from the circular list of the records + that match the join key built out of the record in the join buffer for + the join_tab table + */ + uchar *last_matching_rec_ref_ptr; + /* + The pointer to the next current record from the circular list of the + records that match the join key built out of the record in the join buffer + for the join_tab table. This pointer is used by the class method + get_next_candidate_for_match to iterate over records from the circular + list. + */ + uchar *next_matching_rec_ref_ptr; + + /* + Get the chain of records from buffer matching the current candidate + record for join + */ + uchar *get_matching_chain_by_join_key(); + + bool prepare_look_for_matches(bool skip_last); + + uchar *get_next_candidate_for_match(); + + bool skip_recurrent_candidate_for_match(uchar *rec_ptr); + + void read_next_candidate_for_match(uchar *rec_ptr); + +public: + + /* + This constructor creates an unlinked BNLH join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. + */ + JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab) + { + join= j; + join_tab= tab; + prev_cache= next_cache= 0; + } + + /* + This constructor creates a linked BNLH join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. The parameter 'prev' specifies the previous + cache object to which this cache is linked. + */ + JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) + { + join= j; + join_tab= tab; + prev_cache= prev; + next_cache= 0; + if (prev) + prev->next_cache= this; + } + + /* Initialize the BNLH cache */ + int init(); + + bool is_key_access() { return TRUE; } + +}; + + +/* + The class JOIN_TAB_SCAN_MRR is a companion class for the classes + JOIN_CACHE_BKA and JOIN_CACHE_BKAH. Actually the class implements the + iterator over the records from join_tab selected by BKA/BKAH join + algorithm as the candidates to be joined. + The virtual functions open, next and close are called for any iteration over + join_tab record candidates. The function open is called to initiate the + process of the iteration. The function next shall read the next record from + the set of the record candidates. The record is read into the record buffer + of the joined table. The function close shall perform the finalizing actions + for the iteration. +*/ + +class JOIN_TAB_SCAN_MRR: public JOIN_TAB_SCAN +{ + /* Interface object to generate key ranges for MRR */ + RANGE_SEQ_IF range_seq_funcs; + + /* Number of ranges to be processed by the MRR interface */ + uint ranges; + + /* Flag to to be passed to the MRR interface */ + uint mrr_mode; + + /* MRR buffer assotiated with this join cache */ + HANDLER_BUFFER mrr_buff; + + /* Shall initialize the MRR buffer */ + virtual void init_mrr_buff() + { + cache->setup_aux_buffer(mrr_buff); + } + +public: + + JOIN_TAB_SCAN_MRR(JOIN *j, JOIN_TAB *tab, uint flags, RANGE_SEQ_IF rs_funcs) + :JOIN_TAB_SCAN(j, tab), range_seq_funcs(rs_funcs), mrr_mode(flags) {} + + uint aux_buffer_incr(ulong recno); + + int open(); + + int next(); + +}; + +/* + The class JOIN_CACHE_BKA is used when the BKA join algorithm is + employed to perform a join operation +*/ + +class JOIN_CACHE_BKA :public JOIN_CACHE +{ +private: + + /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ + uint mrr_mode; + + /* + This value is set to 1 by the class prepare_look_for_matches method + and back to 0 by the class get_next_candidate_for_match method + */ + uint rem_records; + + /* + This field contains the current association label set by a call of + the multi_range_read_next handler function. + See the function JOIN_CACHE_BKA::get_curr_key_association() + */ + uchar *curr_association; + +protected: + + /* + Get the number of ranges in the cache buffer passed to the MRR + interface. For each record its own range is passed. + */ + uint get_number_of_ranges_for_mrr() { return records; } + + /* + Setup the MRR buffer as the space between the last record put + into the join buffer and the very end of the join buffer + */ + int setup_aux_buffer(HANDLER_BUFFER &aux_buff) + { + aux_buff.buffer= end_pos; + aux_buff.buffer_end= buff+buff_size; + return 0; + } + + bool prepare_look_for_matches(bool skip_last); + + uchar *get_next_candidate_for_match(); + + bool skip_recurrent_candidate_for_match(uchar *rec_ptr); + + void read_next_candidate_for_match(uchar *rec_ptr); + +public: + + /* + This constructor creates an unlinked BKA join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. + The MRR mode initially is set to 'flags'. + */ + JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags) + { + join= j; + join_tab= tab; + prev_cache= next_cache= 0; + mrr_mode= flags; + } + + /* + This constructor creates a linked BKA join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. The parameter 'prev' specifies the previous + cache object to which this cache is linked. + The MRR mode initially is set to 'flags'. + */ + JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) + { + join= j; + join_tab= tab; + prev_cache= prev; + next_cache= 0; + if (prev) + prev->next_cache= this; + mrr_mode= flags; + } + + uchar **get_curr_association_ptr() { return &curr_association; } + + /* Initialize the BKA cache */ + int init(); + + bool is_key_access() { return TRUE; } + + /* Get the key built over the next record from the join buffer */ + uint get_next_key(uchar **key); + + /* Check index condition of the joined table for a record from BKA cache */ + bool skip_index_tuple(char *range_info); + +}; + + + +/* + The class JOIN_CACHE_BKAH is used when the BKAH join algorithm is + employed to perform a join operation +*/ + +class JOIN_CACHE_BKAH :public JOIN_CACHE_BNLH +{ + +private: + /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ + uint mrr_mode; + + /* + This flag is set to TRUE if the implementation of the MRR interface cannot + handle range association labels and does not return them to the caller of + the multi_range_read_next handler function. E.g. the implementation of + the MRR inteface for the Falcon engine could not return association + labels to the caller of multi_range_read_next. + The flag is set by JOIN_CACHE_BKA::init() and is not ever changed. + */ + bool no_association; + + /* + This field contains the association label returned by the + multi_range_read_next function. + See the function JOIN_CACHE_BKAH::get_curr_key_association() + */ + uchar *curr_matching_chain; + +protected: + + uint get_number_of_ranges_for_mrr() { return key_entries; } + + /* + Initialize the MRR buffer allocating some space within the join buffer. + The entire space between the last record put into the join buffer and the + last key entry added to the hash table is used for the MRR buffer. + */ + int setup_aux_buffer(HANDLER_BUFFER &aux_buff) + { + aux_buff.buffer= end_pos; + aux_buff.buffer_end= last_key_entry; + return 0; + } + + bool prepare_look_for_matches(bool skip_last); + + /* + The implementations of the methods + - get_next_candidate_for_match + - skip_recurrent_candidate_for_match + - read_next_candidate_for_match + are inherited from the JOIN_CACHE_BNLH class + */ + +public: + + /* + This constructor creates an unlinked BKAH join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. + The MRR mode initially is set to 'flags'. + */ + JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags) :JOIN_CACHE_BNLH(j, tab) + { + mrr_mode= flags; + } + + /* + This constructor creates a linked BKAH join cache. The cache is to be + used to join table 'tab' to the result of joining the previous tables + specified by the 'j' parameter. The parameter 'prev' specifies the previous + cache object to which this cache is linked. + The MRR mode initially is set to 'flags'. + */ + JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) + :JOIN_CACHE_BNLH(j, tab, prev) + { + mrr_mode= flags; + } + + uchar **get_curr_association_ptr() { return &curr_matching_chain; } + + /* Initialize the BKAH cache */ + int init(); + + /* Check index condition of the joined table for a record from BKAH cache */ + bool skip_index_tuple(char *range_info); }; @@ -1735,6 +2191,10 @@ public: NULL : join_tab+const_tables; } bool setup_subquery_caches(); + bool shrink_join_buffers(JOIN_TAB *jt, + ulonglong curr_space, + ulonglong needed_space); + private: /** TRUE if the query contains an aggregate function but has no GROUP @@ -1958,7 +2418,6 @@ int report_error(TABLE *table, int error); int safe_index_read(JOIN_TAB *tab); COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value); int test_if_item_cache_changed(List<Cached_item> &list); -void calc_used_field_length(THD *thd, JOIN_TAB *join_tab); int join_init_read_record(JOIN_TAB *tab); void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key); inline Item * and_items(Item* cond, Item *item) diff --git a/storage/innobase/handler/ha_innodb.cc b/storage/innobase/handler/ha_innodb.cc index ebf01fbc296..0e2af4f7b40 100644 --- a/storage/innobase/handler/ha_innodb.cc +++ b/storage/innobase/handler/ha_innodb.cc @@ -6458,6 +6458,7 @@ ha_innobase::info( } stats.check_time = 0; + stats.mrr_length_per_rec= ref_length + 8; // 8 = max(sizeof(void *)); if (stats.records == 0) { stats.mean_rec_length = 0; diff --git a/storage/innodb_plugin/handler/ha_innodb.cc b/storage/innodb_plugin/handler/ha_innodb.cc index 0fc6e786f4c..741848063a6 100644 --- a/storage/innodb_plugin/handler/ha_innodb.cc +++ b/storage/innodb_plugin/handler/ha_innodb.cc @@ -7534,6 +7534,8 @@ ha_innobase::info( } stats.check_time = 0; + stats.mrr_length_per_rec= ref_length + 8; // 8 = max(sizeof(void *)); + if (stats.records == 0) { stats.mean_rec_length = 0; diff --git a/storage/xtradb/handler/ha_innodb.cc b/storage/xtradb/handler/ha_innodb.cc index 02b68357418..8b99586232f 100644 --- a/storage/xtradb/handler/ha_innodb.cc +++ b/storage/xtradb/handler/ha_innodb.cc @@ -7639,6 +7639,7 @@ ha_innobase::info( } stats.check_time = 0; + stats.mrr_length_per_rec= ref_length + 8; // 8 = max(sizeof(void *)); if (stats.records == 0) { stats.mean_rec_length = 0; |