duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING > Class Template Reference

Collaboration diagram for duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >:

Classes
class	BaseSegmentIterator
class	SegmentIterationHelper
class	SegmentNodeIterationHelper

Public Member Functions
	SegmentTree (idx_t base_row_id=0)
SegmentLock	Lock () const
bool	IsEmpty (SegmentLock &l) const
optional_ptr< SegmentNode< T > >	GetRootSegment () const
	Gets a pointer to the first segment. Useful for scans.
optional_ptr< SegmentNode< T > >	GetRootSegment (SegmentLock &l) const
vector< unique_ptr< SegmentNode< T > > >	MoveSegments (SegmentLock &l)
	Obtains ownership of the data of the segment tree.
vector< unique_ptr< SegmentNode< T > > >	MoveSegments ()
vector< unique_ptr< SegmentNode< T > > > &	ReferenceLoadedSegmentsMutable (SegmentLock &l)
idx_t	GetSegmentCount () const
idx_t	GetSegmentCount (SegmentLock &l) const
optional_ptr< SegmentNode< T > >	GetSegmentByIndex (int64_t index) const
	Gets a pointer to the nth segment. Negative numbers start from the back.
optional_ptr< SegmentNode< T > >	GetSegmentByIndex (SegmentLock &l, int64_t index) const
optional_ptr< SegmentNode< T > >	GetNextSegment (SegmentNode< T > &node) const
	Gets the next segment.
optional_ptr< SegmentNode< T > >	GetNextSegment (SegmentLock &l, SegmentNode< T > &node) const
optional_ptr< SegmentNode< T > >	GetLastSegment (SegmentLock &l) const
	Gets a pointer to the last segment. Useful for appends.
optional_ptr< SegmentNode< T > >	GetSegment (idx_t row_number) const
	Gets a pointer to a specific column segment for the given row.
optional_ptr< SegmentNode< T > >	GetSegment (SegmentLock &l, idx_t row_number) const
void	AppendSegment (shared_ptr< T > segment)
void	AppendSegment (SegmentLock &l, shared_ptr< T > segment)
void	AppendSegment (SegmentLock &l, shared_ptr< T > segment, idx_t row_start)
bool	HasSegment (SegmentNode< T > &segment) const
	Debug method, check whether the segment is in the segment tree.
bool	HasSegment (SegmentLock &, SegmentNode< T > &segment) const
void	EraseSegments (SegmentLock &l, idx_t segment_start)
	Erase all segments after a specific segment.
idx_t	GetSegmentIndex (SegmentLock &l, idx_t row_number) const
	Get the segment index of the column segment for the given row.
bool	TryGetSegmentIndex (SegmentLock &l, idx_t row_number, idx_t &result) const
void	Verify (SegmentLock &) const
void	Verify ()
idx_t	GetBaseRowId () const
SegmentIterationHelper	Segments () const
SegmentIterationHelper	Segments (SegmentLock &l) const
SegmentNodeIterationHelper	SegmentNodes () const
SegmentNodeIterationHelper	SegmentNodes (SegmentLock &l) const

Protected Member Functions
virtual shared_ptr< T >	LoadSegment () const
	Load the next segment - only used when lazily loading.
optional_ptr< SegmentNode< T > >	GetRootSegmentInternal () const

Protected Attributes
atomic< bool >	finished_loading

Private Member Functions
bool	LoadNextSegment (SegmentLock &l) const
	Load the next segment, if there are any left to load.
void	LoadAllSegments (SegmentLock &l) const
	Load all segments, if there are any left to load.
void	AppendSegmentInternal (SegmentLock &l, shared_ptr< T > segment, idx_t row_start) const
	Append a column segment to the tree.
void	AppendSegmentInternal (SegmentLock &l, shared_ptr< T > segment) const

Private Attributes
vector< unique_ptr< SegmentNode< T > > >	nodes
	The nodes in the tree, can be binary searched.
mutex	node_lock
	Lock to access or modify the nodes.
idx_t	base_row_id
	Base row id (row id of the first segment)

Detailed Description

template<class T, bool SUPPORTS_LAZY_LOADING = false>
class duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >

The SegmentTree maintains a list of all segments of a specific column in a table, and allows searching for a segment by row number

Constructor & Destructor Documentation

SegmentTree()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::SegmentTree ( idx_t  base_row_id = 0 )

inlineexplicit

                                                : finished_loading(true), base_row_id(base_row_id) {
    }

~SegmentTree()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

virtual duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::~SegmentTree ( )

inlinevirtual

                           {
    }

Member Function Documentation

Lock()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

SegmentLock duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::Lock ( ) const

inline

Locks the segment tree. All methods to the segment tree either lock the segment tree, or take an already obtained lock.

                             {
        return SegmentLock(node_lock);
    }

Here is the caller graph for this function:

IsEmpty()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

bool duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::IsEmpty ( SegmentLock &  l ) const

inline

                                       {
        return GetRootSegment(l) == nullptr;
    }

GetRootSegment() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetRootSegment ( ) const

inline

Gets a pointer to the first segment. Useful for scans.

                                                        {
        auto l = Lock();
        return GetRootSegment(l);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

GetRootSegment() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetRootSegment ( SegmentLock &  l ) const

inline

                                                                      {
        if (nodes.empty()) {
            LoadNextSegment(l);
        }
        return GetRootSegmentInternal();
    }

MoveSegments() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

vector< unique_ptr< SegmentNode< T > > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::MoveSegments ( SegmentLock &  l )

inline

Obtains ownership of the data of the segment tree.

                                                                    {
        LoadAllSegments(l);
        return std::move(nodes);
    }

Here is the call graph for this function:

MoveSegments() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

vector< unique_ptr< SegmentNode< T > > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::MoveSegments ( )

inline

                                                      {
        auto l = Lock();
        return MoveSegments(l);
    }

ReferenceLoadedSegmentsMutable()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

vector< unique_ptr< SegmentNode< T > > > & duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::ReferenceLoadedSegmentsMutable ( SegmentLock &  l )

inline

                                                                                       {
        return nodes;
    }

GetSegmentCount() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

idx_t duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegmentCount ( ) const

inline

                                  {
        auto l = Lock();
        return GetSegmentCount(l);
    }

GetSegmentCount() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

idx_t duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegmentCount ( SegmentLock &  l ) const

inline

                                                {
        LoadAllSegments(l);
        return nodes.size();
    }

GetSegmentByIndex() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegmentByIndex ( int64_t  index ) const

inline

Gets a pointer to the nth segment. Negative numbers start from the back.

                                                                        {
        auto l = Lock();
        return GetSegmentByIndex(l, index);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

GetSegmentByIndex() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegmentByIndex ( SegmentLock &  l, int64_t  index  ) const

inline

                                                                                        {
        if (index < 0) {
            // load all segments
            LoadAllSegments(l);
            index += nodes.size();
            if (index < 0) {
                return nullptr;
            }
            return nodes[UnsafeNumericCast<idx_t>(index)].get();
        } else {
            // lazily load segments until we reach the specific segment
            while (idx_t(index) >= nodes.size() && LoadNextSegment(l)) {
            }
            if (idx_t(index) >= nodes.size()) {
                return nullptr;
            }
            return nodes[UnsafeNumericCast<idx_t>(index)].get();
        }
    }

GetNextSegment() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetNextSegment ( SegmentNode< T > &  node ) const

inline

Gets the next segment.

                                                                            {
        if (!SUPPORTS_LAZY_LOADING) {
            return node.Next();
        }
        if (finished_loading) {
            return node.Next();
        }
        auto l = Lock();
        return GetNextSegment(l, node);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

GetNextSegment() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetNextSegment ( SegmentLock &  l, SegmentNode< T > &  node  ) const

inline

                                                                                            {
#ifdef DEBUG
        D_ASSERT(RefersToSameObject(*nodes[node.GetIndex()], node));
#endif
        return GetSegmentByIndex(l, UnsafeNumericCast<int64_t>(node.GetIndex() + 1));
    }

GetLastSegment()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetLastSegment ( SegmentLock &  l ) const

inline

Gets a pointer to the last segment. Useful for appends.

                                                                      {
        LoadAllSegments(l);
        if (nodes.empty()) {
            return nullptr;
        }
        return nodes.back().get();
    }

Here is the call graph for this function:

GetSegment() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegment ( idx_t  row_number ) const

inline

Gets a pointer to a specific column segment for the given row.

                                                                    {
        auto l = Lock();
        return GetSegment(l, row_number);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

GetSegment() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegment ( SegmentLock &  l, idx_t  row_number  ) const

inline

                                                                                    {
        return nodes[GetSegmentIndex(l, row_number)].get();
    }

AppendSegment() [1/3]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::AppendSegment ( shared_ptr< T >  segment )

inline

                                              {
        auto l = Lock();
        AppendSegment(l, std::move(segment));
    }

AppendSegment() [2/3]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::AppendSegment ( SegmentLock &  l, shared_ptr< T >  segment  )

inline

                                                              {
        LoadAllSegments(l);
        AppendSegmentInternal(l, std::move(segment));
    }

AppendSegment() [3/3]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::AppendSegment ( SegmentLock &  l, shared_ptr< T >  segment, idx_t  row_start  )

inline

                                                                               {
        LoadAllSegments(l);
        AppendSegmentInternal(l, std::move(segment), row_start);
    }

HasSegment() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

bool duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::HasSegment ( SegmentNode< T > &  segment ) const

inline

Debug method, check whether the segment is in the segment tree.

                                                   {
        auto l = Lock();
        return HasSegment(l, segment);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

HasSegment() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

bool duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::HasSegment ( SegmentLock &  , SegmentNode< T > &  segment  ) const

inline

                                                                  {
        auto segment_idx = segment.GetIndex();
        return segment_idx < nodes.size() && RefersToSameObject(*nodes[segment_idx], segment);
    }

EraseSegments()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::EraseSegments ( SegmentLock &  l, idx_t  segment_start  )

inline

Erase all segments after a specific segment.

                                                            {
        LoadAllSegments(l);
        if (segment_start >= nodes.size()) {
            return;
        }
        nodes.erase(nodes.begin() + UnsafeNumericCast<int64_t>(segment_start), nodes.end());
    }

Here is the call graph for this function:

GetSegmentIndex()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

idx_t duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetSegmentIndex ( SegmentLock &  l, idx_t  row_number  ) const

inline

Get the segment index of the column segment for the given row.

                                                                  {
        idx_t segment_index;
        if (TryGetSegmentIndex(l, row_number, segment_index)) {
            return segment_index;
        }
        string error;
        error = StringUtil::Format("Attempting to find row number \"%lld\" in %lld nodes\n", row_number, nodes.size());
        for (idx_t i = 0; i < nodes.size(); i++) {
            error += StringUtil::Format("* Node %lld: Start %lld, Count %lld\n", i, nodes[i]->GetRowStart(),
                                        nodes[i]->GetCount());
        }
        throw InternalException("Could not find node in column segment tree!\n%s", error);
    }

Here is the call graph for this function:

TryGetSegmentIndex()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

bool duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::TryGetSegmentIndex ( SegmentLock &  l, idx_t  row_number, idx_t &  result  ) const

inline

                                                                                   {
        // load segments until the row number is within bounds
        while (nodes.empty() || (row_number >= nodes.back()->GetRowEnd())) {
            if (!LoadNextSegment(l)) {
                break;
            }
        }
        if (nodes.empty()) {
            return false;
        }
        idx_t lower = 0;
        idx_t upper = nodes.size() - 1;
        // binary search to find the node
        while (lower <= upper) {
            idx_t index = (lower + upper) / 2;
            if (index >= nodes.size()) {
                string segments;
                for (auto &entry : nodes) {
                    segments += StringUtil::Format("Start %d Count %d", entry->GetRowStart(), entry->GetCount());
                }
                throw InternalException("Segment tree index not found for row number %d\nSegments:%s", row_number,
                                        segments);
            }
            auto &entry = *nodes[index];
            if (row_number < entry.GetRowStart()) {
                upper = index - 1;
            } else if (row_number >= entry.GetRowEnd()) {
                lower = index + 1;
            } else {
                result = index;
                return true;
            }
        }
        return false;
    }

Verify() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::Verify ( SegmentLock &  ) const

inline

                                     {
#ifdef DEBUG
        idx_t base_start = nodes.empty() ? 0 : nodes[0]->GetRowStart();
        for (idx_t i = 0; i < nodes.size(); i++) {
            D_ASSERT(nodes[i]->GetRowStart() == base_start);
            base_start += nodes[i]->GetCount();
        }
#endif
    }

Verify() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::Verify ( )

inline

                  {
#ifdef DEBUG
        auto l = Lock();
        Verify(l);
#endif
    }

GetBaseRowId()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

idx_t duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetBaseRowId ( ) const

inline

                               {
        return base_row_id;
    }

Segments() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

SegmentIterationHelper duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::Segments ( ) const

inline

                                            {
        return SegmentIterationHelper(*this);
    }

Segments() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

SegmentIterationHelper duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::Segments ( SegmentLock &  l ) const

inline

                                                          {
        return SegmentIterationHelper(*this, l);
    }

SegmentNodes() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

SegmentNodeIterationHelper duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::SegmentNodes ( ) const

inline

                                                    {
        return SegmentNodeIterationHelper(*this);
    }

SegmentNodes() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

SegmentNodeIterationHelper duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::SegmentNodes ( SegmentLock &  l ) const

inline

                                                                  {
        return SegmentNodeIterationHelper(*this, l);
    }

LoadSegment()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

virtual shared_ptr< T > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::LoadSegment ( ) const

inlineprotectedvirtual

Load the next segment - only used when lazily loading.

Reimplemented in duckdb::RowGroupSegmentTree.

                                              {
        return nullptr;
    }

Here is the caller graph for this function:

GetRootSegmentInternal()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

optional_ptr< SegmentNode< T > > duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::GetRootSegmentInternal ( ) const

inlineprotected

                                                                {
        return nodes.empty() ? nullptr : nodes[0].get();
    }

LoadNextSegment()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

bool duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::LoadNextSegment ( SegmentLock &  l ) const

inlineprivate

Load the next segment, if there are any left to load.

                                               {
        if (!SUPPORTS_LAZY_LOADING) {
            return false;
        }
        if (finished_loading) {
            return false;
        }
        auto result = LoadSegment();
        if (result) {
            AppendSegmentInternal(l, std::move(result));
            return true;
        }
        return false;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

LoadAllSegments()

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::LoadAllSegments ( SegmentLock &  l ) const

inlineprivate

Load all segments, if there are any left to load.

                                               {
        if (!SUPPORTS_LAZY_LOADING) {
            return;
        }
        while (LoadNextSegment(l)) {
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

AppendSegmentInternal() [1/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::AppendSegmentInternal ( SegmentLock &  l, shared_ptr< T >  segment, idx_t  row_start  ) const

inlineprivate

Append a column segment to the tree.

                                                                                             {
        D_ASSERT(segment);
        // add the node to the list of nodes
        auto node = make_uniq<SegmentNode<T>>(row_start, std::move(segment), nodes.size());
        if (!nodes.empty()) {
            nodes.back()->SetNext(*node);
        }
        nodes.push_back(std::move(node));
    }

Here is the caller graph for this function:

AppendSegmentInternal() [2/2]

template<class T , bool SUPPORTS_LAZY_LOADING = false>

void duckdb::SegmentTree< T, SUPPORTS_LAZY_LOADING >::AppendSegmentInternal ( SegmentLock &  l, shared_ptr< T >  segment  ) const

inlineprivate

                                                                            {
        idx_t row_start;
        if (nodes.empty()) {
            row_start = base_row_id;
        } else {
            auto &last_node = nodes.back();
            row_start = last_node->GetRowEnd();
        }
        AppendSegmentInternal(l, std::move(segment), row_start);
    }

---

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

• external/duckdb/duckdb.hpp