Re: [sqlite] Index without backing table

[Paul]

> On Mon, 03 Nov 2014 11:50:17 +0200
> Paul  wrote:
> 
> > > > Would be nice to have ability to store both key and payload in the
> > > > index. (Let's call it index-only table)
> > > > This could be a feature that sets some limitations on a table,
> > > > like being unable to have more than one index or inefficient
> > > > table scans, but it will also give some advantage in special
> > > > cases like mine.
> > > 
> > > What you're describing sounds very much to me like a SQLite table.
> > > See http://www.sqlite.org/fileformat2.html, section 1.5, the
> > > reference to "index b-tree". 
> > 
> > So, to be clear, WITHOUT ROWID table will have it's PRIMARY KEY 
> > as a replacement for ROWID and table itself is an index?
> 
> Yes, approximately. http://www.sqlite.org/withoutrowid.html says: 
> 
> > CREATE TABLE IF NOT EXISTS wordcount(
> > word TEXT PRIMARY KEY,
> > cnt INTEGER
> > ) WITHOUT ROWID;
> > 
> > In this latter table, there is only a single B-Tree which uses the
> > "word" column as its key and the "cnt" column as its data. 
> 
> That is, the table is stored as a B-tree with the declared primary key
> as the B-tree key. 
> 
> I wouldn't say, "the table is an index". I reserve the word "index" in
> this sense to mean "something that speeds up searching in something
> else", and in this case there's no "else". 
> 
> The table is stored on disk as a tree. A tree can be used as an index,
> and an index may be implemented as a tree. But not every tree is an
> index. 
> 
> HTH. 
> 
> --jkl

Thank you for your answer, James! 

Regards,

Paul

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[James K. Lowden]

On Mon, 03 Nov 2014 11:50:17 +0200
Paul  wrote:

> > > Would be nice to have ability to store both key and payload in the
> > > index. (Let's call it index-only table)
> > > This could be a feature that sets some limitations on a table,
> > > like being unable to have more than one index or inefficient
> > > table scans, but it will also give some advantage in special
> > > cases like mine.
> > 
> > What you're describing sounds very much to me like a SQLite table.
> > See http://www.sqlite.org/fileformat2.html, section 1.5, the
> > reference to "index b-tree".  
> 
> So, to be clear, WITHOUT ROWID table will have it's PRIMARY KEY 
> as a replacement for ROWID and table itself is an index?

Yes, approximately.  http://www.sqlite.org/withoutrowid.html says: 

> CREATE TABLE IF NOT EXISTS wordcount(
>   word TEXT PRIMARY KEY,
>   cnt INTEGER
> ) WITHOUT ROWID;
> 
> In this latter table, there is only a single B-Tree which uses the
> "word" column as its key and the "cnt" column as its data.  

That is, the table is stored as a B-tree with the declared primary key
as the B-tree key.  

I wouldn't say, "the table is an index".  I reserve the word "index" in
this sense to mean "something that speeds up searching in something
else", and in this case there's no "else".  

The table is stored on disk as a tree.  A tree can be used as an index,
and an index may be implemented as a tree.  But not every tree is an
index.  

HTH.  

--jkl
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

3 November 2014, 13:56:36, by "Richard Hipp" :
 
>   On Mon, Nov 3, 2014 at 6:48 AM, Clemens Ladisch  wrote:
> 
> > Paul wrote:
> > > Are additional indices, created for WITHOUT ROWID, potentially less
> > > efficient and more cumbersome?
> >
> > For tables with a rowid, the index stores the indexed columns and the
> > rowid.  For WITHOUT ROWID tables, the index stores the indexed columns
> > and the primary key.
> >
> 
> And, lookup by rowid is (usually) faster than lookup by arbitrary primary
> key.  So, yes, WITHOUT ROWIDs might be a little slower when using secondary
> indexes.
> 
> But in a complex system, many factors come into play.  It is best to give
> it a try.
> 
> Realize that any schema that works with WITHOUT ROWID on a table, will work
> just as well with the WITHOUT ROWID omitted.  So you can test your
> application both with and without the WITHOUT ROWID clause and see which
> gives the better performance, without making any changes to your internal
> queries.
> 

Thank you, for clarification, Dr. Hipp.

I'll definitely give it a try, especially after the fact that they (tables) 
work identically.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Richard Hipp]

On Mon, Nov 3, 2014 at 6:48 AM, Clemens Ladisch  wrote:

> Paul wrote:
> > Are additional indices, created for WITHOUT ROWID, potentially less
> > efficient and more cumbersome?
>
> For tables with a rowid, the index stores the indexed columns and the
> rowid.  For WITHOUT ROWID tables, the index stores the indexed columns
> and the primary key.
>

And, lookup by rowid is (usually) faster than lookup by arbitrary primary
key.  So, yes, WITHOUT ROWIDs might be a little slower when using secondary
indexes.

But in a complex system, many factors come into play.  It is best to give
it a try.

Realize that any schema that works with WITHOUT ROWID on a table, will work
just as well with the WITHOUT ROWID omitted.  So you can test your
application both with and without the WITHOUT ROWID clause and see which
gives the better performance, without making any changes to your internal
queries.

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

3 November 2014, 13:48:30, by "Clemens Ladisch" :
 
>   Paul wrote:
> > Are additional indices, created for WITHOUT ROWID, potentially less
> > efficient and more cumbersome?
> 
> For tables with a rowid, the index stores the indexed columns and the
> rowid.  For WITHOUT ROWID tables, the index stores the indexed columns
> and the primary key.
> 

Just what I thought, thank you.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Clemens Ladisch]

Paul wrote:
> Are additional indices, created for WITHOUT ROWID, potentially less
> efficient and more cumbersome?

For tables with a rowid, the index stores the indexed columns and the
rowid.  For WITHOUT ROWID tables, the index stores the indexed columns
and the primary key.


Regards,
Clemens
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

 > 
> On 3 Nov 2014, at 9:50am, Paul  wrote:
> 
> > So, to be clear, WITHOUT ROWID table will have it's PRIMARY KEY 
> > as a replacement for ROWID and table itself is an index?
> 
> It would appear that the answer is "yes". I'm not going to go beyond the 
> official documentation at
> 
> 
> 
> but if you have a specific question, please post it.
> 
> Simon.

Dr. Hipp has pointed out to use WITHOUT ROWID table, but I was too ignorant to 
attentively read the whole page :( 


I have one more question though:

Are additional indices, created for WITHOUT ROWID, potentially less efficient 
and more cumbersome?

Thank You, 
Paul
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Simon Slavin]

On 3 Nov 2014, at 9:50am, Paul  wrote:

> So, to be clear, WITHOUT ROWID table will have it's PRIMARY KEY 
> as a replacement for ROWID and table itself is an index?

It would appear that the answer is "yes".  I'm not going to go beyond the 
official documentation at



but if you have a specific question, please post it.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

> 
> > Would be nice to have ability to store both key and payload in the
> > index. (Let's call it index-only table)
> > This could be a feature that sets some limitations on a table, like
> > being unable to have more than one index or inefficient table scans,
> > but it will also give some advantage in special cases like mine.
> 
> What you're describing sounds very much to me like a SQLite table.  See
> http://www.sqlite.org/fileformat2.html, section 1.5, the reference to
> "index b-tree".  
> 
> You're in good company.  The technique of storing key and value together
> "in order" in some sense is as old as databases.  
> 
> --jkl

So, to be clear, WITHOUT ROWID table will have it's PRIMARY KEY 
as a replacement for ROWID and table itself is an index?

If so, it perfectly matches my needs.

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[James K. Lowden]

On Sat, 01 Nov 2014 11:06:51 +0200
Paul  wrote:

> Would be nice to have ability to store both key and payload in the
> index. (Let's call it index-only table)
> This could be a feature that sets some limitations on a table, like
> being unable to have more than one index or inefficient table scans,
> but it will also give some advantage in special cases like mine.

What you're describing sounds very much to me like a SQLite table.  See
http://www.sqlite.org/fileformat2.html, section 1.5, the reference to
"index b-tree".  

You're in good company.  The technique of storing key and value together
"in order" in some sense is as old as databases.  

--jkl
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

 Hi Edward,

To be specific about my case: 

What I really wanted is to have Key -> Value mapping (B-tree). 
I love how SQLite can handle compound keys.
So for example, if my key is a compound key (A, B), 
I can query values by A as well as by (A, B).
This is very useful.

Imagine a case when Key is let's say a string of fixes length of 32 bytes.
The value on the other hand is just an unique id, a 8 byte INTEGER.
This is special case, when key part is much bigger than actual data.

So, if table looks like this,

CREATE TABLE index(Key TEXT, Value INTEGER);

behind the curtain, SQLite will store ROWID + Key + Value 
= 8 + 32 + 8 = 48 bytes of data per row.

This is how I create index:

CREATE INDEX key_idx ON index(Key);

I am strongly sure that behind the curtain, each record in the BTree 
has its own copy of Key as well as ROWID ie, in the perfect
scenario, each node is of size 32 + 8 = 40 bytes.

Lets sum up sizes: 48 + 40 = 88 bytes. This is approximate cost of each record.
But if, somehow, we could get rid of the table part, and store Value instead of
ROWID in the index, the size will go down to 40 bytes.

I am not concerned very much about actual size, but about the fact, that when I 
insert
single record into the table, SQLite will update one or more index (BTree) 
pages + one or
more table pages. If we could skip table updates we would save both space and 
I/O operations.

So, having this structure, we could still perform any query imaginable,
but only one specific use case will be efficient: 

SELECT * FROM index WHERE Key (= | > | <) ?;


To sum up my gibberish: 

Would be nice to have ability to store both key and payload in the index.
(Let's call it index-only table)
This could be a feature that sets some limitations on a table, like being
unable to have more than one index or inefficient table scans, but it will
also give some advantage in special cases like mine.


-

About your case, Edward. I believe you also need mapping where Key is Big 
(text) but Value is small (offset in a file?)?

> Hi Paul:
> 
> 
> Not sure about your specific use case. If you intent to query formatted text 
> log files, and do not need pin-point seek to a record (file scan is 
> acceptable), I am working on an external module that is in alpha stage.
> 
> https://github.com/elau1004/TFR4SQLite/wiki
> 
> 
> It is implemented using virtual tables. The idea of indexing these files did 
> cross my mind and you did beat me to asking the same question.
> 
> 
> Regards.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Richard Hipp]

On Fri, Oct 31, 2014 at 8:35 AM, Alessandro Marzocchi <
alessandro.marzoc...@gmail.com> wrote:

> I think what he wants is a way to create an index on a virtual table.
>

SQLite cannot build an index on a virtual table because SQLite has no idea
if and when the content of the table will change and hence has no way of
keeping the index up-to-date.

The virtual table implementation is free to create its own indexes,
however.  The query planner uses the xBestIndex method on the virtual table
object to let the virtual table implementation know about WHERE clause
constraints and allow the virtual table to suggest appropriate (internal)
indexes to use.  This is possible because the virtual table implementation
does (presumably) know when the content of the table changes and can keep
the indexes updated.

The virtual table implementation is free to construct shadow index tables,
perhaps using WITHOUT ROWID.

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Dominique Devienne]

On Fri, Oct 31, 2014 at 1:35 PM, Alessandro Marzocchi <
alessandro.marzoc...@gmail.com> wrote:

> I think what he wants is a way to create an index on a virtual table.
>

+1 to that. --DD
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Paul]

31 October 2014, 14:19:56, by "Richard Hipp" :

>   I don't really understand what you are asking, but I suspect that
> http://www.sqlite.org/withoutrowid.html is probably the answer you are
> looking for.

I have just realized, how stupid my question is. 
Actually I don't even have to use w/o rowid table since my primary key is an 
INTEGER.

Thank you!


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Alessandro Marzocchi]

I think what he wants is a way to create an index on a virtual table. I
faced a similar problem recently and seeing that there was no apparent way
to do that I steered to a completely different way. Lets say I have a
immutable binary file which contains n rows of struct containing 10 (let's
name them a...j) integers (e.g. as they would be laid out by c in memory).
Writing a virtual table for it would be fairly easy. But what if I want to
make an index to help search rows? Like if I want to make an index on c and
on e,a. My solution would be to create a real table from the virtual table
code and index that. Is there any smarter ways?
Il 31/ott/2014 13:20 "Richard Hipp" <d...@sqlite.org> ha scritto:

> I don't really understand what you are asking, but I suspect that
> http://www.sqlite.org/withoutrowid.html is probably the answer you are
> looking for.
>
> On Fri, Oct 31, 2014 at 8:15 AM, Hick Gunter <h...@scigames.at> wrote:
>
> > Can you give an example of what such a beast would look like?
> >
> > CREATE TABLE not_exist (A, B, C, D, E);-- for illustrative purposes
> > CREATE INDEX no_table ON not_exist (A,B,C,D,E); -- has to be covering
> index
> >
> > The only efficient order to return and/or select rows is by {A}, {A,B},
> > {A,B,C}, ...
> >
> > All other selects need to perform a full table/index scan, e.g. SELECT
> ...
> > WHERE C=15;
> > All other orders need to perform a sort, e.g. SELECT ... ORDER BY C;
> >
> > -Ursprüngliche Nachricht-
> > Von: Paul [mailto:de...@ukr.net]
> > Gesendet: Freitag, 31. Oktober 2014 11:30
> > An: General Discussion of SQLite Database
> > Betreff: [sqlite] Index without backing table
> >
> > Is there a way to have index without table?
> >
> > Is it possible to achieve this with virtual talbe tricks but without
> > implementing B-tree myself?
> >
> > I need this both for space effciency and to minimize disk I/O (by
> avoiding
> > table updates).
> > ___
> > sqlite-users mailing list
> > sqlite-users@sqlite.org
> > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
> >
> >
> > ___
> >  Gunter Hick
> > Software Engineer
> > Scientific Games International GmbH
> > FN 157284 a, HG Wien
> > Klitschgasse 2-4, A-1130 Vienna, Austria
> > Tel: +43 1 80100 0
> > E-Mail: h...@scigames.at
> >
> > This communication (including any attachments) is intended for the use of
> > the intended recipient(s) only and may contain information that is
> > confidential, privileged or legally protected. Any unauthorized use or
> > dissemination of this communication is strictly prohibited. If you have
> > received this communication in error, please immediately notify the
> sender
> > by return e-mail message and delete all copies of the original
> > communication. Thank you for your cooperation.
> >
> >
> > ___
> > sqlite-users mailing list
> > sqlite-users@sqlite.org
> > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
> >
>
>
>
> --
> D. Richard Hipp
> d...@sqlite.org
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Richard Hipp]

I don't really understand what you are asking, but I suspect that
http://www.sqlite.org/withoutrowid.html is probably the answer you are
looking for.

On Fri, Oct 31, 2014 at 8:15 AM, Hick Gunter <h...@scigames.at> wrote:

> Can you give an example of what such a beast would look like?
>
> CREATE TABLE not_exist (A, B, C, D, E);-- for illustrative purposes
> CREATE INDEX no_table ON not_exist (A,B,C,D,E); -- has to be covering index
>
> The only efficient order to return and/or select rows is by {A}, {A,B},
> {A,B,C}, ...
>
> All other selects need to perform a full table/index scan, e.g. SELECT ...
> WHERE C=15;
> All other orders need to perform a sort, e.g. SELECT ... ORDER BY C;
>
> -Ursprüngliche Nachricht-
> Von: Paul [mailto:de...@ukr.net]
> Gesendet: Freitag, 31. Oktober 2014 11:30
> An: General Discussion of SQLite Database
> Betreff: [sqlite] Index without backing table
>
> Is there a way to have index without table?
>
> Is it possible to achieve this with virtual talbe tricks but without
> implementing B-tree myself?
>
> I need this both for space effciency and to minimize disk I/O (by avoiding
> table updates).
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: h...@scigames.at
>
> This communication (including any attachments) is intended for the use of
> the intended recipient(s) only and may contain information that is
> confidential, privileged or legally protected. Any unauthorized use or
> dissemination of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the sender
> by return e-mail message and delete all copies of the original
> communication. Thank you for your cooperation.
>
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Index without backing table

[Hick Gunter]

Can you give an example of what such a beast would look like?

CREATE TABLE not_exist (A, B, C, D, E);-- for illustrative purposes
CREATE INDEX no_table ON not_exist (A,B,C,D,E); -- has to be covering index

The only efficient order to return and/or select rows is by {A}, {A,B}, 
{A,B,C}, ...

All other selects need to perform a full table/index scan, e.g. SELECT ... 
WHERE C=15;
All other orders need to perform a sort, e.g. SELECT ... ORDER BY C;

-Ursprüngliche Nachricht-
Von: Paul [mailto:de...@ukr.net]
Gesendet: Freitag, 31. Oktober 2014 11:30
An: General Discussion of SQLite Database
Betreff: [sqlite] Index without backing table

Is there a way to have index without table?

Is it possible to achieve this with virtual talbe tricks but without 
implementing B-tree myself?

I need this both for space effciency and to minimize disk I/O (by avoiding 
table updates).
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users


___
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: h...@scigames.at

This communication (including any attachments) is intended for the use of the 
intended recipient(s) only and may contain information that is confidential, 
privileged or legally protected. Any unauthorized use or dissemination of this 
communication is strictly prohibited. If you have received this communication 
in error, please immediately notify the sender by return e-mail message and 
delete all copies of the original communication. Thank you for your cooperation.


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Index without backing table

[Paul]

Is there a way to have index without table?

Is it possible to achieve this with virtual talbe tricks but without 
implementing B-tree myself?

I need this both for space effciency and to minimize disk I/O (by avoiding 
table updates).
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users