What happens when SELECT ... FOR UPDATE returns multiple rows?

Question

I'm working on some dead-lock troubleshooting, particularly involving a row-swap.

Currently the statements look like this, all running under the same transaction:

SELECT IDENTIFIER FROM tables WHERE (TABLEID = 4 OR TABLEID = 5) AND DATE = "2015-10-31" FOR UPDATE; 
/* Would imagine this would lock both of these rows.*/

UPDATE tables SET LINK=0 WHERE DATE = "2015-10-31" AND LINK = 5;

UPDATE tables SET TABLEID = -1 WHERE TABLEID = 5 AND DATE = "2015-10-31";

UPDATE tables SET TABLEID = 5 WHERE TABLEID = 4 AND DATE = "2015-10-31";

/* Deadlock on 2nd connection occurs here */
UPDATE tables SET TABLEID = 4 WHERE TABLEID = -1 AND DATE = "2015-10-31";

COMMIT; 
/* Would imagine this would release locks and let the next transaction continue */

If I run two of these transactions at the same time (run query 1 in connection ONE, query 1 in connection TWO, then proceed with 2-3-4-5 in connection ONE) I get a deadlock every time on connection TWO.

Why? Should the first query not lock BOTH rows returned (in this case there are always two) and then not let the later transaction perform any SELECTS for these two rows until the first transaction has COMMIT'ed

Bear in mind the table name is tables in this case, just to avoid any confusion.

Indexes look like:

IDENTIFIER (primary, AI integer)
LINK (regular index)
DATE (regular index)
TABLEID+DATE (unique composite, in that order)

I can circumvent the issue by locking the entire table (LOCK TABLES tables WRITE, UNLOCK TABLES), but I'm trying to avoid an entire table lock.

MySQL 5.6.23, default isolation level (repeatable read)

In response to answer: If FOR UPDATE does not prevent other FOR UPDATEs to lock the same row, how come this happens:

Connection 1: SELECT IDENTIFIER FROM tables WHERE (TABLEID = 4 OR TABLEID = 5) AND DATE = "2015-10-31" FOR UPDATE; 

/* THIS WILL WAIT */
Connection 2: SELECT IDENTIFIER FROM tables WHERE (TABLEID = 4 OR TABLEID = 5) AND DATE = "2015-10-31" FOR UPDATE; 

Connection 1: COMMIT;

Connection 2 (statement runs): COMMIT;

No errors. Both statements returned both rows, but the second one waited for the first to commit. This makes my problem seem irrational. If the FOR UPDATE does indeed wait for the commit, why do I get a deadlock error at all? MySQL Documentation says:

"A kind of lock that prevents any other transaction from locking the same row" about X-locks, which FOR UPDATE is. See https://dev.mysql.com/doc/refman/5.6/en/glossary.html#glos_exclusive_lock

Edit: LATEST DEADLOCK is

------------------------
LATEST DETECTED DEADLOCK
------------------------
2015-10-26 18:39:47 2b308cbde700
*** (1) TRANSACTION:
TRANSACTION 12590262, ACTIVE 19 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 360, 1 row lock(s)
MySQL thread id 199074, OS thread handle 0x2b308cc1f700, query id 5754285 172.31.39.158 awsroot Sending data
SELECT IDENTIFIER,NAME,STATUS,PRICE,GUESTS,EMAIL,NOTE,BOOKER,EDITOR,SELLER,TABLEID,LINK,LASTCLIENT FROM tables WHERE (TABLEID = 4 OR TABLEID = 5) AND DATE = "2015-10-31" 
LIMIT 0, 1000
FOR UPDATE
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 2660 page no 4 n bits 232 index `table_ident` of table `apple`.`tables` trx id 12590262 lock_mode X locks rec but not gap waiting
Record lock, heap no 157 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 2; hex 8004; asc   ;;
 1: len 3; hex 8fbf5f; asc   _;;
 2: len 4; hex 80000004; asc     ;;

*** (2) TRANSACTION:
TRANSACTION 12590261, ACTIVE 22 sec updating or deleting
mysql tables in use 1, locked 1
9 lock struct(s), heap size 1184, 13 row lock(s), undo log entries 3
MySQL thread id 199078, OS thread handle 0x2b308cbde700, query id 5754318 172.31.39.158 awsroot updating
UPDATE tables SET TABLEID = 4 WHERE TABLEID = -1 AND DATE = "2015-10-31"
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 2660 page no 4 n bits 232 index `table_ident` of table `apple`.`tables` trx id 12590261 lock_mode X locks rec but not gap
Record lock, heap no 42 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 2; hex 8005; asc   ;;
 1: len 3; hex 8fbf5f; asc   _;;
 2: len 4; hex 80000005; asc     ;;

Record lock, heap no 157 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 2; hex 8004; asc   ;;
 1: len 3; hex 8fbf5f; asc   _;;
 2: len 4; hex 80000004; asc     ;;

Record lock, heap no 158 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 2; hex 7fff; asc   ;;
 1: len 3; hex 8fbf5f; asc   _;;
 2: len 4; hex 80000005; asc     ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 2660 page no 4 n bits 232 index `table_ident` of table `apple`.`tables` trx id 12590261 lock mode S waiting
Record lock, heap no 157 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 2; hex 8004; asc   ;;
 1: len 3; hex 8fbf5f; asc   _;;
 2: len 4; hex 80000004; asc     ;;

*** WE ROLL BACK TRANSACTION (1)

table_ident is the TABLEID+DATE unique index.

SHOW CREATE TABLE for tables:

CREATE TABLE `tables` (
  `IDENTIFIER` int(11) NOT NULL AUTO_INCREMENT,
  `TABLEID` smallint(6) NOT NULL,
  `NAME` varchar(60) DEFAULT NULL,
  `EMAIL` varchar(255) DEFAULT NULL,
  `PRICE` int(11) unsigned NOT NULL DEFAULT '0',
  `GUESTS` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `STATUS` tinyint(1) NOT NULL DEFAULT '1',
  `NOTE` varchar(1024) DEFAULT NULL,
  `LINK` smallint(6) NOT NULL DEFAULT '0',
  `SELLER` mediumint(8) NOT NULL DEFAULT '0',
  `DATE` date NOT NULL,
  `EDITOR` varchar(255) DEFAULT NULL,
  `CUSTOMER` mediumint(8) NOT NULL DEFAULT '0',
  `LASTEDIT` datetime NOT NULL DEFAULT '0000-00-00 00:00:00' ON UPDATE CURRENT_TIMESTAMP,
  `BOOKER` mediumint(8) NOT NULL DEFAULT '0',
  `LASTCLIENT` smallint(5) unsigned DEFAULT NULL,
  PRIMARY KEY (`IDENTIFIER`),
  UNIQUE KEY `table_ident` (`TABLEID`,`DATE`),
  KEY `DATE` (`DATE`),
  KEY `SELLER` (`SELLER`),
  KEY `LINK` (`LINK`),
  KEY `BOOKER` (`BOOKER`),
  KEY `CUSTOMER` (`CUSTOMER`) USING BTREE,
  CONSTRAINT `tables_booker` FOREIGN KEY (`BOOKER`) REFERENCES `people` (`ID`),
  CONSTRAINT `tables_customer` FOREIGN KEY (`CUSTOMER`) REFERENCES `people` (`ID`),
  CONSTRAINT `tables_link` FOREIGN KEY (`LINK`) REFERENCES `layout` (`TABLEID`) ON UPDATE CASCADE,
  CONSTRAINT `tables_seller` FOREIGN KEY (`SELLER`) REFERENCES `people` (`ID`),
  CONSTRAINT `tables_tableid` FOREIGN KEY (`TABLEID`) REFERENCES `layout` (`TABLEID`) ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=316 DEFAULT CHARSET=utf8

Answer 1

Suggestion: Change

UNIQUE KEY `table_ident` (`TABLEID`,`DATE`),
KEY `DATE` (`DATE`),

to

UNIQUE KEY `table_ident` (`DATE`,`TABLEID`), -- swapped to assist with `SELECT`
KEY `DATE` (`TABLEID`),   -- in case you need it

Answer 2

Single-step swap:

BEGIN;
UPDATE tables
    SET TABLEID = 4+5 - TABLEID
    WHERE TABLEID IN (4, 5)
      AND DATE = "2015-10-31";
COMMIT;

This might help avoid deadlocks.