Using the OSM dataset I noticed there is a significant difference in the following queries:
select * from way_tags where way = 9168360 and k = 'created_by';
Timer 10583.483 msec 2 rows
select * from way_tags where k = 'created_by' and way = 9168360;
Timer 331.086 msec 2 rows
(this is not about hot/cold performance, the next try of the first query results in 10286.816 msec)
Niels noted that this could be solved automatically using a dynamic selectivity optimiser. I first noticed this issue using delete from.
such an optimizer is a feature request, rather then a bug.
This bug was previously known as tracker item 2704025 at http://sourceforge.net/support/tracker.php?aid=2704025