Inheritance diagram for duckdb::ART:

[legend]

Collaboration diagram for duckdb::ART:

[legend]

Public Member Functions
	ART (const string &name, const IndexConstraintType index_constraint_type, const vector< column_t > &column_ids, TableIOManager &table_io_manager, const vector< unique_ptr< Expression > > &unbound_expressions, AttachedDatabase &db, const shared_ptr< array< unsafe_unique_ptr< FixedSizeAllocator >, ALLOCATOR_COUNT > > &allocators_ptr=nullptr, const IndexStorageInfo &info=IndexStorageInfo())

unique_ptr< IndexScanState >	TryInitializeScan (const Expression &expr, const Expression &filter_expr)
	Try to initialize a scan on the ART with the given expression and filter.

unique_ptr< IndexScanState >	InitializeFullScan ()

bool	Scan (IndexScanState &state, idx_t max_count, set< row_t > &row_ids)

void	RemovalMerge (IndexLock &state, BoundIndex &source_index)
	Simple merge: scan source ART and delete each (key, rowid) from this ART.

void	RemovalMerge (BoundIndex &source_index)
	Obtains a lock and calls RemovalMerge while holding that lock.

ErrorData	InsertMerge (IndexLock &state, BoundIndex &source_index, IndexAppendMode append_mode)

ErrorData	InsertMerge (BoundIndex &source_index, IndexAppendMode append_mode)
	Obtains a lock and calls InsertMerge while holding that lock.

ErrorData	Append (IndexLock &l, DataChunk &chunk, Vector &row_ids) override
	Appends data to the locked index.

ErrorData	Append (IndexLock &l, DataChunk &chunk, Vector &row_ids, IndexAppendInfo &info) override
	Appends data to the locked index and verifies constraint violations.

ErrorData	Insert (IndexLock &l, DataChunk &chunk, Vector &row_ids) override
	Insert a chunk.

ErrorData	Insert (IndexLock &l, DataChunk &data, Vector &row_ids, IndexAppendInfo &info) override

ErrorData	InsertKeys (ArenaAllocator &arena, unsafe_vector< ARTKey > &keys, unsafe_vector< ARTKey > &row_id_keys, idx_t count, const DeleteIndexInfo &delete_info, IndexAppendMode append_mode, optional_ptr< DataChunk > chunk=nullptr)
	Insert keys and row_ids into ART and verify constraint violations.

void	VerifyAppend (DataChunk &chunk, IndexAppendInfo &info, optional_ptr< ConflictManager > manager) override
	Verify that data can be appended to the index without a constraint violation.

idx_t	TryDelete (IndexLock &state, DataChunk &entries, Vector &row_identifiers, optional_ptr< SelectionVector > deleted_sel, optional_ptr< SelectionVector > non_deleted_sel) override
	Delete a chunk from the ART.

idx_t	DeleteKeys (unsafe_vector< ARTKey > &keys, unsafe_vector< ARTKey > &row_id_keys, idx_t count, optional_ptr< SelectionVector > deleted_sel=nullptr, optional_ptr< SelectionVector > non_deleted_sel=nullptr)
	Delete keys and row_ids from the ART.

void	CommitDrop (IndexLock &index_lock) override
	Drop the ART.

ARTConflictType	Build (unsafe_vector< ARTKey > &keys, unsafe_vector< ARTKey > &row_ids, const idx_t row_count)
	Build an ART from a vector of sorted keys and their row IDs.

bool	MergeIndexes (IndexLock &state, BoundIndex &other_index) override

void	Vacuum (IndexLock &state) override
	Vacuums the ART storage.

IndexStorageInfo	SerializeToDisk (QueryContext context, const case_insensitive_map_t< Value > &options) override
	Serializes ART memory to disk and returns the ART storage information.

IndexStorageInfo	SerializeToWAL (const case_insensitive_map_t< Value > &options) override
	Serializes ART memory to the WAL and returns the ART storage information.

idx_t	GetInMemorySize (IndexLock &index_lock) override
	Returns the in-memory usage of the ART.

bool	SupportsDeltaIndexes () const override
	Whether or not the index supports the creation of delta indexes.

unique_ptr< BoundIndex >	CreateDeltaIndex (DeltaIndexType delta_index_type) const override

template<bool IS_NOT_NULL = false>
void	GenerateKeys (ArenaAllocator &allocator, DataChunk &input, unsafe_vector< ARTKey > &keys)
	ART key generation.

void	GenerateKeyVectors (ArenaAllocator &allocator, DataChunk &input, Vector &row_ids, unsafe_vector< ARTKey > &keys, unsafe_vector< ARTKey > &row_id_keys)

void	Verify (IndexLock &l) override
	Verifies the nodes.

void	VerifyAllocations (IndexLock &l) override
	Verifies that the node allocations match the node counts.

void	VerifyBuffers (IndexLock &l) override
	Verifies the index buffers.

string	ToString (IndexLock &l, bool display_ascii=false) override
	Returns string representation of the ART.

uint8_t	PrefixCount () const
	Returns the configured prefix byte capacity.

template<>
void	GenerateKeys (ArenaAllocator &allocator, DataChunk &input, unsafe_vector< ARTKey > &keys)

Public Member Functions inherited from duckdb::BoundIndex
	BoundIndex (const string &name, const string &index_type, IndexConstraintType index_constraint_type, const vector< column_t > &column_ids, TableIOManager &table_io_manager, const vector< unique_ptr< Expression > > &unbound_expressions, AttachedDatabase &db)

bool	IsBound () const override
	Returns true if the index is a bound index, and false otherwise.

const string &	GetIndexType () const override
	The index type (ART, B+-tree, Skip-List, ...)

const string &	GetIndexName () const override
	The name of the index.

IndexConstraintType	GetConstraintType () const override
	The index constraint type.

void	InitializeLock (IndexLock &state)
	Obtains a lock on the index.

ErrorData	Append (DataChunk &chunk, Vector &row_ids)
	Obtains a lock and calls Append while holding that lock.

ErrorData	Append (DataChunk &chunk, Vector &row_ids, IndexAppendInfo &info)
	Obtains a lock and calls Append while holding that lock.

void	CommitDrop () override
	Deletes all data from the index.

idx_t	TryDelete (DataChunk &entries, Vector &row_identifiers, optional_ptr< SelectionVector > deleted_sel=nullptr, optional_ptr< SelectionVector > non_deleted_sel=nullptr)
	Obtains a lock and calls TryDelete while holding that lock.

virtual void	Delete (IndexLock &state, DataChunk &entries, Vector &row_identifiers)

void	Delete (DataChunk &entries, Vector &row_identifiers)
	Obtains a lock and calls Delete while holding that lock.

bool	MergeIndexes (BoundIndex &other_index)
	Obtains a lock and calls MergeIndexes while holding that lock.

void	Vacuum ()
	Obtains a lock and calls Vacuum while holding that lock.

idx_t	GetInMemorySize ()
	Returns the in-memory usage of the index.

void	Verify ()
	Obtains a lock and calls VerifyAndToString.

string	ToString (bool display_ascii=false)
	Obtains a lock and calls ToString.

void	VerifyAllocations ()
	Obtains a lock and calls VerifyAllocations.

void	VerifyBuffers ()
	Obtains a lock and calls VerifyBuffers.

bool	IndexIsUpdated (const vector< PhysicalIndex > &column_ids) const
	Returns true if the index is affected by updates on the specified column IDs, and false otherwise.

void	ExecuteExpressions (DataChunk &input, DataChunk &result)
	Execute the index expressions on an input chunk.

void	ApplyBufferedReplays (const vector< LogicalType > &table_types, BufferedIndexReplays &buffered_replays, const vector< StorageIndex > &mapped_column_ids)

Public Member Functions inherited from duckdb::Index
bool	IsUnique () const
	Returns unique flag.

bool	IsPrimary () const
	Returns primary key flag.

bool	IsForeign () const
	Returns foreign key flag.

const vector< column_t > &	GetColumnIds () const

const unordered_set< column_t > &	GetColumnIdSet () const

template<class TARGET >
TARGET &	Cast ()

template<class TARGET >
const TARGET &	Cast () const

Static Public Member Functions
static unique_ptr< BoundIndex >	Create (CreateIndexInput &input)
	Create a index instance of this type.

static IndexType	GetARTIndexType ()

Static Public Member Functions inherited from duckdb::BoundIndex
static string	AppendRowError (DataChunk &input, idx_t index)

Public Attributes
Node	tree = Node()
	Root of the tree.

shared_ptr< array< unsafe_unique_ptr< FixedSizeAllocator >, ALLOCATOR_COUNT > >	allocators
	Fixed-size allocators holding the ART nodes.

bool	owns_data
	True, if the ART owns its data.

optional_idx	storage_version
	Storage version that the ART was created in, used for backwards compatible key generation.

Public Attributes inherited from duckdb::BoundIndex
vector< PhysicalType >	types
	The physical types stored in the index.

vector< LogicalType >	logical_types
	The logical types of the expressions.

string	name
	The name of the index.

string	index_type
	The index type (ART, B+-tree, Skip-List, ...)

IndexConstraintType	index_constraint_type
	The index constraint type.

vector< unique_ptr< Expression > >	unbound_expressions

DeltaIndexType	delta_index_type = DeltaIndexType::NONE
	Whether or not this is a delta index - and if it is, which type it is.

Public Attributes inherited from duckdb::Index
TableIOManager &	table_io_manager
	Associated table io manager.

AttachedDatabase &	db
	Attached database instance.

Static Public Attributes
static constexpr const char *	TYPE_NAME = "ART"
	Index type name for the ART.

static constexpr uint8_t	ALLOCATOR_COUNT = 9
	FixedSizeAllocator count of the ART.

static constexpr uint8_t	DEPRECATED_ALLOCATOR_COUNT = ALLOCATOR_COUNT - 3
	FixedSizeAllocator count of deprecated ARTs.

Private Member Functions
bool	FullScan (idx_t max_count, set< row_t > &row_ids)

bool	SearchEqual (ARTKey &key, idx_t max_count, set< row_t > &row_ids)

bool	SearchGreater (ARTKey &key, bool equal, idx_t max_count, set< row_t > &row_ids)

bool	SearchLess (ARTKey &upper_bound, bool equal, idx_t max_count, set< row_t > &row_ids)

bool	SearchCloseRange (ARTKey &lower_bound, ARTKey &upper_bound, bool left_equal, bool right_equal, idx_t max_count, set< row_t > &row_ids)

string	GenerateErrorKeyName (DataChunk &input, idx_t row)

string	GenerateConstraintErrorMessage (VerifyExistenceType verify_type, const string &key_name)

void	VerifyLeaf (const Node &leaf, const ARTKey &key, DeleteIndexInfo delete_index_info, ConflictManager &manager, optional_idx &conflict_idx, idx_t i)

void	VerifyConstraint (DataChunk &chunk, IndexAppendInfo &info, ConflictManager &manager) override
	Verifies the constraint for a chunk of data.

string	GetConstraintViolationMessage (VerifyExistenceType verify_type, idx_t failed_index, DataChunk &input) override
	Throw a constraint violation exception.

void	InitializeMergeUpperBounds (unsafe_vector< idx_t > &upper_bounds)

void	InitializeMerge (Node &node, unsafe_vector< idx_t > &upper_bounds)

void	InitializeVacuum (unordered_set< uint8_t > &indexes)

void	FinalizeVacuum (const unordered_set< uint8_t > &indexes)

void	InitAllocators (const IndexStorageInfo &info)

void	TransformToDeprecated ()

IndexStorageInfo	PrepareSerialize (const case_insensitive_map_t< Value > &options, const bool v1_0_0_storage)

void	Deserialize (const BlockPointer &pointer)

void	WritePartialBlocks (QueryContext context, const bool v1_0_0_storage)

void	SetPrefixCount (const IndexStorageInfo &info)

string	ToStringInternal (bool display_ascii)

void	VerifyInternal ()

void	VerifyAllocationsInternal ()

template<>
void	GenerateKeys (ArenaAllocator &allocator, DataChunk &input, unsafe_vector< ARTKey > &keys)

Private Attributes
uint8_t	prefix_count
	The number of bytes fitting in the prefix.

Friends
class	Leaf

Additional Inherited Members
Protected Member Functions inherited from duckdb::Index
	Index (const vector< column_t > &column_ids, TableIOManager &table_io_manager, AttachedDatabase &db)

Protected Attributes inherited from duckdb::BoundIndex
mutex	lock
	Lock used for any changes to the index.

vector< unique_ptr< Expression > >	bound_expressions

Protected Attributes inherited from duckdb::Index
vector< column_t >	column_ids

unordered_set< column_t >	column_id_set
	Unordered set of column_ids used by the Index.

Member Function Documentation

◆ Create()

static unique_ptr< BoundIndex > duckdb::ART::Create ( CreateIndexInput & input )

inlinestatic

Create a index instance of this type.

                                                                  {
        auto art = make_uniq<ART>(input.name, input.constraint_type, input.column_ids, input.table_io_manager,
                                  input.unbound_expressions, input.db, nullptr, input.storage_info);
        return std::move(art);
    }

◆ Scan()

bool duckdb::ART::Scan	(	IndexScanState &	state,
		idx_t	max_count,
		set< row_t > &	row_ids
	)

Perform a lookup on the ART, fetching up to max_count row IDs. If all row IDs were fetched, it return true, else false.

◆ InsertMerge()

ErrorData duckdb::ART::InsertMerge	(	IndexLock &	state,
		BoundIndex &	source_index,
		IndexAppendMode	append_mode
	)

Simple merge: scan source ART and insert each (key, rowid) into this ART. Returns error data if constraint violation.

◆ Append() [1/2]

ErrorData duckdb::ART::Append	(	IndexLock &	l,
		DataChunk &	chunk,
		Vector &	row_ids
	)

overridevirtual

Appends data to the locked index.

Implements duckdb::BoundIndex.

◆ Append() [2/2]

ErrorData duckdb::ART::Append	(	IndexLock &	l,
		DataChunk &	chunk,
		Vector &	row_ids,
		IndexAppendInfo &	info
	)

overridevirtual

Appends data to the locked index and verifies constraint violations.

Reimplemented from duckdb::BoundIndex.

◆ Insert() [1/2]

ErrorData duckdb::ART::Insert	(	IndexLock &	l,
		DataChunk &	chunk,
		Vector &	row_ids
	)

overridevirtual

Insert a chunk.

Implements duckdb::BoundIndex.

◆ Insert() [2/2]

ErrorData duckdb::ART::Insert	(	IndexLock &	l,
		DataChunk &	data,
		Vector &	row_ids,
		IndexAppendInfo &	info
	)

overridevirtual

Insert a chunk and verify constraint violations (generates keys and calls InsertKeys which does the verification).

Reimplemented from duckdb::BoundIndex.

◆ VerifyAppend()

void duckdb::ART::VerifyAppend	(	DataChunk &	chunk,
		IndexAppendInfo &	info,
		optional_ptr< ConflictManager >	manager
	)

overridevirtual

Verify that data can be appended to the index without a constraint violation.

Reimplemented from duckdb::BoundIndex.

◆ TryDelete()

idx_t duckdb::ART::TryDelete	(	IndexLock &	state,
		DataChunk &	entries,
		Vector &	row_identifiers,
		optional_ptr< SelectionVector >	deleted_sel,
		optional_ptr< SelectionVector >	non_deleted_sel
	)

overridevirtual

Delete a chunk from the ART.

Reimplemented from duckdb::BoundIndex.

◆ CommitDrop()

void duckdb::ART::CommitDrop ( IndexLock & index_lock )

overridevirtual

Drop the ART.

Implements duckdb::BoundIndex.

◆ MergeIndexes()

bool duckdb::ART::MergeIndexes	(	IndexLock &	state,
		BoundIndex &	other_index
	)

overridevirtual

Merge another ART into this ART. Both must be locked. FIXME: Return ARTConflictType instead of a boolean.

Implements duckdb::BoundIndex.

◆ Vacuum()

void duckdb::ART::Vacuum ( IndexLock & state )

overridevirtual

Vacuums the ART storage.

Implements duckdb::BoundIndex.

◆ SerializeToDisk()

IndexStorageInfo duckdb::ART::SerializeToDisk	(	QueryContext	context,
		const case_insensitive_map_t< Value > &	options
	)

overridevirtual

Serializes ART memory to disk and returns the ART storage information.

Reimplemented from duckdb::BoundIndex.

◆ SerializeToWAL()

IndexStorageInfo duckdb::ART::SerializeToWAL ( const case_insensitive_map_t< Value > & options )

overridevirtual

Serializes ART memory to the WAL and returns the ART storage information.

Reimplemented from duckdb::BoundIndex.

◆ GetInMemorySize()

idx_t duckdb::ART::GetInMemorySize ( IndexLock & index_lock )

overridevirtual

Returns the in-memory usage of the ART.

Implements duckdb::BoundIndex.

◆ SupportsDeltaIndexes()

bool duckdb::ART::SupportsDeltaIndexes ( ) const

overridevirtual

Whether or not the index supports the creation of delta indexes.

Reimplemented from duckdb::BoundIndex.

◆ CreateDeltaIndex()

unique_ptr< BoundIndex > duckdb::ART::CreateDeltaIndex ( DeltaIndexType delta_index_type ) const

overridevirtual

Creates a delta index - an empty copy of the index with the same schema, etc This will only be called if SupportsDeltaIndexes returns true

Reimplemented from duckdb::BoundIndex.

◆ Verify()

void duckdb::ART::Verify ( IndexLock & l )

overridevirtual

Verifies the nodes.

Implements duckdb::BoundIndex.

◆ VerifyAllocations()

void duckdb::ART::VerifyAllocations ( IndexLock & l )

overridevirtual

Verifies that the node allocations match the node counts.

Implements duckdb::BoundIndex.

◆ VerifyBuffers()

void duckdb::ART::VerifyBuffers ( IndexLock & l )

overridevirtual

Verifies the index buffers.

Reimplemented from duckdb::BoundIndex.

◆ ToString()

string duckdb::ART::ToString	(	IndexLock &	l,
		bool	display_ascii = `false`
	)

overridevirtual

Returns string representation of the ART.

Implements duckdb::BoundIndex.

◆ PrefixCount()

uint8_t duckdb::ART::PrefixCount ( ) const

inline

Returns the configured prefix byte capacity.

                                {
        return prefix_count;
    }

◆ VerifyConstraint()

void duckdb::ART::VerifyConstraint	(	DataChunk &	chunk,
		IndexAppendInfo &	info,
		ConflictManager &	manager
	)

overrideprivatevirtual

Verifies the constraint for a chunk of data.

Reimplemented from duckdb::BoundIndex.

◆ GetConstraintViolationMessage()

string duckdb::ART::GetConstraintViolationMessage	(	VerifyExistenceType	verify_type,
		idx_t	failed_index,
		DataChunk &	input
	)

overrideprivatevirtual

Throw a constraint violation exception.

Implements duckdb::BoundIndex.

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

external/duckdb/duckdb.cpp

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Member Function Documentation

◆ Create()

◆ Scan()

◆ InsertMerge()

◆ Append() [1/2]

◆ Append() [2/2]

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ VerifyAppend()

◆ TryDelete()

◆ CommitDrop()

◆ MergeIndexes()

◆ Vacuum()

◆ SerializeToDisk()

◆ SerializeToWAL()

◆ GetInMemorySize()

◆ SupportsDeltaIndexes()

◆ CreateDeltaIndex()

◆ Verify()

◆ VerifyAllocations()

◆ VerifyBuffers()

◆ ToString()

◆ PrefixCount()

◆ VerifyConstraint()

◆ GetConstraintViolationMessage()