Support for Indexes

The use of indexes is implemented as follows:

• Use of indexes is enabled and disabled using the DSIEXT_DATAENGINE_USE_DSII_INDEXES property. If the property is set to N, then use of indexes is disabled. If the property is set to Y, then use of indexes is enabled. By default, the use of indexes is disabled.
• Information about indexes that exist in relation to a DSIExtResultSet result set object are retrieved using the DSIExtResultSet::GetIndexes method.

• Based on the information retrieved about available indexes using DSIExtResultSet::GetIndexes, indexes are retrieved as DSIExtIndex objects using DSIExtResultSet::OpenIndex.

• The columns found in a DSIExtIndex object can be ascertained using IUseableIndexMetadata::GetIndexColumns, IUseableIndexMetadata::GetIncludedColumns, or IUseableIndexMetadata::GetTableColumnToIndexColumnMap.
  • GetIndexColumns returns the column objects on which an index is searchable. For example, if a given index can be used to efficiently satisfy a filter involving a column, then that column should appear in the collection returned by this method. Note that the order of columns returned is significant if the index is a sorted index.
  • GetIncludedColumns returns the column indices for which the SDK can call DSIExtIndex::RetrieveData (i.e. the column indicies for which data can be retrieved from the index as opposed to the associated DSIExtResultSet). Note that this is usually a subset of the columns that would be returned from GetIndexColumns and this subset can sometimes be empty. When all columns required for the current query appear in this set, it can allow the SDK to retrieve data from the index instead of from the table, which can be more efficient in some cases. It can also help efficiency when there is a condition on one of the included columns which cannot be directly satisfied by the index (e.g. ‘C1 LIKE %ness’), as it allows the SDK to evaluate the filter before looking up the row in the associated DSIExtResultSet.
  • GetTableColumnToIndexColumnMap returns a mapping from columns in the parent DSIExtResultSet to columns included (see GetIncludedColumns above) in this index. For example, given a column index i (with respect to the parent result), if the map contains an entry for i, then dsiextresult.RetrieveData(i, …) retrieves data from the same column as dsiextindex.RetrieveData(indexMeta.GetTableColumnToIndexColumnMap()[i], …).
• SQL Engine can take advantage of an index’s structure to reduce the number of rows retrieved from the index.

This functionality will be explained further in the following sections.

 

In this example, the SQL Engine is executing the following query:

SELECT C1 FROM T1 WHERE C1 = 5

The column T1.C1 has type SQL_INTEGER (signed). Also, a DSII index that has the capability of retrieving data from T1.C1 exists and is named IDX1.

From the perspective of the DSII, the following steps occur:

1. The SDK opens the table T1 via a call to DSIExtSqlDataEngine::OpenTable, creating the object <A>.
2. The SDK requests information related to T1’s indexes by calling DSIExtResultSet::GetIndexes on <A>.
3. The SDK opens the index IDX1 by passing in the appropriate IUseableIndexMetadata* into DSIExtResultSet::OpenIndex on <A>, as well as values of false for the in_mustKeepOrder and in_mustSupplyBookmarks parameters. The SDK shall not attempt to retrieve bookmarks from the index and the order of rows retrieved is irrelevant for the example query. Calling DSIExtResultSet::OpenIndex creates and returns a DSIExtIndex object <B> representing the index IDX1.
4. The SDK searches IDX1 by calling DSIExtIndex::Seek on <B>, passing in a DSIExtSeekCondition object <C>, with <C>.GetEqualitySegments returning a vector of size 1 containing the simba_int32 value 5 wrapped in a DSIExtKeySegment, and <C>.HasLastColumnCondition returning false.

Note:

For more details on seek conditions, see Last Column Conditions for Sorted Indexes.

5. After the call to DSIExtIndex::Seek, calling DSIExtIndex::MoveNext followed by DSIExtIndex::RetrieveData in a loop steps through <B>, returning the values in the column C1 for rows satisfying the condition T1.C1 = 5. In an index-only scan, <B> acts similarly to an IResult object.

6. The SDK may also call DSIExtIndex::Reset or DSIExtIndex::Seek.

For a flow chart illustrating methods in the DSIExtIndex class, see the DSIExtIndex class in the C++ API Reference Guide.

The following sequence diagram illustrates the general steps of the index-only scan example.

If an index does not contain the data for all needed columns, then the SQL Engine accesses table data using bookmarks. If an index is unable to provide bookmarks, then the index is ineligible for use.

Consider the following example, where the SQL Engine is executing the following query:

SELECT D1 FROM T1 WHERE C1 = 5

The column T1.C1 has type SQL_INTEGER (signed). Also, a DSII index on T1.C1 named IDX1 is capable of retrieving bookmarks.

From the perspective of the DSII, the following steps occur:

1. The SDK opens the table T1 via a call to DSIExtSqlDataEngine::OpenTable, creating the object <A>.
2. The SDK requests information related to T1’s indexes by calling DSIExtResultSet::GetIndexes on <A>.
3. The SDK opens the index IDX1 by passing in the appropriate IUseableIndexMetadata* into DSIExtResultSet::OpenIndex on <A>, as well as a value of false for the in_mustKeepOrder parameter and a value of true for the in_mustSupplyBookmarks parameter. The SDK needs to retrieve bookmarks from the index and the order of rows retrieved is irrelevant for the example query. Calling DSIExtResultSet::OpenIndex creates and returns a DSIExtIndex object <B> representing the index IDX1.
4. The SDK searches IDX1 by calling DSIExtIndex::Seek on <B>, passing in a DSIExtSeekCondition object <C>, with <C>.GetEqualitySegments returning a vector of size 1 containing the simba_int32 value 5 wrapped in a DSIExtKeySegment, and <C>.HasLastColumnCondition returning false.

5. The SDK calls DSIExtResultSet::SetBookmarkSource on <A>, passing in a DSIExtBookmarkSource object <D>. <D> is an opaque iterator for bookmarks that internally retrieves bookmarks from <B>.
6. Calling DSIExtResultSet::Move positions the cursor to the table row indicated by the next bookmark retrieved from <D>. The DSIExtResultSet calls DSIExtBookmarkSource::MoveNext on <D> followed by DSIExtBookmarkSource::GetBookmark to produce a pointer <E> to the bookmark for the next row satisfying the condition T1.C1 = 5. Repeating this step in a loop facilitates retrieving the value in column T1.D1 for all records satisfying the condition T1.C1 = 5.

For joins, Seek is called multiple times—once for each row of an outer relation during a join operation. Sorting combined lists of bookmarks based on a well-defined IBookmarkComparator object ensures that rows are retrieved as efficiently as possible.

For more information on sorting lists of bookmarks, see Understanding Bookmarks.

The following sequence diagram shows how bookmarks are used:

 

A bookmark is an opaque iterator that identifies a row. Lists of bookmarks that satisfy query conditions, retrieved from an index, can be sorted based on the IBookmarkComparator object that the index exposes.

If IBookmarkComparator::ShouldAlwaysSortBookmarks() is true, then bookmarks are sorted. You must define an order for bookmarks via IBookmarkComparator. The order for bookmarks must be a strict total ordering. Ordering is defined per DSIExtResultSet and must be consistent in the context of a single query. While not essential, the ordering should facilitate retrieving bookmarks from a table as efficiently as possible.

If IBookmarkComparator::ShouldAlwaysSortBookmarks() is false, then bookmarks are not sorted based on the IBookmarkComparator object. Bookmarks may be sorted by coincidence, for example if an intersection of bookmark sets is performed.

To avoid unnecessary sorts, indicate whether a specific index naturally produces bookmarks in IBookmarkComparator order (as long as the in_mustKeepOrder flag was set on construction of the index) via IUseableIndexMetadata:: IsInBookmarkComparatorOrder()

IBookmarkComparator::GetBookmarkSize() gets the size, in bytes, of bookmarks that the IBookmarkComparator object compares.

DSIExtBookmarkSource::GetBookmark() retrieves a pointer to data for the current bookmark.

The DSII also must implement DSIExtResultSet::GetBookmarkSize() and DSIExtResultSet::GetBookmark()

DSIExtResultSet::GotoBookmark() moves the cursor to the row identified by the given bookmark.

 

A last column condition is a condition applied to the next column of an index, after the columns taken care of by the equality conditions. When searching indexes by calling DSIExtIndex::Seek(), the SDK will only use last column conditions if an index is sorted.

If DSIExtSeekCondition::HasLastColumnCondition() returns true, then you may retrieve the last column condition using DSIExtSeekCondition::GetLastColumnCondition().

Important: If a DSIExtSeekCondition seek condition object passed to DSIExtIndex::Seek() contains a last column condition, then the last column condition must be satisfied or an exception must be thrown. Otherwise, an incorrect result set may return.

The following last column conditions are defined in the DSIExtColumnConditionType.h file:

• COLUMN_CONDITION_IS_NOT_NULL—Corresponds to “C1 IS NOT NULL” in SQL or, in some cases, is used for range queries when conversions overflow or underflow. When present, the index should filter out rows with null values for the associated column.
• COLUMN_CONDITION_IS_IN_RANGE—A range condition can contain either a minimum endpoint, a maximum endpoint, or both. If a range condition contains a minimum endpoint, then the index should filter out rows in which the associated column has a value less than the endpoint. If the minimum endpoint is exclusive, then the index should also filter out rows where the associated column has a value equal to the endpoint. If a range condition contains a maximum endpoint, then the index should filter out rows in which the associated column has a value greater than the endpoint. If the maximum endpoint is exclusive, then the index should filter out rows where the associated column has a value equal to the endpoint.
• COLUMN_CONDITION_MINIMUM—Selects only the row having the lowest value for the given column, within the subset of rows matching any other equality conditions. COLUMN_CONDITION_MINIMUM is currently unused.
• COLUMN_CONDITION_MAXIMUM—Selects only the row having the highest value for the given column, within the subset of rows matching any other equality conditions. COLUMN_CONDITION_MAXIMUM is currently unused.
• COLUMN_CONDITION_INVALID—Indicates that no last column condition is set.

IUseableIndexMetadata::IsConditionTypeSupported() returns true if a DSIExtColumnConditionType is applicable to a specific index column.

IUseableIndexMetadata::CanIndexOnNull() returns true if a specific index column supports indexing IS NULL. IS NULL conditions are specified as an equality condition, but the DSIExtKeySegment is NULL.

For more details on conditions that may apply to the last column of a sorted index, see the SimbaEngine C++ API Reference.

 

In the current version of SimbaEngine X SDK, the use of indexes is limited as follows:

• SQL OR, IN and LIKE operators are not supported.
• Indexes are not used for SQL UPDATE or DELETE statements.
• User-defined and interval SQL data types are not supported.
• If the index does not support IS_NOT_NULL, then some range filters are not supported.
• In some cases, table reordering may cause indexes not to be used.
• Indexes can be used to apply filters and joins in a query that contains sorts or aggregations, but indexes cannot be used to perform sorts or aggregations.

Further enhancements and new features will be introduced in upcoming releases of SimbaEngine X SDK.

 

This section describes how to implement the most complex parts of a data store index using the SDK. Note that implementation can vary depending on the DSII developer’s design decisions.

Before the SQLEngine is able to use a data store index, it needs to receive information about all of the data store indexes available for a table and its columns. The SQLEngine achieves this by calling the GetIndexes() method, defined in the abstract DSIExtResultSet class that the data source table class implements.

This method is expected to return a reference to an IIndexMetadataList object. This list must be composed of objects derived from the IUseableIndexMetadata abstract class, one for each data store index linked to the table. Each of these IUseableIndexMetadata objects contains general information about the index (e.g. the name of the index, flags to indicate if the index is sorted and unique, etc.) and metadata information for all the columns that are part of this index.

Step 1: Create the List of Table Columns and Their Related Metadata

1. Add the following member variable to your table class:

DSIResultSetColumns m_tableColumns;

2. In your table object’s constructor, build the list of table column metadata. For each column of your table, do the following:
   1. Determine the characteristics of the column and populate the following variables:

   simba_wstring catalogName = <catalog name of the table>;

   simba_wstring schemaName = <schema name of the table>;

   simba_wstring tableName = <name of the table>;

   simba_wstring columnName = <name of the column>;

   simba_int16 sqlType = <SQL type corresponding to the internal type of your column>;

   bool isSigned = <true if the column is signed or false otherwise>;

   simba_int16 precision = <precision for the column>;

   simba_int16 scale = <scale for the column>;

   DSINullable nullable = <see enumerated values for DSINullable and set accordingly>;

   2. Create a new DSIColumnMetadata object and initialize all of its attributes. The following example shows most of the attributes (see “Include/DSI/Client/DSIColumnMetadata.h” for the full list of attributes and determine which value to put into each depending on your DSII):

   AutoPtr<DSIColumnMetadata> columnMetadata;

   columnMetadata->m_catalogName = catalogName;

   columnMetadata->m_schemaName = schemaName;

   columnMetadata->m_tableName = tableName;

   columnMetadata->m_name = columnName;

   columnMetadata->m_label = columnName;

   columnMetadata->m_autoUnique = false;

   columnMetadata->m_caseSensitive = true;

   columnMetadata->m_nullable = nullable;

   columnMetadata->m_unnamed = false;

   columnMetadata->m_updatable = DSI_WRITE;

   3. Create a SqlTypeMetadata object and initialize all of its attributes (see “Include/Support/TypedDataWrapper/SqlTypeMetadata.h” for details about these attributes):

   AutoPtr<SqlTypeMetadata> sqlTypeMetadata( SqlTypeMetadataFactorySingleton::GetInstance()-> CreateNewSqlTypeMetadata(sqlType, !isSigned));

   if (sqlTypeMetadata->IsDateTimeType() || sqlTypeMetadata->IsExactNumericType()) {

   sqlTypeMetadata->SetPrecision(precision);

   }

   if (sqlTypeMetadata->IsExactNumericType()){

   sqlTypeMetadata->SetScale(precision);

   }

   if (sqlTypeMetadata->IsCharacterOrBinaryType()){

   sqlTypeMetadata->SetLengthOrIntervalPrecision(len);

   /// VERY IMPORTANT STEP: it is necessary to set the length

   /// of the DSIColumnMetadata object for variable size

   /// types otherwise the column is considered having a size

   /// of 0 bytes.

   columnMetadata->m_charOrBinarySize = len;

   }

   4. Create a DSIResultSetColumn object from the columnMetadata and sqlTypeMetadata objects (it is necessary to detach the auto pointers of both objects to transfer ownership to the column object, since they are destroyed once the method exits, resulting in the column object referencing an invalid object):

      AutoPtr<IColumn> column(new DSIResultSetColumn(sqlTypeMetadata.Get(),columnMetadata.Get()));

      sqlTypeMetadata.Detach();

      columnMetadata.Detach();

   5. Add the column object to the list of columns and detach it:

      m_tableColumns.AddColumn(column.Get());

      column.Detach();

At this point, the list of table columns is available during the life of the table object. Since it is under control of an AutoVector, this list and all of its elements are automatically destroyed during the destruction of the table object.

Step 2: Implement the IUseableIndexMetadata class

Write a class that implements the IUseableIndexMetadata class. An instance of this class represents the metadata of one index. Therefore it has to reference the DSIResultSetColumn objects representing the column of this index, though implementation of this interface will depend on your data source.

For a possible implementation of this class, see Sample Index Implementation. While a DSII developer might implement it differently, the following are some of the important points:

1. This class contains CreatePrimaryKeyInstance() for creating a primary index, and CreateIndexInstance() for other indexes. If primary keys are handled the same as other indexes, or there are no primary keys, only one factory method may be needed or the construction of the instance can be performed in the constructor.
2. The objective of the constructor factories is to create the link between the index columns and the table columns. The two most significant parameters received by the factories are:
   1. in_indexColumns (type IColumns): the list of table columns. When creating an index for a specific table, we provide the m_tableColumns variable (see Step 1) that was built for the table object to which this index relates.
   2. in_indexColumns (type vector<simba_unit16>): a vector of columns index. This is the index of the column in the in_indexColumns set. For example, if you have Table A with columns C1, C2, C3 and C4 and the index is composed of columns C3 and C1 in this order, then in_indexColumns should contain the (zero‑based) index values: 2, 0.
3. These factories create a DSIExtIndexColumn object for each column included in the index in the order they are referenced in the in_indexColumns vector and push them into an IndexColumns object (an AutoVector of DSIExtIndexColumn objects). The implementation provided creates another mapping between the index columns and the table columns, but this may not be needed for other data sources. Once these mappings are done, these objects call the constructor of the DBIndexMetadata class.
4. The constructor stores the previously created IndexColumns vector and some other fields into a member variable. 
5.  The other methods of the DBIndexMetadata class implement the pure virtual methods of IUseableIndexMetadata. These methods should be implemented in order to return values meaningful for the DSII, in particular, GetIndexColumns() which returns the list of DSIExtIndexColumn objects this index is based on.

At this point, a DBIndexMetadata object has been created for each index of the table. These objects derive from IUseableIndexMetadata and are to be placed in the list returned by GetIndexes().

Step 3: Create the List That Needs to be Returned by GetIndexes()

Create the list that needs to be returned by GetIndexes():

1. If the DSII table object class derives from DSIExtSimpleResultSet, then the m_indexMetaList protected member variable (type DSIExtIndexMetadataList) is available for population. If not, then create the member in the DSII table class.
2. In the constructor of the DSII table class, go through all the indexes for the related table of your data store and create one DBIndexMetadata object per index as follows:
   1. Create the vector of column indexes as explained in Step 2.b.
   2. Create the DBIndexMetadata object by calling the factory corresponding to your index and adding this object to the m_indexMetaList member variable using the AddIndexMetadata() method. The following is an example for a non‑primary key index:

      AutoPtr<DBIndexMetadata> indexMeta(

      DBIndexMetadata::CreateIndexInstance(

      m_indexName, m_indexID, m_columns, m_indexColumns,

      m_primaryKeyColumns, m_indexIsUnique));

      m_indexes.AddIndexMetadata(AutoPtr<IIndexMetadata>(

      indexMeta.Detach()));

When the DSII table object is created, it creates the list of objects needed for the definition of the data store’s indexes. Since these objects are AutoVectors, they will have the same lifespan as the table object.

Step 4: Implement the GetIndexes() method

Implement the GetIndexes() method and return a reference to the m_indexMetaList member variable. If the DSII table class derives from DSIExtSimpleResultSet, then its implementation of GetIndexes() already performs the correct logic and there is nothing more to do. If not, implement GetIndexes() to return m_indexMetalist:

const IIndexMetadataList& DSIITable::GetIndexes() const

{

return m_indexMetaList;

}