[MDEV-34352] Execution time for Block Nested Loop Hash (BNLH) join with charset utf8mb4 is 7-20 times slower than with latin1 - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Critical
Resolution: Duplicate
Affects Version/s: 10.5, 10.6, 10.11, 11.1(EOL), 11.2(EOL), 11.4, 11.5(EOL), 11.6(EOL)
Fix Version/s: N/A
Component/s: Character Sets
Labels:
- bnlh

Description

2024-06-21 Update

This issue appeared to be a combination of two problems:

~~MDEV-34417~~ Wrong result set with utf8mb4_danish_ci and BNLH join
MDEV-34427 BNL-H has not optimal implementation for varchar type

All further work will be done under terms of the above two tickets.

The original report

Testcase:
1. Enable Block Nested Loop Hash (BNLH):

set join_cache_level =3;

2. Variables join_buffer_size and join_buffer_space_limit were used with default value (They can be changed, but the difference in execution time will still remain)

+-------------------------+----------------------+

| Variable_name           | Value                |

+-------------------------+----------------------+

| join_buffer_size        | 262144               |

| join_buffer_space_limit | 2097152              |

+-------------------------+----------------------+

3. Create table with charset=latin1 or charset=utf8mb4:

CREATE TABLE t1(col1 VARCHAR(500)) engine=INNODB character set latin1 collate latin1_swedish_ci;

CREATE TABLE t2(col2 VARCHAR(500)) engine=INNODB character set latin1 collate latin1_swedish_ci;

CREATE TABLE t1(col1 VARCHAR(500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci;

CREATE TABLE t2(col2 VARCHAR(500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci;

4. Fill out the tables

insert into t1 select  FLOOR(1 + (RAND() * 200000)) from seq_1_to_200000;

insert into t2 select  FLOOR(1 + (RAND() * 20000)) from seq_1_to_200000;

5. Execute the query:

select max(A.col1) from t1 A, t2 B where A.col1=B.col2;

Results for v. 11.6:
Debug build:

latin1	utf8mb4
7 min 6,426 sec	54 min 2,303 sec

Release build:

latin1	utf8mb4
17,266 sec	8 min 21,989 sec

The results of statistics collected using perf are also attached to the task.

Attachments

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

mariadb_11.5_latin1_flamegraph_2.svg
585 kB
2024-06-10 16:07
mariadb_11.5_utf8_flamegraph.svg
257 kB
2024-06-10 16:07

Issue Links

duplicates

MDEV-34417 Wrong result set with utf8mb4_danish_ci and BNLH join

Closed

MDEV-34427 BNL-H has not optimal implementation for varchar type

Open

relates to

MDEV-19123 Change default charset from latin1 to utf8mb4

Closed

MDEV-34232 Check performance of BNL-H vs MySQL's hash join

Open

MDEV-34417 Wrong result set with utf8mb4_danish_ci and BNLH join

Closed

MDEV-34427 BNL-H has not optimal implementation for varchar type

Open

(1 relates to)

Activity

Ascending order - Click to sort in descending order

Alexander Barkov added a comment - 2024-06-13 04:52

Changing to Critical, as utf8mb4 is going to be the default character set starting from 11.6.

Alexander Barkov added a comment - 2024-06-13 04:52 Changing to Critical, as utf8mb4 is going to be the default character set starting from 11.6.

Sergei Petrunia added a comment - 2024-06-20 07:47

Looking at ANALYZE FORMAT=JSON output, I see the difference in block-nl-join.r_loops time.
in the "short" case it is 41, in the "long" 158. block-nl-join.buffer_size is nearly the same. This means that for some reason, the "long" case is using much more buffer space.

Sergei Petrunia added a comment - 2024-06-20 07:47 Looking at ANALYZE FORMAT=JSON output, I see the difference in block-nl-join.r_loops time. in the "short" case it is 41, in the "long" 158. block-nl-join.buffer_size is nearly the same. This means that for some reason, the "long" case is using much more buffer space.

Sergei Petrunia added a comment - 2024-06-20 07:52

Indeed, the BNL-H join has "non-embedded keys" (check JOIN_CACHE::check_emb_key_usage()). If we are joining a varchar(100) column, the join buffer record for it WILL include space for 100 characters (lookup tuple in KeyTupleFormat), even if the joined values are much shorter.

Sergei Petrunia added a comment - 2024-06-20 07:52 Indeed, the BNL-H join has "non-embedded keys" (check JOIN_CACHE::check_emb_key_usage()). If we are joining a varchar(100) column, the join buffer record for it WILL include space for 100 characters (lookup tuple in KeyTupleFormat), even if the joined values are much shorter.

Sergei Petrunia added a comment - 2024-06-20 07:53

This seems to be "by design" of Join Buffer code.

Sergei Petrunia added a comment - 2024-06-20 07:53 This seems to be "by design" of Join Buffer code.

Alexander Barkov added a comment - 2024-06-20 08:40 - edited

Even if the underlying low-level algorithm heavily replies on the fixed length nature of the records, the performance degradation on multi-byte character sets can still be avoided:

It could be refactored to have buckets, at least two:

one bucket for lengths 0..MAX_CHAR_LENGTH octets
another bucket for lengths MAX_CHAR_LENGTH+1 .. MAX_OCTET_LENGTH

E.g. in case of *{VARCHAR(100) CHARACTER SET utf8mb4}}

one bucket for 0..100 bytes
another bucket for 100...400 bytes

Or even have more buckets:

0..100 bytes
101..200 bytes
201..300 bytes
301..400 bytes

Or even yet more buckets with a higher length granularity.

Alexander Barkov added a comment - 2024-06-20 08:40 - edited Even if the underlying low-level algorithm heavily replies on the fixed length nature of the records, the performance degradation on multi-byte character sets can still be avoided: It could be refactored to have buckets, at least two: one bucket for lengths 0..MAX_CHAR_LENGTH octets another bucket for lengths MAX_CHAR_LENGTH+1 .. MAX_OCTET_LENGTH E.g. in case of * {VARCHAR(100) CHARACTER SET utf8mb4}} one bucket for 0..100 bytes another bucket for 100...400 bytes Or even have more buckets: 0..100 bytes 101..200 bytes 201..300 bytes 301..400 bytes Or even yet more buckets with a higher length granularity.

Alexander Barkov added a comment - 2024-06-20 14:18 - edited

Timings after the fix for ~~MDEV-34417~~:

CREATE OR REPLACE TABLE t1(col1 VARCHAR(500)) engine=INNODB character set latin1 collate latin1_swedish_ci;

CREATE OR REPLACE TABLE t2(col2 VARCHAR(500)) engine=INNODB character set latin1 collate latin1_swedish_ci;

insert into t1 select  FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000;

insert into t2 select  FLOOR(1 + (RAND() * 20000))  from seq_1_to_20000;

set join_cache_level=3;

select max(A.col1) from t1 A, t2 B where A.col1=B.col2;

1 row in set (0.222 sec)

CREATE OR REPLACE TABLE t1(col1 VARCHAR(500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci;

CREATE OR REPLACE TABLE t2(col2 VARCHAR(500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci;

insert into t1 select  FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000;

insert into t2 select  FLOOR(1 + (RAND() * 20000))  from seq_1_to_20000;

set join_cache_level=3;

select max(A.col1) from t1 A, t2 B where A.col1=B.col2;

1 row in set (0.995 sec)

CREATE OR REPLACE TABLE t1(col1 VARCHAR(2000)) engine=INNODB character set latin1 collate latin1_swedish_ci;

CREATE OR REPLACE TABLE t2(col2 VARCHAR(2000)) engine=INNODB character set latin1 collate latin1_swedish_ci;

insert into t1 select  FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000;

insert into t2 select  FLOOR(1 + (RAND() * 20000))  from seq_1_to_20000;

set join_cache_level=3;

select max(A.col1) from t1 A, t2 B where A.col1=B.col2;

1 row in set (0.823 sec)

Observation:

VARCHAR(500) CHARACTER SET utf8mb4 (2000 octets max) is now only 18% slower than the same binary size VARCHAR(2000) CHARACTER SET latin1 (2000 octets max)

Alexander Barkov added a comment - 2024-06-20 14:18 - edited Timings after the fix for MDEV-34417 : CREATE OR REPLACE TABLE t1(col1 VARCHAR (500)) engine=INNODB character set latin1 collate latin1_swedish_ci; CREATE OR REPLACE TABLE t2(col2 VARCHAR (500)) engine=INNODB character set latin1 collate latin1_swedish_ci; insert into t1 select FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000; insert into t2 select FLOOR(1 + (RAND() * 20000)) from seq_1_to_20000; set join_cache_level=3; select max (A.col1) from t1 A, t2 B where A.col1=B.col2; 1 row in set (0.222 sec) CREATE OR REPLACE TABLE t1(col1 VARCHAR (500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci; CREATE OR REPLACE TABLE t2(col2 VARCHAR (500)) engine=INNODB character set utf8mb4 collate utf8mb4_general_ci; insert into t1 select FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000; insert into t2 select FLOOR(1 + (RAND() * 20000)) from seq_1_to_20000; set join_cache_level=3; select max (A.col1) from t1 A, t2 B where A.col1=B.col2; 1 row in set (0.995 sec) CREATE OR REPLACE TABLE t1(col1 VARCHAR (2000)) engine=INNODB character set latin1 collate latin1_swedish_ci; CREATE OR REPLACE TABLE t2(col2 VARCHAR (2000)) engine=INNODB character set latin1 collate latin1_swedish_ci; insert into t1 select FLOOR(1 + (RAND() * 200000)) from seq_1_to_20000; insert into t2 select FLOOR(1 + (RAND() * 20000)) from seq_1_to_20000; set join_cache_level=3; select max (A.col1) from t1 A, t2 B where A.col1=B.col2; 1 row in set (0.823 sec) Observation: VARCHAR(500) CHARACTER SET utf8mb4 (2000 octets max) is now only 18% slower than the same binary size VARCHAR(2000) CHARACTER SET latin1 (2000 octets max)

Alexander Barkov added a comment - 2024-06-21 05:42

As the character set specific problem was solved, all further work should be done under terms of MDEV-34427.

Alexander Barkov added a comment - 2024-06-21 05:42 As the character set specific problem was solved, all further work should be done under terms of MDEV-34427 .

People

Assignee:: Alexander Barkov

Reporter:: Lena Startseva

Votes:: 0 Vote for this issue

Watchers:: 3 Start watching this issue

Dates

Created:: 2024-06-10 16:16

Updated:: 2024-06-21 05:46

Resolved:: 2024-06-21 05:42

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server

Details

Description

2024-06-21 Update

The original report

Attachments

Attachments

Issue Links

Activity

People

Dates

Git Integration