martinc

Cost of JetIntersectIndexes

2013-04-19T20:50:48Z

We recently had a question about JetIntersectIndexes()'s performance. Here's what Brett wrote up:

Intersect is to save disk IO at the cost of CPU time.

The cost of intersect indices, is the cost of iterating over ALL the index ranges (choice #3 below).　 That may not sound like a savings, HOWEVER index entries are stored together, and we try to maintain sequentially … and so iterating over index entries generally speaking is very fast off disk.　 If you walk an index, and retrieve columns you have to get from the real record … you have to jump back and forth between the index and the table, you will end up seeking into the table, and seeking is slow if the cache is not full of that data.　 Likely your cache is full of data … but let me continue on the cold case points though …

Some examples help imagining cold IO cases:

Base Index Range Scan – Scanning or counting a range of secondary index entries (where you do not have to retrieve the main data) you can walk 100s of thousands or even single digit millions of entries in a second, because the index entry data is often sequentially laid out and a good index range tells us exactly what you’ll want to read (so we preread aggressively often in a few IOs [1] … let’s say 3 IOs for argument… though a range of 241k entries would probably be more than 3 IOs), and the indices often have very dense / smaller entries … so we sometimes even end up being CPU bound here even if the index is cold.
Base Index Range + Primary Data Scan – Generally on a _cold_ DB, you can walk like 100 entries / sec via a secondary index … b/c while you can retrieve a range of 100s or thousands of index entries in a second (per #1), each seek into the main table is cold, requires a disk operation and random disk operations are typically ~100 IO per sec (IOPS)[2] on HDs (not SSD).　 Such a case is thoroughly random-IO disk bound.
a. Best Case 3-way Index Range – So if you have 3 index ranges that selects (as you have) 3k records, 240k records, and 71k records … and it turns out only 1 record satisfies all 3 index ranges, then it will only cost say 3 IOs * 3 index ranges + 1 seek IO for the final data of the primary record = 9 random IOs total.　 But how much did the 240k index range save you …
b. Even the most costly 240k index range probably processes in ~1 second or less (maybe a bit more, not truly sure of the speed of our insert into the sort) … so if you dropped that, and it ended up giving you an extra 150 records to process (over the 1 that you’ll eventually select), you just barely lose out w/ the extra 150 random disk IOPS (1.5 seconds) from dropping that index range.
c. If dropping the 240k index range gave you an extra 2999 records to process (b/c not sure if this is obvious, but implicitly we would know in this case the 71k index range didn’t add much additional selectivity over the 3k range), then that index range will have been EXTREMELY beneficial as that’d be 2999 extra seeks (an extra 30 seconds of disk IO savings) to determine the 1 true good record.　 Vs. ~1 second to process the super large index range, that’s extremely fast (30x improvement).
If dropping the 240k index range gave you NO extra records (b/c there is already only 1 record in common between the 3k and the 71k index ranges … sort of the opposite of 3.b.), then the 241k is pure cost … this is of course difficult to predict.

Every time another index range is added it generally takes a few IOs[1] / 30 ms and let’s say 1 sec CPU / 250k entries of range.　 For a small index range of say 100 entries (where IO cost is dominant), if the selectivity of the eventual set of records you have to look up improves by only 3 records per 3 IOs, then you save those costly #2 type seeks that can only be performed at a measly 100 IOPS pace.　 For a large index range, if the selectivity of the eventual set of records improves by 100 records per 250k entries processed (CPU wise) then you save enough costly #2 type disk seeks that you win over the CPU cost.　 Keep in mind also you have 4 cores to process things, but generally speaking only 1 disk … so again there CPU over disk is nicer to the system as a whole.

However, if everything is warm, generally it becomes an "even numbers" game … where more entries is just more processing … it probably would’ve been better to just select the most selective (smallest) index range and process them straight off by applying the left over terms (residual predicate in query parlance) through the primary record … as that’s 2000 index entries + 2000 seeks (but no IO, just CPU)… every index range you add is a cost / penalty of CPU processing you add to your operational time at likely little improvement.　 Which is likely what you’re seeing here … but this is again another thing that is difficult to know a-priori.

[1] I am generally assuming we have generally good indices, like those over dates, auto-inc-like IDs, common terms or common names, etc.　 Keep in mind some really randomized indices, like GUID indices can have much poorer contiguity and thus can cost a lot more IO to traverse a range of them … and that can change the results dramatically.

[2] This is numbers for HDs … SSDs change things significantly, as they can often do 2000+ random IOPS, and don’t experience as much speed differential from sequential IOs.

JetGetObjectInfo() does not get record count by default

2012-12-07T23:29:00Z

We recently had the following question:

I am trying to get the space occupied by each table that we have by using JetGetObjectInfo. The api succeeds but it returns 0 for both number of cRecords and cPages.

JET_OBJECTINFO tableInfo = {0};
 
 hr = ::JetGetObjectInfoA(m_spSession->GetSessionId(), m_dbId, JET_objtypTable, nullptr, strTableName, &tableInfo, sizeof(tableInfo), JET_ObjInfo);
 
 if (FAILED(hr)) return hr;

JetGetTableInfo didnt help as well.

However if i open the cursor and do a JetIndexRecordCount I see lots of records present in this table/index.

If i use JetGetIndexInfo on the clustered index I get the space occupied (using JET_IdxInfoSpaceAlloc) i get 80 as result (I beleive this is in pages).

Please let me know if i am missing some options that ought to be passed (grbits in the tableInfo ?).

Thanks,

It's not obvious, but you need to call JetComputeStats() first.

Calculating these numbers can be expensive to calculate on a large table, which is why the default behaviour is to leave them at zero.

Documentation on JetComputeStats() can be found at http://msdn.microsoft.com/en-us/library/windows/desktop/gg269192(v=exchg.10).aspx

Introduction to Indices

2012-09-10T07:33:45Z

ESE is an ISAM engine -- Indexed Sequential Access Method. Wikipedia has an article on ISAMs: http://en.wikipedia.org/wiki/ISAM.

ESE allows you to insert data in a structured manner, with data types such as integer or strings. Then you need to be able to find the data, which is where indexing comes in. As one co-worker put it '80% of ESE's coolness is in its indexing'.

ESE stores records in a B+tree (http://en.wikipedia.org/wiki/B%2B_tree). This tree is ordered by the Primary Key. You can either use the default order (an internally-incrementing number, so any new records inserted just end up at the end), or you can explicitly define a primary index (sometimes called 'Clustered Index') by specifying JET_bitIndexPrimary to the index definition. This is very beneficial when you have a unique property that you know will be accessed sequentially. (For example sorting by Employee ID or by Social Security Number [US] or Social Insurance Number [Canada] could be useful. But a primary index on employee name wouldn't be good because two people may have the same name.)

It's usually more interesting to be able to sort on properties other than the Primary Index. For example, sorting by employee names can be useful. This can't be a primary index, since full names aren't unique. You may want to create an index over "+LastName\0+FirstName\0\0". And maybe an index over "+Salary\0\0". These would be secondary indices.

But how do secondary indices work? They are also B+trees. Take the following data:

EmployeeId	LastName	FirstName	Salary
3	Pertwee	Jon	1000
5	Agyeman	Freema	2200
101	Gillan	Karen	2200
202	Smith	Matt	2000

(Obviously 'Salary' is not unique, but 'EmployeeId' is.)

The Primary Index over 'EmployeeId' will have the primary keys of {3, 5, 101, 202}. The contents in that tree will be the records themselves.

The LastName/FirstName index would be: { [ "AGYEMAN\0FREEMA\0", 5 ], [ "GILLAN\0KAREN\0", 101 ], [ "PERTWEE\0JON\0", 3 ], [ "SMITH\0MATT\0", 202 ] }.

The Salary index would be { [ 1000, 3], [2000, 202], [2200, 5], [2200, 101] }.

Some things to note are:
-The contents of the secondary indices are the primary keys.
-By default, ESE converts ANSI text to uppercase for sorting. (Unicode text is treated differently.)
-The Salary index has a couple of duplicate entries. it's not a Unique index, so this is OK. The tie-breaker isthe value of the Primary Key.

If one was to insert a new record (e.g. { 55, "Baker", "Tom", 3000 } ), then a few things happen:
-By inserting in the middle, if there is no space left on the database page, then it may be necessary to split the page in two. Doing this page split may result in some discontiguous data. So specifying an index density of less than 100 when creating the index can avoid splits. (Data contiguity in general should be another blog topic...)
-It also requires updating the two secondary indices (including uniqueness checks). The more secondary indices you have, the more expensive this will be.

The uniqueness check is done at JetUpdate() time, not JetSetColumn/JetSetColumns.

Conclusion:

That just scratches the surface of indexing. Secondary indices are useful, but can also expensive. Use them wisely!

Sharp Corner: Close a table after creating it

2012-06-24T01:02:00Z

The ESENT API has existed for a while, so there are quite a few oddities to it.

After creating a database with ESENT, you need to close the returned JET_TABLEID.

The original way to create a usable table was to create the table with JetCreateTable, add some columns with repeated calls to JetAddColumn, then index the columns with JetCreateIndex. But in a multi-threaded concurrent program, you wouldn't want two threads to try and do the same thing, so the returned JET_TABLEID from JetCreateTable() is opened with exclusive access. No other JET_SESID can open that table.

Fast-forward to the introduction of JetCreateTableColumnIndex (and later JetCreateTableColumnIndex3, and in Windows 8 JetCreateTableColumnIndex4 [not yet on MSDN]). This API takes a large JET_TABLECREATE structure that holds the information needed for the table, column, and indices. Everything can be done with a single API call, without a need to do a bunch of loops.

But take a closer look at the JET_TABLECREATE structure:

typedef struct tagJET_TABLECREATE {
 unsigned long cbStruct;
 tchar* szTableName;
 tchar* szTemplateTableName;
 unsigned long ulPages;
 unsigned long ulDensity;
 JET_COLUMNCREATE* rgcolumncreate;
 unsigned long cColumns;
 JET_INDEXCREATE* rgindexcreate;
 unsigned long cIndexes;
 JET_GRBIT grbit;
 JET_TABLEID tableid;
 unsigned long cCreated;
 } JET_TABLECREATE;

There are two output variables there: tableid and cCreated. cCreated returns the number of objects returned (e.g. when create a table with 5 columns and 3 indices, cCreated will be 1+5+3). This helps narrow down which table/column/index had a problem if the API failed. tableid is the JET_TABLEID of the newly created table.

We don't like to have multiple implementations of the code lying around, so internally JetCreateTable() will call the same function as JetCreateTableColumnIndex. The tableid was opened exclusively, to be just like the JetCreateTable/JetAddColumn/JetCreateIndex combination, it was also opened exclusively. So now it should be closed with JetCloseTable().

ManagedEsent is Metro Compliant

2012-06-12T00:00:05Z

I'm inaugurating this blog with an announcement: ManagedEsent is Metro Compliant.

What does this mean to you? If you write a Metro program in C#, you can grab ManagedEsent from CodePlex (http://managedesent.codeplex.com) and you can use your favourite ESENT APIs from from C#, and still pass certification.

The update is currently available only in source form (http://managedesent.codeplex.com/SourceControl/list/changesets). Binaries will be coming.

Don't hesitate to start new discussions or bug reports in the Discussions area (http://managedesent.codeplex.com/discussions).

-martin