Собственные типы индексов в СУБД Caché

    В объектной и реляционной моделях данных СУБД Caché есть три типа индексов — обычные, bitmap и bitslice. Если по каким-то причинам этих индексов не хватает, начиная с версии 2013.1 программист может определить свой тип индексов и использовать его в любых классах.

    Подробности под катом (если вас не пугают слова типа метод-генератор).

    «Свой тип индексов» — это класс, реализующий методы интерфейса %Library.FunctionalIndex для вставки / удаления / изменения значений в индексе. Этот класс можно указывать как тип индекса в определении индекса.

    Например:

    Property A As %String;
    
    Property B As %String;
    
    Index someind On (A,B) As CustomPackage.CustomIndex;
    

    Класс CustomPackage.CustomIndex как раз и есть реализация своего типа индексов.

    В качестве примера рассмотрим небольшой прототип индекса-квадродерева для пространственных данных, созданный на хакатоне командой в составе Андрея ARechitsky Речитского, Александра Погребникова и автора этих строк. Хакатон проходил в рамках ежегодной школы разработчиков InterSystems (отдельное спасибо вдохновителю хакатона tsafin). Материалы школы, кстати, доступны на нашем сайте.

    В данной статье мы не будем касаться того, что такое квадродерево и как с ним работать.

    Остановимся на создании класса, реализующего интерфейс %Library.FunctionalIndex для имеющейся реализации квадродерева. Ей в нашей хакатонной команде занимался Андрей. Андрей создал класс SpatialIndex.Indexer, который умел два метода — Insert(x, y, id) и Delete(x, y, id). При создании объекта класса SpatialIndex.Indexer нужно было указать узел глобала, в подузлы которого писался индекс. Мне оставалось создать класс SpatialIndex.Index, реализующий методы InsertIndex, UpdateIndex, DeleteIndex и PurgeIndex. Первые три из этих методов принимают на входе Id изменяемой строки и индексируемые значения в том же порядке, как и в определении индекса в классе, где этот индекс используется. В нашем примере, pArg(1)A, pArg(2)B.

    Class SpatialIndex.Index Extends %Library.FunctionalIndex [ System = 3 ]
    {
    
    ClassMethod InsertIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
    {
        if %mode'="method" { //'
       	 set IndexGlobal = ..IndexLocation(%class,%property)
       	 $$$GENERATE($C(9)_"set indexer = ##class(SpatialIndex.Indexer).%New($Name("_IndexGlobal_"))")
       	 $$$GENERATE($C(9)_"do indexer.Insert(pArg(1),pArg(2),pID)")
        }
    }
    
    ClassMethod UpdateIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
    {
        if %mode'="method" { //'
       	 set IndexGlobal = ..IndexLocation(%class,%property)
       	 $$$GENERATE($C(9)_"set indexer = ##class(SpatialIndex.Indexer).%New($Name("_IndexGlobal_"))")
       	 $$$GENERATE($C(9)_"do indexer.Delete(pArg(3),pArg(4),pID)")
       	 $$$GENERATE($C(9)_"do indexer.Insert(pArg(1),pArg(2),pID)")
        }
    }
    
    ClassMethod DeleteIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
    {
        if %mode'="method" { //'
       	 set IndexGlobal = ..IndexLocation(%class,%property)
       	 $$$GENERATE($C(9)_"set indexer = ##class(SpatialIndex.Indexer).%New($Name("_IndexGlobal_"))")
       	 $$$GENERATE($C(9)_"do indexer.Delete(pArg(1),pArg(2),pID)")
        }
    }
    
    ClassMethod PurgeIndex() [ CodeMode = generator, ServerOnly = 1 ]
    {
        if %mode'="method" { //'
       	 set IndexGlobal = ..IndexLocation(%class,%property)
       	 $$$GENERATE($C(9)_"kill " _ IndexGlobal)
        }
    }
    
    ClassMethod IndexLocation(className As %String, indexName As %String) As %String
    {
        set storage = ##class(%Dictionary.ClassDefinition).%OpenId(className).Storages.GetAt(1).IndexLocation
        quit $Name(@storage@(indexName))
    }
    
    }

    Метод IndexLocation — вспомогательный, по имени класса и индекса он возвращает имя узла глобала, в котором нужно хранить значения индекса.

    Рассмотрим тестовый класс с индексом типа SpatialIndex.Index:

    Class SpatialIndex.Test Extends %Persistent
    {
    Property Name As %String(MAXLEN = 300);
    
    Property Latitude As %String;
    
    Property Longitude As %String;
    
    Index coord On (Latitude, Longitude) As SpatialIndex.Index;
    }

    При компиляции класса SpatialIndex.Test для каждого индекса типа SpatialIndex.Index в INT-коде генерируются методы:

    zcoordInsertIndex(pID,pArg...) public {
        set indexer = ##class(SpatialIndex.Indexer).%New($Name(^SpatialIndex.TestI("coord")))
        do indexer.Insert(pArg(1),pArg(2),pID) }
    zcoordPurgeIndex() public {
        kill ^SpatialIndex.TestI("coord") }
    zcoordSegmentInsert(pIndexBuffer,pID,pArg...) public {
        do ..coordInsertIndex(pID, pArg...) }
    zcoordUpdateIndex(pID,pArg...) public {
        set indexer = ##class(SpatialIndex.Indexer).%New($Name(^SpatialIndex.TestI("coord")))
        do indexer.Delete(pArg(3),pArg(4),pID)
        do indexer.Insert(pArg(1),pArg(2),pID)
    }

    А методы %SaveData, %DeleteData, %SQLInsert, %SQLUpdate, %SQLDelete вызывают методы индекса. Например, в %SaveData:

     if insert {
         // ...
         do ..coordInsertIndex(id,i%Latitude,i%Longitude,"")
         // ...
     } else {
         // ...
         do ..coordUpdateIndex(id,i%Latitude,i%Longitude,zzc27v3,zzc27v2,"")
         // ...
     }

    Веселее всего смотреть на работающий пример — загрузите файлы из репозитория https://github.com/intersystems-ru/spatialindex/tree/no-web-interface. Это ссылка на ветку без веб-интерфейса. Импортируйте сами классы, распакуйте RuCut.zip и загрузите данные:

    do $system.OBJ.LoadDir("c:\temp\spatialindex","ck")
    do ##class(SpatialIndex.Test).load("c:\temp\rucut.txt")
    

    В файле rucut.txt хранятся данные о 100’000 населённых пунктах России — название и координаты. Метод load читает каждую строку из файла и сохраняет как объект класса SpatialIndex.Test. После его выполнения в глобале ^SpatialIndex.TestI(«coord») будет хранится квадродерево по координатам Latitude и Longitude.

    А теперь запросы


    Построить индекс — полдела. Интереснее всего, когда запросы могут этот индекс использовать. Для индексов нестандартных типов есть стандартный синтаксис их использования, который выглядит примерно так:

    SELECT *
    FROM SpatialIndex.Test
    WHERE %ID %FIND search_index(coord, 'window', 'minx=56,miny=56,maxx=57,maxy=57')
    

    Здесь %ID %FIND search_index — фиксированная часть. Дальше идёт имя индекса, обратите внимание, без кавычек. Все остальные параметры ('window', 'minx=56,miny=56,maxx=57,maxy=57) передаются в метод Find, который тоже нужно определить в классе, описывающем тип индекса (в нашем случае — SpatialIndex.Index):

    ClassMethod Find(queryType As %Binary, queryParams As %String) As %Library.Binary [ CodeMode = generator, ServerOnly = 1, SqlProc ]
    {
        if %mode'="method" { //'
       	 set IndexGlobal = ..IndexLocation(%class,%property)
       	 set IndexGlobalQ = $$$QUOTE(IndexGlobal)
       	 $$$GENERATE($C(9)_"set result = ##class(SpatialIndex.SQLResult).%New()")
       	 $$$GENERATE($C(9)_"do result.PrepareFind($Name("_IndexGlobal_"), queryType, queryParams)")
       	 $$$GENERATE($C(9)_"quit result")
        }
    }

    Здесь параметра два — queryType и queryParams, но это совершенно не обязательно, их может быть больше или меньше.

    Метод Find при компиляции класса, в котором используется индекс SpatialIndex.Index, генерирует вспомогательный метод z<IndexName>Find, который вызывается при выполнении SQL запросов:

    zcoordFind(queryType,queryParams) public { Set:'$isobject($get(%sqlcontext)) %sqlcontext=##class(%Library.ProcedureContext).%New()
        set result = ##class(SpatialIndex.SQLResult).%New()
        do result.PrepareFind($Name(^SpatialIndex.TestI("coord")), queryType, queryParams)
        quit result }
    

    Метод Find должен возвращать экземпляр класса, реализующего интерфейс %SQL.AbstractFind. Методы этого интерфейса — NextChunk, PreviousChunk возвращают битовые строки кусками по 64000 бит. Если запись с номером ID удовлетворяет условиям выборки, то соответствующий бит (номер_куска * 64000 + номер_позиции_внутри_куска) установлен в 1.

    Class SpatialIndex.SQLResult Extends %SQL.AbstractFind
    {
    
    Property ResultBits [ MultiDimensional, Private ];
    
    Method %OnNew() As %Status [ Private, ServerOnly = 1 ]
    {
        kill i%ResultBits
        kill qHandle
        quit $$$OK
    }
    
    Method PrepareFind(indexGlobal As %String, queryType As %String, queryParams As %Binary) As %Status
    {
        if queryType = "window" {
       	 for i = 1:1:4 {
       		 set item = $Piece(queryParams, ",", i)
       		 set param = $Piece(item, "=", 1)
       		 set value = $Piece(item, "=" ,2)
       		 set arg(param) = value
       	 }
             set qHandle("indexGlobal") = indexGlobal
             do ##class(SpatialIndex.QueryExecutor).InternalFindWindow(.qHandle,arg("minx"),arg("miny"),arg("maxx"),arg("maxy"))
             set id = ""
             for  {
       	      set id = $O(qHandle("data", id),1,idd)
       	      quit:id=""
            	 set tChunk = (idd\64000)+1, tPos=(idd#64000)+1
            	 set $BIT(i%ResultBits(tChunk),tPos) = 1
             }
          }
        quit $$$OK
    }
    
    Method ContainsItem(pItem As %String) As %Boolean
    {
        set tChunk = (pItem\64000)+1, tPos=(pItem#64000)+1
        quit $bit($get(i%ResultBits(tChunk)),tPos)
    }
    
    Method GetChunk(pChunk As %Integer) As %Binary
    {
        quit $get(i%ResultBits(pChunk))
    }
    
    Method NextChunk(ByRef pChunk As %Integer = "") As %Binary
    {
        set pChunk = $order(i%ResultBits(pChunk),1,tBits)
        quit:pChunk="" ""
        quit tBits
    }
    
    Method PreviousChunk(ByRef pChunk As %Integer = "") As %Binary
    {
        set pChunk = $order(i%ResultBits(pChunk),-1,tBits)
        quit:pChunk="" ""
        quit tBits
    }
    }
    

    Метод InternalFindWindow класса SpatialIndex.QueryExecutor в приведённом выше примере, это реализация поиска точек, попадающих в заданных прямоугольник. Дальше, в цикле FOR, ID подходящих строк пишутся в битовые наборы.

    В нашем хакатонном проекте кроме поиска в прямоугольнике Андрей реализовал поиск внутри овала:

    SELECT *
    FROM SpatialIndex.Test
    WHERE %ID %FIND search_index(coord,'radius','x=55,y=55,radiusX=2,radiusY=2')
    and name %StartsWith 'Z'
    

    Немного о предикате %FIND


    У этого предиката есть дополнительный параметр SIZE, который может подсказать оптимизатору запроса примерный порядок количества строк, которые будут удовлетворять предикату. На основе этого параметра оптимизатор сделает выбор использовать или нет индекс, к которому %FIND обращается.

    Для примера, добавим следующий индекс к классу SpatialIndex.Test:

    Index ByName on Name;

    Перекомпилируем класс и построим этот индекс:

    write ##class(SpatialIndex.Test).%BuildIndices($LB("ByName"))

    И, конечно, запустим TuneTable:

    do $system.SQL.TuneTable("SpatialIndex.Test", 1)

    Рассмотрим план запроса:

    SELECT *
    FROM SpatialIndex.Test
    WHERE name %startswith 'za'
    and %ID %FIND search_index(coord,'radius','x=55,y=55,radiusX=2,radiusY=2') size ((10))



    Индекс coord предположительно вернёт мало строк, поэтому в индекс по полю Name оптимизатор обращаться не будет.

    Другая картина для запроса:

    SELECT *
    FROM SpatialIndex.Test
    WHERE name %startswith 'za'
    and %ID %FIND search_index(coord,'radius','x=55,y=55,radiusX=2,radiusY=2') size ((1000))



    При выполнении этого запроса будут использоваться оба индекса.

    В качестве последнего примера, запрос, который использует только индекс по полю Name — использовать индекс coord, если ожидается что он вернёт около 100’000 строк,  бесполезно:

    SELECT *
    FROM SpatialIndex.Test
    WHERE name %startswith 'za'
    and %ID %FIND search_index(coord,'radius','x=55,y=55,radiusX=2,radiusY=2') size ((100000))



    Спасибо всем, кто дочитал или хотя бы просмотрел эту статью до конца.

    Большим подспорьем кроме документации, ссылки на которую чуть ниже, будут другие реализации интерфейсов %Library.FunctionalIndex и %SQL.AbstractFind. Чтобы эти реализации посмотреть — откройте в студии один из этих классов и в меню выберите Класс -> Унаследованные классы.

    Ссылки:
    InterSystems
    InterSystems IRIS: СУБД, ESB, BI, Healthcare

    Comments 2

      +1
      А демо посмотреть как работает нету?
        0
        Ну мне кажется, что тут интересней исходники смотреть, как это сделано. А демо можно достаточно просто запустить на своём компьютере — в статье описано как.

      Only users with full accounts can post comments. Log in, please.