Not all databases optimize NULL columns, so searching for items that aren't deleted might be a table scan worst case. I speak from hard-earned experience... In

Not all databases optimize NULL columns, so searching for items that aren't deleted might be a table scan worst case. I speak from hard-earned experience... In such cases I fall back to computed columns. A deleted flag which value depends on deleted_time being set or not, for example. This retains your atomic state goal.