null safe equal support in joins

[advancedxy]

Is your feature request related to a problem?

I'm planning to add intersect and intersect all operator into Daft and get some feature parity with Spark. During the evaluation and code browsing, I noticed that Daft doesn't support null safe equal in joins, it would be great that we can support null safe equal in joins.

P.S: an intersect operator could be rewritten as a semi join with null safe equal.

SELECT a1, a2 FROM t1 INTERSECT SELECT b1, b2 FROM t2
-- is effective the same as
SELECT DISTINCT a1, a2 FROM t1 LEFT SEMI join t2 on a1 <> b1 and a2 <> b2

Describe the solution you'd like

1. add one more parameter to indicate whether the equality condition are null safe or not in joins' DataFrame API and various join ops
2. passing the null safe equality property down to the native execution level
3. build is_equal in src/daft-table/src/ops/joins/hash_join.rs#hash_semi_anti_join and other related code, makes the execution null safe aware

Describe alternatives you've considered

Another possible solution is to make join operators to relies on join conditions rather the left_on and right_on keys directly, in that way, null safe equal could be easily added as a new expression.
However, that would require massive code change in daft's current code base and I don't think it's worthy for just null safe equal support.

Additional Context

I can submit a PR to add null safe equal support if we all agree it's the right time to add.

Would you like to implement a fix?

No

[advancedxy]

@jaychia @colin-ho it would be much appreciated if you can have some comments on this feature.

[samster25]

Hi @advancedxy, thanks for making an issue here! @universalmind303 is building out SQL support and @kevinzwang has done lots of work on the semi joins. Would love to hear their thoughts

[kevinzwang]

What do you think about doing an outer join + filter instead? Would this work:

SELECT DISTINCT a1, a2 
  FROM (t1 LEFT OUTER JOIN t2 ON a1 = b1 AND a2 = b2) 
  WHERE (a1 = b1 OR (a1 IS NULL and b1 IS NULL)) AND (a2 = b2 OR (a2 IS NULL and b2 IS NULL))

[advancedxy]

What do you think about doing an outer join + filter instead? Would this work:

SELECT DISTINCT a1, a2 
  FROM (t1 LEFT OUTER JOIN t2 ON a1 = b1 AND a2 = b2) 
  WHERE (a1 = b1 OR (a1 IS NULL and b1 IS NULL)) AND (a2 = b2 OR (a2 IS NULL and b2 IS NULL))

left outer join + filter might work for normal cases, but it doesn't handle null input on the left side correctly. Consider the following case:

-- select * from t1
+----+
|  a1|
+----+
|   1|
|NULL|
+----+

-- select * from t2
+---+
| b1|
+---+
|  1|
|  2|
+---+

-- the output of intersect should be
-- select a1 from t1 intersect select b1 from t2
+---+
| a1|
+---+
|  1|
+---+

-- the output of left outer + filter
-- select distinct t1.a1 from (t1 left outer join t2 on a1=b1) where (a1=b1 or (a1 is null and b1 is null)
+----+
|  a1|
+----+
|   1|
|NULL|
+----+

Besides the correctness issue, the left outer join + filter might have performance issue considering:

1. for large table/Dataframe that has thousands of columns, the filter expressions will be exploded, which might bring some evaluation overhead
2. the number of output of left out join might be multiplied if there are many matches in the right, which brings more work to the distinct operator

And BTW, I think null safe equal join is applicable to all type of joins, not just for semi joins. It's just the intersect operator could be implemented by semi join with null safe equal.

[advancedxy]

Hi @advancedxy, thanks for making an issue here! @universalmind303 is building out SQL support and @kevinzwang has done lots of work on the semi joins. Would love to hear their thoughts

Thanks for pinging them and the background. I will reach to them instead when having SQL or join related issues/PRs.

[advancedxy]

What do you think about doing an outer join + filter instead? Would this work:

SELECT DISTINCT a1, a2 
  FROM (t1 LEFT OUTER JOIN t2 ON a1 = b1 AND a2 = b2) 
  WHERE (a1 = b1 OR (a1 IS NULL and b1 IS NULL)) AND (a2 = b2 OR (a2 IS NULL and b2 IS NULL))

I did another digging on this: maybe we don't need to pass the null_safe_equal parameter down to the physical operator side, the null equal safe a1 <> b1 is effective the same as nvl(a1, default_value) = nvl(b1, default_value) and isnull(a1) = isnull(b1) where the default value is the zero value for the corresponding data type.

SELECT DISTINCT a1, a2 FROM t1 LEFT SEMI join t2 on a1 <> b1 and a2 <> b2
-- is effectively the same as the following supposing a1/b1 is in string type, a2/ b2 is in int type
SELECT DISTINCT a1, a2 FROM t1 LEFT SEMI join t2 on nvl(a1, '') = nvl(b1, '') and is_null(a1) = is_null(b1) and nvl(a2, 0) = nvl(b2, 0) and is_null(a2) = is_null(b2)

So I think we only need null safe equal parameter in the DataFrame and logical plan level, which would make the whole change less invasive.

Anyway, I think I can add intersect operation first by writing null safe equal in an expanded manner. We can discuss a bit more here about how to support null safe equals in joins generally.

[kevinzwang]

I think a null safe equality does make sense. We could make it an expression as well, similar to pyspark's eqNullSafe. @advancedxy thanks for bringing this up, and feel free to take a stab at implementation yourself first!

[advancedxy]

similar to pyspark's eqNullSafe.

Good point. I may make a PR about intersect support first to demonstrate how null safe equal could be rewrote, then I can submit PRs about null safe equal in join and then the eqNullSafe expression.

[kevinzwang]

Thank you @advancedxy !