Simple query with a single join very slow

I have this very slow, simple query that joins a large table (~180M rows) with a smaller table (~60k rows) with a foreign key, filtering an indexed column on the smaller table, ordering by the primary key in the larger table, and then taking the 25 latest rows. The EXPLAIN shows Using index; Using temporary; Using filesort on the smaller table. Why? Engine: MySQL 5.7. Query:

SELECT
    order.id,
    order.company_id,
    order.total
FROM
    order
INNER JOIN
    company ON company.id = order.company_id
WHERE
    company.company_headquarter_id = 23133
ORDER BY order.id DESC
LIMIT 25;

+----+-------------+------------+------------+------+---------------------------------------+----------------------------+---------+-----------------------+------+----------+----------------------------------------------+
| id | select_type | table      | partitions | type | possible_keys                         | key                        | key_len | ref                   | rows | filtered | Extra                                        |
+----+-------------+------------+------------+------+---------------------------------------+----------------------------+---------+-----------------------+------+----------+----------------------------------------------+
|  1 | SIMPLE      | company    | NULL       | ref  | PRIMARY,company_headquarter_id_idx    | company_headquarter_id_idx | 8       | const                 |    6 |   100.00 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | order      | NULL       | ref  | company_id_idx                        | company_id_idx             | 8       | company.id            |  381 |   100.00 | NULL                                         |
+----+-------------+------------+------------+------+---------------------------------------+----------------------------+---------+-----------------------+------+----------+----------------------------------------------+

CREATE TABLE order (
  id bigint(20) NOT NULL AUTO_INCREMENT,
  company_id bigint(20) NOT NULL,
  total double(18,2) NOT NULL,
  PRIMARY KEY (id),
  KEY company_id_idx (company_id),
  CONSTRAINT company_id_fk FOREIGN KEY (company_id) REFERENCES company (id)
) ENGINE=InnoDB AUTO_INCREMENT=186518644 DEFAULT CHARSET=latin1

CREATE TABLE company (
  id bigint(20) NOT NULL AUTO_INCREMENT,
  company_headquarter_id bigint(20) NOT NULL,
  name varchar(100) NOT NULL,
  PRIMARY KEY (id),
  KEY company_headquarter_id_idx (company_headquarter_id),
  CONSTRAINT company_headquarter_id_fk FOREIGN KEY (company_headquarter_id) REFERENCES company_headquarter (id)
) ENGINE=InnoDB AUTO_INCREMENT=60825 DEFAULT CHARSET=latin1

CREATE TABLE company_headquarter (
  id bigint(20) NOT NULL AUTO_INCREMENT,
  name varchar(100) NOT NULL,
  phone varchar(10) DEFAULT NULL,
  address_id bigint(20) NOT NULL,
  PRIMARY KEY (id),
  UNIQUE KEY name (name),
  KEY address_id_idx (address_id),
  CONSTRAINT address_id_fk FOREIGN KEY (address_id) REFERENCES address (id)
) ENGINE=InnoDB AUTO_INCREMENT=43862 DEFAULT CHARSET=latin1

CREATE TABLE address (
  id bigint(20) NOT NULL AUTO_INCREMENT,
  street_address varchar(100) DEFAULT NULL,
  zip varchar(7) DEFAULT NULL,
  state varchar(2) DEFAULT NULL,
  city varchar(50) DEFAULT NULL,
  country varchar(10) DEFAULT NULL,
  PRIMARY KEY (id)
) ENGINE=InnoDB AUTO_INCREMENT=147360955 DEFAULT CHARSET=latin1

The query becomes faster when I: * Remove the ORDER BY clause. * Filter company.company_headquarter_id with a company_headquarter_id that has a smaller number of orders. (company_headquarter_id = 23133 has ~3M rows in the order table) * Split it into two separate queries: First:

SELECT
    company.id
FROM
    company
WHERE
    company.company_headquarter_id = 23133;

Second:

SELECT
    order.id,
    order.company_id,
    order.total
FROM
    order
WHERE
    order.company_id IN (20122, 50729, 50730, 50731, 50732, 50733)  /* From first query */
ORDER BY order.id DESC
LIMIT 25;

Any ideas? Thank you. EDIT: When I do:

SELECT STRAIGHT_JOIN
    order.id,
    order.company_id,
    order.total
FROM
    order
INNER JOIN
    company ON company.id = order.company_id
WHERE
    company.company_headquarter_id = 23133
ORDER BY order.id DESC
LIMIT 25;

The query is much faster and EXPLAIN shows a temporary table is not created.