Witam

jak najlepiej gromadzić dane które przyjmują tylko dwie wartości : 0/1 (20 kolumn) przy czym ilość rekordów w bazie pracująca z tymi ustawieniami będzie zawierać 500 000 rekordów 

Jak dla mnie idealny byłby BOOLEAN.

również tak myslałem ,lecz nie pamietam gdzie ale zminne boolean = tinyint(1) czyli 1 bajt ( myślałem nad zastosowaniem 3 zmiennych typu tinyint(1) a w php stosować przesunięcie bitowe

Pytanie, czy nadmiarowość kodu jest lepsza w tym przypadku od ewentualnej nadmiarowości danych w bazie.
Dlaczego ewentualnej? Bo nie widzę potrzeby żeby rozliczać się co do jednego bajta.

MySQL obsługuje też typ danych SET, może ci się przyda.