То, что это длится долго - это нормально. потому что большая выборка. 500 тыщ аписей - это очень много. То, что ты видишь, как оно выполняется в каком-то SQLAnalizere за 4 сек - это оптический обман. Просто там в процессе выборки данных они тут же выводятся в окно, нигде не сохраняясь. Ты видешь первые 100 строк и думаешь, что уже все. А на самом деле еще не все.
А в программе ты наверное выбираешь все данные и только потом отсекаешь время. Да еще возможно ты (или не ты) память динамически выделяешь под набор данных. А это для полумиллиона записей тоже не быстро.
(кстати, в Release-е замерял уже ? Померяй).