Вам нужно проанализировать ваш запрос. Мы можем только догадываться, почему ваши запросы работают плохо, не просматривая план выполнения (который вы можете легко получить из SQL Server или Oracle).
Учитывая, что GUID является 128-битным значением (если оно хранится в необработанном виде), GUID снижает плотность блоков данных и индекса на целых 50% (в случае индекса первичного ключа), поэтому убедитесь, что GUID уместно.
Но это может и не быть проблемой, поэтому просмотрите план запроса. Это может быть несколько других проблем.