[MDEV-7474] Semi-Join's DuplicateWeedout strategy skipped for some values of optimizer_search_depth - JIRA

Details

Type: Bug
Status: Closed
Priority: Major
Resolution: Fixed
Affects Version/s: 10.0.15, 5.5.41
Fix Version/s: 10.0.18, 5.5.43
Component/s: Optimizer
Labels:
- optimizer
Environment:
Linux

Description

When "semijoin" is enabled via "optimizer_switch", data can be duplicated with certain values of "optimizer_search_depth".

According to this documentation page:

https://mariadb.com/kb/en/mariadb/documentation/managing-mariadb/optimization-and-tuning/query-optimizations/optimization-strategies/duplicateweedout-strategy/

A DuplicateWeedout strategy is supposed to be implemented using temporary tables for semijoin queries. For some values of "optimizer_search_depth", this duplicate weedout step may not occur.

Attached is the following:

optimizer_search_depth_semijoin_data_setup.sql - A script that sets up a database and a few tables.

optimizer_search_depth_semijoin_query_test.sql - A script that queries the tables to demonstrate the problem.

optimizer_search_depth_semijoin_output.txt - Example execution of the scripts and their output.

Gliffy Diagrams

Attachments

Options
- Sort By Name
- Sort By Date
- Ascending
- Descending
- Thumbnails
- List
- Download All

Attachments

optimizer_search_depth_semijoin_data_setup.sql
1 kB
2015-01-19 15:26
optimizer_search_depth_semijoin_output.txt
3 kB
2015-01-19 15:26
optimizer_search_depth_semijoin_query_test.sql
4 kB
2015-01-19 15:26

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

Elena Stepanova added a comment - 2015-01-21 16:00

Thanks for the report and the test case.
Reproducible as described.

test_type
semijoin=ON, optimizer_search_depth=1
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	T3_0_	ref	PRIMARY,FK_T3_T2Id	PRIMARY	8	const	3	Using index
1	PRIMARY	T2_1_	eq_ref	PRIMARY,FK_T2_T1Id	PRIMARY	8	semijoin_test.T3_0_.T2IdRef	1	
1	PRIMARY	T1_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T2_1_.T1IdRef	1	Using index
1	PRIMARY	T2_0_	ref	FK_T2_T1Id	FK_T2_T1Id	8	semijoin_test.T2_1_.T1IdRef	1	Using index
T1IdRef	T2Id
200001	200011
200001	200012
200001	200013
200001	200011
200001	200012
200001	200013
200001	200011
200001	200012
200001	200013

test_type
semijoin=ON, optimizer_search_depth=3
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	T3_0_	ref	PRIMARY,FK_T3_T2Id	PRIMARY	8	const	3	Using index; Start temporary
1	PRIMARY	T2_1_	eq_ref	PRIMARY,FK_T2_T1Id	PRIMARY	8	semijoin_test.T3_0_.T2IdRef	1	
1	PRIMARY	T1_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T2_1_.T1IdRef	1	Using index
1	PRIMARY	T2_0_	ref	FK_T2_T1Id	FK_T2_T1Id	8	semijoin_test.T2_1_.T1IdRef	1	Using index; End temporary
T1IdRef	T2Id
200001	200011
200001	200012
200001	200013

test_type
semijoin=OFF, optimizer_search_depth=1
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	T2_0_	index	NULL	FK_T2_T1Id	8	NULL	27	Using where; Using index
2	MATERIALIZED	T3_0_	ref	PRIMARY,FK_T3_T2Id	PRIMARY	8	const	3	Using index
2	MATERIALIZED	T2_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T3_0_.T2IdRef	1	
2	MATERIALIZED	T1_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T2_1_.T1IdRef	1	Using index
T1IdRef	T2Id
200001	200011
200001	200012
200001	200013

test_type
semijoin=OFF, optimizer_search_depth=3
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	T2_0_	index	NULL	FK_T2_T1Id	8	NULL	27	Using where; Using index
2	MATERIALIZED	T3_0_	ref	PRIMARY,FK_T3_T2Id	PRIMARY	8	const	3	Using index
2	MATERIALIZED	T2_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T3_0_.T2IdRef	1	
2	MATERIALIZED	T1_1_	eq_ref	PRIMARY	PRIMARY	8	semijoin_test.T2_1_.T1IdRef	1	Using index
T1IdRef	T2Id
200001	200011
200001	200012
200001	200013

Show

Elena Stepanova added a comment - 2015-01-21 16:00 Thanks for the report and the test case. Reproducible as described. test_type semijoin=ON, optimizer_search_depth=1 id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY T3_0_ ref PRIMARY,FK_T3_T2Id PRIMARY 8 const 3 Using index 1 PRIMARY T2_1_ eq_ref PRIMARY,FK_T2_T1Id PRIMARY 8 semijoin_test.T3_0_.T2IdRef 1 1 PRIMARY T1_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T2_1_.T1IdRef 1 Using index 1 PRIMARY T2_0_ ref FK_T2_T1Id FK_T2_T1Id 8 semijoin_test.T2_1_.T1IdRef 1 Using index T1IdRef T2Id 200001 200011 200001 200012 200001 200013 200001 200011 200001 200012 200001 200013 200001 200011 200001 200012 200001 200013 test_type semijoin=ON, optimizer_search_depth=3 id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY T3_0_ ref PRIMARY,FK_T3_T2Id PRIMARY 8 const 3 Using index; Start temporary 1 PRIMARY T2_1_ eq_ref PRIMARY,FK_T2_T1Id PRIMARY 8 semijoin_test.T3_0_.T2IdRef 1 1 PRIMARY T1_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T2_1_.T1IdRef 1 Using index 1 PRIMARY T2_0_ ref FK_T2_T1Id FK_T2_T1Id 8 semijoin_test.T2_1_.T1IdRef 1 Using index; End temporary T1IdRef T2Id 200001 200011 200001 200012 200001 200013 test_type semijoin=OFF, optimizer_search_depth=1 id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY T2_0_ index NULL FK_T2_T1Id 8 NULL 27 Using where; Using index 2 MATERIALIZED T3_0_ ref PRIMARY,FK_T3_T2Id PRIMARY 8 const 3 Using index 2 MATERIALIZED T2_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T3_0_.T2IdRef 1 2 MATERIALIZED T1_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T2_1_.T1IdRef 1 Using index T1IdRef T2Id 200001 200011 200001 200012 200001 200013 test_type semijoin=OFF, optimizer_search_depth=3 id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY T2_0_ index NULL FK_T2_T1Id 8 NULL 27 Using where; Using index 2 MATERIALIZED T3_0_ ref PRIMARY,FK_T3_T2Id PRIMARY 8 const 3 Using index 2 MATERIALIZED T2_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T3_0_.T2IdRef 1 2 MATERIALIZED T1_1_ eq_ref PRIMARY PRIMARY 8 semijoin_test.T2_1_.T1IdRef 1 Using index T1IdRef T2Id 200001 200011 200001 200012 200001 200013

4 older comments

Hide

Permalink

Sergei Petrunia added a comment - 2015-03-13 17:48

Pushed a patch into https://github.com/MariaDB/server/tree/bb-10.0-mdev7474 . I'll need testing from Elena Stepanova.

Show

Sergei Petrunia added a comment - 2015-03-13 17:48 Pushed a patch into https://github.com/MariaDB/server/tree/bb-10.0-mdev7474 . I'll need testing from Elena Stepanova .

Hide

Permalink

Elena Stepanova added a comment - 2015-03-17 01:49

Ran a set of tests, got several hundred of mismatches between the patched version and baseline 10.0 (low optimizer_search_depth values). All differences look legit, related to the bugfix, so the good news is that tests hit the right spot; but due to the sheer amount of mismatches it's unrealistic to check each one separately.
Next step – I'll run a similar test, but between the patched version with low optimizer_search_depth and baseline 10.0 with normal optimizer_search_depth. The expectation is that there should be no mismatches.

On a separate note, I wonder if the commit comment is correct:

JOIN::cur_dups_producing_tables was not maintained correctly in
the cases of greedy optimization (search_depth > n_tables).

Is it not the other way round, search-depth < n_tables?

Show

Elena Stepanova added a comment - 2015-03-17 01:49 Ran a set of tests, got several hundred of mismatches between the patched version and baseline 10.0 (low optimizer_search_depth values). All differences look legit, related to the bugfix, so the good news is that tests hit the right spot; but due to the sheer amount of mismatches it's unrealistic to check each one separately. Next step – I'll run a similar test, but between the patched version with low optimizer_search_depth and baseline 10.0 with normal optimizer_search_depth. The expectation is that there should be no mismatches. On a separate note, I wonder if the commit comment is correct: JOIN::cur_dups_producing_tables was not maintained correctly in the cases of greedy optimization (search_depth > n_tables). Is it not the other way round, search-depth < n_tables?

Hide

Permalink

Elena Stepanova added a comment - 2015-03-17 12:25

The second run went okay. I will also try valgrind tests, but please go ahead and push (we need to decide first whether it's for 5.5 or 10.0).

Show

Elena Stepanova added a comment - 2015-03-17 12:25 The second run went okay. I will also try valgrind tests, but please go ahead and push (we need to decide first whether it's for 5.5 or 10.0).

Hide

Permalink

Sergei Petrunia added a comment - 2015-03-17 15:39

Considering the nature of the fix, it should be 5.5

Show

Sergei Petrunia added a comment - 2015-03-17 15:39 Considering the nature of the fix, it should be 5.5

Hide

Permalink

Sergei Petrunia added a comment - 2015-03-17 15:39

Pushed into 5.5 tree

Show

Sergei Petrunia added a comment - 2015-03-17 15:39 Pushed into 5.5 tree

Semi-Join's DuplicateWeedout strategy skipped for some values of optimizer_search_depth

Details

Description

Gliffy Diagrams

Attachments

Attachments

Activity

People

Dates

Agile