A simple recommendation may alleviate this problem without any significant overhaul/modifications to the Query Activity. Specifically, what you'll want to do is stage the data that will be Added/Updated to an intermediate Data Extension before writing it to the target Data Extension.
This will allow you to capitalize on the most expensive portion of the Query Activity itself which is the period of time where the Query checks for existence and writes each row as mentioned above. Doing this will allow us to leverage the Import method available within Contact Builder that allows you to use the "From Existing Data Extension" source. Import Activities are capable of doing the same Add/Update operation that a Query activity does faster and at a larger scale more efficiently than a Query activity is able to do. If you have a Query Activity that exists simply to copy its records (without a where clause) from one Data Extension to another, this methodology would also be superior and should be used as an alternative. Of note, utilizing a Data Copy Import activity will be much more reliable, however it can increase the time the activity runs, which is due to the batching process for imports. There is no timeout for imports, though, like there is for Query Activities.
Here are the steps that you would leverage to do this:
000396776

We use three kinds of cookies on our websites: required, functional, and advertising. You can choose whether functional and advertising cookies apply. Click on the different cookie categories to find out more about each category and to change the default settings.
Privacy Statement
Required cookies are necessary for basic website functionality. Some examples include: session cookies needed to transmit the website, authentication cookies, and security cookies.
Functional cookies enhance functions, performance, and services on the website. Some examples include: cookies used to analyze site traffic, cookies used for market research, and cookies used to display advertising that is not directed to a particular individual.
Advertising cookies track activity across websites in order to understand a viewer’s interests, and direct them specific marketing. Some examples include: cookies used for remarketing, or interest-based advertising.