Skip to content

Conversation

Tishj
Copy link
Contributor

@Tishj Tishj commented Feb 11, 2024

https://github.com/duckdb/duckdb/actions/runs/7858410788/job/21443540929

with groups as (select distinct g from dummy)
select g, FINALIZE(sum_state), FINALIZE(sum_state2), FINALIZE(COMBINE(sum_state, sum_state2))  from groups left join state2 using(g) left join (select g, sum(d) EXPORT_STATE sum_state2 from dummy where g >= 3 GROUP BY g) using (g) order by g;
================================================================================
Mismatch on row 1, column 1
7 <> 0
================================================================================
Expected result:
================================================================================
0    450    NULL    450
1    460    NULL    460
2    470    NULL    470
3    480    480    960
4    490    490    980
5    NULL    500    500
6    NULL    510    510
7    NULL    520    520
8    NULL    530    530
9    NULL    540    540
================================================================================
Actual result:
================================================================================
7    NULL    520    520
8    NULL    530    530
9    NULL    540    540
0    450    NULL    450
1    460    NULL    460
2    470    NULL    470
3    480    480    960
4    490    490    980
5    NULL    500    500
6    NULL    510    510

@Tishj Tishj marked this pull request as draft February 11, 2024 09:56
@Tishj
Copy link
Contributor Author

Tishj commented Feb 11, 2024

It looks like ALTERNATIVE_VERIFY=1 is the reason for this failure, maybe the solution is actually require noalternativeverify or there is a bug somewhere

@kryonix
Copy link
Contributor

kryonix commented Feb 11, 2024

This may be related to #10357. ALTERNATIVE_VERIFY forces CTEs to be materialized. As materialized CTEs after this PR can be executed in parallel, the ordering is no longer guaranteed and an ORDER BY-clause must be used. Edit: Just saw that the query already has an ORDER BY-clause. That's strange. There is propably something wrong with the OrderPreservationType-information of materialized CTEs.

@Mytherin Mytherin marked this pull request as ready for review February 11, 2024 10:38
@Tishj
Copy link
Contributor Author

Tishj commented Feb 11, 2024

This may be related to #10357. ALTERNATIVE_VERIFY forces CTEs to be materialized. As materialized CTEs after this PR can be executed in parallel, the ordering is no longer guaranteed and an ORDER BY-clause must be used. Edit: Just saw that the query already has an ORDER BY-clause. That's strange. There is propably something wrong with the OrderPreservationType-information of materialized CTEs.

I think you're right, so this is probably not the fix, thanks for providing the much needed context I was missing 👍

I assume this is the part that sets this in motion?

#ifdef DUCKDB_ALTERNATIVE_VERIFY
		if (cte.ctematerialized == duckdb_libpgquery::PGCTEMaterializeDefault) {
#else
		if (cte.ctematerialized == duckdb_libpgquery::PGCTEMaterializeAlways) {
#endif

@Tishj
Copy link
Contributor Author

Tishj commented Feb 11, 2024

@kryonix

explain_key     explain_value
VARCHAR VARCHAR
[ Rows: 1]
physical_plan   ┌───────────────────────────┐                                                                                       
│            CTE            │                                                                                       
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                                                       
│           groups          ├──────────────┐                                                                        
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │              │                                                                        
│           idx: 0          │              │                                                                        
└─────────────┬─────────────┘              │                                                                                                     
┌─────────────┴─────────────┐┌─────────────┴─────────────┐                                                          
│         PROJECTION        ││          ORDER_BY         │                                                          
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
│__internal_decompress_integ││          ORDERS:          │                                                          
│     ral_bigint(#0, 0)     ││       "groups".g ASC      │                                                          
└─────────────┬─────────────┘└─────────────┬─────────────┘                                                                                       
┌─────────────┴─────────────┐┌─────────────┴─────────────┐                                                          
│       HASH_GROUP_BY       ││         PROJECTION        │                                                          
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
│             #0            ││             g             │                                                          
│                           ││    finalize(sum_state)    │                                                          
│                           ││    finalize(sum_state2)   │                                                          
│                           ││finalize(combine(sum_state,│                                                          
│                           ││        sum_state2))       │                                                          
└─────────────┬─────────────┘└─────────────┬─────────────┘                                                                                       
┌─────────────┴─────────────┐┌─────────────┴─────────────┐                                                          
│         PROJECTION        ││         HASH_JOIN         │                                                          
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
│          dummy.g          ││           RIGHT           │                                                          
│                           ││           g = g           ├──────────────┐                                           
│                           ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │              │                                           
│                           ││          EC: 100          │              │                                           
└─────────────┬─────────────┘└─────────────┬─────────────┘              │                                                                        
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐                             
│         PROJECTION        ││         PROJECTION        ││         HASH_JOIN         │                             
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                             
│__internal_compress_integra││__internal_decompress_integ││           RIGHT           │                             
│     l_utinyint(#0, 0)     ││     ral_bigint(#0, 3)     ││           g = g           ├──────────────┐              
│                           ││             #1            ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │              │              
│                           ││                           ││           EC: 5           │              │              
└─────────────┬─────────────┘└─────────────┬─────────────┘└─────────────┬─────────────┘              │                                           
┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││   PERFECT_HASH_GROUP_BY   ││         SEQ_SCAN          ││          CTE_SCAN         │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│           dummy           ││             #0            ││           state2          ││           idx: 0          │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││aggregate_state_export_sum(││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││                           │
│             g             ││            #1)            ││             g             ││                           │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││                           ││         sum_state         ││                           │
│          EC: 100          ││                           ││   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   ││                           │
│                           ││                           ││           EC: 5           ││                           │
└───────────────────────────┘└─────────────┬─────────────┘└───────────────────────────┘└───────────────────────────┘                             
                             ┌─────────────┴─────────────┐                                                          
                             │         PROJECTION        │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │             g             │                                                          
                             │             d             │                                                          
                             └─────────────┬─────────────┘                                                                                       
                             ┌─────────────┴─────────────┐                                                          
                             │         PROJECTION        │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │__internal_compress_integra│                                                          
                             │     l_utinyint(#0, 3)     │                                                          
                             │             #1            │                                                          
                             └─────────────┬─────────────┘                                                                                       
                             ┌─────────────┴─────────────┐                                                          
                             │         SEQ_SCAN          │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │           dummy           │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │             g             │                                                          
                             │             d             │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │ Filters: g>=3 AND g IS NOT│                                                          
                             │            NULL           │                                                          
                             │   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │                                                          
                             │          EC: 100          │                                                          
                             └───────────────────────────┘

physical CTE says SinkOrderDependent = false so that explains a lot

@Tishj Tishj marked this pull request as draft February 11, 2024 12:47
@kryonix
Copy link
Contributor

kryonix commented Feb 11, 2024

I assume this is the part that sets this in motion?

#ifdef DUCKDB_ALTERNATIVE_VERIFY
  	if (cte.ctematerialized == duckdb_libpgquery::PGCTEMaterializeDefault) {
#else
		if (cte.ctematerialized == duckdb_libpgquery::PGCTEMaterializeAlways) {
#endif

Yes, that's correct. The idea was that this generates more test cases "for free".
Materialization of CTEs should not change the result in general (there is a corner case for recursive CTEs).

The PhysicalCTE operator is similar to DELIM-Joins. I think the sink (materialization phase) is fine, but the source seems to be the issue. Delim joins define the following OrderPreservationType for the source, which materialized CTEs may be missing:

OrderPreservationType SourceOrder() const override {
    return OrderPreservationType::NO_ORDER;
}

I suspect that the wrong result collector is used because of that above the physical CTE (which unfortunately is invisible in the plan output).

Side note: #10560 results from the same issue.

@carlopi
Copy link
Contributor

carlopi commented Feb 11, 2024

Side note: #10560 results from the same issue.

Right, thanks for noticing this. @kryonix: would it be better to revert the changes to test/sql/cte/recursive_hang_2745.test ? Or also the rest?

@Tishj
Copy link
Contributor Author

Tishj commented Feb 11, 2024

Ah then it might be a bug in StreamQueryResult, because the ALTERNATIVE_VERIFY flag makes us use the stream query result in the unittester.

If it's batched we'll use the single threaded collector, if it's not we'll parallelize (if the rest of the plan agrees)

We're hitting this:

	if (!PhysicalPlanGenerator::PreserveInsertionOrder(context, *data.plan)) {
		// the plan is not order preserving, so we just use the parallel materialized collector
		if (data.is_streaming) {
			return make_uniq_base<PhysicalResultCollector, PhysicalBufferedCollector>(data, true); // <-- this
		}
		return make_uniq_base<PhysicalResultCollector, PhysicalMaterializedCollector>(data, true);

So I think the problem is that the PhysicalCTE does not propagate that insertion order needs to be preserved down to the result collector

@kryonix
Copy link
Contributor

kryonix commented Feb 12, 2024

I think I have found a solution. I will do a few more tests before I open a PR.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants