ID list for deleted records in a syncing solution

I feel like I'm missing something obvious. I'm trying to write some SQL to get an ID list for deleted records in a syncing solution. I'm finding that its slower than I'd like and this method feels like it's not efficient at all, anyone have a better idea?

To explain what I'm doing I'm getting a list of ID's where the creation timestamp is before the last sync and then I check to see if it doesn't exist in the other file. The problem is that for every record I'm running rather large select statement within the EXISTS().

The table SP stands for Sync Projects and Q stands for Questions, I'm using SP to get only the questions that are attached to the projects on the client file.

Get the ID's in the local file:

ExecuteSQL("SELECT id FROM Q WHERE zCrTS < ? AND NOT EXISTS(SELECT * FROM H_Q WHERE Q.id=H_Q.id)";""; ""; $$LastSync) 

Get the ID's in the hosted file:

ExecuteSQL("SELECT H_Q.id FROM H_Q , SP WHERE zCrTS < ? AND H_Q.id_project = SP.id AND NOT EXISTS(SELECT * FROM Q WHERE H_Q.id=Q.id)";""; ""; $$LastSync)