Document non-deterministic ordering of joining, group by, etc.

[caseykneale]

Describe the bug

I am using the SQL interface to query parquet data. I am registering each file in a datafusion context. The query contains some joins, and groupbys (where I speculate the trouble is). Maybe 1/5 attempts I get the correct answer from a compiled binary (0 records). but the other 4/5 attempts I see a lot of erroneous results appearing.

So to be clear, the correct answer is 0 records, and we should never see records appearing otherwise (unless DF's groupby operations are nondeterministic/nonsequential?). Yet I only see that on a rare occasion of runs.

I feel like I might be missing something here(do I need to sort first?) but this looks like a bug to me.

To Reproduce

I can't share the data, but the query looks like the last two queries on this sql fiddle(they're the same) I borrowed from someone on stack overflow and wrote the query I care about.

https://dbfiddle.uk/hA8-ejaw

In this example we do see some rows being returned but in my actual use case there should be none.

Expected behavior

The correct answer of records are returned or there is documentation explaining why this doesn't happen/an example?

Additional context

No response

[caseykneale]

I figured it out. Basically joins often happen out of the original order of the data, which is a good thing in general because we aren't doing single core linear search joins, but when you go to groupby after you may end up with out of order data. Groupbys have no context for this change, and incorrectly returns unexpected values.

So if you run into this you need to make a subquery where you orderby AFTER the internal join. So the order of the groups is preserved for the groupby step. I would close this out, but I really wish this was in the documentation.

[Dandandan]

@caseykneale thanks for opening the issue. It would help if you could provide a small reproducible example (example query with some data). Would it be possible to provide such an example?

[caseykneale]

@Dandandan Thanks for the reply. If you read my second comment I think the main thing here is adding documentation about how using ORDER BY post joins may be necessary to get deterministic ordering for operations such as groupbys. I think this is somewhat known/implied for technologies similar to this, but its a gotchya that people may forget about and is probably worth mentioning. Maybe just a section in the SQL capabilities docs about the differences between DF and a typical SQL DB would be useful.

Feel free to close this issue out at your own discretion. It's not a bug, but a documentation improvement suggestion.

[Dandandan]

@Dandandan Thanks for the reply. If you read my second comment I think the main thing here is adding documentation about how using ORDER BY post joins may be necessary to get deterministic ordering for operations such as groupbys. I think this is somewhat known/implied for technologies similar to this, but its a gotchya that people may forget about and is probably worth mentioning. Maybe just a section in the SQL capabilities docs about the differences between DF and a typical SQL DB would be useful.

Thanks for clarifying.
Yes, some join types are not order preserving. Also DataFusion will parallelize the query plan, which also might change the order of the output.

Though I fail to see how the example you linked applies to those queries and group by specifically: group by shouldn't depend on the order of the input (some aggregation functions might) and should not result in the number of rows to be different, only the order of rows.

[Dandandan]

Could it be you're reading only a part of the output (e.g. only reading one of the output partitions)?

[caseykneale]

Could it be you're reading only a part of the output (e.g. only reading one of the output partitions)?

The aggregation functions I was using were counting over a column with nulls. Introducing an ORDER BY over the aggregation keys, before the GROUP BY, but after the JOINs resolved the issue.

All data for each table is in 1 parquet file. I am serializing the output from the query directly from the vec of record batches in a vec of simple structs.

My instinct was that groupbys require ordering as there are no indices on tables, and joins are nondeterministic by design, leading to groups that are split across an intermediate form. Possibly across partitions? That's not a bug in my opinion, but worth documenting. However, if groupbys are skipping partitions when records are far enough out of order - that could be a bug? It depends on how groupbys are implemented, and what an end user should expect of them.

In several dataframe technologies I've used it's been expected to have sorted the data before performing a groupby. Maybe some implementations do this for the end user without them explicitly writing it, but several I've used and made did not. So it's only a bug if this wasn't the teams intentions in my opinion :), otherwise it's a documentation issue, or there's something I'm still missing here.

[Xavrir]

Hi! I would like to work on improving the documentation for this. My plan is to add a note to the SQL user guide that result row order is only guaranteed when an ORDER BY clause is present, especially after joins, GROUP BY, UNION, and parallel scans. If that sounds reasonable, I will open a PR shortly.

[Xavrir]

Hi again I opened #21019 for this. It adds a note in the SQL SELECT guide and FAQ explaining that DataFusion only guarantees row order when ORDER BY is present, especially for joins, GROUP BY, UNION, and other parallel execution paths. If you would prefer this guidance to live in a different page as well, I am happy to adjust it.