Table structure with new Index and final search query for Stack Overflow question: http://dba.stackexchange.com/questions/39764/individual-queries-run-on-10ms-with-union-all-they-are-taking-290ms-7-7m-reco/39782

gistfile1.sql

CREATE TABLE `teacher_slots` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `teacher_id` mediumint(8) unsigned NOT NULL,
  `city_id` smallint(5) unsigned NOT NULL,
  `subject_id` smallint(5) unsigned NOT NULL,
  `date_from` datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  `date_to` datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  `status` tinyint(4) NOT NULL DEFAULT '0',
  `order_of_arrival` tinyint(1) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `main_idx` (`teacher_id`,`order_of_arrival`,`status`,`city_id`,`subject_id`,`date_from`,`date_to`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

LOCK TABLES `teacher_slots` WRITE;
/*!40000 ALTER TABLE `teacher_slots` DISABLE KEYS */;

INSERT INTO `teacher_slots` (`id`, `teacher_id`, `city_id`, `subject_id`, `date_from`, `date_to`, `status`, `order_of_arrival`)
VALUES
  (1,1,6015,1,'2013-04-12 08:00:00','2013-04-12 12:00:00',0,1),
	(2,1,6015,1,'2013-04-12 15:00:00','2013-04-12 19:00:00',0,1),
	(3,1,6015,1,'2013-04-13 08:00:00','2013-04-13 19:00:00',0,1),
	(4,1,6015,1,'2013-04-16 15:00:00','2013-04-16 19:00:00',0,1),
	(5,2,6015,1,'2013-04-12 08:00:00','2013-04-12 08:00:00',0,0),
	(6,2,6015,1,'2013-04-12 08:30:00','2013-04-12 08:30:00',1,0),
	(7,2,6015,1,'2013-04-12 09:00:00','2013-04-12 09:00:00',0,0),
	(8,2,6015,1,'2013-04-12 09:30:00','2013-04-12 09:30:00',1,0),
	(9,2,6015,1,'2013-04-12 10:00:00','2013-04-12 10:00:00',0,0),
	(10,2,6015,1,'2013-04-13 10:00:00','2013-04-13 10:00:00',0,0),
	(11,2,6015,1,'2013-04-13 10:30:00','2013-04-13 10:30:00',0,0),
	(12,2,6015,1,'2013-04-13 08:00:00','2013-04-13 08:00:00',0,0);

/*!40000 ALTER TABLE `teacher_slots` ENABLE KEYS */;
UNLOCK TABLES;


-- QUERY
(
     SELECT id, teacher_slots.teacher_id, date_from, date_to, order_of_arrival
     FROM teacher_slots
     JOIN (
          SELECT DATE(MIN(date_from)) as closestDay, teacher_id
          FROM teacher_slots
          WHERE date_from >= '2013-04-13 08:00:00' AND order_of_arrival = 0 AND status = 0 AND city_id = 6015 AND subject_id = 1
          GROUP BY teacher_id
          ORDER BY date_from ASC
          LIMIT 10
     ) a ON a.teacher_id = teacher_slots.teacher_id
     AND DATE(teacher_slots.date_from) = closestDay
     WHERE teacher_slots.date_from >= '2013-04-13 08:00:00'
          AND teacher_slots.status = 0
)

UNION ALL

(
     SELECT id, teacher_id, date_from, date_to, order_of_arrival
     FROM teacher_slots
     WHERE order_of_arrival = 1 AND status = 0 AND city_id = 6015 AND subject_id = 1
          AND (
               (date_from <= '2013-04-13 08:00:00' AND  date_to >= '2013-04-13 08:00:00')
               OR (date_from >= '2013-04-13 08:00:00')
          )
     GROUP BY teacher_id
     ORDER BY date_from ASC
     LIMIT 10
)

ORDER BY date_from ASC;

After some tests with 7.7M rows, conclusions:

• Where there are only order of arrival rows (it may happen in some cases, so the UNION nor the first query won't be necessary) up to 100k rows = no index.
• Where the 1st query is involved, or only by hour the index is required (9-10ms each query).