[balfirevic]

How does it change the complexity class of an algorithm?

Database performing a table read because additional columns were requested shouldn't change the complexity class if the query was otherwise successfully satisfied using the index.

I searched the article for "complexity class" and, while I found the phrase, it didn't explain much.

[calpaterson]

Sorry, yes, you're right. It doesn't change the complexity class just because you have to go to the heap. It is however a lot slower for the usual reasons: the heap is less dense in memory, it's a second thing you have to do, you have to serialise/deserialise more, etc etc.

But yes, you're right: just going to the heap is not a change in complexity class.