Water quality sensor placement optimization refers to deploying sensor networks at optimal locations in the water distribution system so as to detect the contaminant, thus monitoring and making early warning once pollution occurs. This problem is a largescale discrete combination optimization problem in essence. We firstly analyze the problem from the perspective of mathematic theory, and prove that the problem is NP-complete. Secondly, aiming at the huge computation overhead, we propose a distributed genetic algorithm based on the Spark cloud computing model to solve the problem. Finally, experiments on a typical complex water distribution network show that the proposed algorithm has fast search speed with high accuracy, as well as a high linear speedup.