List:General Discussion« Previous MessageNext Message »
From:SGreen Date:August 1 2005 1:47pm
Subject:Re: query unexpectedly took too long.
View as plain text  
jpyeron@stripped wrote on 08/01/2005 09:13:46 AM:

> I have this query which gets executed often, but when I saw this today I 

> panicked. Any suggestions to why this took so long?
> 
> mysql> SELECT t2.id, t2.bdate, t2.level FROM bvolset AS t1 JOIN bvolset 
AS 
> t2 ON t2.bdate<t1.bdate AND t2.level<t1.level WHERE t1.id=30 ORDER BY 
> bdate DESC LIMIT 1;
> 
> Empty set (22.82 sec)
> 
> here is the schema and data:
> 
> CREATE TABLE bvolset (
>     id int(11) NOT NULL auto_increment,
>     bdate datetime default NULL,
>     level int(11) NOT NULL default '0',
>     PRIMARY KEY  (id),
>     UNIQUE KEY bdate (bdate),
>     KEY level (level)
> ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
> 
> 
> 
> INSERT INTO `bvolset` VALUES (1,'2005-07-05 00:00:00',0),
> (15,'2005-01-01 00:00:00',3),(16,'2005-01-02 00:00:00',4),
> (17,'2005-01-03 00:00:00',3),(18,'2005-01-04 00:00:00',2),
> (19,'2005-01-05 00:00:00',3),(20,'2005-01-06 00:00:00',4),
> (21,'2005-01-07 00:00:00',3),(22,'2005-01-08 00:00:00',1),
> (23,'2005-01-09 00:00:00',3),(24,'2005-01-10 00:00:00',4),
> (25,'2005-01-11 00:00:00',3),(26,'2005-01-12 00:00:00',2),
> (27,'2005-01-13 00:00:00',3),(28,'2005-01-14 00:00:00',4),
> (29,'2005-01-15 00:00:00',3),(30,'2005-01-16 00:00:00',0),
> (31,'2005-01-17 00:00:00',3),(32,'2005-01-18 00:00:00',4),
> (33,'2005-01-19 00:00:00',3),(34,'2005-01-20 00:00:00',2),
> (35,'2005-01-21 00:00:00',3),(36,'2005-01-22 00:00:00',4),
> (37,'2005-01-23 00:00:00',3),(38,'2005-01-24 00:00:00',1),
> (39,'2005-01-25 00:00:00',3),(40,'2005-01-26 00:00:00',4),
> (41,'2005-01-27 00:00:00',3),(42,'2005-01-28 00:00:00',2),
> (43,'2005-01-29 00:00:00',3),(44,'2005-01-30 00:00:00',4),
> (45,'2005-01-31 00:00:00',3),(46,'2004-12-31 00:00:00',0),
> (47,'2005-07-07 12:12:59',0),(48,'2005-07-07 12:21:33',0),
> (49,'2005-07-07 12:24:42',0),(50,'2005-07-07 12:26:20',0),
> (51,'2005-07-07 12:27:34',0),(52,'2005-07-07 12:28:21',0),
> (53,'2005-07-07 12:29:00',0),(54,'2005-07-07 14:05:09',0),
> (55,'2005-07-07 14:20:02',0),(56,'2005-07-07 14:20:33',0),
> (57,'2005-07-07 14:22:03',0),(58,'2005-07-07 14:22:09',0),
> (59,'2005-07-07 14:22:21',0),(60,'2005-07-07 14:22:28',0),
> (61,'2005-07-07 14:25:24',0),(62,'2005-07-07 14:25:42',0),
> (63,'2005-07-07 16:42:52',0),(64,'2005-07-07 16:43:09',0),
> (65,'2005-07-07 16:43:26',0),(66,'2005-07-07 16:43:34',0),
> (67,'2005-07-07 16:43:51',0),(68,'2005-07-07 16:44:59',0),
> (69,'2005-07-07 16:47:25',0),(70,'2005-07-07 16:48:26',0),
> (71,'2005-07-07 16:51:10',0),(72,'2005-07-07 16:52:37',0),
> (73,'2005-07-07 16:57:39',0),(74,'2005-07-07 16:58:47',0),
> (75,'2005-07-07 17:00:43',0),(76,'2005-07-07 17:00:53',0),
> (77,'2005-07-07 17:12:07',0),(78,'2005-07-07 17:53:46',0),
> (79,'2005-07-07 18:03:20',0),(80,'2005-07-07 18:05:19',0),
> (81,'2005-07-08 00:13:26',0),(82,'2005-07-08 01:05:06',0),
> (83,'2005-07-08 01:06:14',0),(84,'2005-07-08 01:06:32',0),
> (85,'2005-07-08 01:09:36',0),(86,'2005-07-08 01:11:51',0),
> (87,'2005-07-08 01:12:11',0),(88,'2005-07-08 01:12:19',0),
> (89,'2005-07-08 09:54:34',0),(90,'2005-07-08 09:59:11',0),
> (91,'2005-07-08 09:59:55',0),(92,'2005-07-08 10:26:02',0),
> (93,'2005-07-08 10:28:11',0),(94,'2005-07-08 10:28:25',0),
> (95,'2005-07-08 10:35:19',0),(96,'2005-07-08 10:36:16',0),
> (97,'2005-07-08 10:36:37',0),(98,'2005-07-08 10:38:07',0),
> (99,'2005-07-08 10:38:59',0),(100,'2005-07-08 10:39:24',0),
> (101,'2005-07-08 10:40:34',0),(102,'2005-07-08 10:42:24',0),
> (103,'2005-07-08 10:42:51',0),(104,'2005-07-08 10:43:37',0),
> (105,'2005-07-08 10:43:50',0),(106,'2005-07-08 10:44:08',0),
> (107,'2005-07-08 11:45:37',0),(108,'2005-07-08 11:45:44',0),
> (109,'2005-07-08 11:55:15',0),(110,'2005-07-08 11:57:01',0),
> (111,'2005-07-08 11:57:17',0),(112,'2005-07-08 11:57:27',0),
> (113,'2005-07-08 11:57:34',0),(114,'2005-07-08 11:57:43',0),
> (115,'2005-07-08 11:58:03',0),(116,'2005-07-08 11:58:36',0),
> (117,'2005-07-08 11:59:57',0),(118,'2005-07-08 12:00:24',0),
> (119,'2005-07-08 12:10:28',0),(120,'2005-07-08 13:56:29',0),
> (121,'2005-07-08 13:56:35',0),(122,'2005-07-08 13:56:43',0),
> (123,'2005-07-08 13:56:47',0),(124,'2005-07-08 13:57:13',0),
> (125,'2005-07-08 13:57:54',0),(126,'2005-07-08 13:58:35',0),
> (127,'2005-07-09 12:25:41',0),(128,'2005-07-09 12:26:42',0),
> (129,'2005-07-09 12:34:01',0),(130,'2005-07-09 12:35:11',0),
> (131,'2005-07-09 12:38:37',0),(132,'2005-07-09 12:46:47',0),
> (133,'2005-07-09 12:48:15',0),(134,'2005-07-09 12:49:48',0),
> (135,'2005-07-09 12:57:10',0),(136,'2005-07-09 13:17:12',0),
> (137,'2005-07-09 14:22:30',0),(138,'2005-07-09 14:23:11',0),
> (139,'2005-07-09 14:23:41',0),(140,'2005-07-09 19:11:40',0),
> (141,'2005-07-09 19:16:17',0),(142,'2005-07-09 19:17:45',0),
> (143,'2005-07-09 19:19:12',0),(144,'2005-07-10 01:06:42',0),
> (145,'2005-07-10 01:07:19',0),(146,'2005-07-10 01:07:39',0),
> (147,'2005-07-10 01:10:06',0),(148,'2005-07-10 02:00:46',0),
> (149,'2005-07-10 02:06:58',0),(150,'2005-07-10 02:08:19',0),
> (151,'2005-07-10 02:08:41',0),(152,'2005-07-10 02:09:50',0),
> (153,'2005-07-10 02:43:35',0),(154,'2005-07-12 10:20:00',0),
> (155,'2005-07-12 10:20:41',0),(156,'2005-07-12 10:21:01',0),
> (157,'2005-07-12 10:21:31',0);
> 
> 
> 
> -- 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> -                                                               -
> - Jason Pyeron                      PD Inc. http://www.pdinc.us -
> - Partner & Sr. Manager             7 West 24th Street #100     -
> - +1 (443) 921-0381                 Baltimore, Maryland 21218   -
> -                                                               -
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> 
> This message is for the designated recipient only and may contain 
> privileged, proprietary, or otherwise private information. If you 
> have received it in error, purge the message from your system and 
> notify the sender immediately.  Any other use of the email by you 
> is prohibited.
> 

I believe you are beginning to feel the pain of a geometrically increasing 
query load to execute this query. If I understand the intent of your 
query, you want the most recently dated entry, in the same group as but 
dated earlier than a given entry.

I would not try to do this query with a self join. Your execution time 
approaches N! which gets horrible very quickly. A more linear approach is 
to do this in two steps. This is similar to the group-wize maximum problem 
detailed here: 
http://dev.mysql.com/doc/mysql/en/example-maximum-column-group-row.html. 
In your case, you want to find the row with the max() date for the subset 
you specify (same group as but earlier date than your target record). (I 
will generalize this to return the 5 most recent records not just the one 
most recent)

SELECT @targetLevel := level from bvolset where id=30;

CREATE TEMPORARY TABLE tmpList
SELECT DISTINCT bdate
FROM bvolset 
WHERE id<30
        AND level =@targetLevel
ORDER BY bdate desc
Limit 5;
/* assuming, worst case, one entry per date then we will need at most 5 
dates to find 5 records */

SELECT b.id, b.bdate, b.level
FROM bvolset b
INNER JOIN tmpList t
        on t.bdate = b.bdate
ORDER BY b.bdate desc, b.id desc
LIMIT 5;

DROP TEMPORARY TABLE tmpList;

Most people are "afraid" of using multiple statement to do what can be 
represented in a single query (like yours) but the performance advantages 
can be enormous. Most of the slow queries that use self-joins or 
subqueries will improve their performance remarkably by breaking them into 
separate steps, like my example. Sure it takes more than one statement, 
but it still works faster when performed correctly.

Shawn Green
Database Administrator
Unimin Corporation - Spruce Pine




Thread
query unexpectedly took too long.jpyeron1 Aug
  • Re: query unexpectedly took too long.SGreen1 Aug
RE: query unexpectedly took too long.Jay Blanchard1 Aug
  • RE: query unexpectedly took too long.SGreen1 Aug
  • RE: query unexpectedly took too long.Jason Pyeron1 Aug
RE: query unexpectedly took too long.Jay Blanchard1 Aug