Optimise query

asa_carter

I have the following query but it is slow because of the ORDER BY. There are currently over 450,000 rows in both tables.

Trending bookmarks

SELECT
b.bookmark_id, b.title, b.url, b.created,
(SELECT COUNT(*) FROM bookmark_user bu WHERE bu.bookmark_id = b.bookmark_id AND bu.private = 0 AND bu.user_id > 0) AS user_count
FROM
bookmark b
INNER JOIN
bookmark_user bu ON bu.bookmark_id = b.bookmark_id
WHERE
bu.private = 0
GROUP BY
bu.bookmark_id
ORDER BY
user_count;

Without the "ORDER BY user_count" it executes in 0.008 seconds. When it is ordered it takes over 25 seconds.

How can I optimise this to order by the number of many bookmark_users to one bookmark?

Thanks

johanafm

The query look strange to me. First off, you have one subquery which is counting rows where some bookmark id is equal to a bookmark in the outer query. No matter how many rows you go through, each of those ids are unique (aren't they?), which means the count will be 1 for every single bookmark. Next up, you are not only performing a subquery, but you are also performing an inner join on the exact same condition.

But mainly I'm wondering about what data you are trying to put into each row. Each row contains data about one bookmark so far as id, title, url and created are concerned. What is the count supposed to be a count of?

As far as ordering speed goes, how big is the entire result set and how big is each row? If you are reordering the entire result set and each row is huge, sorting will take longer time since there will be few rows in memory when sorting since each rows need a lot of memory. Perhaps it would be quicker to retrieve ids and COUNT(), reorder that set and perform a join on the ordered set to get the rest of the data.

asa_carter

The table structures are as follows:

bookmark (p key on bookmark_id, unique key on url)

bookmark_id int(11) NOT NULL
title varchar(255) NOT NULL
url varchar(255) NOT NULL
created datetime NOT NULL

bookmark_user (p key combined on bookmark_id and user_id)

bookmark_id int(11) NOT NULL
user_id int(11) NOT NULL
title varchar(255) NOT NULL
private tinyint(1) NOT NULL
notes text NOT NULL
created datetime NOT NULL

So.. bookmark stores a unique list of url's. bookmark_user relates a user to a bookmark, so that bookmark_id and user_id combination will be unique.

so for example

bookmark

1 Google http://www.google.com

bookmark_user

1 1 User 1 title for Google
1 2 User 2 title for Google
1 3 User 3 title for Google

I want to be able to count the number of users that have the related bookmark and also order the results by the highest count.

Hope this makes sense? Maybe I'm going the wrong way about it?

johanafm

SELECT COUNT(*) AS bookmark_user, b.bookmark_id, title, url, created
FROM bookmark_users bu
INNER JOIN bookmark b ON b.bookmark_id = bu.bookmark_id
WHERE bu.private = 0
GROUP BY b.bookmark_id, title, url, created

asa_carter

That seems a more logical solution but I still have issues with speed. If I limit that to 200 results it takes 38 seconds which is much slower than the first query.

SELECT COUNT(*) AS user_count, b.bookmark_id, b.title, b.url, b.created
FROM bookmark_user bu
INNER JOIN bookmark b ON b.bookmark_id = bu.bookmark_id
WHERE bu.private = 0
GROUP BY b.bookmark_id, title, url, created
LIMIT 200;

id	select_type	TABLE	TYPE	possible_keys	KEY	key_len	ref	ROWS	Extra
1	SIMPLE	bu	ALL	PRIMARY	\N	\N	\N	456361	USING WHERE; USING TEMPORARY; USING filesort
1	SIMPLE	b	eq_ref	PRIMARY	PRIMARY	4	dev_clicksave.bu.bookmark_id	1

If I do a describe, there is no key on boomark_user table and it is using temporary.

johanafm

You might want to format your explain output to make it readable. That is, make info line up with their headers so it's possible to see what's what.

Apart from that, if there is no key used from book_user, then you obviouslu havn't added the proper foreign key constraint, which you should.

asa_carter

Ok. I've modified the query a bit. It is working fine for small amounts of data but over thousands of rows it is still very very slow. I'm getting a bit confused about the keys and indexes..... So I'll just list everything...

bookmark

contains a list of unique bookmarks. bookmark_id is unique and auto increments.
url is also unique.

bookmark user

a bookmark can have many users (that save it). bookmark_user maps users to bookmarks. A combination of bookmark_id and user_id are unique. bookmark_user also holds some details about a bookmark that are specific to that user (when they bookmarked it, notes and a custom title).

The SQL:

SELECT COUNT(*) AS user_count, b.bookmark_id, b.title, b.url, b.created
FROM bookmark_user bu
INNER JOIN bookmark b ON b.bookmark_id = bu.bookmark_id
WHERE bu.private = 0
GROUP BY b.bookmark_id
ORDER BY user_count DESC;

The Tables:

CREATE TABLE `bookmark` (
  `bookmark_id` INT(11) NOT NULL AUTO_INCREMENT,
  `title` VARCHAR(255) NOT NULL,
  `url` VARCHAR(255) NOT NULL,
  `created` DATETIME NOT NULL,
  `like` INT(11) NOT NULL,
  `dislike` INT(11) NOT NULL,
  PRIMARY KEY (`bookmark_id`),
  UNIQUE KEY `url` (`url`)
) ENGINE=MYISAM AUTO_INCREMENT=456361 DEFAULT CHARSET=latin1

CREATE TABLE `bookmark_user` (
  `bookmark_id` INT(11) NOT NULL,
  `user_id` INT(11) NOT NULL,
  `title` VARCHAR(255) NOT NULL,
  `private` TINYINT(1) NOT NULL,
  `notes` TEXT NOT NULL,
  `created` DATETIME NOT NULL,
  PRIMARY KEY (`bookmark_id`,`user_id`)
) ENGINE=MYISAM DEFAULT CHARSET=latin1

I have tried adding a FK to bookmark user.

ALTER TABLE bookmark_user
    ADD FOREIGN KEY (bookmark_id) REFERENCES bookmark(bookmark_id);

Then I get: 456361 row(s) affected

... but there doesn't seem to be any change to the strucure???

johanafm

If you successfully added the foreign key and issue another SHOW CREATE TABLE bookmake_user, then you should see something like this listed towards the end of that output

CONSTRAINT bookmark_ibfk_1 FOREIGN KEY (bookmark_id) REFERENCES bookmark(id)

While I belive that you should always use foreign key constraints (for matters of keeping the DB in a consistent state), adding this particular one will do nothing for the speed of that query. You allready have index bookmark_user (bookmark_id, user_id) and bookmark (id), which means that bookmark_id and bookmark (involved in the join) can be used. However, had you instead wanted to join bookmark_user and user you'd have no index in bookmark_user to use, since (bookmark_id, user_id) means you need to start from bookmark_id. It would work for joining those tables if you also specified WHERE bookmark_user.bookmark_id= 2, since the index would then start by looking up indices with bookmark_id = 2 and follow that to user_id indices. Either way, you should add FOREIGN KEY (user_id) REFERENCES user(id).

As for speed, you might gain a little by adding index for bookmark_user(private, bookmark_id). However, indexing on values that are the same for too big subsets of the table don't work very well.

Finally I'm curious about one thing in your explain output above: It says "filesort", yet that should not be present for the query you showed above the explain. Do you actually have an order by clause still present?

asa_carter

The FK does not seem to be created successfully. The output is the following:

CREATE TABLE `bookmark_user` (
 `bookmark_id` int(11) NOT NULL,
 `user_id` int(11) NOT NULL,
 `title` varchar(255) NOT NULL,
 `private` tinyint(1) NOT NULL,
 `notes` text NOT NULL,
 `created` datetime NOT NULL,
 PRIMARY KEY (`bookmark_id`,`user_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1

I have tried adding it in phpmyadmin and sqlyog.

I added an index on (private, bookmark_id) and there was a slight speed improvement. On 456,361 rows, the execution time was reduced from 30 seconds to 19 seconds but this is not acceptable.

Is it possible to improve this query further or will I have to just do a query on bookmark_user and then do another separate query in a loop for every bookmark pragmatically? Without the join, the query executes in 0.001 seconds.

As for the filesort, I ran that explain again and it is using the filesort even though order by is not being used.... I don't know why??

Derokorian

Foreign keys are not available for the MyISAM engine. You would need to use InnoDB to support Foreign Keys in MySQL.

johanafm

Oh, MyISAM. I would consider moving to InnoDB which is much more reliable (just be aware that it doesn't handle full text indexing). But if you stay with MyISAM I'd create an index instead of a foreign key (which is actually an index with some extra functionality) each place where there should have been a foreign key.

Ah well, then the filesorting is due to the group by clause. Perhaps you could improve it a bit further by grouping on less data, namely count() and bookmark_id only, then join in the rest of the data once this has been done.

SELECT user_count, b.bookmark_id, b.title, b.url, b.created
FROM bookmark b
INNER JOIN
(
  SELECT COUNT(*) AS user_count, bookmark_id
  FROM bookmark_user
  WHERE by.private=0
  GROUP BY bookmark_id
) t
ON b.bookmark_id = t.bookmark_id
ORDER BY user_count DESC;

On my little test tables this was about 10x faster.

But your query is taking way longer than I would have expected. I tested a similar query by joining tables with 100k rows and 75k rows respectively. Far less than your 450k table, but my query finished in about 0.07 seconds. As far as I can tell the indexing seems to be ok, but you might want to consider reposting your explain output and format it so that data line up with its headers so it's actually possible to read it.

Should things be ok so far then perhaps you havn't assigned enough resources, such as disk space and RAM to MySQL. And perhaps there are other configuration issues you need to deal with as well. If this is the case, I'd turn to the MySQL forums intead.

jewel86

Thanks asa_carter's question and everyone's answer. they're interesting. information is useful
servsafe.com

asa_carter

Thanks, that's a massive speed improvement. I will stay with myISAM for now though.

Over the 450,000 rows the query still executed in a similar time. In production the results will also paginated.

I also need to enhance this query further with a join on two more tables relating to tags within the bookmark.

tag is a list of unique tags. bookmark_tag relates a tag to a bookmark and user.

bookmark_tag
bookmark_id
user_id
tag_id

tag
tag_id
tag

At the moment with the join I have the query is executed in 12 seconds when limited to 200 but I am going to have a shot at trying to optimize it.

I'd also like to sort the results by the number of occurrences of tags before the user_count. I'm wondering whether this going to use too much load and I should store the results in an array and sort that instead of doing it all in mysql?

asa_carter

I haven't managed to get it working quickly by joining the tag tables.

The query on its own below works ok but by combining it with the existing query slows everything down.

SELECT bt.bookmark_id, t.tag_id, COUNT(*) AS tag_count
FROM bookmark_tag bt
LEFT JOIN tag t ON bt.tag_id = t.tag_id
WHERE t.tag = 'php' OR t.tag ='mysql'
GROUP BY bookmark_id
ORDER BY tag_count DESC;

So the query below works on a small set of data. Hopefully you can see what I am trying to do but obviously the way the sub queries are joined is what seems to be the issue over large data.

SELECT tag_count, user_count, b.bookmark_id, b.title, b.url, b.created
FROM bookmark b
INNER JOIN
(
  SELECT COUNT(*) AS user_count, bookmark_id
  FROM bookmark_user bu
  WHERE bu.private=0
  GROUP BY bookmark_id
) t1
ON b.bookmark_id = t1.bookmark_id
INNER JOIN
(
  SELECT COUNT(*) AS tag_count, bookmark_id
  FROM bookmark_tag bt
  LEFT JOIN tag t ON bt.tag_id = t.tag_id
  WHERE t.tag = 'php' OR t.tag ='mysql'
  GROUP BY bookmark_id
) t2
ON b.bookmark_id = t2.bookmark_id
ORDER BY tag_count DESC, user_count DESC;

How should I join these queries to optimise it for scalability?

johanafm

You need to order each subquery and then join in the rest of the data so that the larger data set is ordered to begin with. Since you want to order by [tag_count, user_count], you need to start by getting the tag_count order.

SELECT final, data
FROM (
	SELECT COUNT(*) AS tag_count, bookmark_id
	ORDER BY tag_count
) tag
INNER JOIN (
	SELECT COUNT(*) AS user_count, bookmark_id 
	ORDER BY user_count
) user ON user.bookmark_id = tag.bookmark_id
INNER JOIN bookmark b ON b.id = user.bookmark_id