http://roaringbitmap.org/

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

http://roaringbitmap.org/

Robert M. Münch
Hi, I think that SQLite use some bitmap indexes and this here might be of interest if not already used/known: http://roaringbitmap.org/ I think it’s from the same guy how did SIMDJSON.

Viele Grüsse.

--

Robert M. Münch, CEO

Saphirion AG
smarter | better | faster

http://www.saphirion.com
http://www.nlpp.ch

Check my calendar at https://doodle.com/saphirion to find a free slot.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

signature.asc (891 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: http://roaringbitmap.org/

Dominique Devienne
On Mon, Sep 2, 2019 at 8:06 AM Robert M. Münch <[hidden email]>
wrote:

> Hi, I think that SQLite use some bitmap indexes


Not that I know of, but I don't know the full source code. Maybe FTS[345]
do/es,
but SQLite itself only uses BTree-indexes AFAIK.


> and this here might be of interest if not already used/known:
> http://roaringbitmap.org/ I think it’s from the same guy how did SIMDJSON.
>

Thanks for sharing. --DD
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: http://roaringbitmap.org/

Hick Gunter
Back in 2011 I implemented a virtual table using the "fastbit" library by John Wu of the Lawrence Berekely National Laboratory. This allowed selects of the form

SELECT ... FROM <base_table> WHERE rowid IN (SELECT rowid FROM <fastbit_index> WHERE <constraints>);

provided that the data had been inserted before by running

INSERT INTO <fastbit_index> SELECT rowid,<indexed fields>;



-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Dominique Devienne
Gesendet: Montag, 02. September 2019 10:59
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] Re: [sqlite] http://roaringbitmap.org/

On Mon, Sep 2, 2019 at 8:06 AM Robert M. Münch <[hidden email]>
wrote:

> Hi, I think that SQLite use some bitmap indexes


Not that I know of, but I don't know the full source code. Maybe FTS[345] do/es, but SQLite itself only uses BTree-indexes AFAIK.


> and this here might be of interest if not already used/known:
> http://roaringbitmap.org/ I think it’s from the same guy how did SIMDJSON.
>

Thanks for sharing. --DD
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: http://roaringbitmap.org/

Dominique Devienne
On Mon, Sep 2, 2019 at 12:08 PM Hick Gunter <[hidden email]> wrote:

> Back in 2011 I implemented a virtual table using the "fastbit" library by
> John Wu of the Lawrence Berekely National Laboratory. This allowed selects
> of the form
>
> SELECT ... FROM <base_table> WHERE rowid IN (SELECT rowid FROM
> <fastbit_index> WHERE <constraints>);
>

Did it work well? Did you get any speedup compared to a normal BTree index?
Available anywhere?
How low the cardinality of indexed columns value-space needs to be to
benefit from a bitmap index?


> provided that the data had been inserted before by running
>
> INSERT INTO <fastbit_index> SELECT rowid,<indexed fields>;


Custom (user-defined) indexes is an area that I'd welcome in SQLite. You
can work around it
as you did above, but that implies the index maintenance rests on the
user's shoulders. While
it would be relatively easy I suspect for SQLite core to notify a custom
index of table changes.

Conversely, you can't use SQLite (sole for now) BTree indexes with a
virtual table, AFAIK,
(I have a doubt all of a sudden...), the vtable must do all the indexing
itself.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: http://roaringbitmap.org/

Hick Gunter
The base table is also a virtual table (we have nearly no native SQLite tables) that stores variable length, variable content logfiles and supports access via record offset, serial number and stored datetime. The effort of decoding specific attributes is significant (sequential read and decode is 10% CPU and 90% IO bound). Certain well defined and commonly used discrete attributes (e.g. ACK/NAK, transaction type, retailer number,..) were lifted from the records via batch programs and inserted into the bitmap index. This reduced the numbe rof records to be read from disk and decoded by a factor of about 1000-4000 with proportional performance gains.

Cardinality of columns ranged from 2 (true/false) to several thousand; the software does a very good job of compressing and processing the bitmaps, leading to high performance.

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Dominique Devienne
Gesendet: Montag, 02. September 2019 13:50
An: SQLite mailing list <[hidden email]>
Betreff: Re: [sqlite] [EXTERNAL] Re: http://roaringbitmap.org/

On Mon, Sep 2, 2019 at 12:08 PM Hick Gunter <[hidden email]> wrote:

> Back in 2011 I implemented a virtual table using the "fastbit" library
> by John Wu of the Lawrence Berekely National Laboratory. This allowed
> selects of the form
>
> SELECT ... FROM <base_table> WHERE rowid IN (SELECT rowid FROM
> <fastbit_index> WHERE <constraints>);
>

Did it work well? Did you get any speedup compared to a normal BTree index?
Available anywhere?
How low the cardinality of indexed columns value-space needs to be to benefit from a bitmap index?


> provided that the data had been inserted before by running
>
> INSERT INTO <fastbit_index> SELECT rowid,<indexed fields>;


Custom (user-defined) indexes is an area that I'd welcome in SQLite. You can work around it as you did above, but that implies the index maintenance rests on the user's shoulders. While it would be relatively easy I suspect for SQLite core to notify a custom index of table changes.

Conversely, you can't use SQLite (sole for now) BTree indexes with a virtual table, AFAIK, (I have a doubt all of a sudden...), the vtable must do all the indexing itself.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: http://roaringbitmap.org/

Robert M. Münch
In reply to this post by Dominique Devienne
On 2 Sep 2019, at 10:59, Dominique Devienne wrote:

> On Mon, Sep 2, 2019 at 8:06 AM Robert M. Münch <[hidden email]>
> wrote:
>
>> Hi, I think that SQLite use some bitmap indexes
>
>
> Not that I know of, but I don't know the full source code. Maybe FTS[345]
> do/es, but SQLite itself only uses BTree-indexes AFAIK.

I think what would be very nice to have in SQLite is a bitmap (not image) datatype where I can store & query single bits and get back a rowid cursor. So, that I can iterate over the hits.

That would unify the API and access pattern to be SQLite compliant. No need to fiddle around with other data-structure or concepts.

--

Robert M. Münch, CEO

Saphirion AG
smarter | better | faster

http://www.saphirion.com
http://www.nlpp.ch

Check my calendar at https://doodle.com/saphirion to find a free slot.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

signature.asc (891 bytes) Download Attachment