Help with a connect by prior query

Question

I have the following data

Order_ID  Pallet_ID
O1        P1
O2        P1
O2        P2
O3        P2
O3        P3
O4        P4

Where orders can be on multiple pallets, and more than one order can be on a pallet. I need to select the group of orders that make up a group, in that they all share the same group of pallets. In the test data above, there are two such groups, {O1,O2,O3} and {O4}, because O1, O2 and O3 have at least one pallet in common with another member of the group.

Now I need some SQL to do this. I tried (where greg_test contains the data above)

select distinct order_id
from greg_test
start with order_id = :order_id
connect by pallet_id = prior pallet_id

But that gave me a circular reference error (ORA-01436 CONNECT BY loop in user data). Adding nocycle didn't give the correct set.

Answer 1

This query only uses a single full table scan, or can use index range scans if there are indexes.

select distinct order_id
from greg_test
start with order_id = :order_id
connect by nocycle pallet_id = prior pallet_id or order_id = prior order_id;

If you're on 11gR2, this will run a little faster than the above connect by query, although the syntax is weirder IMO.

with orders(order_id, pallet_id) as
(
    select order_id, pallet_id
    from greg_test
    where order_id = :order_id
    union all
    select greg_test.order_id, greg_test.pallet_id
    from greg_test
    inner join orders
        on greg_test.pallet_id = orders.pallet_id
            or greg_test.pallet_id = orders.pallet_id
) cycle order_id, pallet_id set is_cycle to 'Y' default 'N'
select distinct order_id from orders;

If you have large amounts of data you'll want to thoroughly test whichever solution you use. Hierarchical queries often have serious performance problems.

Answer 2

-- Z lists all order pairs that share a pallet, and also pairs each order with itself
WITH pairs AS (
    -- all pairs of orders on the same pallet
    SELECT DISTINCT a.order_id a, b.order_id b FROM greg_test a, greg_test b 
    WHERE a.pallet_id = b.pallet_id AND a.order_id != b.order_id
  UNION ALL 
    -- pair all orders with themselves
    SELECT DISTINCT order_id a, order_id b FROM greg_test
)
-- Now connect all the pairs
SELECT DISTINCT a FROM pairs 
CONNECT BY NOCYCLE PRIOR a = b 
START WITH a = :order_id

Probably there is a more efficient solution.