MySQL Bugs: #94296: Poor Optimizer Performance with Composite Index, IN() function, and many Tuples

Bug #94296	Poor Optimizer Performance with Composite Index, IN() function, and many Tuples
Submitted:	12 Feb 2019 18:17	Modified:	13 Feb 2019 19:41
Reporter:	Daniel Jeffery	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	8.0.11	OS:	Ubuntu (Ubuntu 16.04.1 LTS)
Assigned to:		CPU Architecture:	x86 (x86_64)
Tags:	composite_index

Description:
Query optimization takes a very long time for a SELECT query on a composite index with a large list of tuples. The performance degradation as the list of tuples grows seems to be geometric, compared to linear performance of an unindexed query or one using simple AND/OR clauses.

My expectation is that performance of the IN() function using an index would be similar, if not better, than alternatives, and that query optimization would not take more time than query execution.

I believe this is an issue with the optimizer, as the use of the index even affects "EXPLAIN SELECT ..." queries.

How to repeat:
-- Create simple table with composite index
CREATE TABLE tupleTest (
  id INT NOT NULL AUTO_INCREMENT,
  firstColumn INT NOT NULL,
  secondColumn INT NOT NULL,
  PRIMARY KEY (id),
  INDEX multiIndex (firstColumn, secondColumn)
) ENGINE=InnoDB;

-- Populate tupleTest with 100 rows
INSERT INTO tupleTest
  (firstColumn, secondColumn)
VALUES
  (1, 1), (2, 2), (3, 5), (4, 10), (5, 20), (6, 1), (7, 2), (8, 5), (9, 10), (10, 20), (11, 1), (12, 2), (13, 5), (14, 10), (15, 20), (16, 1), (17, 2), (18, 5), (19, 10), (20, 20),
  (21, 1), (22, 2), (23, 5), (24, 10), (25, 20), (26, 1), (27, 2), (28, 5), (29, 10), (30, 20), (31, 1), (32, 2), (33, 5), (34, 10), (35, 20), (36, 1), (37, 2), (38, 5), (39, 10), (40, 20),
  (41, 1), (42, 2), (43, 5), (44, 10), (45, 20), (46, 1), (47, 2), (48, 5), (49, 10), (50, 20), (51, 1), (52, 2), (53, 5), (54, 10), (55, 20), (56, 1), (57, 2), (58, 5), (59, 10), (60, 20),
  (61, 1), (62, 2), (63, 5), (64, 10), (65, 20), (66, 1), (67, 2), (68, 5), (69, 10), (70, 20), (71, 1), (72, 2), (73, 5), (74, 10), (75, 20), (76, 1), (77, 2), (78, 5), (79, 10), (80, 20),
  (81, 1), (82, 2), (83, 5), (84, 10), (85, 20), (86, 1), (87, 2), (88, 5), (89, 10), (90, 20), (91, 1), (92, 2), (93, 5), (94, 10), (95, 20), (96, 1), (97, 2), (98, 5), (99, 10), (100, 20);

-- Query tupleTest, allowing index, with large list of tuples
SELECT * FROM tupleTest WHERE (firstColumn, secondColumn) IN ((1, 4), (3, 7), <5000 tuples>, (5, 2), (6, 10));

Example SELECT queries (5000 tuples)

Attachment: tupleQueries.sql (application/octet-stream, text), 332.32 KiB.

Could you please try version 8.0.15. Thanks.

Upgrading to 8.0.15 resolved the issue - thank you Miguel!

To verify, I increased the size of my test table to 30000 rows, and queried with 1000 and 10000 tuples; performance will favour the indexed query at 1000 tuples, and the loss of performance at 10000 tuples is no longer significant enough to concern me.

Thank you for the feedback.