We want to minimize the downtime for our users during the upgrade process and want to ensure that our schema changes can all be performed in O(1) and are not O(n). Is there a list of documented schema changes that can be performed in O(1) with Microsoft SQL Server?

E.g. adding a nullable column is O(1) - at least our empiric tests show that.


1 Answer 1


This blog post by Russ Thomas – SQL Judo, as shared by one of the commenters here, has a list of several O(1) commands.

I'll do my best to create a more extensive list here.

Please note that while these commands are performed in O(1), some may require very high-level locks, and therefore may cause contention with other sessions in the database. Especially when potentially affecting dependent objects such as indexed views and foreign key constraints.

So, please don't take them lightly.

All of the following commands will be performed in O(1), not including waiting on locks on database objects:

  • All CREATE commands, except CREATE INDEX (this does not include ALTER TABLE ... ADD ... commands).
  • All DROP commands, except the DROP of a CLUSTERED INDEX.
  • Adding a new nullable column at the end of a table's columns list.
  • ALTER TABLE ... SWITCH TO ... - this is commonly identified with partitioning, but you don't actually require partitioning on a table in order to use it. This is because technically, since SQL 2005, ALL tables are partitioned (having only partition 1 by default).
  • CREATE NONCLUSTERED ... INDEX ... ON ... WITH STATISTICS_ONLY - this creates a hypothetical index in O(1).
  • All ALTER TABLE ... DROP ... commands, except the DROP of a CLUSTERED constraint (such as a UNIQUE or PRIMARY KEY constraint).
  • ALTER TABLE ... ADD CONSTRAINT ... WITH NOCHECK (the NOCHECK option is crucial for avoiding retroactively checking all existing data in the table).
  • ALTER TABLE ... ADD DEFAULT ... on an existing column should be performed in O(1).
  • ALTER TABLE ... ALTER COLUMN ... when increasing the maxsize of variable length columns (varchar, nvarchar, varbinary) should be performed in O(1).
  • Starting with SQL 2016, in some very rare cases, with data compression enabled, it's also possible to increase fixed-size numerical columns (e.g. tinyint to smallint to int to bigint, or decimal(14,1) to decimal(18,9)). But in most cases this would not be possible so be careful with it.

If I recall additional commands, I'll edit this message and add them to the list.

  • Adding a non-nullable column with a default also? Commented May 23, 2023 at 14:26
  • 2
    I hate to be the uhm, ackshually...-guy, but I don't feel it's correct at all to refer to these operations as "O(1)" because operations aren't algorithms, and plenty of these operations will internally involve some algorithms with time and space complexity beyond O(1) - e.g. adding a new column to a table with n columns is necessarily O(n), except the time-per-n is tiny... and so on and so forth...
    – Dai
    Commented May 23, 2023 at 20:16
  • ALTER TABLE ... ADD DEFAULT ... observed to be not O(1) ... oh wait you mean add just the default constraint not the column
    – Joshua
    Commented May 23, 2023 at 20:37
  • @Dai I'm gonna have to be the uhm, ackshually.. guy in return and say that - when it comes to databases and O(n) calculations, "n" normally represents the DATA, not something that's schema-based such as number of columns. Commented Jan 19 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.