# Hashed and heap indexed object storage table insert and query performance

This question is partly to ask advice and assure this design is sane. I state the the desired properties upfront here, then go in more detail in the rationale and follow up with the design and example query and test data.

1. To locate the right row should be fast.
2. It would nice to avoid index fragmentation as much as possible.
3. A fair assumption is that some types have pattern than UPDATE the row as often as SELECT it after INSERT while other SELECT more than UPDATE. It is not plausible to think the same entity would be queried with a high-frequency. More likely occasionally.
4. A fair assumption is that UPDATE calls dominate as the application updates the state, with occasional SELECT queries. The application doesn't make a difference if it either updates or inserts other than that when inserting it doesn't have a valid version when issuing the call (i.e. etag/ROWVERSION). If it fails, it just reads the latest etag and retries if the developer so chooses. DELETE can be (maybe should be) a soft delete where a flag is set and it means more like reset than a delete. When a reset is followed by a upsert, it just sets the IsDeleted bit to 0 in the following design.

I'm trying to design a table that may hold arbitrary objects serialized by the application either in binary, XML or JSON form. The reason for not using only a binary blob is that a desirable property is to be able to manipulate the objects in the store.

It can be assumed there can be millions or even hundreds of millions of these objects stored. It's OK for not to consider "enterprise grade" features such as table partitioning. I'm more concerned about of the "basic design" and if it sane. This is partially a learning exercise for me.

The application will have a unique ID per object per class type by design and it uses these two to uniquely to both store and to locate a given object in the database. The class type is one's usual outernamespace.innernamespace.class and the ID can be taken to be on average about 50 characters (could be of randomish 32 bit integers, GUIDs or something user-defined). Both ID and the type are 16-bit Unicode characters. Because it is desirable to locate the objects quickly, both the unique ID and the type are hashed to 32 bit integers by the application and stored in the database as of type INT. The code handles the mapping from the hashed unsigned integer to INT in the database and back.

I read an interesting blog post by Thomas Kejser Clustered Index vs. Heap and based on that it looks like following design without a clustered heap and using a heap is the way to go.

But is it so? The following design is a bit simplified in that I'd like to avoid committing to certain design without first being more sure it works. I will add a column for version and likely split the ObjectType to a separate table in order avoid storing the type name multiple times in its entirety. I modify the sample query to either always return all three payload fields and let the application handle picking the right one or modify it to correctly return only the one with actual data and set the type to VARBINARY(MAX), I don't know if this conversion has adverse performance penalties.

I have further questions:

1. When an object is deleted and if I'd like to save on storage but avoid index fragmentation, would it be useful to set the *Payload fields to NULL, but otherwise leave the row? If I use the MAX on VARBINARY and NVARCHAR, I understand they will be stored separately from the table and setting it to NULL may not be that a much saving in the following ObjectStore table, but I wonder if it could be a saving elsewhere.

2. Are there better ways of organizing the DELETE than with the IsDeleted. I'm not sure what could be the ratio of either set or not set on this bit. One assumption that could be made is that a cleanup operation perhaps could be done that physically removes the deleted rows from the DB and defragments the table. I left it out of the index and it is not in a filtered index as this should work also on SQL Server Standard.

3. From a DBA perspective, would it be an OK arrangement to make it so the DBA can modify the SELECT, INSERT (not shown here) and UPDATE (not shown here) queries correspondingly so that that the system can, say, further optimize the system by type by storing some of them to separate tables?

5. What's wrong with my query? I have also a bug in the query in that with the given example it should return only one the other one of the duplicate rows, but I can't figure out what's the problem. In the most common case, without hash collision, the query looks like being a index seek using the index.

4. Would roughly something like this work also for MySQL?

Phew! That was a lot of text. I hope this would be useful to others too. If it matters, I plan to utilize ADO.NET on using this table (maybe with streaming).

DROP TABLE ObjectStore;
CREATE TABLE ObjectStore
(
-- These are for the book keeping. The application calculates
-- these hashes, which are unsigned 32 integers mapped to
-- the *Id fields. The mapping is done in the code. The
-- *Name columns contain the corresponding clear name fields.
--
-- If there are duplicates
ObjectId INT NOT NULL,
ObjectIdName NVARCHAR(512) NOT NULL,
ObjectType INT NOT NULL,
ObjectTypeName NVARCHAR(512) NOT NULL,

-- The usage of the payload records is exclusive in that
-- only one is populated at any given time and two others
-- are NULL. When all three are returned, the application
-- knows how to handle the situation.

-- Informational field, no other use.
ModifiedOn DATETIME2(3) NOT NULL,

-- If this particular object has been deleted from the database
-- or not. The objects can be inserted, deleted and reinserted.
-- Would it be beneficial to set the Payload* columns to NULL
-- to save space but still to avoid index fragmentation?
IsDeleted BIT NOT NULL

-- The following would in principle be the primary key, but hashing can produce
-- collisions.
-- CONSTRAINT PK_ObjectStore PRIMARY KEY NONCLUSTERED (ObjectId, ObjectType)
);

SELECT
FROM
ObjectStore
WHERE
ObjectId = @objectId
AND ObjectType = @objectType
AND IsDeleted = 0
AND ObjectIdName = @objectIdName
AND ObjectTypeName = @objectTypeName;


Some test data with a simulated collision

INSERT INTO ObjectStore
(
ObjectId,
ObjectIdName,
ObjectType,
ObjectTypeName,
ModifiedOn,
IsDeleted
)
VALUES
(
1,
N'First',
1,
N'FirstType',
NULL,
NULL,
N'{ "id": First, "field1": "Red", "field2": 1.0, "objects": ["birch", "pine"] }',
GETUTCDATE(),
0
);

-- Simulate a collision.
INSERT INTO ObjectStore
(
ObjectId,
ObjectIdName,
ObjectType,
ObjectTypeName,
ModifiedOn,
IsDeleted
)
VALUES
(
1,
N'First',
1,
N'NonFirstType',
NULL,
NULL,
N'{ "id": First, "field1": "Green", "field2": 1.2, "objects": ["pine", "birch"] }',
GETUTCDATE(),
0
);

INSERT INTO ObjectStore
(
ObjectId,
ObjectIdName,
ObjectType,
ObjectTypeName,
ModifiedOn,
IsDeleted
)
VALUES
(
2,
N'Second',
2,
N'SecondType',
NULL,
NULL,
N'{ "id": First, "field1": "Green", "field2": 2.0, "objects": ["oak", "juniper"] }',
GETUTCDATE(),
0
);

DECLARE @objectId   AS INT = 1;
DECLARE @objectIdName AS NVARCHAR(512) = N'First';
DECLARE @objectType AS INT = 1;
DECLARE @objectTypeName AS NVARCHAR(512) = N'FirstType';


<edit: A relevant SO post When should a primary key be declared non-clustered?. Here it could be expected there can be a plenty of INSERT and UPDATE operations happening at once. I'm unsure about hardware or the patterns, but having a general feeling of the way to go is what I'm researching here.

(The comments below apply to MySQL; some may apply to other engines.)

• UUIDs slow things down because of their random nature.

• Don't use Unicode; use utf8. (Better yet, CHARACTER SET utf8mb4)

• InnoDB keeps index fragmentation low by design.

• Rule of Thumb: In a table with millions of rows, a "point query" via the PRIMARY KEY can be expected to take about as long as one disk hit. InnoDB uses a "clustered" PRIMARY KEY organized in a BTree.

• Normalize your class names. Short integers are more efficient than medium sized strings, especially since there is a lot of repetition.

• Hash indexes are not available. They are useless for scans and not much better than BTrees for point queries. (Competing products are better at providing the rarely useful features, such as hash and bitmap indexes, than MySQL.)

• Fetching a record is the dominant cost in any operation. Function calls, expression evaluation, character sets, collations, conversion, VARBINARY, etc., are insignificant in comparison.

• Data is stored in blocks, so freeing row(s) may lead to freeing blocks. Quit worrying about fragmentation. You have not indicated whether you are likely to be deleting 10% of the rows (not a big deal), or 90% (maybe an issue).

• Segregating the DBA from the developer is folly.

• Approximately 10% of the SQL rows in your sample code would cause syntax error in MySQL. SQL implementations are very much not compatible. If you try to have code that works between engines, you will have to leave out some performance features.

• "Objects" and "Relational databases" are alien to each other.