Duckdb: Correlated SQL sub-queries crashing

[PedroTadim]

I have been testing some complex SQL sub-queries on MonetDB before the Nov2019 release and they triggered crashes. Meanwhile I see the same happens on DuckDB.

I think the best plan should be fixing one query at the time, because some of the problems might be correlated altogether.

Bellow each query I output the outcome from MonetDB, but notice that it might differ on DuckDB depending where the correlation happens, either inner or outer query.

CREATE TABLE tbl_ProductSales (ColID int, Product_Category  varchar(64), Product_Name  varchar(64), TotalSales int); 
INSERT INTO tbl_ProductSales VALUES (1,'Game','Mobo Game',200),(2,'Game','PKO Game',400),(3,'Fashion','Shirt',500),(4,'Fashion','Shorts',100);
CREATE TABLE another_T (col1 INT, col2 INT, col3 INT, col4 INT, col5 INT, col6 INT, col7 INT, col8 INT);
INSERT INTO another_T VALUES (1,2,3,4,5,6,7,8), (11,22,33,44,55,66,77,88), (111,222,333,444,555,666,777,888), (1111,2222,3333,4444,5555,6666,7777,8888);

SELECT col1 IN (SELECT ColID + col1 FROM tbl_ProductSales) FROM another_T GROUP BY col1; 
    -- False
    -- False
    -- False
    -- False

PS: I know these queries are very complex and barely anyone writes them. At the same time, I have a hard time figuring out Niels' code 🙁

[hannesmuehleisen]

Indeed a bug, I get
Assertion failed: (index != INVALID_INDEX), function VisitReplace, file ../../src/execution/column_binding_resolver.cpp, line 23.

[Mytherin]

Thanks for the bug report! If something is not working properly it will always eventually end up in a real query :) it's much better to catch it early in a small unit test. The bug seems to be related to the aggregation, basically the correlated column col1 is bound to the base table column col1 instead of to the group col1, which then fails to resolve the column during the column binding as the base table columns are not available after the grouping. Will look into fixing it now.

[Mytherin]

Interestingly this is not actually related to subqueries, but rather to GROUP BY binding. The subquery handling is fine. The following query experiences a crash as well:

CREATE TABLE another_T (col1 INT);
SELECT col1+1, col1+42 FROM another_T GROUP BY col1+1;

Going to take another look tomorrow when I have time.

[Mytherin]

Addressed in b077e6673ca2bf02dba2135f62790eedbe5a0a91, this was basically a combination of two problems:

(1) If a query had no aggregations but only groups, no error would be thrown if there were column references bound outside of the original grouping columns and the subsequent column resolution would fail.

(2) Binding to the group inside the subquery would not work because BindTableNames() was not called prior to performing the group lookup, leading to col1 being not equal to another_T.col1.

There was also an additional problem found relating to the BoundExpression that would make a composite grouping column not bind properly in subqueries, e.g. the following query would fail to bind:

SELECT (col1 + 1) IN (SELECT ColID + (col1 + 1) FROM tbl_ProductSales) FROM another_T GROUP BY (col1 + 1);

Note that this query actually also fails to bind in PostgreSQL, but SQLite correctly binds it. This I resolved by making the BoundExpression use the underlying ParsedExpression, so now this query also works correctly.

All in all three bugs found :) Thanks for the bug report! Let us know if you find any other issues.

[PedroTadim]

This was really fast Mark!
This is the next one:

SELECT
    col5 = ALL (SELECT 1 FROM tbl_ProductSales HAVING MIN(col8) IS NULL)
FROM another_T
GROUP BY col1, col2, col5, col8;
    -- True
    -- True
    -- True
    -- True

It gives me a SIGSEGV in in std::__cxx11::basic_string.
I think the issue is because the sub-query has an HAVING clause without GROUP BY.

[Mytherin]

This might be an old bug, for me I get the following error: Query failed with message: Parser: a GROUP BY clause is required before HAVING. Thanks for the report though! Let me know if you have more problematic subqueries.

[PedroTadim]

I'm using the Debug build instead of RelWithDebInfo (i.e. default one). We have to check if the SQL standard allows this or not. I think it does, as I compiled it successfully on MonetDB and PostgreSQL. I know the only purpose of it is to either output the global aggregate value or an empty result set, which makes it not much useful.

[hannesmuehleisen]

I would think that SELECT 1 FROM tbl_ProductSales HAVING MIN(TotalSales) IS NULL is not permissible on its own already? But indeed Postgres, SQL Server and MySQL disagree.

[Mytherin]

SQLite does not allow a HAVING clause without a GROUP BY clause. I would also argue that there is not much of a point to allowing it. It only introduces potential errors for users. Testing it I did find this bug in MonetDB (although I am using an old version)

SELECT SUM(42) HAVING 42>80;
-- expected result: empty set
-- actual result: 42

[PedroTadim]

Thanks Mark for the bug in MonetDB, I fixed it today. I tried the following little query on DuckDB:

select avg(rank() over ()) over();

and it crashed. MonetDB outputs a result, but it shouldn't as windowing functions cannot be nested. About the HAVING query I have to say DuckDB allows WHERE without FROM, which can correlate to HAVING without GROUP BY. Let's fix the bugs together :)

[PedroTadim]

Doing this combination of queries, makes the second go forever. Maybe it's stuck on an infinite loop:

SELECT
    NOT -SUM(col2) NOT IN (SELECT ColID FROM tbl_ProductSales GROUP BY ColID HAVING SUM(ColID - col8) <> col5),
    NOT col5 = ALL (SELECT 1 FROM tbl_ProductSales HAVING MAX(col8) > 2 AND MIN(col8) IS NOT NULL),
    NOT EXISTS (SELECT ColID - 12 FROM tbl_ProductSales GROUP BY ColID HAVING MAX(col2) IS NULL OR NOT col8 <> 2 / col1)
FROM another_T
GROUP BY col1, col2, col5, col8;
--Error: Parser: a GROUP BY clause is required before HAVING

SELECT
    SUM(col1) IN (SELECT DISTINCT col2 FROM another_T GROUP BY col2)
FROM another_T
GROUP BY col4;
    -- False
    -- False
    -- False
    -- False

The backtrace shows it's stuck on a lock. Maybe because the query before didn't release the lock after throwing the error. Please confirm if you can reproduce this.

[Mytherin]

Indeed, thanks for the bug reports! I will take a look next week as I'm still on holiday now and will be without my laptop for a few days. You have gotten very good at finding bugs and it's great to catch them early like this :) thanks for taking the time to add small testcases too!

[Mytherin]

I just fixed the nested window function one, but I cannot reproduce the second one. Did you run only the create table + inserts and those two queries, or where there other queries involved as well? Did you run them in the shell?

As for the having, indeed since other RDBMS engines allow it perhaps it's better we also allow it. I will take a look at fixing it and allowing a HAVING without a GROUP BY clause as well.

[PedroTadim]

Yes. I switched to the RelWithDebInfo build. I started the shell, then created the two tables and ran the two queries combination shown above.

[Mytherin]

Ah I see, I tried it now on Linux and I get the same behavior, however it looks like it's related to the shell itself and not to the database. The shell doesn't properly handle deletion of the error because the statement is not properly initialized. I won't fix this for now, the shell in its entirety was written very early in DuckDB's lifecycle and in my opinion requires a rewrite anyway. The current version is more for easy testing of queries rather than being very stable/bug-free. Thanks for the report :)

[Mytherin]

HAVING without GROUP BY is now allowed #306.

[hannesmuehleisen]

@PedroTadim this issue can be closed now?

[PedroTadim]

Here's the next one:

SELECT
    CASE WHEN 1 IN (SELECT (SELECT MAX(col7)) UNION ALL (SELECT MIN(ColID) FROM tbl_ProductSales INNER JOIN another_T t2 ON t2.col5 = t2.col1)) THEN 2 ELSE NULL END
FROM another_T t1;

Depending here the correlation happens, the output can be either a single NULL value or four. I got a Segmentation fault.

[hannesmuehleisen]

@PedroTadim do you have more? if so, please post all of them. This trickling method seems odd.

[PedroTadim]

After this one, we can close it, and I take the remaining queries offline.

[Mytherin]

Thanks for the bug report again! Should be fixed in b0f46c3312b6fa10f16d4c64ecd301ba388884da, the plan_subquery and has_unplanned_subqueries were not properly being propagated through set operations which lead to nested correlated subqueries being prematurely planned which triggered an assertion (and which lead to a crash on release mode).

Maybe indeed it is better to take the queries offline, or post all the queries here. I realize the bugs might be "correlated" (hehe) but better to have a large batch of queries to test at once to verify they all work correctly :) also less work for you in having to recompile and verify again after every fix.

[Mytherin]

Closing this now