Yes, is doable.
I suggest you to add a custom field when some terms of that specific taxonomy are added to the post.
You should also delete that custom field when all the terms are removed from same post.
That can be done using 'set_object_terms'.
Please read the comments in code for more explaination:
add_action( 'set_object_terms', function( $object_id, $terms, $tt_ids, $taxonomy ){
// Customize post type in next line according to your needs. I used 'category' as example
if ( $taxonomy === 'category' ) {
$post = get_post( $object_id );
if ( empty( $post ) ) return;
// Customize post type in next line according to your needs. I used 'post' as example
if ( $post->post_type !== 'post' ) return;
// let's see if the post has some terms of this category,
// because the hoook is fired also when terms are removed
$has_terms = get_the_terms( $object_id, $taxonomy );
// here we see if the post already has the custom field
$has = get_post_meta( $post->ID, "_category_relation_added", true );
if ( ! $has && ! empty( $has_terms ) ) {
// if the post has not the custom field but has some terms,
// let's add the custom field setting it to current timestamp
update_post_meta( $post->ID, "_category_relation_added", time() );
} elseif ( $has && empty( $has_terms ) ) {
// on the countrary if the post already has the custom field but has not terms
// (it means terms are all removed from post) remove the custom fields
delete_post_meta( $post->ID, "_category_relation_added" );
}
}
}, 10, 4);
Don’t forget to change your taxonomy and post type name.
After adding previous code to your functions.php you can order your posts using that custom field:
$args = array(
// all your args here
'meta_key' => '_category_relation_added',
'orderby' => 'meta_value_num',
'order' => 'DESC' // from more to less recent
);
$query = new WP_Query( $args );