Referential dependencies for RESTORE #43834

vitlibar · 2022-11-30T15:00:58Z

Changelog category:

Improvement

Changelog entry:

Implement referential dependencies and use them to create tables in the correct order while restoring from a backup.

Algunenano · 2022-12-01T00:45:45Z

src/Storages/System/StorageSystemTables.cpp

@@ -37,8 +37,8 @@ StorageSystemTables::StorageSystemTables(const StorageID & table_id_)
        {"data_paths", std::make_shared<DataTypeArray>(std::make_shared<DataTypeString>())},
        {"metadata_path", std::make_shared<DataTypeString>()},
        {"metadata_modification_time", std::make_shared<DataTypeDateTime>()},
-        {"dependencies_database", std::make_shared<DataTypeArray>(std::make_shared<DataTypeString>())},
-        {"dependencies_table", std::make_shared<DataTypeArray>(std::make_shared<DataTypeString>())},
+        {"dependent_views_database", std::make_shared<DataTypeArray>(std::make_shared<DataTypeString>())},


Will this break queries accessing the old names? If so, is it really worth it?

I'd like to rename it, and this is a system table so it can be changed from time to time.
But it's not necessary to do that right now in this PR, so I think I'll move this change to a separate PR.

I'd like to rename it, and this is a system table so it can be changed from time to time.

Yes, but it's still a pain from the user point of view as it requires different queries for different CH version (and CH doesn't support SQL scripts).

If you are thinking about renaming it, why not take the opportunity to improve the API with other types? Maybe it should be an array of tuples (database, table) so you don't have to be doing arrayZip to use get the pair.

when restoring tables from a backup.

Slach · 2022-12-02T14:08:02Z

will this PR resolve #39416 ?

vitlibar · 2022-12-02T14:08:54Z

will this PR resolve #39416 ?

I expect so.

tavplubix · 2022-12-02T14:17:37Z

tests/queries/0_stateless/01155_rename_move_materialized_view.sql

@@ -65,7 +65,9 @@ SELECT dictGet('test_01155_ordinary.dict', 'x', 'after renaming database');
 SELECT database, substr(name, 1, 10) FROM system.tables WHERE database like 'test_01155_%';

 -- Move tables back
+SET check_table_dependencies=0; -- Otherwise we'll get error "test_01155_atomic.dict depends on test_01155_ordinary.dist" in the next line.


The comment is incorrect because there's no table test_01155_atomic.dict when we rename test_01155_ordinary to test_01155_atomic

The comment should be

Otherwise we'll get error "test_01155_ordinary.dict depends on test_01155_ordinary.dist" in the next line.

I'll change that in my next PR.

tavplubix · 2022-12-02T14:48:11Z

src/Interpreters/Context.h

@@ -14,6 +14,7 @@
 #include <Common/MultiVersion.h>
 #include <Common/OpenTelemetryTraceContext.h>
 #include <Common/RemoteHostFilter.h>
+#include <Common/ThreadPool.h>


This include looks redundant

ThreadPool is used in this header

I found only two usages: two functions return ThreadPool &, but it does not require the definition

tavplubix · 2022-12-02T15:35:03Z

src/Databases/DDLDependencyVisitor.cpp

+            /// TO target_table (for materialized views)
+            if (to_table.database.empty())
+                to_table.database = data.default_database;


It should not be empty, because the query is normalized . Btw, can default_database be different from current_database? (Seems like it can)

It must be the same for the global context. I just thought maybe it's better to check dependencies for a backup in the query context, not in the global context, so probably I'll replace that with the current database.

I changed the code so now it uses the current database (#44158)

tavplubix · 2022-12-02T15:38:26Z

src/Databases/DDLDependencyVisitor.cpp

+        QualifiedTableName as_table{create.as_database, create.as_table};
+        if (!as_table.table.empty())
+        {
+            /// AS table_name
+            if (as_table.database.empty())
+                as_table.database = data.default_database;
+            data.dependencies.emplace(as_table);


Probably we should not count it as a referential dependency, because we always replace AS table clause with normal table definition.

I thought maybe someone will try to forge a backup manually so I tried to support maximum of what's easy to support, and not to rely on that all the queries are normalized too much. Because a backup works with create queries, and not attach queries. Though it's very likely that all queries inside a backup are normalized (because those queries are basically the output of SHOW CREATE TABLE)

tavplubix · 2022-12-02T15:56:18Z

src/Databases/DDLDependencyVisitor.cpp

+    /// ASTTableExpression represents a reference to a table in SELECT query.
+    /// DDLDependencyVisitor should handle ASTTableExpression because some CREATE queries can contain SELECT queries after AS
+    /// (for example, CREATE VIEW).
+    void visitTableExpression(const ASTTableExpression & expr, DDLDependencyVisitor::Data & data)
+    {
+        if (!expr.database_and_table_name)
+            return;


Could you please add a test with queries like CREATE VIEW ... AS SELECT ... FROM (SELECT ... FROM table)? (I guess it will just visit another ASTTableExpression, and it will work fine, but it's good to have more complex tests)

I added the test in #44158

tavplubix · 2022-12-02T16:02:04Z

src/Databases/DDLDependencyVisitor.cpp

+        if (table_engine.name == "Buffer")
+            extractDatabaseAndTableNameFromArguments(table_engine, data, 0, 1);


It would be great to add a test for this as well

I had the test before but it was removed because I needed to shorten this PR. I'll add it again in the next PR.

I added the test in #44158

tavplubix · 2022-12-02T16:04:42Z

src/Databases/DDLDependencyVisitor.cpp

+    void visitTableEngine(const ASTFunction & table_engine, DDLDependencyVisitor::Data & data)
    {
-        /// It can be table/dictionary from default database or XML dictionary, but we cannot distinguish it here.
-        qualified_name.database = data.default_database;
+        if (table_engine.name == "Dictionary")
+            extractQualifiedTableNameFromArgument(table_engine, data, 0);


Should we also handle Distributed and Merge engines?

Distributed - yes, in the next PR. I'm not sure about Merge (because of regexp)

The Distributed engine is handled in #44158

tavplubix · 2022-12-02T18:34:06Z

src/Databases/TablesDependencyGraph.h

+    void log() const;
+
+private:
+    struct Node : public std::enable_shared_from_this<Node>


The only reason why enable_shared_from_this is required is

nodes.erase(node->shared_from_this());

Consider using "heterogeneous lookup": https://godbolt.org/z/YKn96GzWh

I did that in #44158

Slach · 2022-12-02T19:13:30Z

@vitlibar @tavplubix could you look to
#39416 (comment)

is "head" version is build for master github branch?

tavplubix · 2022-12-02T19:18:30Z

src/Databases/TablesDependencyGraph.cpp

+    if (remove_isolated_tables && dependency_node->dependencies.empty() && dependency_node->dependents.empty())
+    {
+        removeNode(dependency_node);
+        if (table_node == dependency_node)


Do I understand correctly that it's possible only when a table depends on itself? I would prefer to forbid it and do not add dependencies like this

Yes. But it looks like there is no difference actually between a view selecting from itself and a view selecting from a second view which selects from the first view. So I think the graph can handle it like any other cyclic dependency.

tavplubix · 2022-12-02T19:20:36Z

src/Databases/TablesDependencyGraph.cpp

+        }
+    }
+
+    if (remove_isolated_tables && !table_node_removed && table_node->dependencies.empty() && table_node->dependents.empty())


table_node->dependencies.empty() is always true

tavplubix · 2022-12-02T19:24:07Z

src/Databases/TablesDependencyGraph.cpp

+            if (table_id.hasUUID() && node->storage_id.hasUUID() && (table_id.uuid != node->storage_id.uuid))
+                return nullptr; /// UUID is different, it's not the node we're looking for.


When is it possible?

If everything is fine that shouldn't happen. I've added a comment and a warning here (#44158).

tavplubix · 2022-12-02T19:58:08Z

src/Databases/TablesDependencyGraph.cpp

+    while (!nodes_to_process.empty())
+    {
+        size_t old_num_sorted = nodes_sorted_by_level_lazy.size();
+
+        for (auto it = nodes_to_process.begin(); it != nodes_to_process.end();)


Seems like it's at least O(V^2) in the worst case. Imagine a graph that looks like a linked list (A -> B -> C -> D -> ...). It will remove only one node on each iteration of the outer loop. But the inner loop will do nodes_to_process.size() iterations each time. So it will be V + (V-1) + (V-2) + (V-3) + ... = O(V^2) iterations in total. But the previous topsort implementation was O(V + E) if I'm not mistaken.

Seems like it's even O(V^3) if we add A->C, A->D, A->E, ..., B->D, B->E, ... edges to the linked list.

I changed the code so now it's O(V + E) again.

nickitat · 2022-12-03T22:04:29Z

#43911

Fix clang tidy errors introduced in #43834

tavplubix · 2022-12-05T11:50:53Z

src/Databases/TablesLoader.cpp

-    auto need_exclude_dependency = [this, remove_loaded](const QualifiedTableName & dependency_name, const DependenciesInfo & info)
+    for (const auto & [table_name, table_metadata] : metadata.parsed_tables)
+    {
+        auto new_loading_dependencies = getLoadingDependenciesFromCreateQuery(global_context, table_name, table_metadata.ast);


It will traverse all ASTs in single thread, but maybe it's okay

tavplubix · 2022-12-05T11:56:18Z

src/Interpreters/DatabaseCatalog.cpp

 {
+    const auto & dependents = referential_dependencies.getDependents(removing_table);


Maybe we should add another setting for checking referential dependencies, but I'm not sure

tavplubix

In general LGTM

vitlibar · 2022-12-05T14:15:49Z

In general LGTM

Thank you for the review, I'm working on your comments and will create a new PR soon.

Slach · 2022-12-05T14:16:50Z

@vitlibar please refer new PR in this comments

Algunenano

I've been looking at the code changes due to a related issue (#44496, but not introduced in this PR) and it seems to be it's missing several functions

Algunenano · 2022-12-22T15:08:21Z

src/Databases/DDLLoadingDependencyVisitor.cpp

+
+ssize_t DDLMatcherBase::getPositionOfTableNameArgument(const ASTFunction & function)
+{
+    if (function.name == "joinGet" ||


This seems to be missing joinGetOrNull and could be greatly simplified (and grouped logically) by doing something like:

if (functionIsJoinGet(function.name) || functionIsDictGet(function.name))

Algunenano · 2022-12-22T15:09:11Z

src/Databases/DDLLoadingDependencyVisitor.cpp

+        function.name.starts_with("dictGet"))
+        return 0;
+
+    if (Poco::toLower(function.name) == "in")


In a similar fashion, what about notIn, nullIn, globalIn, etc? Should this be functionIsInOrGlobalInOperator(function.name)?

Algunenano · 2022-12-22T15:10:47Z

src/Databases/DDLDependencyVisitor.cpp

    {
-        assert(false);
-        return;
+        if (function.name == "joinGet" || function.name == "dictHas" || function.name == "dictIsIn" || function.name.starts_with("dictGet"))


Same here. Having this logic repeated seems wrong and I think using the functions in misc.h is much cleaner.

vitlibar added the do not test disable testing on pull request label Nov 30, 2022

vitlibar mentioned this pull request Nov 30, 2022

Fix calculating loading dependencies #39825

Closed

tavplubix self-assigned this Nov 30, 2022

nikitamikhaylov added the force tests The label does nothing, NOOP, None, nil label Nov 30, 2022

robot-clickhouse added the pr-improvement Pull request with some product improvements label Nov 30, 2022

nikitamikhaylov removed the force tests The label does nothing, NOOP, None, nil label Nov 30, 2022

Algunenano reviewed Dec 1, 2022

View reviewed changes

vitlibar added 2 commits December 1, 2022 14:55

Rename DDLDependencyVisitor -> DDLLoadingDependencyVisitor.

c0388d7

Move building a loading graph to TablesLoader.

5ef8967

vitlibar force-pushed the referential-dependencies branch from ecdeb4e to c565430 Compare December 1, 2022 15:11

vitlibar removed the do not test disable testing on pull request label Dec 1, 2022

vitlibar force-pushed the referential-dependencies branch from c565430 to 202eb9a Compare December 1, 2022 15:22

vitlibar marked this pull request as ready for review December 1, 2022 15:24

vitlibar force-pushed the referential-dependencies branch from 6711f26 to cff43d1 Compare December 1, 2022 20:41

vitlibar changed the title ~~Referential dependencies~~ Referential dependencies for RESTORE Dec 1, 2022

vitlibar force-pushed the referential-dependencies branch 2 times, most recently from b7b1da3 to 37546d2 Compare December 1, 2022 21:11

vitlibar added 2 commits December 1, 2022 23:36

Implement referential dependencies for tables and use them

0153edb

when restoring tables from a backup.

Remove StorageID::operator < (because of its inconsistency with ==).

825035d

vitlibar force-pushed the referential-dependencies branch from 37546d2 to 730034a Compare December 1, 2022 22:37

vitlibar added 2 commits December 1, 2022 23:48

Add new tests.

34bce96

Fix test.

e3186b6

vitlibar force-pushed the referential-dependencies branch from 730034a to e3186b6 Compare December 1, 2022 22:50

vitlibar and others added 2 commits December 2, 2022 11:45

Fix memory leak.

dd4966a

Merge branch 'master' into referential-dependencies

63833ff

nikitamikhaylov merged commit e1f7f04 into ClickHouse:master Dec 2, 2022

tavplubix reviewed Dec 2, 2022

View reviewed changes

vitlibar deleted the referential-dependencies branch December 2, 2022 15:30

tavplubix reviewed Dec 2, 2022

View reviewed changes

Slach mentioned this pull request Dec 2, 2022

RESTORE can't recognize source table during restore materialized view #39416

Closed

tavplubix reviewed Dec 2, 2022

View reviewed changes

rschu1ze added a commit that referenced this pull request Dec 4, 2022

Merge pull request #43911 from nickitat/fix_tidy

44312e3

Fix clang tidy errors introduced in #43834

tavplubix reviewed Dec 5, 2022

View reviewed changes

vitlibar mentioned this pull request Dec 12, 2022

Improve referential dependencies #44158

Merged

Algunenano reviewed Dec 22, 2022

View reviewed changes

		if (table_engine.name == "Buffer")
		extractDatabaseAndTableNameFromArguments(table_engine, data, 0, 1);

		if (table_id.hasUUID() && node->storage_id.hasUUID() && (table_id.uuid != node->storage_id.uuid))
		return nullptr; /// UUID is different, it's not the node we're looking for.

		{
		const auto & dependents = referential_dependencies.getDependents(removing_table);

Referential dependencies for RESTORE #43834

Referential dependencies for RESTORE #43834

Conversation

vitlibar commented Nov 30, 2022 • edited

Changelog category:

Changelog entry:

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Slach commented Dec 2, 2022

vitlibar commented Dec 2, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vitlibar Dec 2, 2022 • edited

Choose a reason for hiding this comment

vitlibar Dec 12, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vitlibar Dec 2, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vitlibar Dec 12, 2022 • edited

Choose a reason for hiding this comment

Slach commented Dec 2, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nickitat commented Dec 3, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

tavplubix left a comment

Choose a reason for hiding this comment

vitlibar commented Dec 5, 2022

Slach commented Dec 5, 2022

Algunenano left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vitlibar commented Nov 30, 2022 •

edited

vitlibar Dec 2, 2022 •

edited

vitlibar Dec 12, 2022 •

edited

vitlibar Dec 2, 2022 •

edited

vitlibar Dec 12, 2022 •

edited