How do I delete only related records in a multi-key MERGE in SQL Server?

You can filter out the rows you need to consider from the target table in a CTE and use the CTE as the target in the merge.

WITH T AS
(
  SELECT M.LeftId, 
         M.RightId, 
         M.CustomValue
  FROM @Mappings AS M
  WHERE EXISTS (SELECT *
                FROM @Values AS V
                WHERE M.LeftId = V.LeftId) 
)
MERGE T
USING @Values AS S
ON T.LeftId = S.LeftId and
   T.RightId = S.RightId
WHEN NOT MATCHED BY TARGET THEN
  INSERT (LeftId, RightId, CustomValue) 
  VALUES (S.LeftId, S.RightId, S.CustomValue)
WHEN MATCHED THEN
  UPDATE SET CustomValue = S.CustomValue
WHEN NOT MATCHED BY SOURCE THEN
  DELETE
;

This is the separate DELETE operation I had in mind:

DELETE m
FROM dbo.Mapping AS m
WHERE EXISTS 
  (SELECT 1 FROM @Values WHERE LeftID = m.LeftID)
AND NOT EXISTS 
  (SELECT 1 FROM @Values WHERE LeftID = m.LeftID AND RightID = m.RightID);

As I outline here, for a left anti-semi join, the NOT EXISTS pattern will often outperform the LEFT JOIN / NULL pattern (but you should always test).

Not sure if your overall goal is clarity or performance, so only you can judge if this will work out better for your requirements than the NOT MATCHED BY source option. You'll have to look at the plans qualitatively, and the plans and/or runtime metrics quantitatively, to know for sure.

If you expect your MERGE command to protect you from race conditions that would happen with multiple independent statements, you better make sure that is true by changing it to:

MERGE dbo.Mapping WITH (HOLDLOCK) AS target

(From Dan Guzman's blog post.)

Personally, I would do all of this without MERGE, because there are unresolved bugs, among other reasons. And Paul White seems to recommend separate DML statements as well.

And here's why I added a schema prefix: you should always reference objects by schema, when creating, affecting, etc.

You can use the WHEN NOT MATCHED BY SOURCE clause and provide an additional condition with it like this:

SQL Fiddle

MS SQL Server 2008 Schema Setup:

CREATE TABLE dbo.Vals (
  LeftId INT NOT NULL,
  RightId INT NOT NULL,
  CustomValue varchar(100) NULL
);

CREATE TABLE dbo.Mapping (
  LeftId INT NOT NULL,
  RightId INT NOT NULL,
  CustomValue varchar(100) NULL
);

INSERT INTO dbo.Vals(LeftId,RightId,CustomValue)
VALUES(1, 10, 'foo10'),(1, 11, 'foo11');

INSERT INTO dbo.Mapping(LeftId,RightId,CustomValue)
VALUES(1, 10, 'bar'),(1, 12, 'foo'),(2, 20, 'car');

Query 1:

MERGE dbo.Mapping WITH(HOLDLOCK) AS target
USING (SELECT LeftId, RightId, CustomValue FROM dbo.Vals) 
  AS source (LeftId, RightId, CustomValue)
  ON target.LeftId = source.LeftId
    AND target.RightId = source.RightId
WHEN NOT MATCHED THEN
  INSERT (LeftId, RightId, CustomValue)
  VALUES (source.LeftId, source.RightId, source.CustomValue)
WHEN MATCHED THEN
  UPDATE SET
    CustomValue = source.CustomValue


WHEN NOT MATCHED BY SOURCE AND EXISTS(SELECT 1 FROM dbo.Vals iVals WHERE target.LeftId = iVals.LeftId) THEN
  DELETE



OUTPUT $action AS Action,
       INSERTED.LeftId AS INS_LeftId,INSERTED.RightId AS INS_RightId,INSERTED.CustomValue AS INS_Val,
       DELETED.LeftId AS DEL_LeftId,DELETED.RightId AS DEL_RightId,DELETED.CustomValue AS DEL_Val;

Results:

| ACTION | INS_LEFTID | INS_RIGHTID | INS_VAL | DEL_LEFTID | DEL_RIGHTID | DEL_VAL |
------------------------------------------------------------------------------------
| INSERT |          1 |          11 |   foo11 |     (null) |      (null) |  (null) |
| UPDATE |          1 |          10 |   foo10 |          1 |          10 |     bar |
| DELETE |     (null) |      (null) |  (null) |          1 |          12 |     foo |

Query 2:

SELECT * FROM dbo.Mapping;

Results:

| LEFTID | RIGHTID | CUSTOMVALUE |
----------------------------------
|      1 |      10 |       foo10 |
|      2 |      20 |         car |
|      1 |      11 |       foo11 |

I added the output clause to the MERGE statement to show what action was taken for each row.

As others have commented, you need to also provide the WITH(HOLDLOCK) hint on the target table to prevent race conditions.