Which queries are faster with Postgres than with MySQL InnoDB
To avoid flame war, I'll just glance the way each storage work on querying, not really a benchmark. I'll use this table as reference (the code should be slightly modified to run on both RDBMS):

CREATE TABLE employees (
    emp_id int,
    name varchar,
    depto_no int,
    salary decimal,
    CONSTRAINT emp_pk PRIMARY KEY (emp_id);
);
CREATE INDEX emp_depto_idx ON employees (depto_no);


On PostgreSQL there will be 3 structures:


The employees heap, which is basically the table stored sequentially (just like you imagine a table)
The emp_pk index (which is also the primary key), stored as a B-tree index where each element has a pointer to the employee's heap, with the exact page/offset in disk
The emp_depto_idx index, that is like emp_pk, a B-tree with pointers to the heap, except that it does not enforce uniqueness


On MySQL InnoDB, there will be only two:


emp_pk and employees will be stored as one structure, a B-tree ordered by emp_id column, and just keep the value on the other columns as a payload in the leaf nodes.
emp_depto_idx index is a B-tree that on each element it will have the emp_id value referencing that row (not a physical location pointer).


Primary key lookup


  why PK lookup is much better for MySQL


I know you know that, but let's make it clear.

When you query it like:

SELECT * FROM employees WHERE emp_id = 10;


On PostgreSQL it can navigate through emp_pk index (one scan on the B-tree index) and then get the page/offset to get referencing row from employees heap table (one direct page/row fetch, not really a scan). So, one scan on the index, and one direct fetch on the heap.

On MySQL it will just navigate through primary key index (one scan on the B-tree index), as all the information is already there, no other lookup is required. So, just one scan on the index.

So, while PostgreSQL needs to do one scan and one fetch, MySQL just do one scan.

Secondary index lookup


  Why lookup through two indexes (InnoDB, lookup through non-PK index) is much slower? Does it requires two times more I/O or CPU? Can it compensate that huge benefit of PK lookup boost?


Now, assume this other query:

SELECT * FROM employees WHERE depto_no = 14;


On PostgreSQL, it won't be much different from the other. It will scan emp_depto_idx and then, for each row returned, fetch the value directly from the heap. So, one scan on the index, and a direct fetch on the heap for each row matched.

On MySQL it will scan the emp_depto_idx (one scan on the index), then, for each row returned it will get the referencing emp_id and scan the primary key index. So, one scan on a secondary index, and one scan on the primary index for each row matched.

See the difference? While PostgreSQL will do a scan and then fetch each matching row with a direct pointer, InnoDB will do a similar scan first, then another scan for each matching row. Now, it may be fast enough if department 14 has few employees, but really slow as it gets more employees (of course it will get slower on both RDBMS, but the curve is probably higher with InnoDB).

Full scan


  Why InnoDB sequential scans are slower?


Simple answer, because it is not really "sequential"...

Well, let's see the simplest (and certainly slow for all) query:

SELECT * FROM employees;


On PostgreSQL, it may can simple scan the whole employees heap, row by row, in its physical sequential order (no matter the insertion order here, what matters is how the tuples and pages are physically arranged now).

On InnoDB, it needs to traverse the index, which means more random scans (as index pages are not necessarily ordered physically and logically the same way).

If you think about magnetic disks, the difference is quite obvious, it is know that sequential access is way faster than random access. For SSDs it is not necessarily true, although there is still advantages on sequential access, like read-ahead. So in most scenarios, PostgreSQL's full scan will probably faster than InnoDB's, at least for considerable large tables (notice I didn't define what is "large", you must try it out and see where that difference really matters, it may just not matter in many cases). The best, for both RDBMS, is to design your model and your queries to avoid full scans, if possible.

Complex queries


  Internet says that Postgres is better for complex queries and subquering, but I still don't understand WHY is it better?


This is a huge topic, and probably the one that would generate more flame war, so I'll just give you some examples. It is common to say that PostgreSQL is better for complex queries, and it may be a true if you simple think on its query capabilities that are not present in MySQL (not considering performance yet), like:


Common Table Expression (CTE)
Window Functions
LATERAL joins
Arrays
JSON types, functions and operators
etc.


Besides that, there are many difference in the planner and executor of those two. For instance, PostgreSQL can do joins using Nested Loops, Hash Joins and Merge Joins, while MySQL can only do using Nested Loops. Despite that, MySQL has many optimizations in its Nested Loop algorithms, and PostgreSQL has a harder choice on its planner, and sometimes it makes mistake (but so does MySQLs).

Final words

This answer is just a really fast glance on the topic, there are still many things to consider for those two RDBMS when it comes to performance, like index-only scan, vacuum vs undo, parallelism, etc. The truth is that you can't simple say one is faster than the other, it is clear to me (is it to you?) that one can be faster in some environments while the other may be faster in others.