How to select similar sets in SQL

This isn't really an answer so much as an extended comment. I'll remove it if it's deemed not to make sense.

If you're trying to find the 'similar' items on the fly, then the problem is that you have a lot (~79k) of Orders to look at. So if you're trying to do this, then you need ways to cut down the number of Orders you're considering before you do the expensive set comparison.

One way, pointed out by @Will, is to take into account the number of items in the Orders. So if your target order has 20 items then you only need to consider Orders with 17-23 OrderItems (or something like that, depending upon the exact calculation for '85% similarity'). I'm assuming that these numbers can be calculated via a trigger, whenever an Order is created or changed, and stored in columns on the Order table.

But if you can store the size of the set then you could also store other numbers. For instance, you could store the number of odd OrderItem primary key values in each Order. Then the Orders that you're considering would have to be appropriately close to having that number of odd order numbers (I might do the maths at some point to fill out 'appropriately close').

And if you think of partitioning the values by 'odd' numbers as splitting into size-1 stripes, you can easily partition by differently sized stripes using the modulus operator. Eg. ItemID%4<2 will made size-2 stripes. You can then record for each Order the number of OrderItem primary keys within those stripes. Your candidate Orders will have to be appropriately close to your target Order on each way of partitioning the values.

So what you'll end up with is a big subquery that tries to limit the size of the candidates in the Orders table by looking at a whole bunch of metrics that are stored - and indexed - on that table.

The approach that I would take would be to first of all find all orderitems that are 85% similar to the orderitems for the selected order, then count the number of these orderitems for each order and check whether the number of items is 85% similar to the selected order, using the following query:

DECLARE @OrderId int = 2
SET @OrderId = 6

/*
Retrieve orderitems that match 85% with required @orderId
*/
;WITH SelectedOrderItemCount
AS
(
    SELECT COUNT(*) * 0.85 AS LowerBoundary, COUNT(*) * 1.15 AS UpperBoundary
    FROM OrderItem
    WHERE OrderId = @OrderId
)
SELECT OtherOrders.OrderId, COUNT(*) as NumberOfOrderItems
FROM OrderItem SpecificOrder
INNER JOIN OrderItem OtherOrders
    ON OtherOrders.ItemId = SpecificOrder.ItemId
WHERE SpecificOrder.OrderId = @OrderId AND
      OtherOrders.OrderId <> @OrderId AND
    OtherOrders.Quantity BETWEEN SpecificOrder.Quantity * 0.85 AND SpecificOrder.Quantity * 1.15
GROUP BY OtherOrders.OrderId
HAVING COUNT(*) BETWEEN (SELECT LowerBoundary FROM SelectedOrderItemCount) 
                    AND (SELECT UpperBoundary FROM SelectedOrderItemCount)

Full SQLFiddle demo here