this looks a bit similar to MDEV-10927. Varun, can you check if the patch is fixed by the fix for MDEV-10927 (that is, repeatable before it and not repeatable after?)

#0 Unique::get (this=0x10c2dd2a0, table=0x10c2a6070) at /Users/varun/MariaDB/10.1/10.1/sql/uniques.cc:753
#1 0x00000001001c1a16 in read_keys_and_merge_scans (thd=0x10be529b0, head=0x10c2a6070, quick_selects=..., pk_quick_select=0x0, read_record=0x10c226b28,
intersection=false, filtered_scans=0x0, unique_ptr=0x10c226ac0) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10778
#2 0x00000001001c1cd7 in QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10800
#3 0x00000001001aee33 in QUICK_INDEX_SORT_SELECT::reset (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:1365
#4 0x0000000100358451 in join_init_read_record (tab=0x10c238560) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:19209
#5 0x0000000100363717 in sub_select (join=0x10c235688, join_tab=0x10c238560, end_of_records=false)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:18301
#6 0x000000010034ce8e in do_select (join=0x10c235688, fields=0x10be56c10, table=0x0, procedure=0x0)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:17959
#7 0x000000010034beb8 in JOIN::exec_inner (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3215
#8 0x0000000100349292 in JOIN::exec (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:2505
#9 0x0000000100330dc4 in mysql_select (thd=0x10be529b0, rref_pointer_array=0x10be56d70, tables=0x10c2336b0, wild_num=1, fields=..., conds=0x10c2354a8,
og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=2147748608, result=0x10c235668, unit=0x10be563f8, select_lex=0x10be56af8)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3439
#10 0x000000010033071f in handle_select (thd=0x10be529b0, lex=0x10be56330, result=0x10c235668, setup_tables_done_option=0)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:372
#11 0x00000001002e87c5 in execute_sqlcom_select (thd=0x10be529b0, all_tables=0x10c2336b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:5899
#12 0x00000001002dcb71 in mysql_execute_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:2971
#13 0x00000001002d9403 in mysql_parse (thd=0x10be529b0,
rawbuf=0x10c233308 "SELECT * FROM t1 FORCE KEY (state,capital) \nWHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'", length=193, parser_state=0x700000abae70)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:7322
#14 0x00000001002d4d25 in dispatch_command (command=COM_QUERY, thd=0x10be529b0, packet=0x109b5edf1 "", packet_length=194)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1488
#15 0x00000001002d7cc3 in do_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1109
#16 0x00000001004531b8 in do_handle_one_connection (thd_arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1350
#17 0x0000000100452f3d in handle_one_connection (arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1262
#18 0x00000001006d3975 in pfs_spawn_thread (arg=0x109bb7470) at /Users/varun/MariaDB/10.1/10.1/storage/perfschema/pfs.cc:1860
#19 0x00007fff94ca199d in _pthread_body () from /usr/lib/system/libsystem_pthread.dylib
#20 0x00007fff94ca191a in _pthread_start () from /usr/lib/system/libsystem_pthread.dylib
#21 0x00007fff94c9f351 in thread_start () from /usr/lib/system/libsystem_pthread.dylib
#22 0x0000000000000000 in ?? ()

The issue is that all the row ids are not getting added to the tree. The size of the tree is showing 1 instead of 8.
/*
Ok all rowids are in the Unique now. The next call will initialize
head->sort structure so it can be used to iterate through the rowids
sequence.
*/
result= unique->get(head);
(gdb)
11398 result= unique->get(head);
(gdb) p unique->tree.elements_in_tree
$1 = 1

Lets take a row from the above query:
(id, state, capital)= ( 7 , Pennsylvania , Harrisburg)

The WHERE clause is:

 WHERE 

( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9     

OR 

( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9`=TRUE

( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'` = TRUE

(but it doesn't matter because the first line evaluated to TRUE already)

—

 T@7    : | | | | | | | | | | >print_quick

quick index_merge select

merged scans {

  quick range select, key capital, length: 67

    Topeka <= X

  quick range select, key state, length: 71

    Alabama <= X < Alabama/9

    Alabama/9 < X <= Alabama

    Kansas <= X <= Kansas

    Texas <= X

}

other_keys: 0x0:

T@7    : | | | | | | | | | | <print_quick

(id, state, capital)= ( 7 , Pennsylvania , Harrisburg)

quick range select, key capital, length: 67
Topeka <= X

^ this scan will not read the row with city="Harrisburg"

looking at the second scan

Kansas <= X <= Kansas
// Pennsylvania should be here
Texas <= X

^ this scan will also not read the row with state=Pennsylvania

Sergey,
I've taken the bug because I investigated it and found a fix.

This is a 5.5 bug (actually a 5.3 bug). It can be reproduced in 5.5 with the following test case:

CREATE TABLE t1 (

  id INT NOT NULL,

  state VARCHAR(64),

  capital VARCHAR(64),

  UNIQUE KEY (id),

  KEY state (state,id),

  KEY capital (capital, id)

) ENGINE=MyISAM;

INSERT INTO t1 VALUES  

  (1,'Arizona','Phoenix'), 

  (2,'Hawaii','Honolulu'),

  (3,'Georgia','Atlanta'), 

  (4,'Florida','Tallahassee'), 

  (5,'Alaska','Juneau'),

  (6,'Michigan','Lansing'),

  (7,'Pennsylvania','Harrisburg'),

  (8,'Virginia','Richmond')

;

SELECT * FROM t1 FORCE KEY (state,capital) 

WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 

   OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

For this test case we have:

MariaDB [test]> SELECT * FROM t1 FORCE KEY (state,capital) 

    -> WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 

    ->    OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

+----+----------+----------+

| id | state    | capital  |

+----+----------+----------+

|  8 | Virginia | Richmond |

+----+----------+----------+

The problem is that the range optimizer builds here an invalid index merge: the scan for the index 'state' contains wrong ranges.
As the cost of this invalid index merge is the cheapest the optimizer chooses it . Following it the server returns wrong result set.

The fix for this bug was pushed into the 5.5 tree.
The fix should be applied upstream as it is (to 10.0, 10.1, 10.2)