Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-34352

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

Details

    • Bug
    • Status: Closed (View Workflow)
    • Critical
    • Resolution: Duplicate
    • 10.5, 10.6, 10.11, 11.1(EOL), 11.2(EOL), 11.4, 11.5(EOL), 11.6(EOL)
    • N/A
    • Character Sets

    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;
      

      or

      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

        Issue Links

          Activity

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

            bar Alexander Barkov added a comment - Changing to Critical, as utf8mb4 is going to be the default character set starting from 11.6.

            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.

            psergei Sergei Petrunia added a comment - 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.

            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.

            psergei Sergei Petrunia added a comment - 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.

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

            psergei Sergei Petrunia added a comment - This seems to be "by design" of Join Buffer code.
            bar Alexander Barkov added a comment - - 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.

            bar Alexander Barkov added a comment - - 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.
            bar Alexander Barkov added a comment - - 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)
            bar Alexander Barkov added a comment - - 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)

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

            bar Alexander Barkov added a comment - As the character set specific problem was solved, all further work should be done under terms of MDEV-34427 .

            People

              bar Alexander Barkov
              lstartseva Lena Startseva
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Git Integration

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