Sql-server – Varbinary startswith query using index

indexsql servervarbinary

I've got this tree-like key (think object OIDs–it's very similar) to store and index in a table, for which queries want to select subtrees thereof. The most straightforward way to do this on a btree is to use the tree path as the single key and descend the key with a starts-with operation to find the row blocks.

So the obvious representation is VARBINARY(n)*. I cannot think of a way to express starts with in a way that SQL Server can figure out to use the index thereof.

The next-most obvious is to pack the data into some VARCHAR with a binary collation and use a like operation; however I've discovered that like @n + '%' will never use an index, but only like 'literal%. Adding the WITH INDEX hint still scans the index in its entirety because SQL server just doesn't understand. I really don't want to think about how to escape arguments in SQL so I can build an EXEC. That's just madness and a security disaster waiting to happen.

Expressing this in ordinary recursive tables and querying with recursive SQL is out of the question. The recursive query will power-sink the database server.

I actually have the data in a long string of long variables right now and can select my serialization form. As I said, the natural form is VARBINARY and it really would look like 0x000000100004A010000000D0000A000. The most common query is of the form "give me everything starting with 0x000000100004A01" or in natural model, the first n values from the string of long values. I could write them in the form a.b.c.d.e.f... but the individual numbers are long and come from clicking on things on the GUI.

Roughly speaking I'm looking at a plausible form of

CREATE TABLE Record (
   RecordId BIGINT NOT NULL IDENTITY(1,1),
   RecordedDate DATETIME NOT NULL,
   RecordClass CHAR(1) NOT NULL,
   UserId INT NOT NULL,
   ObjectId VARBINARY(384) NOT NULL,
   RecordValue NVARCHAR(100) NULL,
   OwnerId BIGINT NULL, -- Joins to another table
   SubOwnerId BIGINT NULL, -- and yet another table
   PRIMARY KEY (RecordId)
)
CREATE INDEX name ON Record(RecordedDate);
CREATE INDEX name ON Record(OwnerId);
CREATE INDEX name ON Record(SubOwnerId);
CREATE INDEX name ON Record(ObjectId);

What is the best way to do a starts-with index?

^{*I've computed the largest possible n and it's less than 400}

Best Answer

So as a matter of fact, starts with is not so hard to write as it would first seem. Given the initial key of 0x000000100004, obviously equals won't work and there is no starts with operation, but we can write ObjectId >= 0x000000100004 AND ObjectId < 0x000000100005.

By forcing the string of long values to VARBINARY conversion to be big-endian the natural form actually works correctly. We want >= (value0 & value1 & ... & lastvalue) AND < (value0 & value1 & ... & (lastvalue + 1)). As far as I know, the conversion to VARBINARY has to be written in application code, which is fine for me.

Related Solutions

Sql-server – Unique index corrupted SQL. Select query returns single row but create unique index fails

if you consider error, Msg 1505, Level 16, State 1, Line 2 The CREATE UNIQUE INDEX statement terminated because a duplicate key was found for the object name 'dbo.MSmerge_contents' and the index name 'uc1SycContents'. The duplicate key value is (7696031, 08703987-557d-e111-9888-e61f13c44f03)...... I am running below Query
select * from msmerge_contents where rowguid='08703987-557d-e111-9888-e61f13c44f03'
and it is returning only 1 row

When you have index corruption problems (ie. keys present in NC index but not in base table or vice-versa) you must be very careful about the SQL you use to validate data. At this moment your data is inconsistent but the query optimizer does not know that and completely trusts your schema, including these incorrect indexes. As such it may optimize your query to use one of the NC indexes that is missing a key and the result will also miss a a key falsely returning no duplicates. To solve this catch-22 situation you need to force the optimizer hand by explicitly requesting an index or another and make sure the projected list of columns can be satisfied by the index you enforced (ie. no *). Assuming uc1SycContents is not the clustered index, try out the following:

select rowguid
from msmerge_contents with INDEX (1)
where rowguid='08703987-557d-e111-9888-e61f13c44f03';

select rowguid
from msmerge_contents with INDEX ([uc1SycContents])
where rowguid='08703987-557d-e111-9888-e61f13c44f03';

This will forcefully check if the rowguid has a duplicate for that guid in the base table clustered index (index id 1) vs. the index uc1SycContents. I expect that the first query returns 2 (or more) rows while the second returns 1.

MySQL looking up more rows than needed (indexing issue)

Your indexes are fine for the two types of queries you mentioned.

This query will be satisfied by traversing the clustered index on the primary key...

[...] WHERE participant_id = x AND question_id = y AND given_answer_id = z;

...and this one is satisfied by the index on 'question_id':

[...] WHERE question_id = x;

The output of EXPLAIN SELECT is not telling you what you think it is telling you, because the value shown in rows is an estimate of the number of rows the server will need to consider, not the actual rows it will examine. For InnoDB these are based on index statistics.

rows

The rows column indicates the number of rows MySQL believes it must examine to execute the query.

For InnoDB tables, this number is an estimate, and may not always be exact.

^{— http://dev.mysql.com/doc/refman/5.5/en/explain-output.html#explain_rows}

The optimizer gathers information about different possible query plans, and chooses the one with the lowest cost. The information shown in EXPLAIN is the information the optimizer gathered about the plan it selected.

When type is ref and key is not NULL, this means that the name listed in the key column is the name of the index that the optimizer has chosen to use to find the desired rows, so your query plan looks exactly as it should.

Note, sometimes you will see Using index in the Extra column and a lot of people assume that this means an index is being used, or that no index is being used when that doesn't appear, but that's not correct, either. Using index describes a special case called a "covering index" -- it does not indicate whether an index is being used to locate the rows of interest.

It's possible that running ANALYZE [LOCAL] TABLE would cause the numbers in rows shown by EXPLAIN to differ, but this is a simple query and selecting this index is an obvious choice for the optimizer to make, so ANALYZE TABLE is unlikely to make any actual difference in performance.

It is possible, however, that your overall performance might see some marginal improvement with an occasional OPTIMIZE [LOCAL] TABLE, because you are not inserting rows in primary key order (as would be the case with an auto_increment primary key)... but on large tables this can be time-consuming because it rebuilds a new copy of the table... but, again, I wouldn't expect any significant change.

Best Answer

Related Solutions

Sql-server – Unique index corrupted SQL. Select query returns single row but create unique index fails

MySQL looking up more rows than needed (indexing issue)

Related Question