Implementing Z-order optimization on columns that are frequently queried together reorganizes the data to group related data physically closer on disk. This method significantly boosts query performance without a notable increase in storage costs, as it avoids data duplication or reshuffling. Other options like repartitioning or converting formats either increase storage costs or do not effectively optimize for specific query patterns.