duckdb::ColumnDependencyManager Class Reference

Dependency Manager local to a table, responsible for keeping track of generated column dependencies. More...

Collaboration diagram for duckdb::ColumnDependencyManager:

Public Member Functions
	ColumnDependencyManager (ColumnDependencyManager &&other)=default
	ColumnDependencyManager (const ColumnDependencyManager &other)=delete
stack< LogicalIndex >	GetBindOrder (const ColumnList &columns)
	Get the bind order that ensures dependencies are resolved before dependents are.
void	AddGeneratedColumn (LogicalIndex index, const vector< LogicalIndex > &indices, bool root=true)
	Adds a connection between the dependent and its dependencies.
void	AddGeneratedColumn (const ColumnDefinition &column, const ColumnList &list)
	Add a generated column from a column definition.
vector< LogicalIndex >	RemoveColumn (LogicalIndex index, idx_t column_amount)
	Removes the column(s) and outputs the new column indices.
bool	IsDependencyOf (LogicalIndex dependent, LogicalIndex dependency) const
bool	HasDependencies (LogicalIndex index) const
const logical_index_set_t &	GetDependencies (LogicalIndex index) const
bool	HasDependents (LogicalIndex index) const
const logical_index_set_t &	GetDependents (LogicalIndex index) const

Private Member Functions
void	RemoveStandardColumn (LogicalIndex index)
void	RemoveGeneratedColumn (LogicalIndex index)
void	AdjustSingle (LogicalIndex idx, idx_t offset)
vector< LogicalIndex >	CleanupInternals (idx_t column_amount)

Private Attributes
logical_index_map_t< logical_index_set_t >	dependencies_map
	A map of column dependency to generated column(s)
logical_index_map_t< logical_index_set_t >	dependents_map
	A map of generated column name to (potentially generated)column dependencies.
logical_index_map_t< logical_index_set_t >	direct_dependencies
	For resolve-order purposes, keep track of the 'direct' (not inherited) dependencies of a generated column.
logical_index_set_t	deleted_columns

Detailed Description

Dependency Manager local to a table, responsible for keeping track of generated column dependencies.

Constructor & Destructor Documentation

ColumnDependencyManager()

duckdb::ColumnDependencyManager::ColumnDependencyManager

(

)

                                                 {
}

~ColumnDependencyManager()

duckdb::ColumnDependencyManager::~ColumnDependencyManager

(

)

                                                  {
}

Member Function Documentation

GetBindOrder()

stack< LogicalIndex > duckdb::ColumnDependencyManager::GetBindOrder

(

const ColumnList &

columns

)

Get the bind order that ensures dependencies are resolved before dependents are.

Skip the dependents that are also dependencies

If this column does not have dependencies, the queue stops getting filled

                                                                                   {
    stack<LogicalIndex> bind_order;
    queue<LogicalIndex> to_visit;
    logical_index_set_t visited;
 
    for (auto &entry : direct_dependencies) {
        auto dependent = entry.first;
        if (dependencies_map.find(dependent) != dependencies_map.end()) {
            continue;
        }
        bind_order.push(dependent);
        visited.insert(dependent);
        for (auto &dependency : direct_dependencies[dependent]) {
            to_visit.push(dependency);
        }
    }
 
    while (!to_visit.empty()) {
        auto column = to_visit.front();
        to_visit.pop();
 
        if (direct_dependencies.find(column) == direct_dependencies.end()) {
            continue;
        }
        bind_order.push(column);
        visited.insert(column);
 
        for (auto &dependency : direct_dependencies[column]) {
            to_visit.push(dependency);
        }
    }
 
    // Add generated columns that have no dependencies, but still might need to have their type resolved
    for (auto &col : columns.Logical()) {
        // Not a generated column
        if (!col.Generated()) {
            continue;
        }
        // Already added to the bind_order stack
        if (visited.count(col.Logical())) {
            continue;
        }
        bind_order.push(col.Logical());
    }
 
    return bind_order;
}

AddGeneratedColumn() [1/2]

void duckdb::ColumnDependencyManager::AddGeneratedColumn	(	LogicalIndex	index,
		const vector< LogicalIndex > &	indices,
		bool	root = true
	)

Adds a connection between the dependent and its dependencies.

                                                                                                                   {
    if (indices.empty()) {
        return;
    }
    auto &list = dependents_map[index];
    // Create a link between the dependencies
    for (auto &dep : indices) {
        // Add this column as a dependency of the new column
        list.insert(dep);
        // Add the new column as a dependent of the column
        dependencies_map[dep].insert(index);
        // Inherit the dependencies
        if (HasDependencies(dep)) {
            auto &inherited_deps = dependents_map[dep];
            D_ASSERT(!inherited_deps.empty());
            for (auto &inherited_dep : inherited_deps) {
                list.insert(inherited_dep);
                dependencies_map[inherited_dep].insert(index);
            }
        }
        if (!root) {
            continue;
        }
        direct_dependencies[index].insert(dep);
    }
    if (!HasDependents(index)) {
        return;
    }
    auto &dependents = dependencies_map[index];
    if (dependents.count(index)) {
        throw InvalidInputException("Circular dependency encountered when resolving generated column expressions");
    }
    // Also let the dependents of this generated column inherit the dependencies
    for (auto &dependent : dependents) {
        AddGeneratedColumn(dependent, indices, false);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

AddGeneratedColumn() [2/2]

void duckdb::ColumnDependencyManager::AddGeneratedColumn	(	const ColumnDefinition &	column,
		const ColumnList &	list
	)

Add a generated column from a column definition.

                                                                                                       {
    D_ASSERT(column.Generated());
    vector<string> referenced_columns;
    column.GetListOfDependencies(referenced_columns);
    vector<LogicalIndex> indices;
    for (auto &col : referenced_columns) {
        if (!list.ColumnExists(col)) {
            throw BinderException("Column \"%s\" referenced by generated column does not exist", col);
        }
        auto &entry = list.GetColumn(col);
        indices.push_back(entry.Logical());
    }
    return AddGeneratedColumn(column.Logical(), indices);
}

Here is the call graph for this function:

RemoveColumn()

vector< LogicalIndex > duckdb::ColumnDependencyManager::RemoveColumn	(	LogicalIndex	index,
		idx_t	column_amount
	)

Removes the column(s) and outputs the new column indices.

                                                                                                  {
    // Always add the initial column
    deleted_columns.insert(index);
 
    RemoveGeneratedColumn(index);
    RemoveStandardColumn(index);
 
    // Clean up the internal list
    vector<LogicalIndex> new_indices = CleanupInternals(column_amount);
    D_ASSERT(deleted_columns.empty());
    return new_indices;
}

IsDependencyOf()

bool duckdb::ColumnDependencyManager::IsDependencyOf	(	LogicalIndex	dependent,
		LogicalIndex	dependency
	)		const

                                                                                      {
    auto entry = dependents_map.find(gcol);
    if (entry == dependents_map.end()) {
        return false;
    }
    auto &list = entry->second;
    return list.count(col);
}

HasDependencies()

bool duckdb::ColumnDependencyManager::HasDependencies

(

LogicalIndex

index

)

const

                                                                      {
    auto entry = dependents_map.find(index);
    if (entry == dependents_map.end()) {
        return false;
    }
    return true;
}

GetDependencies()

const logical_index_set_t & duckdb::ColumnDependencyManager::GetDependencies

(

LogicalIndex

index

)

const

                                                                                            {
    auto entry = dependents_map.find(index);
    D_ASSERT(entry != dependents_map.end());
    return entry->second;
}

HasDependents()

bool duckdb::ColumnDependencyManager::HasDependents

(

LogicalIndex

index

)

const

                                                                    {
    auto entry = dependencies_map.find(index);
    if (entry == dependencies_map.end()) {
        return false;
    }
    return true;
}

GetDependents()

const logical_index_set_t & duckdb::ColumnDependencyManager::GetDependents

(

LogicalIndex

index

)

const

                                                                                          {
    auto entry = dependencies_map.find(index);
    D_ASSERT(entry != dependencies_map.end());
    return entry->second;
}

RemoveStandardColumn()

void duckdb::ColumnDependencyManager::RemoveStandardColumn ( LogicalIndex  index )

private

                                                                     {
    if (!HasDependents(index)) {
        return;
    }
    auto dependents = dependencies_map[index];
    for (auto &gcol : dependents) {
        // If index is a direct dependency of gcol, remove it from the list
        if (direct_dependencies.find(gcol) != direct_dependencies.end()) {
            direct_dependencies[gcol].erase(index);
        }
        RemoveGeneratedColumn(gcol);
    }
    // Remove this column from the dependencies map
    dependencies_map.erase(index);
}

RemoveGeneratedColumn()

void duckdb::ColumnDependencyManager::RemoveGeneratedColumn ( LogicalIndex  index )

private

                                                                      {
    deleted_columns.insert(index);
    if (!HasDependencies(index)) {
        return;
    }
    auto &dependencies = dependents_map[index];
    for (auto &col : dependencies) {
        // Remove this generated column from the list of this column
        auto &col_dependents = dependencies_map[col];
        D_ASSERT(col_dependents.count(index));
        col_dependents.erase(index);
        // If the resulting list is empty, remove the column from the dependencies map altogether
        if (col_dependents.empty()) {
            dependencies_map.erase(col);
        }
    }
    // Remove this column from the dependents_map map
    dependents_map.erase(index);
}

AdjustSingle()

void duckdb::ColumnDependencyManager::AdjustSingle ( LogicalIndex  idx, idx_t  offset  )

private

                                                                         {
    D_ASSERT(idx.index >= offset);
    LogicalIndex new_idx = LogicalIndex(idx.index - offset);
    // Adjust this index in the dependents of this column
    bool has_dependents = HasDependents(idx);
    bool has_dependencies = HasDependencies(idx);
 
    if (has_dependents) {
        auto &dependents = GetDependents(idx);
        for (auto &dep : dependents) {
            auto &dep_dependencies = dependents_map[dep];
            dep_dependencies.erase(idx);
            D_ASSERT(!dep_dependencies.count(new_idx));
            dep_dependencies.insert(new_idx);
        }
    }
    if (has_dependencies) {
        auto &dependencies = GetDependencies(idx);
        for (auto &dep : dependencies) {
            auto &dep_dependents = dependencies_map[dep];
            dep_dependents.erase(idx);
            D_ASSERT(!dep_dependents.count(new_idx));
            dep_dependents.insert(new_idx);
        }
    }
    if (has_dependents) {
        D_ASSERT(!dependencies_map.count(new_idx));
        dependencies_map[new_idx] = std::move(dependencies_map[idx]);
        dependencies_map.erase(idx);
    }
    if (has_dependencies) {
        D_ASSERT(!dependents_map.count(new_idx));
        dependents_map[new_idx] = std::move(dependents_map[idx]);
        dependents_map.erase(idx);
    }
}

CleanupInternals()

vector< LogicalIndex > duckdb::ColumnDependencyManager::CleanupInternals ( idx_t  column_amount )

private

                                                                                  {
    vector<LogicalIndex> to_adjust;
    D_ASSERT(!deleted_columns.empty());
    // Get the lowest index that was deleted
    vector<LogicalIndex> new_indices(column_amount, LogicalIndex(DConstants::INVALID_INDEX));
    idx_t threshold = deleted_columns.begin()->index;
 
    idx_t offset = 0;
    for (idx_t i = 0; i < column_amount; i++) {
        auto current_index = LogicalIndex(i);
        auto new_index = LogicalIndex(i - offset);
        new_indices[i] = new_index;
        if (deleted_columns.count(current_index)) {
            offset++;
            continue;
        }
        if (i > threshold && (HasDependencies(current_index) || HasDependents(current_index))) {
            to_adjust.push_back(current_index);
        }
    }
 
    // Adjust all indices inside the dependency managers internal mappings
    for (auto &col : to_adjust) {
        auto offset = col.index - new_indices[col.index].index;
        AdjustSingle(col, offset);
    }
    deleted_columns.clear();
    return new_indices;
}

---

The documentation for this class was generated from the following file:

• external/duckdb/duckdb.cpp