P A R A L L E L U N I V E R S E Technology White Paper - MySQL Query Execution using Multiple Threads 1. Motivation for the New Technology Today microprocessors which provide computational resource to RDBMS (Relational Data Base Management System) contain multiple CPU cores where each core is capable of executing its own code independently. If RDBMS server (hereafter referred as the server) can break down its task into a number of smaller subtasks then these subtasks may be performed by those multiple cores concurrently resulting in faster execution. This new technology speeds up the execution phase of query tasks. 2. Background Information MySQL query determines combinations of records from given tables which satisfy a given condition. SELECT field_list FROM table_list WHERE condition; where field_list represents fields from the tables to be output, each table consists of a number of records and each record is comprised of a number of fields(attributes) and the condition specifies field relationships. The server parses and translates the query into the optimum query execution plan which specifies a order by which the tables are processed, how records are read from the tables, conditions which must be satisfied by these records and process/output record method. Current Technology (All operations carried out by a single thread) --- Optimization Phase ---- ------------------ Execution Phase ----------------- | | | | | | ---------- ----------- --------- | | Table Order | | | #Process| Query --> | Parse & | --Table Access Methods--> | Execute | --Record--> | Records | --> Result | Optimize | Record Match Conds | *Thread 1 | Combo | Thread 1| -------- ----------- --------- #Process Record Method | | ------------------------ Query Execution Plan *Thread is a flow of code execution scheduled by the host operating system to run on a particular core of the CPU. New Technology This new technology provides multiple (n) threads execution of this plan. ------------------ Execution Phase ----------------- | | | | ----------- --------- Table Order | | | Process | Table Access Methods--> | Execute | --Record--> | Records | --> Result Record Match Conds |Threads 1~n| Combo | Thread n| ----------- --------- Process Record Method 3. Current Technology, example with 3 tables, recursive execution by one thread 1st table(t1) Read a record (may use an index) and store (used fields only) and if it satisfies the condition associated with this table then move down to the next table otherwise continue reading records when there is no more record to read, the procedure is finished. 2nd table(t2) Read a record (may use an index derived from record of t1) and if it satisfies the condition associated with this table which depends on records from this table and t1 then move down to the next table otherwise continue reading records when there is no more record to read, move back up to the previous table. Last table(t3) Read a record (may use an index derived from records of t2 and t1) and if it satisfies the condition associated with this table which depends on records from this table, t2 and t1 then process and output this particular combination of records according to the process record method of the query execution plan in any case continue reading records when there is no more record to read, move back up to the previous table. Disk Storage ------------------ | | | | ---------------------------- | | | | | | | | | | | Processing of | | | | t1 | | | | (by thread 1) | | | | | | ---------- | | record | | | | | | ----- ------ | read | | | | | |cond | <-- | | | <---------- | | t1 | | | ----- ------ | | | | | | | | | | | ---------------------------- | ---------- | | | | | | | ---------------------------- | | | | | | | | | | | Processing of | | | | t2 | | | | 1 (by thread 1) | | | | | | | ---------- | | V record | | | | | | ----- ------ | read | | | | | |cond | <-- | | | <---------- | | t2 | | | ----- ------ | | | | | | | | | | | ---------------------------- | ---------- | 1 represents a record of t1 | | | | | | ---------------------------- | | | | | | | | | | | Processing of | | | | t3 | | | | 2 1 (by thread 1) | | | | | | | | ---------- | | V V record | | | | | | ----- ------ | read | | | | | |cond | <-- | | | <---------- | | t3 | | | ----- ------ | | | | | | | | | | | ---------------------------- | ---------- | 2 represents a record of t2 | | | | | | | | | | ------------------ 4. New Technology, same example, execution by 3 threads 1st table(t1, executed by thread 1) Read a record and if it satisfies the condition then insert this record into inter table buffer between this table and the next (possibly waits in case the buffer is full). Continue reading records when there is no more record to read, processing of this table is finished. 2nd table(t2, executed by thread 2) Wait for a record from t1 to be available in the inter table buffer between this table and the previous, read a record of this table and if it satisfies the condition then insert this record and the record of t1 into the inter table buffer. Continue reading records when there is no more record to read, remove the record of t1 from the buffer and wait for the next record. Last table(t3, executed by thread 3) Wait for a record set of t2 and t1 to be available in the inter table buffer then read a record of this table and if it satisfies the condition then process and output this particular combination of records. Continue reading records when there is no more record to read remove the record set of t2 and t1 from the buffer and wait for the next record set. ---------------------------- | | | | | Processing of | | t1 | | (by thread 1) | | | | record | | ----- ------ | read | |cond | <-- | | | <---------- | ----- ------ | | | ---------------------------- | V Inter Table ----- Buffer | | | | |-----| | 1 | |-----| | 1 | |-----| | 1 | |-----| | 1 | |-----| | 1 | |-----| -- | 1 | | Record Set ----- -- | V ---------------------------- | | | | | Processing of | | t2 | | 1 (by thread 2) | | | | | V record | | ----- ------ | read | |cond | <-- | | | <---------- | ----- ------ | | | ---------------------------- | V ----- | | | | |-----| | 2 | |-----| | 1 | |-----| | 2 | |-----| | 1 | -- |-----| | | 2 | Record Set | |-----| | | 1 | -- ----- | V ---------------------------- | | | | | Processing of | | t3 | | 2 1 (by thread 3) | | | | | | V V record | | ----- ------ | read | |cond | <-- | | | <---------- | ----- ------ | | | ----------------------------