Mysql binary tree select query optimization

Question

I have a accounts table. every account creation I am pushing treeRight id and treeLeft id into account_device_tree table.

Now I have more than 10M accounts under first parent account. when I select all the subaccouts it is taking more than a min to execute.

my query is given below

select * 
FROM
    accounts acc 
        JOIN
    account_device_tree ON acc.tree_id = account_device_tree.tree_id
WHERE
(acc.account_id = 1 OR (account_device_tree.tree_left >= 1 AND account_device_tree.tree_right <= 748534))

I need to optimize as much as possible.

schema of account_device_tree

CREATE TABLE `account_device_tree` (
  `tree_id` int(11) NOT NULL AUTO_INCREMENT,
  `tree_left` int(11) NOT NULL,
  `tree_right` int(11) NOT NULL,
  PRIMARY KEY (`tree_id`),
  KEY `tree_left` (`tree_left`),
  KEY `tree_right` (`tree_right`)
) ENGINE=InnoDB AUTO_INCREMENT=388173 DEFAULT CHARSET=latin1

accounts table Schema

 CREATE TABLE `accounts` (
  `account_id` int(11) NOT NULL AUTO_INCREMENT,
  `parent_id` int(11) NOT NULL,
  `name` varchar(64) NOT NULL,
  `tree_id` int(11) NOT NULL,
  PRIMARY KEY (`account_id`),
  UNIQUE KEY `tree_id` (`tree_id`),
  KEY `name` (`name`),
  KEY `idx_parent_id` (`parent_id`)
) ENGINE=InnoDB AUTO_INCREMENT=389739 DEFAULT CHARSET=latin1

What indexes do you have if any? ad.account_id, account_user_device_tree.tree_left, account_user_device_tree.tree_right should have indexes, as should your joined fields treeid unles already a PK — jimmy8ball
– jimmy8ball, Commented Jun 14, 2019 at 13:10
Also please confirm which DBMS you are using so other users can assist, you have declared both MySQL and Postgresql — jimmy8ball
– jimmy8ball, Commented Jun 14, 2019 at 13:14
accounts table tree_id is a index and account_user_device_tree table tree_left and tree_right colums are indexed — Padmanathan J
– Padmanathan J, Commented Jun 14, 2019 at 13:15
you need to generate a query execution plan when you execute the query, this will give you an idea where its hanging — jimmy8ball
– jimmy8ball, Commented Jun 14, 2019 at 13:15

Rick James · Accepted Answer · 2019-06-15 18:42:58Z

1

Hard to suggest something without table structures and query plan.. But rewritting the query into UNION ALL instead of using OR tends to optimize beter assuming the correct indexes are in the table.

select * 
FROM
    accounts acc 
        JOIN
    account_user_device_tree ON acc.tree_id = account_user_device_tree.tree_id
WHERE
  acc.account_id = 1 

UNION ALL

select * 
FROM
    accounts acc 
        JOIN
    account_user_device_tree ON acc.tree_id = account_user_device_tree.tree_id
WHERE
   account_user_device_tree.tree_left >= 1
 AND
  account_user_device_tree.tree_right <= 748534

edited Jun 15, 2019 at 18:42

Rick James

144k15 gold badges144 silver badges255 bronze badges

answered Jun 14, 2019 at 13:20

Raymond Nijland

11.6k2 gold badges26 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Rick James Over a year ago

INDEX(tree_left, tree_right, tree_id) and (presumably) PRIMARY KEY(account_id)?

Raymond Nijland Over a year ago

But @NathanSrivi for a better answer (if you still need it) you should provide all table structures not just one.

Padmanathan J Over a year ago

@RaymondNijland I have added account table schema. account_user_device_tree table name I updated to account_device_tree

Raymond Nijland Over a year ago

iám pretty sure you have manually changed/wrote the create table statements.. @NathanSrivi as there are syntax errors all over, use SHOW CREATE TABLE table .. if need to edit make sure you test these CREATE TABLE statements.

Collectives™ on Stack Overflow

Mysql binary tree select query optimization

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related