8 of 14 incorporated clarification from OP

While it is always good to keep efficiency in mind, first you need to consider what the actual desired functionality is.

First: Does org_path exist in another table? If yes, then it should be the PK of that table that should be in this table instead of org_path, and the PK would be the combination of both of the Foreign Keyed fields in this table. If no, then this is not a "cross-reference" table, at least not in terms of what I expect "cross-reference" to mean.

           Please note: the O.P. has clarified in a comment on this Answer that this table is, in fact, not a cross-reference
           table, and that org_path is not in any other table (and is also unique per company).

Second: Assuming that org_path is not in another table, then how do you need to reference rows in this table? Will you be looking up records on the combination of both company_id and org_path? Do you need to enforce uniqueness of org_path within a company_id? If yes to these, then adding an auto-increment field will not help, especially in the case of enforcing uniqueness.

While you could use a Trigger on INSERT, UPDATE to enforce uniqueness, you might have success by adding a hash of org_path, via a Persisted Computed Column, which would assist with both enforcing uniqueness and lookups on this table using both company_id and org_path since the hash is a function of org_path.

The Computed Column needs to be PERSISTED in order to be used in a Primary Key. Also, given the non-sequential nature of a hash, the FILLFACTOR should be set to something under 100, but not too low; I would start with a value of 90

For example:

CREATE TABLE dbo.SomeTable
(
  company_id BIGINT NOT NULL,
  org_path NVARCHAR(2048) NOT NULL,
  op_hash AS (CONVERT(BINARY(64), HASHBYTES('SHA2_512', [org_path]))) PERSISTED,
  CONSTRAINT [PK_SomeTable] PRIMARY KEY ([company_id] ASC, [op_hash] ASC)
             WITH (FILLFACTOR = 90)
);

Then you reference in queries via:

INNER JOIN dbo.SomeTable tbl
        ON tbl.company_id = other.company_id
       AND tbl.op_hash = HASHBYTES('SHA2_512', other.org_path)

Points to consider:

  1. The hash is not guaranteed unique, although in practice it usually is. Collisions are always possible when reducing a value to a smaller form, so this would need a bit of testing. Some people argue that the likelihood of a collision is too low to worry about and have tests to support this claim. Still others can demonstrate via their tests that collisions do happen. It is really a matter of the data. I am usually the one arguing on the side of "but it's not guaranteed unique", and am usually being ignored. So, assuming there is merit to the side of "it's unique enough" (and there are plenty of folks using hashes under the assumption that they are unique), then this approach is at least worthy of consideration ;-).
  2. The SHA2_512 algorithm is 64 bytes which is a bit wider than ideal, but if you don't have 10's of millions of rows, then probably not an issue, especially if this really isn't a cross-reference table and this composite PK isn't used as an FK somewhere else.
  3. While the additional 60 bytes (as compared to an INT column with the IDENTITY property) is technically less efficient, the benefit is that the PK will be used by queries instead of existing merely for the benefit of having a PK on this table. Meaning, the purpose of a PK is to uniquely identify each row, so if you won't be using company_id, some_identity_column in your queries, then you won't be using the PK for what a PK is intended to do, because you will still be JOINing on company_id AND org_path, and I'm not sure that doing a case-insensitive comparison (see final paragraph for more info) on an NVARCHAR(2048) is more efficient than what you lose by adding those 60 bytes and comparing the 64 byte binary values (although you still need to compute the hash for the "other" value, so that timing needs to be factored in).

Or, you could get the benefit of the hash column without the potential for collisions by instead foregoing the Primary Key and instead creating a non-unique Clustered Index on company_id, op_hash AND a Trigger on INSERT, UPDATE to enforce uniqueness of org_path within a company_id. The Clustered Index, not being UNIQUE, will allow for duplicate op_hash values without breaking. If there is ever a duplicate, the penalty will be an extra 4 bytes added to any duplicated values (but not the initial instance of the value -- as also noted in @Martin's answer). And for the majority of the time when the hashed values are unique, then the combined key size for the Clustered Index is no different than it would be had this been the PK. The difference here is that the Clustered Index in this case is not enforcing uniqueness, but that is where the Trigger comes in.


Regardless of adding an IDENTITY or Persisted Computed Column of HASHBYTES, depending on what the data in org_path looks like and behaves, you would probably be better off at least specifying a binary Collation for that column to provide for the most efficient comparisons. This assumes, based on at least my expectations of an "org path", that you need neither linguistic normalization (i.e. equating an accented character -- ü -- with the equivalent non-accented letter -- u -- plus an additional accent-only character -- NCHAR(0x0308) = ̈ -- that are displayed in the same position so as to appear as an accented character: N'u' + NCHAR(0x0308) = ) nor case-insensitivity. In which case it is very inefficient to make use of those rules. Meaning, when creating the table, specify that column as:

org_path NVARCHAR(2048) COLLATE Latin1_General_100_BIN2 NOT NULL,