mORMot Open Source

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,682

Website

SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

An R-Tree is a special index that is designed for doing range queries. R-Trees are most commonly used in geospatial systems where each entry is a rectangle with minimum and maximum X and Y coordinates. Given a query rectangle, an R-Tree is able to quickly find all entries that are contained within the query rectangle or which overlap the query rectangle. This idea is easily extended to three dimensions for use in CAD systems. R-Trees also find use in time-domain range look-ups. For example, suppose a database records the starting and ending times for a large number of events. A R-Tree is able to quickly find all events, for example, that were active at any time during a given time interval, or all events that started during a particular time interval, or all events that both started and ended within a given time interval. And so forth. See http://www.sqlite.org/rtree.html

A dedicated ORM class, named TSQLRecordRTree, is available to create such tables. It inherits from TSQLRecordVirtual, like the other virtual tables types (e.g. TSQLRecordFTS3).

Any record which inherits from this TSQLRecordRTree class must have only sftFloat (i.e. Delphi double) published fields, grouped by pairs, each as minimum- and maximum-value, up to 5 dimensions (i.e. 11 columns, including the ID property). Its ID: integer property must be set before adding a TSQLRecordRTree to the database, e.g. to link an R-Tree representation to a regular TSQLRecord table containing the main data.

Queries against the ID or the coordinate ranges are almost immediate: so you can e.g. extract some coordinates box from the main regular TSQLRecord table, then use a TSQLRecordRTree-joined query to make the process faster; this is exactly what the TSQLRestClient. RTreeMatch method offers: for instance, running with aMapData.BlobField filled with [-81,-79.6,35,36.2] the following lines:

 aClient.RTreeMatch(TSQLRecordMapData,'BlobField',TSQLRecordMapBox,
   aMapData.BlobField,ResultID);

will execute the following SQL statement:

 SELECT MapData.ID From MapData, MapBox WHERE MapData.ID=MapBox.ID
  AND minX>=:(-81.0): AND maxX<=:(-79.6): AND minY>=:(35.0): AND :(maxY<=36.2):
  AND MapBox_in(MapData.BlobField,:('\uFFF0base64encoded-81,-79.6,35,36.2'):);

The MapBox_in SQL function is registered in TSQLRestServerDB.Create constructor for all TSQLRecordRTree classes of the current database model. Both BlobToCoord and ContainedIn class methods are used to handle the box storage in the BLOB.

By default, it will process a raw array of double, with a default box match (that is ContainedIn method will match the simple minX>=...maxY<=... where clause).

See http://synopse.info/fossil/info/736af989cf

friedolin_nk

Member

Registered: 2012-02-15

Posts: 2

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

Hello,

where can I find a short code example which shows how to create a virtual table with TSQLRecordRtree, add some Data and search data?

Thanks.

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,682

Website

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

You may try the regression tests associated to TSQLRecordRTree.

friedolin_nk

Member

Registered: 2012-02-15

Posts: 2

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

We try to implement a rtee on a virtual table using TSQLRecordRTree and TSQLRestServerStaticInMemory.

The descendant of TSQLRecordRTree is defined as:
 
  TSQLRecordMapBox = class(TSQLRecordRTree)
  protected
    fMinX, fMaxX, fMinY, fMaxY: double;
  public
    AData: tObject;
  published
    property MinX: double read fMinX write fMinX;
    property MaxX: double read fMaxX write fMaxX;
    property MinY: double read fMinY write fMinY;
    property MaxY: double read fMaxY write fMaxY;
  end;
 

The virtual Table is created and filled like this:

procedure TForm2.FormCreate(Sender: TObject);
  procedure Add(x1, y1, x2, y2: double);
  var
    Rec: TSQLRecordMapBox;
  begin
    Rec := TSQLRecordMapBox.Create;
    try

      Rec.MinX := x1;
      Rec.MinY := y1;
      Rec.MaxX := x2;
      Rec.MaxY := y2;
      if m_Database.Add(Rec,true)=0 then begin
        ShowMessage('Error adding the data');
      end;
    finally
      Rec.Free;
    end;
  end;
begin
  m_Database := TSQLRestServerStaticInMemory.Create(TSQLRecordMapBox,nil,
    ChangeFileExt(paramstr(0),'.db'));
  m_Model := TSQLModel.Create([TSQLRecordMapBox]);

  Add(0,0,1,1);
  Add(1,1,2,2);
end;

The first problem is that TSQLRestServerStaticInMemory is a descendant of TSQLRestServer but the procedure RTreeMatches is a method of TSQLRestClient.

How can I query the data in TSQLRestServerStaticInMemory using the RTree.

In my second trial I used the NamedPipeClientServerExample to test the RTReeMach-Method.

On serverside I replaced TSQLSampleRecord with my TSQLRecordMapBox.

On clientside I changed the eventhandler of the "add the message"-button to:

procedure TForm1.AddButtonClick(Sender: TObject);
  procedure Add(x1, y1, x2, y2: double);
  var
    Rec: TSQLRecordMapBox;
  begin
    Rec := TSQLRecordMapBox.Create;
    try

      Rec.MinX := x1;
      Rec.MinY := y1;
      Rec.MaxX := x2;
      Rec.MaxY := y2;
      if Database.Add(Rec,true)=0 then begin
        ShowMessage('Error adding the data');
      end;
    finally
      Rec.Free;
    end;
  end;
begin
  Add(0,0,1,1);
  Add(1,1,2,2);
end;

Then I changed the eventhandler of the "Find a previous message"-Button to:

procedure TForm1.FindButtonClick(Sender: TObject);
var Rec: TSQLRecordMapBox;
  DataID: TIntegerDynArray;
begin
  Rec := TSQLSampleRecord.Create;
  try
    (database as TSQLRestClientURINamedPipe).RTreeMatch(TSQLSampleRecord,'BlobField',TSQLRecordMapBox, Rec.BlobField,DataID);
  finally
    Rec.Free;
  end;
end;

But the TSQLRecordRTree has not a member Blobfield which can be used.

Obviously is that one the differences between the TSQLRecordMapBox and the TSQLRecordMapData. Unfortunately I could not find the declaration of TSQLRecordMapData.

Is there any possibility to get an example for implementing a virtual table with RTrees?
Or is there any possibility to get a (paid) support?

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,682

Website

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

I suppose something like that:

type
  TSQLRecordMapData = class(TSQLRecord)
  private
    fIdent: RawUTF8;
    fCoordinates: TDoubleDynArray;
  published
    property Coordinates: TDoubleDynArray read fCoordinates write fCoordinates;
    property Ident: RawUTF8 read fIdent write fIdent;
  end;

Coordinates is just some internal coordinates.
By default (with the default class functions/procedures in TSQLRecordRTree) those are a list of X,Y pairs, depending on the RTree dimension.

When you insert one TSQLRecordMapData record, you have to insert the corresponding "search box" in TSQLRecordMapBox, forcing the ID property to be the one of the just inserted TSQLRecordMapData.

The use TSQLRestClient.RTreeMatch(TSQLRecordMapData,'Coordinates',TSQLRecordMapBox,SomeBlobDataToBeSearched,ResultIDArray).

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

Is anyone use RTree with mORMot? It seems that it's totally broken.

I try this simple code (on version 1.18.1525):

program SynRTreeTest;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  mORMot,
  mORMotSQLite3,
  SynCommons,
  SynSQLite3Static;

type
  TSQLRecordMapBox = class(TSQLRecordRTree)
  protected
    fMinX, fMaxX, fMinY, fMaxY: double;
  published
    property MinX: double read fMinX write fMinX;
    property MaxX: double read fMaxX write fMaxX;
    property MinY: double read fMinY write fMinY;
    property MaxY: double read fMaxY write fMaxY;
  end;

  TSQLRecordMapData = class(TSQLRecord)
  private
    FBBox: TSQLRawBlob;
  published
    property BBox: TSQLRawBlob read FBBox write FBBox;
  end;

function CoordsToBlob(AMinX, AMaxX, AMinY, AMaxY: Double): TSQLRawBlob;
var
  VBox: TDoubleDynArray;
  VSize: Integer;
begin
  SetLength(VBox, 4);
  VBox[0] := AMinX;
  VBox[1] := AMaxX;
  VBox[2] := AMinY;
  VBox[3] := AMaxY;
  VSize := 4 * SizeOf(Double);
  SetLength(Result, VSize);
  Move(VBox[0], Result[1], VSize);
end;

procedure InsertTestRecord(const AClient: TSQLRestClient);
var
  VMapBox: TSQLRecordMapBox;
  VMapData: TSQLRecordMapData;
begin
  VMapBox := TSQLRecordMapBox.Create;
  VMapData := TSQLRecordMapData.Create;
  try
    VMapData.BBox := CoordsToBlob(-10, 10, -5, 5);
    AClient.Add(VMapData, True);
    AClient.UpdateBlob(TSQLRecordMapData, VMapData.ID, 'BBox', VMapData.BBox);

    VMapBox.IDValue := VMapData.ID;
    VMapBox.MinX := -10;
    VMapBox.MaxX := 10;
    VMapBox.MinY := -5;
    VMapBox.MaxY := 5;
    AClient.Add(VMapBox, True);
  finally
    VMapData.Free;
    VMapBox.Free;
  end;
end;

procedure TestSearchBBox(const AClient: TSQLRestClient);
var
  VIDArray: TIDDynArray;
  VSearchBBox: TSQLRawBlob;
begin
  VSearchBBox := CoordsToBlob(-20, 20, -25, 25);
  AClient.RTreeMatch(TSQLRecordMapData, 'BBox', TSQLRecordMapBox, VSearchBBox, VIDArray);
  Assert(Length(VIDArray) > 0);
end;

var
  VModel: TSQLModel;
  VClient: TSQLRestClientDB;
begin
  try
    Writeln(SYNOPSE_FRAMEWORK_FULLVERSION);
    VModel := TSQLModel.Create([TSQLRecordMapData, TSQLRecordMapBox]);
    VClient := TSQLRestClientDB.Create(VModel,nil,'rtree.db3',TSQLRestServerDB);
    try
      VClient.Server.CreateMissingTables;
      InsertTestRecord(VClient);
      TestSearchBBox(VClient);
    finally
      VClient.Free;
      VModel.Free;
    end;
    Writeln('Press ENTER to exit...');
    Readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Database created and record's inserted as expected. But, RTreeMatch rise an error:

Exception class ESQLite3Exception with message 'Error SQLITE_ERROR (1) using 3.8.10.2 - 'near "WHERE": syntax error' extended_errcode=1'. Process SynRTreeTest.exe (616)

I found very strange generated request in TSQLRestClient.RTreeMatch (mORMot.pas)

Res.fQuerySQL: 'SELECT MapData.RowID FROM MapData,MapBox WHERE WHERE MapData.RowID=MapBox.RowID AND MinX >= :(1.8124101858365E-307): AND MaxX <= :(1.85060611072132E-307): AND MinY >= :(0): AND MaxY <= :(3.47621106758535E-308): AND MapBox_in(MapData,:(￰AAAAAAAANMAAAAAAAAA0QAAAAAAAADnAAAAAAAAAOUA=):);;'

- there is 2 WHERE statements
- garbage in coordinates

Then I try make few fixes in TSQLRestClient.RTreeMatch:

if Blob=nil then
    exit;
  RTreeTable.BlobToCoord(DataTableBlobField[1],B);                                  // call this before build 'Where'
  for i := 0 to (RTree.Fields.Count shr 1)-1 do
    Where := FormatUTF8('%% >= :(%): AND % <= :(%): AND ',
      [Where,RTree.Fields.List[i*2].Name,B[i].Min,RTree.Fields.List[i*2+1].Name,
       B[i].Max]);
  //RTreeTable.BlobToCoord(DataTableBlobField[1],B);                               // too late... 
  Res := ListFmt([DataTable,RTreeTable],Data.SQLTableName+'.RowID',
    '%.RowID=%.RowID AND %%(%,:(%):);',                                          // remove unexpected WHERE
    //'WHERE %.RowID=%.RowID AND %%(%,:(%):);',
      [Data.SQLTableName,RTree.SQLTableName,Where,
       RTreeTable.RTreeSQLFunctionName,Data.SQLTableName,
       BinToBase64WithMagic(DataTableBlobField)]);
  if Res<>nil then

and in TSQLRecordRTree.BlobToCoord:

class procedure TSQLRecordRTree.BlobToCoord(const InBlob;
  var OutCoord: TSQLRecordTreeCoords);
begin // direct memory copy with no memory check
  MoveFast(InBlob,OutCoord,(RecordProps.Fields.Count)*sizeof(double));   
  //MoveFast(InBlob,OutCoord,(RecordProps.Fields.Count shr 1)*sizeof(double));  // wrong size calculation  
end;

After all this, I still got an error:

Exception class ESQLite3Exception with message 'Error SQLITE_ERROR (1) using 3.8.10.2 - 'unrecognized token: ":"' extended_errcode=1'

SQL request is:

'SELECT MapData.RowID FROM MapData,MapBox WHERE MapData.RowID=MapBox.RowID AND MinX >= :(-20): AND MaxX <= :(20): AND MinY >= :(-25): AND MaxY <= :(25): AND MapBox_in(MapData,:(￰AAAAAAAANMAAAAAAAAA0QAAAAAAAADnAAAAAAAAAOUA=):);;'

I need help :(

Last edited by zed (2015-06-22 14:51:37)

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

And I found that I can't use TDoubleDynArray as type for TSQLRecordMapData.BBox, because TSQLRestClient.RTreeMatch can't detect this field as Blob. This is bug too?

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

Workaround is to create a direct SQL request:

  VSQL := FormatUTF8(
    'SELECT RowID FROM MapBox WHERE MinX>=? AND MaxX<=? AND MinY>=? AND MaxY<=?;',
    [], [-20, 20, -25, 25]
  );
  VIDList := AClient.ExecuteList([TSQLRecordMapBox], VSQL);

It works and doesn't require FBBox field in MapData record. As I understand, this field is used if we store a real Coordinates of our geometry in it and do our private checks in our implementation of ContainedIn function. And that is a default implementation of this function is no sense, because it simple repeat RTree checks by rect boundary and just slow down all search process.

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,682

Website

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

1. "can't use TDoubleDynArray as type for TSQLRecordMapData.BBox"
This is by design: only supported type is a raw BLOB, by now.

2. I do not get why you use both "MinX>=? AND MaxX<=? AND MinY>=? AND MaxY<=?" and "MapBox_in()".
AFAIR MapBox_In() should be enough in your case.
But I guess there may be issues with MapBox_In().
Ticket http://synopse.info/fossil/info/c9c9989cd7 is worth it.

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

Re: SQLite3 Framework: TSQLRecordRTree to implement R-Tree virtual tables

2. I do not get why you use both "MinX>=? AND MaxX<=? AND MinY>=? AND MaxY<=?" and "MapBox_in()".
AFAIR MapBox_In() should be enough in your case.

It's not I use, it's RTreeMatch use Take a look:

function TSQLRestClient.RTreeMatch(DataTable: TSQLRecordClass;
  const DataTableBlobFieldName: RawUTF8; RTreeTable: TSQLRecordRTreeClass;
  const DataTableBlobField: RawByteString; var DataID: TIDDynArray): boolean;
var Blob: PPropInfo;
    Res: TSQLTableJSON;
    B: TSQLRecordTreeCoords;
    Where: RawUTF8;
    Data, RTree: TSQLRecordProperties;
    i: integer;
begin
  result := false;
  if (self=nil) or (DataTable=nil) or (RTreeTable=nil) or (DataTableBlobField='') then
    exit;                                                                                                                 
  RTree := RTreeTable.RecordProps;
  Data := DataTable.RecordProps;
  Blob :=  Data.BlobFieldPropFromRawUTF8(DataTableBlobFieldName);
  if Blob=nil then
    exit;                                                                                                                 
  for i := 0 to (RTree.Fields.Count shr 1)-1 do
    Where := FormatUTF8('%% >= :(%): AND % <= :(%): AND ',
      [Where,RTree.Fields.List[i*2].Name,B[i].Min,RTree.Fields.List[i*2+1].Name,
       B[i].Max]);
  RTreeTable.BlobToCoord(DataTableBlobField[1],B);
  Res := ListFmt([DataTable,RTreeTable],Data.SQLTableName+'.RowID',
    'WHERE %.RowID=%.RowID AND %%(%,:(%):);',
      [Data.SQLTableName,RTree.SQLTableName,Where,
       RTreeTable.RTreeSQLFunctionName,Data.SQLTableName,
       BinToBase64WithMagic(DataTableBlobField)]);
  if Res<>nil then
  try
    if (Res.FieldCount<>1) or (Res.fRowCount<=0) then
      exit;
    Res.GetRowValues(0,TInt64DynArray(DataID));
    result := true;
  finally
    Res.Free;
  end;
end;

Maybe, you should redesign it.