SQL Query Engine Without Dynamic Queries

There are many ways to implement query engines, dynamic SQL, stored procedures with finite amount of IFs, dynamically creating stored procedures for each query  and a solution I'm writing here.

(I'm sure there are other solutions, I'll be glad to hear about them...)

Dynamic SQL is probably the fastest if you need to execute a one time query, but if multiple actions execute different queries the sql query engine will be very busy with building query plans and executing them, if you need more performance, sometimes the amount of indexes you'll need to create is significant and then the updates and deletes become very slow.

The problem with stored procedure is either your one stored procedures is going to be a maintenance nightmare or if you're creating stored procedures dynamically, its going to be a nightmare to write the code that maintains these stored procedures.

And then again, there's the indexes issue which must be addressed.

I've figured out another way of creating dynamic queries, its not very fast since its using cross joins, but its very quick to set up, so you can get started with low volume tables (< 100k records).

So lets start with our data structure:

1. The Entities table

CREATE TABLE Entities (
  EntityId int  IDENTITY(1,1) NOT NULL,
  Name varchar(255) default NULL,
  Phone varchar(100) default NULL,
  Email varchar(255) default NULL,
  Address varchar(255) default NULL,
  City varchar(50) default NULL,
  Zip varchar(10) default NULL,
  State varchar(50) default NULL,
  Country varchar(50) default NULL,
  BirthDate varchar(50) default NULL
)

2. The Query table

CREATE TABLE Queries
(
    QueryId int NOT NULL IDENTITY (1, 1),
    Name varchar(100) NOT NULL
)

3. The Query Items table

create table QueryItems
(
    QueryItemId int not null identity (1,1),
    QueryId int,
    GroupId tinyint,
    AttributeCode tinyint,
    Value nvarchar(255)
)

The Entities table is pretty straight forward and so is the Queries table.

The QueryItems table has GroupId for queries with groups of items (each group is ANDed, each item inside a group is ORed), the AttributeCode is what this item is asking for, 0 for Country, 1 for Birthday Month and 2 for Email Contains queries, so all possible combinations of these attributes, groups and values will produce a correct answer.

And for the query engine part:

WITH cte AS 
(
   SELECT EntitiesRulesGroups.EntityId, EntitiesRulesGroups.QueryId, MatchingUserGroups.EntityId AS MatchingEntityId
   FROM (
    SELECT EntityId, QueryId, GroupId
    FROM Entities
    CROSS JOIN (
     SELECT DISTINCT QueryId, GroupId
     FROM QueryItems
     ) AS QueryItemsGroups
    ) EntitiesRulesGroups
   LEFT OUTER JOIN 
   (
    SELECT EntityId, QueryId, GroupId, Sum(MatchBit) AS MatchBit
    FROM 
    (
         SELECT EntityId, QueryItems.QueryId, QueryItems.GroupId, 
            (
       /*Country*/            (CASE WHEN ((AttributeCode = 0) AND (Entities.Country = QueryItems.Value))                      THEN 1 ELSE 0 END) +
       /*Birthday Month*/   (CASE WHEN ((AttributeCode = 1) AND (datepart(MONTH, Entities.BirthDate) = QueryItems.Value)) THEN 1 ELSE 0 END) +
       /*email contains*/   (CASE WHEN ((AttributeCode = 2) AND (Entities.email like '%' + QueryItems.Value + '%'))          THEN 1 ELSE 0 END) 
            ) AS MatchBit
            
         FROM Entities
     CROSS JOIN QueryItems
    ) as Matching
   WHERE (MatchBit > 0)
   GROUP BY EntityId, QueryId, GroupId
   ) AS MatchingUserGroups
    ON MatchingUserGroups.EntityId = EntitiesRulesGroups.EntityId AND MatchingUserGroups.QueryId = EntitiesRulesGroups.QueryId AND MatchingUserGroups.GroupId = EntitiesRulesGroups.GroupId
)


select EntityId, QueryId
from Entities
cross join Queries
where not exists
(
    SELECT *
    FROM cte
    WHERE cte.EntityId = Entities.EntityId AND cte.QueryId = Queries.QueryId AND MatchingEntityId IS NULL
)

So what's happening here?

First, we're writing a CTE that will cross check all entities against all query items, so we're creating a big table that tells us if an entity is valid for a specific query item.

In the actual query, we're generating a cross on all entities and all queries and then we're asking the CTE if there is not match in the list.

So why aren't we checking if there is a record instead of there is no nulls?

Well, if there is a record will only tell us if there is a match between a query item and an entity, but there is no way to detect if there are no matches for the ANDed groups except asking if there was a failure to compare a group and an entity.

Of curse its a slow query, its a cross join on multiple tables and there is no way for the query optimizer to do anything, the amount of comparison that is done its almost as comparing each item in code rather than in SQL, but the advantage of it is that everything is done inside the SQL without cursors so data access is actually faster.

There are ways to improve this engine, I'm showing here only the basics for better understanding:

1. Caching the results and only update the cache on changes to either a specific entity against all queries or for a specific query against all entities, then querying the cache is very fast.
If the cache ever gets out of sync, its relatively quick to do a rebuild of the results. You should read up on SQL Merge.
2. Building a pre-calculated temp tables for the queries and the entities so a cast or convert is done only once for an entity <> query item pair.
3. Use with (nolock) where applicable.

I've tested this method with 500k entities (and their own entities - up to 10 sub entities) and 1k queries, the performance was about 500ms for a query to all entities and entity to all queries and a total cache rebuild was about 5 minutes, your results may vary based on too many things to count.

Read More

Tags: cte, query engine, sql

Dror Gluska June 11, 2012  No comment

Hierarchy Cache

In the past I tried to avoid using hierarchies in SQL, but I couldn't find another simple data structure for a system requirement: all elements must be children of other elements with no depth limit.


I was able to change the depth limit to 100.


So I started out with:

CREATE TABLE [dbo].[Hierarchy](
    [ElementId] [int] IDENTITY(1,1) NOT NULL,
    [ParentId] [int] NULL,
 CONSTRAINT [PK_Hierarchy] PRIMARY KEY CLUSTERED 
(
    [ElementId] ASC
)

at first everything worked fine, I could traverse the tree with CTE without any problem, it was even fast for the current load, then came another system requirement, the tree size will be about 1 million records.

with cte as
(
 select ElementId, ParentId, 0 as Level
 from Hierarchy
 where ParentId is null
 
 union all
 
 select Hierarchy.ElementId, Hierarchy.ParentId, Level + 1
 from Hierarchy
  join cte on cte.ElementId = Hierarchy.ParentId
)

select * from cte

trying to traverse a tree of 1M records with CTE with only 15 levels took more than a production sql should take, even if the system's requirement should be live or near live.


We've been looking for solutions in every corner of the internet, graph databases (we'll still need to use these IDs in the SQL so passing the data back will be a design nightmare or we can move the portions or whole application, I guess these are other options), trying to find all sorts of algorithms (which will be error prune and might be a heavy toll on the development team), CLR functions and of curse scrapping the whole hierarchy idea (no can do, system requirements).


Eventually we came to the conclusion that keeping a cache will not be too costly on the memory, cpu and disk provided that the right indexes will be created and they will provide the best result and the fun part is, its very easy and fast to join the cache table on any other table we'll need. 


But we had to compromise somewhere, we compromised on node parent changes, some of them might cause the entire tree to rebuild.


I built a method to quickly update the tree given an elementid and if elementid was not provided, it will rebuild the whole tree.


I can smell just one little problem, which will be solved when updating records, need to detect circular references.

CREATE TABLE [dbo].[HierarchyCache](
 [OwnerId] [int] NOT NULL,
 [ElementId] [int] NOT NULL
)

And the SQL code updating the HierarchyCache, note that I'm using merge instead of dropping the whole table or writing individual insert/delete.

declare @ElementId int = null


--if no ElementId was supplied, it means we should go over all Hierarchy and rebuild the table
if (@ElementId is null)
begin


    with parentHierarchy (ElementId, ParentId , TopElementId)
    as
    (
        select  ElementId, ParentId, ElementId as TopElementId
        from Hierarchy with (nolock)

        union all

        select  [Hierarchy].ElementId,[Hierarchy].ParentId , pu.TopElementId
        from Hierarchy with (nolock)
        inner join parentHierarchy as pu
            on pu.ParentId = [Hierarchy].ElementId
    )

    --instead of updating the entire table, we're doing a merge, more efficient and easier on the disk
    merge into HierarchyCache as target
    using parentHierarchy
        on (parentHierarchy.TopElementId = target.OwnerId and parentHierarchy.ElementId = target.ElementId)
    when not matched by target then
        insert (ElementId, OwnerId) values (parentHierarchy.ElementId,parentHierarchy.TopElementId)
    when not matched by source then
        delete;

end
else
begin
    --a ElementId was supplied, update only its tree

    with parentHierarchy (ElementId, ParentId  , TopElementId)
    as
    (
        select  ElementId, ParentId , ElementId as TopElementId
        from Hierarchy with (nolock)
        where ElementId = @ElementId

        union all

        select  [Hierarchy].ElementId,(case when (Hierarchy.ParentId = Hierarchy.ElementId) then null else Hierarchy.ParentId end) as ParentId , pu.TopElementId
        from Hierarchy  with (nolock)
        inner join parentHierarchy as pu
            on pu.ParentId = [Hierarchy].ElementId

    )

    --instead of updating the entire table, we're doing a merge, more efficient and easier on the disk
    merge into HierarchyCache as target
    using parentHierarchy
        on (parentHierarchy.TopElementId = target.OwnerId and parentHierarchy.ElementId = target.ElementId)
    when not matched by target then
        insert (ElementId, OwnerId) values (parentHierarchy.ElementId,parentHierarchy.TopElementId);


end

Read More

Tags: cte, hierarchy, merge, sql

Dror Gluska May 25, 2012  No comment