Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C++

Database Virtual Cursor

Rate me:
Please Sign up or sign in to vote.
4.96/5 (60 votes)
5 Jun 2008CPOL24 min read 71.3K   46   23
This article demonstrates a new technique to optimize DBMS output cursor storage using Virtual Cursor.

Contents

Introduction

When I was developing a relational database engine, I was testing some queries in Microsoft SQL Server, and I found that some simple queries were taking a very long time to be executed, or I received a message "not enough space on the disk". After some investigation, I found that the problem was in the saving of the query result, or to be more accurate, the time to save the recordset cursor values. So, I tried to overcome this time issue in my design. This article will take a simple overview about recordset cursors, SQL statement execution, and then take a look at a simple query and explain the problem that slows down the performance of most DBMSs. Then, I'll introduce the idea of virtual cursors, and apply the idea to more sophisticated queries.

The SQL statement "Select * from orders,employees,customers where orders.employeeid=4" in SQL server takes 55 seconds to execute. I know that SQL Server can search in the field orders.employeeid for the value 4 in no more than 0 ms, but the problem is taking the result and combining it with that from two other tables (employees, customers) and saving the output cursor. That means, if the output result contains a big or a huge number of rows, SQL Server takes a lot of time to save the whole result, which motivated me to think about finding a way to overcome this problem in my company's engine.

Image 1

I know that this is not a normal query and the cross product of the three tables returns 664,830 rows, but if you look at my execution time for the same query, you can find the difference, and it will motivate you to read the whole article to know the idea behind the virtual cursor. The following figure displays my engine time to execute the same query. It takes less than 1 millisecond.

Image 2

Actually, SQL server takes no time to execute the query; the total time depends on the final resultant cursor vector; if it is too large, it takes a long time, or returns an error of "not enough space on the disk". If it is small, it takes no time to store it. And as a proof for its speed, if we use the query "Select count(*) from ...", it takes no time. So, the problem is in the saving of the cursor values. For example, for the query:

SQL
Select * from Orders, Employees, Customers, Products 
  WHERE Orders.EmployeeID IN (4, 5, 6) 
  AND Employees.EmployeeID IN (1, 2, 3) 
  AND Customers.CustomerID LIKE 'A%'

SQL Server takes 3 seconds to return 244,860 rows (it takes 16 ms to return the same rows in my engine). If you try to delete the condition "Customers.CustomerID LIKE 'A%'", you can go make a sandwich in the time you get a result; it takes about 35 seconds!!! While my engine takes 1 ms to get 5,448,135 rows. Any way, let us start an overview about the recordset cursor and it internal structure, and then discuss cursor expansion as an introduction to virtual cursors. Please take your time to read each section, as each section is the key for the next section.

Recordset Cursor

To interact with any database management system, you should execute a SQL statement with a Recordset object. the Recordset object executes the input query and stores the results in a certain data structure to enable the caller to enumerate through the execution result. The enumeration usually is done with the functions:

int GetRecordCount()return the number of rows
bool IsBOF()check if the cursor is at the top of the rows
bool IsEOF()check if the cursor is at the end of the rows
void MoveNext()move to the next row
void MovePrev()move to the previous row
void MoveFirst()move to the first row
void MoveLast()move to the last row
Move(int nRows)move nRows from the current row
MoveTo(int nRow)move to nRow

The following figure represents the location of the Cursor component in the DCMS components:

Image 3

Let us have a simple example to try to find a suitable structure to represent the Cursor. I'll assume that I have four tables: T1, T2, T3, and T4. F1 is a foreign key in T1, and a primary key in T2.

Image 4

For the query "Select * from T1,T2", we have the result of a cross join, as in the following table:

T1.F1T2.F1
BA
CA
AA
AA
CA
BB
CB
AB
AB
CB
BC
CC
AC
AC
CC

So, we can imagine the result as a view of rows, and the cursor is just a vector of values ranging from 0 to the number of rows-1. The cursor functions are just incremented and decremented: a variable between the min and max values. But, what is the case if we have a condition that limits the result, for example, if we modify the input query to: "Select * from T1,T2 where T2.F1=T1.F1"? In this case, we have the result as:

T1.F1T2.F1
AA
AA
BB
CC
CC

So, the result is a subset of the cross join of the two tables (the product of the two tables). As in the following figure:

Image 5

So, the cursor vector just included the items (2, 3, 5, 11, 14), and the rows count is just the length of the vector (5 rows). A simple algorithm to map the cursor values to the fields record values, in its simple form, is:

C++
void CRecordSet::GetFieldValue(CField* pField, VARIANT& var)
{
    // get field record from cursor
    int nFieldRecord = GetFieldRecord(pField);
    // retrieve field value from field
    pField->GetRecord(nFieldRecord, var);
}

int CRecordSet::GetFieldRecord(CField* pField, bool bUseCursor)
{
    // map cursor position a the global cross product of tables (look figure 1)
    int nCursor = bUseCursor ? m_vCursor[m_nCursor] : m_nCursor;
    // iterate  through recordset tables
    int nTableCount = m_vTables.size(), nTableSize, nPrefixSize = 1;
    for (int n = 0; n < nTableCount; n++)
    {
        nTableSize = m_vTables[n]->GetRecordCount();
        if(m_vTables[n] == pField->m_pTable)
            return (nCursor / nPrefixSize) % nTableSize;
        nPrefixSize *= nTableSize;
    }
    return -1;
}

GetFieldRecord is a simplified version of my original code. It maps the recordset internal cursor (m_nCursor) through the cursor vector m_vCursor which includes the final result as in figure 1. To understand the function, we should first understand the cross product of any number of tables as it is the secret behind this function. The cross product for two tables is just repeating each row from the second table with all the rows of the first table. That is clear in the left side table of figure 1. So, if we execute:

SQL
Select * from T3, T4

we get the rows:

T3.F2T4.F3
1X
2X
3X
4X
1Y
2Y
3Y
4Y
1Z
2Z
3Z
4Z

Each item of T4 is repeated with the whole rows of T3, which is the key here. In the algorithm, you can find a variable nPrefixSize which is initialized to "1". So, if we iterate through the recordset tables (m_vTables) while multiplying nPrefixSize with each table size, for the first table, nPrefixSize equal to 1. Each row is repeated once. Then, nPrefixSize is multiplied with the first table size. So, for the second table, nPrefixSize equal to the first table size. Each row for it repeats with the size of the first table times. This iteration continues till we reach the table of the field:

C++
if(m_vTables[n] == pField->m_pTable)
    return (nCursor / nPrefixSize) % nTableSize;

Divide nCursor by nPrefixSize to remove the repetition, then take the reminder of dividing the result by nTableSize. This algorithm can be applied for any number of tables. So, we can map the cursor position to a field row value with a simple and short for loop.

Recordset Execution

Before digging into my target of recordset cursor construction, let us have a look at the general SELECT statement structure.

SELECT .....Specifies what fields or aggregate/mathematical functions to displayNecessary
DISTINCTSpecifies what all returned rows must be uniqueOptional
FROM table0, table1, ..., tablenSpecifies the tables to initialize the recordset viewNecessary
WHERE ......Specifies the conditions to filter the recordset viewOptional
GROUP BY field0, field1, ..., fieldnGroups data with the same value for field0, field1, ..., fieldnOptional
HAVING ......Specifies conditions to filter the recordset view after GROUP BYOptional
ORDER BY field0, field1, ..., fieldnSort the data based on the value in field0, field1, ..., fieldnOptional

The Select section can contain field names or math operations on the fields, or aggregate functions (count, sum, avg, min, max, stdev).

The following activity diagram shows the steps of execution of a SELECT statement. I'll talk here only about the part ExecuteWhere.

Image 6

The ExecuteWhere uses the "WHERE ......." conditions to filter the cross join of the "FROM tablename(s)" part. The function does Boolean operations between sub-conditions; each condition is a filter of one or more fields of the specified table(s). For example, in the following condition:

SQL
(orders.orderdate>'5/10/1996' and employees.employeeID=3) and shipname like 'Toms*'

the ParseCondition operation constructs an execution stack like this:

and
and
orders.orderdate > '5/10/1996'
employees.employeeID = 3
shipname like 'Toms*'

Image 7

I'll describe three ways to execute the previous query. The first one is for clarifying the idea of direct filtering, the second is the key for the virtual cursor (so, take time to understand it), but it takes a lot of memory in some cases, and the third is the virtual cursor solution which has the power of the second solution plus less memory usage.

Direct View Filtering

The first step is to assume that the recordset is fully expanded by the cross join of the two tables (Orders, Employees). So, the total number of records is equal to the size of Orders multiplied by the size of Employees. The second step is to loop through this record count and call the function GetFieldRecord(pField, false) for the field that needs to be filtered, and add to the cursor vector only the values that match the condition (e.g.: orders.orderdate>'5/10/1996'). So, after the loop, we have a cursor that can share in boolean operations with other cursors to have the final cursor of the recordset.

So, the function calls a function search for the top of the stack, which calls its two operands and asks them for search, then takes their two cursors and do a boolean operation depending on its operator (AND, OR, XOR). I think you understand that that is a recursion operation, no need to waste time and space here to discuss it.

Advantages

  1. This can be used for a "Having" execution (no indexes for aggregate functions output)
  2. It can be used to filter fields of mathematical expressions like: sin(t1.f1)/cos(t2.f2/t3.f3)^2

Disadvantages

  1. Large number of comparisons as we compare the expanded recordset view (cross join)
  2. Comparisons are done with field values, which is very slow (field indices should be used)
  3. Each condition cursor can take a lot of memory in some cases

Cursor Expansion

First, we need to understand the concept of expanding the cursor. So, I need to take a very simple example, then enlarge the scale with a sophisticated one. If we have a table like "Orders" in the NorthWind database, and want to execute a query like:

SQL
Select * from Orders

we get 830 rows (the cursor vector is equal to the table length). But, if we execute a query like:

SQL
Select * from orders where freight<0.2

then, we get 5 rows with a cursor vector of (48, 261, 396, 724, 787). These values are a direct mapping to the full table rows, and we can get the table row number as I described in the section "Recordset Cursor". But, what is the case if we have two or three tables in the query, and we have a filter like where freight<0.2. Should we use the first way: "Direct view filtering", to filter the whole view of the three tables? Imagine the three tables: Orders, Employees, and Customers. The cross join (full view) of the tables will have 664830 rows. We don't have this view expanded in the memory, we just have the cursor vector that includes a serial from 0 to 664829, and then using the algorithm of the "Recordset Cursor", we can reach the right record number of any field. But in the case of the filter (where freight<0.2), how can we construct the cursor vector without "Direct View Filtering"? That is the question!!!

How can we transfer the vector of the query "Select * from orders where freight<0.2" (48, 261, 396, 724, 787) to the vector of the query "Select * from orders,employees,customers where freight<0.2" (48, 261, 396, 724, 787, 878, 1091, 1226, ......, 664724, 664787) which includes 4005 rows? I think you know now what the meaning of Cursor Expansion is, so we can define it as: "Cursor Expansion is the process of expanding a cursor of one (or more) table(s) (resulting from a search with table indexes) to a cursor over the cross join of this (these) table(s) with many tables".

Image 8

That expansion depends on many factors:

  1. Location of the table in the cross join (table of the filter):
  2. For three tables, we have three positions for the Orders table: 0, 1, and 2. It depends on its order in the input query. So, we must have an algorithm that considers the whole case.

  3. Number of tables that share in the filter:
  4. For example, if we have a condition like "Employees.employeeid=Orders.employeeid" (relation condition), we have two tables. The expansion depends on the location of the two tables and the distance between them, if they are sequenced or separated by other tables.

Example of Cursor Expansion

Suppose we have our tables:

Image 9

and we have the query "SELECT T1.F1,T2.F1,T3.F2 FROM T1,T2,T3 WHERE T1.F1='C'".

  • First, using the indexes of T1.F1, we get the records (1,4)
  • Second, we need to cross join this result with T2, T3 to get the result:

Image 10

The final result is a subset of the cross join of the three tables T1, T2, and T3, with cursor values (1, 4, 6, 9, 11, 14, 16, 19, 21, 24, 26, 29, 31, 34, 36, 39, 41, 44, 46, 49, 51, 54, 56, 59).

And, if we change the order of the three tables in the query like this: "SELECT T1.F1,T2.F1,T3.F2 FROM T2, T1, T3 WHERE T1.F1='C'", it will be (3, 4, 5, 12, 13, 14, 18, 19, 20, 27, 28, 29, 33, 34, 35, 42, 43, 44, 48, 49, 50, 57, 58, 59), and for the order of "SELECT T1.F1,T2.F1,T3.F2 FROM T2, T1, T3 WHERE T1.F1='C'", it will be (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59).

Image 11

So, the order of tables affects the output cursor values (we get the same data, just the order is different; to get a certain order, we can use Order By). So, we need an algorithm to expand the condition vector to the final cursor depending on the order of the shared tables. One can say, "Instead of that, we can construct a vector for each field containing its records, and use them to retrieve values with the cursor position". But, that will take a lot of space to keep these vectors for all the selected fields, especially if the number of fields is large (over ~ 20 fields). In addition to the wasted space, we need a very sophisticated algorithm to do boolean operations between conditions (T1.F1='C' AND T3.F2=2). But, in our case of saving only cursor values (relative to the cross join of the sharing tables), for each condition, we can do boolean operations simply between conditions' cursor values, using a simple algorithm like set_intersection and merge of the STL library.

In the whole case, the view (output) size is equal to the condition cursor size multiplied by the other tables' sizes.

view size = condition size * other tables' sizes

Back to the section Recordset Cursor and figures 2, 3. The recordset object contains a stack of conditions saved in a tree structure as in figure 3. Each node represents an object of type WhereItem. The execution of the query starts at the top WhereItem of the stack, which receives a reference to the recordset cursor. The Recordset Cursor is a simple vector of values and a group of functions, like that:

C++
// simplified code for recordset cursor
class CCursor : public vector<__int64>
{
public:
    ... constructors

public:
    vector<CTable*> m_vTables;
    // tables that share in the cursor (ordered with recordset tables)

public:
    // Boolean operators
    CCursor& operator=(const CCursor& input);
    CCursor& operator|=(const CCursor& input);    
    CCursor& operator&=(const CCursor& input);
    CCursor& operator^=(const CCursor& input);
    CCursor operator|(const CCursor& input);    
    CCursor operator&(const CCursor& input);
    CCursor operator^(const CCursor& input);

    // calculate cursor records count
    __int64 GetRecordCount(bool bCursor = true);
    // retrieve field record corresponding to cursor nRow
    int GetRecord(__int64 nRow, CIRField* pField, bool bOrdered = true);
    // Filter current cursor with a condition cursor
    bool Filter(CCursor& vCursor);
    // Expand vCursor (with its tables) to *this (with its tables)
    void Expand(CCursor& vCursor);
    
    ... order by, group by, and distinct functions
};

Each WhereItem may be an operator (node with two operands), or an operand (leaf - direct condition). So, if the top of the stack is a leaf, it will directly apply the condition to the WhereItem tables (assigned in the parsing process - out of this article's scope). If it is an operator, it will call its two operands' Search function and apply its operator to the output cursors. So, we can imagine a code like that:

C++
// this a simplified code (original include more 
// conditions for time optimization and logging)
void WhereItem::Search(CCursor& cursor)
{
    if(m_cOperator) // node
    {
        // copy my cursor (take same tables)
        CCursor copy = m_vCursor;
        // search in the two operands
        m_pOperands[0]->Search(m_vCursor);
        m_pOperands[1]->Search(copy);
        switch(m_cOperator)
        {
        case 'a':    m_vCursor &= copy;  break; // and 
        case 'o':    m_vCursor |= copy;  break; // or
        case 'x':    m_vCursor ^= copy;  break; // xor
        }
    }
    else // leaf
    {
        if(m_vFields.size() == 1)
            // search using Field indexes
            m_vFields[0]->Search();
        else    if(!m_bRelation)  // relation cursor retrieved at parsing process
            m_vCursor.Filter(m_vFields[0], m_vFields[1], m_strQuery, m_op);
    }
    // filter input cursor (may contain more tables) with my filtered values
    cursor.Filter(m_vCursor);
}

Top of the stack takes the recordset cursor which contains all the FROM tables, but the leaf nodes may contain one or more tables. And, each node contains the tables of its operands (ordered as Recordset FROM tables). So, imagine the input query and its node working tables:

SQL
SELECT * FROM
Categories,Products,Employees,Customers,Orders
WHERE
Categories.CategoryID = Products.CategoryID AND
Customers.CustomerID = Orders.CustomerID AND
Employees.EmployeeID = Orders.EmployeeID

Image 12

As you can see from the WhereItem::Search function, it calls cursor.Filter(m_vCursor) to expand the parent cursor (input to the function from the parent). For example, the lower AND of figure 4 calls its operands with the cursor that contains the tables Employees, Customers, and Orders. Operand 0 has a cursor of the tables Customers, Orders. So, it takes the cursor (relation cursor) on tables Customers, Orders, and tries to expand it to the tables Employees, Customers, Orders. And, operand 1 has a cursor of the tables Employees, Orders. So, it takes the cursor (relation cursor) on the tables Employees, Orders, and tries to expand it to the tables Employees, Customers, Orders. After that, the two operands' cursors are expanded with the same tables (with the same order). So, we can apply the boolean operations safely.

C++
switch(m_cOperator)
{
    case 'a':   m_vCursor &= copy;  break; // and 
    case 'o':   m_vCursor |= copy;  break; // or
    case 'x':   m_vCursor ^= copy;  break; // xor
}

The process is done till we expand the cursor of the top stack WhereItem with the recordset cursor, which may include more tables, as each node collects tables from its children. The key here is that each leaf/node is expanded to its parent node tables only, not the recordset tables. So, it accelerates the entire execution. As I mentioned before, the cursor expansion for any condition depends on the condition tables order relative to its parent tables. If there is no condition, the tables are cross joined, but with the condition, we have the cross join of the condition cursor with the other tables. After some examples, I found that I needed to calculate some variables that are shared in the expansion process:

C++
// size of the cursor after expansion (calculated before expansion)
__int64 m_nViewSize;
// product of tables' sizes before the first table condition
__int64 m_nPrefixSize;
// product of condition tables' sizes located
// before first middle table (see m_nMiddleSize)
__int64 m_nGroupSize;
// product of tables' sizes between condition tables
__int64 m_nMiddleSize;
// tables cross product records count
// (calculated once) without the condition
__int64 m_nRecordCount;

As in the following figure:

Image 13

C++
m_nViewSize = T1.size * T3.size * T5.size * condition.size;
m_nPrefixSize = T1.size;
m_nGroupSize = T2.size;
m_nMiddleSize = T3.size;
m_nRecordCount = T1.size * T2.size * T3.size * T4.size * T5.size;

The function Filter(CCursor& vCursor) of the cursor takes the cursor of the condition (filter) and expands it to its tables (or from another side, filters the cross join of its tables by the condition cursor).

C++
bool CCursor::Filter(CCursor& vCursor)
{
    if(vCursor.m_vTables.size() == m_vTables.size())
    {   // if same tables then copy cursor (no need for expansion)
        *this = vCursor;
        return true;
    }
    // initialize values
    m_nViewSize = vCursor.size(), m_nMiddleSize = 1, m_nPrefixSize = 1;
    if(m_nViewSize == 0)
        return true;
    // seek through cursor tables to find search fields' tables 
    vector<int&gt vTableOrder;
    for (vector<CTable*>::iterator table = vCursor.m_vTables.begin(); 
               table != vCursor.m_vTables.end(); table++)
        vTableOrder.push_back(m_vTables.lfindIndex(*table));

    // loop through cursor tables to get relation size
    // before expansion and cursor size after expansion
    int nTableCount = m_vTables.size(), nTableSize;
    for (int nTable = 0; nTable < nTableCount; nTable++)
        if(vTableOrder.lfindIndex(nTable) == -1)
        {
            m_nViewSize *= 
              (nTableSize = m_vTables[nTable]->GetRecordCount());
            for(vector<int&gt::iterator i = 
                   vTableOrder.begin(); i < vTableOrder.end()-1; i++)
                if(nTable > *i && nTable < *(i+1))
                    m_nMiddleSize *= nTableSize;
        }
    // seek for search table to expand cursor
    m_nGroupSize = 1;
    bool bFound = false;
    for (int nTable = 0; nTable < nTableCount; nTable++)
    {
        nTableSize = m_vTables[nTable]->GetRecordCount();
        if(vTableOrder.lfind(nTable))
        {    // expand vCursor into (*this)
            m_nGroupSize *= nTableSize;
            bFound = true;
        }
        else
        {
            if(bFound)
                break;
            m_nPrefixSize *= nTableSize;
        }
    }
    m_nSegmentSize = vCursor.size()*m_nMiddleSize*m_nPrefixSize;
    Expand(vCursor);
    return true;
}

The previous function initializes the variables needed for cursor expansion. It is time now to introduce the Expand function. Remember, the Expand function works as in the definition "Cursor Expansion is the process of expanding a cursor of one (or more) table(s) (resulting from a search with table indexes) to a cursor over the cross join of this (these) table(s) with many tables".

To find the way to expand a condition filter to the cross join values, I did an example by hand, and investigated the results to find the general expression to calculate the values. The following tables show the trial for the query:

SQL
Select * from T1,T2,T3,T4,T5 where T3.F2=T5.F2

Imagine first the result of the query: "Select * from T3,T5 where T3.F2=T5.F2"; then we can expand its cursor to the tables T1, T2, T3, T4, T5.

Image 14

and for the expanded query "Select * from T1,T2,T3,T4,T5 where T3.F2=T5.F2":

Image 15

Actually, that was not the only trial. I tried many samples, but each trial needed a very large Excel sheet to illustrate the expansion, which is difficult to be included in the article. Finally, I found the following general expression: NC=m*G*P+(C+m)*P+p: where NC is the new cursor value and C is the old one. I implemented the following Expand function to map the old cursor to the new sharing tables:

C++
// not optimized version of the original code (for company privacy)
void CCursor::Expand(CCursor& vCursor)
{
    // resize destination cursor with the calculated view size
    resizeEx((int)m_nViewSize);
    // loop in source cursor items to expand items to recordset view
    __int64 nForeignMatch, nViewIncrement = 0, 
      nSegmentSize = vCursor.size()*m_nMiddleSize*m_nPrefixSize, nCursor;
    __int64 nMiddle, nMatch;
    vector<__int64>::iterator _first = vCursor.begin(), 
      _end = vCursor.end(), _dest = begin();
    // loop to fill all calculated view size
    while(m_nViewSize)
    {
        __int64 nMaxForeignMatch = m_nGroupSize;
        for(vector<__int64>::iterator i = _first; 
            i != _end; i += nForeignMatch, 
            nViewIncrement += m_nMiddleSize, 
            nMaxForeignMatch += m_nGroupSize)
        {
            // count cursor values that are under the size
            // of the foreign table
            // (it should be 1 for FroeignPrimary sequence)
            for(nForeignMatch = 0; i+nForeignMatch != _end && 
                 (*(i+nForeignMatch)) < nMaxForeignMatch; 
                 nForeignMatch++);
            // repeat cursor items with the size
            // of table(s) located between relation tables
            for(nMiddle = 0; nMiddle < m_nMiddleSize; nMiddle++)
            {
                nCursor = (nMiddle + nViewIncrement) * 
                           m_nGroupSize * m_nPrefixSize;
                for(nMatch = 0; nMatch < nForeignMatch; nMatch++)
                    for (__int64 nPrefix = 0, c = nCursor + 
                               (*(i+nMatch)%m_nGroupSize)*m_nPrefixSize; 
                               nPrefix < m_nPrefixSize; nPrefix++)
                        *(_dest++) = c+nPrefix;
            }
        }
        m_nViewSize -= nSegmentSize;
    }
}

The algorithm starts by resizing the cursor with the expected view size. To understand the meaning of Segment Size, we should first understand how we can estimate the output view size. Actually, the view size should be the product of the condition size with the remaining tables' sizes (check figure 5). And, it can be calculated by using another method. It can be:

m_nViewSize = vCursor.size()*m_nMiddleSize*
   m_nPrefixSize*(product of tables after last condition table)
// in our case: no tables after last condition table T5, So
m_nViewSize = 5 * 3 * 15 = 225

nSegmentSize is simply equal to vCursor.size()*m_nMiddleSize*m_nPrefixSize. Any way, I hope you understand the idea of Cursor Expansion, no need to fully understand the algorithm now, as I think that any one who knows the idea can extract the algorithm and implement it in his own way.

Advantages

  1. Simple and fast algorithm.
  2. Simple boolean algorithms between expanded cursors using STL merge and intersect algorithms.

Disadvantages

  1. The main problem of Cursor Expansion is the heavy memory usage as the expanded cursor may use a lot of memory; even if we use the hard disk to keep it, it will take a long time to be saved and retrieved to do boolean operations. The following section discusses this disadvantage.

Let us check the query and have some measurements from the Windows Task Manger:

SQL
Select * 
from orders,employees,customers,orderdetails,shippers,suppliers 
where
customers.customerid=orders.customerid and 
employees.employeeid=orders.employeeid and 
orders.orderid=orderdetails.orderid and 
orders.shipvia=shippers.shipperid

The following table includes each condition and its cursor size before and after expansion:

No.ConditionExpansion tablesBefore expansionAfter expansionSize
1customers.customerid = orders.customeridorders, employees, customers, orderdetails, shippers825 rows48,002,625 rows366 MB
2employees.employeeid = orders.employeeidorders, employees, orderdetails, shippers830 rows5,365,950 rows41 MB
3orders.orderid = orderdetails.orderidorders, orderdetails, shippers2155 rows6,465 rows50.50 KB
4orders.shipvia = shippers.shipperidorders, orderdetails, shippers830 rows1,788,650 rows13.6 MB
5condition3 and condition4orders, orderdetails, shippers2155 rows19,395 rows151.5 KB
6condition2 and condition5orders, employees, orderdetails, shippers2155 rows191,795 rows1.46 MB
7condition1 and condition6orders, employees, customers, orderdetails, shippers2155 rows62,176 rows485.7 KB

If you notice, the condition customers.customerid=orders.customerid takes 366 MB after its cursor expansion (!!!), while it was 6600 bytes before expansion (825 rows * sizeof(__int64)). The following figures show the Windows Task Manger during the query execution:

Image 16

Image 17

To overcome this problem, I thought about a Virtual Cursor which I will demonstrate in the next section.

SQL Server again: I don't think that SQL Server works the same way. Actually, it doesn't take memory during query execution or for the final result. But, if the final cursor is too large, it takes a long time as it saves it to the hard disk, which may fail if there is not enough space on the hard disk, or if it needs more area to be saved. Anyway, there is a problem in the way that SQL Server saves the final cursor if it is huge. So, read the next section to check if it can help solve this problem.

Virtual Cursor

In the previous section, we introduced the idea of Cursor Expansion and how this expansion is useful to do boolean operations between expanded cursors of query conditions. But, we faced the problem of heavy memory usage and the risk of out of memory. So, I'll introduce a new idea for Cursor Expansion.

What if we don't expand cursors at all and leave them unexpanded. You may ask "but we need to expand them for the cross join of shared tables". You are right, but, as you know, we have the algorithm of Cursor Expansion at the Expand() function, so we can keep the same algorithm and expand the cursor values on demand. Yes, that is the idea. We can make a new function GetCursor() that receives the required row number and use the same algorithm to calculate the cursor value (relative to the cross join). So, we only need to keep the variables that share the algorithm to use it in the function. You may say "it will be slow". You are right too. But, if we add some caching and extend the cache window to an optimum number, we can accelerate the process. In addition, I have added some tricks to optimize the speed and jump faster to the required cursor value.

So, the solution now can be summarized in keeping the cursor without expansion and expanding only a small window (e.g.: 10240) of cursor values, and sliding this window as needed foreword or backward depending on the cursor type. So, we replace the size of the expanded cursor with only its original size plus the size of the cache window.

GetCursor Algorithm

The GetCursor algorithm is the same as the Expand GetCursor, except that it expand only a small window of cursor values. So, we can take the same algorithm with some modifications. To simplify the code, we do these modifications step by step. The initial code is as follows:

C++
// not optimized version of the original code (for company privacy)
__int64 CCursor::GetCursor(__int64 nRow)
{
    if(empty() || m_bSerial)
        return nRow;
    if(m_bVirtual == false)
        return (*this)[(int)nRow];
    if(m_nCacheRow != -1 && nRow >= m_nCacheRow && 
            nRow < m_nCacheRow+m_nCacheIndex)
        return m_vCache[nRow-m_nCacheRow];
    m_vCache.resizeEx(m_nCachePageSize);
    m_nCacheRow = nRow;
    m_nCacheIndex = 0;

    __int64 nSegment = nRow/m_nSegmentSize, nMiddle, 
                       nMatch, nPrefix, nForeignMatch;
    __int64 nViewIncrement = nSegment*m_nPageViewIncrement,
        nAdded = nSegment*m_nSegmentSize, 
        nViewSize = m_nViewSize-nAdded;
    while(nViewSize > 0)
    {
        __int64 nForeignMatchIndex = 0;
        // loop in source cursor items to expand items to this
        for(iterator i = begin(), _end = end(); 
                      i != _end; i += nForeignMatch,
            nViewIncrement += m_nMiddleSize)
            // repeat cursor items with the size
            // of table(s) located between relation
            // tables
            if(nForeignMatch = m_vForeignMatch[nForeignMatchIndex++])
                for(nMiddle = 0; nMiddle < m_nMiddleSize; nMiddle++)
                    for(nMatch = 0; nMatch < nForeignMatch; nMatch++)
                        for(nPrefix = 0; nPrefix < m_nPrefixSize; nPrefix++)
                            if(nAdded++ >= nRow)
                            {
                                m_vCache[m_nCacheIndex++] = 
                                  (nMiddle + nViewIncrement) *
                                   m_nGroupSize * m_nPrefixSize + 
                                  (*(i+nMatch)%m_nGroupSize)*m_nPrefixSize + 
                                  nPrefix;
                                if(m_nCacheIndex == m_nCachePageSize)
                                    return m_vCache[0];
                            }
        nViewSize -= m_nSegmentSize;
    }
    return m_vCache[0];
}
  • m_nCachePageSize is the cache window size with a default value of 10240.
  • m_nCacheIndex is the actual cache window size.
  • m_nCacheRow is the start row of the cache window.
  • m_vCache is the cache window vector.

To accelerate the execution of the functions, we can add some checks to the for loops. Look for the nested loops:

C++
for(nMiddle = 0; nMiddle < m_nMiddleSize; nMiddle++)
    for(nMatch = 0; nMatch < nForeignMatch; nMatch++)
        for(nPrefix = 0; nPrefix < m_nPrefixSize; nPrefix++)
            if(nAdded++ >= nRow)

they can be:

C++
if(m_nCacheIndex == 0 && nRow-nAdded > m_nMiddleSize*nForeignMatch*m_nPrefixSize)
    nAdded += m_nMiddleSize*nForeignMatch*m_nPrefixSize;
else
    for(nMiddle = 0; nMiddle < m_nMiddleSize; nMiddle++)
        if(m_nCacheIndex == 0 && nRow-nAdded > nForeignMatch*m_nPrefixSize)
            nAdded += nForeignMatch*m_nPrefixSize;
        else
            for(nMatch = 0; nMatch < nForeignMatch; nMatch++)
                if(m_nCacheIndex == 0 && nRow-nAdded > m_nPrefixSize)
                    nAdded += m_nPrefixSize;
                else
                    for(nPrefix = 0; nPrefix < m_nPrefixSize; nPrefix++)
                        if(nAdded++ >= nRow)

Each if statement is to avoid doing the loop if there is no need to do it. Anyway, it is not correct to try to explain the function here, as it needs a white board and a marker to breakdown each detail and get an example for each part. I am interested only in the idea and the problem it faces, not its details.

Boolean operations with Virtual Cursor: Boolean operations are done between cursors of conditions. What is the case if cursors are not expanded? How can we intersect or merge them? I mentioned before that I am using the simple algorithm set_intersection and merge of the STL library. These algorithms take the two cursors (vectors) and do its work and output the result to a destination vector. But, in the case of the Virtual Cursor, we don't have a vector. We only have a cache window of the vector. Let us first have a look at the STL set_intersection algorithm and see how we can use it to do our task.

STL set_intersection

C++
template<class _InIt1,
class _InIt2,
class _OutIt> inline _OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
    _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
{   // AND sets (_First1, _Last1) and (_First2, _Last2)
    for (; _First1 != _Last1 && _First2 != _Last2; )
        if (*_First1 < *_First2)
            ++_First1;
        else if (*_First2 < *_First1)
            ++_First2;
        else
            *_Dest++ = *_First1++, ++_First2;
        return _Dest;
}

The algorithm iterates through the two vectors linearly, and if two values are equal, it adds it to the destination. I'll use the same idea, but instead of getting the value from the vector, I'll call GetCursor(). And, because of caching and the foreword cursor (default implementation), it will be very fast. Here is a part of the &= operator of the CCursor class:

C++
CCursor& CCursor::operator&=(const CCursor& input)
{
    if(input.empty())
        clear();
    else    if(m_bVirtual || input.m_bVirtual)
    {
        vector<__int64> dest;
        dest.set_grow_increment(10240);
        __int64 nCursor[2] = { GetCursor(0),
           ((CCursor*)&input)->GetCursor(0) };
        __int64 nSize0 = GetCursorCount(), 
          nSize1 = ((CCursor*)&input)->GetCursorCount();
        // STL set_intersection algorithm
        for (__int64 n0 = 0, n1 = 0; n0 < nSize0 && n1 < nSize1; )
            if (nCursor[0] < nCursor[1])
                nCursor[0] = GetCursor(++n0);
            else    if (nCursor[0] > nCursor[1])
                nCursor[1] = ((CCursor*)&input)->GetCursor(++n1);
            else
                dest.push_backEx(nCursor[0]), 
                    nCursor[0] = GetCursor(++n0),
                    nCursor[1] = ((CCursor*)&input)->GetCursor(++n1);
        assignEx(dest);
        m_bVirtual = false;
    }
    else
        // if the two input vectors are sorted use normal intersection
        resizeEx(set_intersection(begin(), end(), (iterator)input.begin(),
            (iterator)input.end(), begin())-begin());
    ...
    return *this;
}

In the same way, we can implement the other operators (|= , ^=, -=). The output cursor is not virtual, so the variable m_bVirtual is set to false. The output cursor is not virtual, but it can be taken by its composer WhereItem and made virtual relative to the parent of WhereItem. To clarify the previous statement, we should know that the cursor is made virtual if its condition contains tables less than its parent tables. So, we have to expand it or make it virtual. One can ask, what about Order By, Group By, and Distinct? How can we order a virtual cursor? Is that possible? Actually, I tried to do that and thought about it many times, but I failed to find a clear idea about ordering a virtual cursor. But, the good point here is Order By is done over the final cursor of the recordset, which is usually small as it is the result of some filtering conditions. So, to solve this problem, if the query contains Order By, Group By, or Distinct, I expand the final cursor as explained in the section Cursor Expansion.

C++
bool CRecordset::ExecuteWhere()
{
    // construct record set initial view
    m_vCursor.m_vTables = m_vFromTables;
    // check if there is a where statement to be parsed
    if(m_strWhere.IsEmpty() == false)
    {
        // start search from stack top item
        m_vWhereStack[0]->Search(m_vCursor, false);
        if(m_vGroupByFields.empty() == false || m_bDistinct ||
            m_vOrderFields.empty() == false)
            m_vCursor.Expand();
    }
    else
        m_vCursor.m_bSerial = true;
    return true;
}

Note the condition:

C++
if(m_vGroupByFields.empty() == false || m_bDistinct ||
    m_vOrderFields.empty() == false)
    m_vCursor.Expand();

and look at figure 2 to see that this function is called before the Order By or Group By execution.

After applying the technique of virtual cursor with the query:

SQL
Select * 
from orders,employees,customers,orderdetails,shippers,suppliers 
where
customers.customerid=orders.customerid and 
employees.employeeid=orders.employeeid and 
orders.orderid=orderdetails.orderid and 
orders.shipvia=shippers.shipperid

we can check each condition and its cursor size in the following table:

No.ConditionExpansion tablesCursorSize
1customers.customerid = orders.customeridorders, employees, customers, orderdetails, shippers825 rows6600 Bytes
2employees.employeeid = orders.employeeidorders, employees, orderdetails, shippers830 rows6640 Bytes
3orders.orderid = orderdetails.orderidorders, orderdetails, shippers2155 rows17 KB
4orders.shipvia = shippers.shipperidorders, orderdetails, shippers830 rows6640 Bytes
5condition3 and condition4orders, orderdetails, shippers2155 rows17 KB
6condition2 and condition5orders, employees, orderdetails, shippers2155 rows17 KB
7condition1 and condition6orders, employees, customers, orderdetails, shippers2155 rows17 KB

Note that the maximum cursor size is just 17 KB, while it was 366 MB in the Expansion case.

Thanks to...

Thanks to God and thanks to the Harf Company which gave me the chance to develop this interesting project.

Updates

  • 01-05-2008: Initial post.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Egypt Egypt

Comments and Discussions

 
QuestionWhy a Cartesian-product join? Pin
supercat95-Jun-08 18:25
supercat95-Jun-08 18:25 
AnswerRe: Why a Cartesian-product join? [modified] Pin
Hatem Mostafa5-Jun-08 23:07
Hatem Mostafa5-Jun-08 23:07 
GeneralRe: Why a Cartesian-product join? Pin
supercat96-Jun-08 15:09
supercat96-Jun-08 15:09 
AnswerRe: Why a Cartesian-product join? Pin
Hatem Mostafa6-Jun-08 22:22
Hatem Mostafa6-Jun-08 22:22 
GeneralVery interesting... Pin
JacquesKruger.129-May-08 1:08
JacquesKruger.129-May-08 1:08 
GeneralRe: Very interesting... Pin
Hatem Mostafa29-May-08 1:54
Hatem Mostafa29-May-08 1:54 
GeneralExcellent article Pin
Guido_d16-May-08 3:19
Guido_d16-May-08 3:19 
GeneralRe: Excellent article Pin
Hatem Mostafa16-May-08 8:11
Hatem Mostafa16-May-08 8:11 
Question[Message Deleted] Pin
Hatem Mostafa4-May-08 21:12
Hatem Mostafa4-May-08 21:12 
Answer[Message Deleted] Pin
Sacha Barber5-May-08 22:47
Sacha Barber5-May-08 22:47 
GeneralRe: Why "2" ??? Pin
Member 966-May-08 19:29
Member 966-May-08 19:29 
AnswerRe: Why "2" ??? Pin
Member 966-May-08 8:57
Member 966-May-08 8:57 
GeneralRe: Why "2" ??? Pin
Hatem Mostafa6-May-08 19:24
Hatem Mostafa6-May-08 19:24 
GeneralRe: Why "2" ??? Pin
Member 966-May-08 19:30
Member 966-May-08 19:30 
AnswerRe: Why "2" ??? Pin
Islam ElDemery6-May-08 13:11
Islam ElDemery6-May-08 13:11 
AnswerRe: Why "2" ??? Pin
berzie8-May-08 9:57
berzie8-May-08 9:57 
GeneralRe: Why "2" ??? [modified] Pin
Parker M cCauley7-Feb-09 19:33
Parker M cCauley7-Feb-09 19:33 
Dear Bernard Gressing

Why don't you write an artical and impress us with your intellect instead of nonsense?

Don't criticize other for somthing you can't/won't do.

Your reply to this contributor was highly inappropriate.

Parker McCauley
Principal Engineer, R&D
Advanced Control Systems

cell : (906) 440-6100
fax : (678) 348-7275
email : parker.mccauley@acsnorth.net

modified on Monday, February 9, 2009 12:20 PM

QuestionSample Code? Pin
Ed K4-May-08 12:42
Ed K4-May-08 12:42 
AnswerRe: Sample Code? Pin
Hatem Mostafa4-May-08 21:21
Hatem Mostafa4-May-08 21:21 
GeneralVery Nice Article Pin
salah_gis2-May-08 22:36
salah_gis2-May-08 22:36 
QuestionWill it effective than cursor? Pin
Srinath Gopinath1-May-08 3:38
Srinath Gopinath1-May-08 3:38 
AnswerRe: Will it effective than cursor? Pin
Hatem Mostafa1-May-08 3:43
Hatem Mostafa1-May-08 3:43 
QuestionNice article but have quetsion Pin
abosafia1-May-08 3:10
abosafia1-May-08 3:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.