Not exactly answers the question, but might be a better solution than the above when dealing with bigger databases
// Get all posts IDs - Query took 0.0030 seconds
$all_posts_ids_query = $wpdb->prepare( "SELECT $wpdb->posts.ID FROM $wpdb->posts WHERE $wpdb->posts.post_type = '%s' GROUP BY $wpdb->posts.ID", 'your-post-type' );
$all_posts_ids = $wpdb->get_col( $all_posts_ids_query );
// Get all posts IDs that has tags - Query took 0.0300 seconds
$all_posts_ids_with_tags_query = $wpdb->prepare( "SELECT $wpdb->posts.ID FROM $wpdb->posts
INNER JOIN $wpdb->term_relationships ON ($wpdb->posts.ID = $wpdb->term_relationships.object_id)
INNER JOIN $wpdb->term_taxonomy ON ($wpdb->term_relationships.term_taxonomy_id = $wpdb->term_taxonomy.term_taxonomy_id)
WHERE 1=1 AND ( $wpdb->term_taxonomy.taxonomy = '%s' )
AND $wpdb->posts.post_type = '%s' GROUP BY $wpdb->posts.ID", 'your-taxonomy-name', 'your-post-type' );
$all_posts_ids_with_tags = $wpdb->get_col( $all_posts_ids_with_tags_query );
// Diff IDs arrays to get posts without tags
$all_posts_ids_without_tags = array_diff( $all_posts_ids, $all_posts_ids_with_tags );
DB size this was tested on (quite small but may give some representation), posts: ~3.000, terms: ~1.000, term relationships: ~6.000