[MCOL-4753] Performance problem in Typeless join Created: 2021-06-08  Updated: 2021-06-10  Resolved: 2021-06-10

Status: Closed
Project: MariaDB ColumnStore
Component/s: PrimProc
Affects Version/s: 6.1.1
Fix Version/s: 6.1.1

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

Issue Links:
Relates
relates to MCOL-4173 Support JOINs wide-DECIMAL keys. Closed
relates to MCOL-4755 Allow joins on all numeric data type ... Open

 Description   

Joins involving string data types are implemented using so called Typeless join.

The idea is the following:

  • 1. ExeMgr iterates rows in the small side RowGroup and pack them into "Typeless" representation (i.e. column values written in a single byte array).
  • 2. ExeMgr sends Typeless row representations over the network to PrimProc.
  • 3. PrimProc receives the small side row Typeless prepresentations and feeds them into a hash table.
  • 4. PrimProc iterates through the large side RowGroup, converts every row into Typeless representation again, and searches this Typeless row representation in the hash table. So the large side row is included into the join result set if it is found in the hash table populated by the small side rows.

The 4th step is a problem. There is no sense to convert the large side from RowGroup/Row format into Typeless format. It's possible to use the Row representation directly.

The underlying hash and comparison routines should be extended to understand both Typeless and Row formats. So PrimProc can:

  • Calculate the hash of the large side row directly on its Row representation
  • Compare the small side Typeless representation directly to the large side Row representation

This change will be done on the PrimProc side. ExeMgr most likely won't change its behaviour in any ways.

 Comments   
Comment by Alexander Barkov [ 2021-06-10 ]

A script to measure the performance:

SET @length=64;
 
DROP TABLE IF EXISTS t1,t2;
 
SET default_storage_engine=ColumnStore;
 
EXECUTE IMMEDIATE REPLACE('CREATE TABLE t1 (a VARCHAR(XLENGTH))','XLENGTH',@length);
 
EXECUTE IMMEDIATE REPLACE('CREATE TABLE t2 (a VARCHAR(XLENGTH))','XLENGTH',@length);
 
INSERT INTO t1 VALUES (REPEAT('a',@length));
 
INSERT INTO t1 VALUES (REPEAT('b',@length));
 
INSERT INTO t1 VALUES (REPEAT('c',@length));
 
INSERT INTO t1 VALUES (REPEAT('d',@length));
 
INSERT INTO t1 VALUES (REPEAT('e',@length));
 
INSERT INTO t1 VALUES (REPEAT('f',@length));
 
INSERT INTO t1 VALUES (REPEAT('g',@length));
 
INSERT INTO t1 VALUES (REPEAT('i',@length));
 
INSERT INTO t2 SELECT * FROM t1;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
INSERT INTO t2 SELECT * FROM t2;
 
 
 
SELECT MAX(t1.a) FROM t1,t2 WHERE t1.a=t2.a;

Comment by Alexander Barkov [ 2021-06-10 ]

The patch in PR#1983 demonstrates the following performance improvement:

  • 10% on VARCHAR(16)
  • 15% on VARCHAR(128)

The SELECT query was tested with help of sysbench with this command:

sysbench join.lua  --skip_trx --threads=10 --events=1000 --histogram --time=600 run

Generated at Thu Feb 08 02:52:43 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.