[MDEV-17511] Improve performance for ORDER BY with a CHAR(N) CHARACTER SET utf8_unicode_ci Created: 2018-10-21  Updated: 2018-10-21  Resolved: 2018-10-21

Status: Closed
Project: MariaDB Server
Component/s: Character Sets
Fix Version/s: 10.4.0

Type: Task Priority: Major
Reporter: Alexander Barkov Assignee: Alexander Barkov
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Blocks
blocks MDEV-16413 test performance of distinct range qu... Closed

 Description   

Note, this problem is repeatable with all UCA collations with PAD SPACE attribute. This MDEV uses utf8_uncide_ci as an example for explanation.

There is a bottleneck in these functions:

  • my_uca_strnxfrm_no_contractions_utf8mb3
  • my_uca_strnxfrm_onelevel_internal_no_contractions_utf8mb3
    called from Field_string::sort_string() in this scenario:

CREATE OR REPLACE TABLE t1 (a CHAR(10) CHARACTER SET utf8 COLLATE utf8_unicode_ci);
 
INSERT INTO t1 VALUES ('a'),('b'),('c'),('d');
 
SELECT * FROM t1 ORDER BY a;

Generating weights for trailing spaces (which almost always present in case of CHAR) seems to be CPU hungry.
my_uca_strnxfrm_onelevel_internal_no_contractions_utf8mb3() scans trailing spaces as normal characters and so it calls my_uca_scanner_next_no_contractions_utf8mb3() for every trailing space and then calculate its weight using UCA weights.

It should be faster to trip trailing spaces in my_uca_strnxfrm_no_contractions_utf8mb3() before calling my_uca_strnxfrm_onelevel_internal_no_contractions_utf8mb3(). If we because of this change return a too short key, the caller will append weights for implicit spaces anyway, up to the desired key size. This will effectively generate exactly the same sortable key result.

Appending weights for implicit spaces is much less CPU hungry that a loop with scanner_next calls.

 Comments   
Comment by Alexander Barkov [ 2018-10-21 ] 

DROP TABLE IF EXISTS t1;
 
CREATE TABLE t1 (pk SERIAL, field CHAR(120) CHARACTER SET utf8 COLLATE utf8_unicode_ci);
 
INSERT INTO t1 (field) VALUES ('a'),('b'),('c'),('d');
 
INSERT t1 (field)
 
WITH  RECURSIVE int_seq AS (
 
  SELECT 1 AS val
 
  UNION ALL
 
  SELECT val + 1
 
  FROM int_seq
 
  WHERE val < 1000
 
) SELECT 'a' FROM int_seq;
 
 
 
DROP PROCEDURE IF EXISTS p1;
 
DELIMITER $$
 
CREATE PROCEDURE p1()
 
BEGIN
 
  DECLARE a INT DEFAULT 100000;
 
  WHILE (a > 0)
 
  DO
 
    SELECT DISTINCT field INTO @a FROM t1 WHERE pk BETWEEN 1 AND 11 ORDER BY field LIMIT 1;
 
    SET a=a-1;
 
  END WHILE;
 
END;
 
$$
 
DELIMITER ;
 
CALL p1;

  • 9.37 sec - MariaDB-10.4 before MDEV-17511
  • 8.75 sec - MariaDB-10.4 after MDEV-17511
  • 8.30 sec - MySQL-8.0

SET NAMES utf8 COLLATE utf8_unicode_ci;
 
SET @a=CONCAT('a', REPEAT(' ',359));
 
SELECT BENCHMARK(500000, WEIGHT_STRING(@a,1024,960,128));

Generated at Thu Feb 08 08:37:00 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.