Re: [sqlite] suggestion: bitwise shift right optimization

[Max Vlasov]

>   In the case of SQLite, it is also very unlikely to save space.  In
>  fact, because of the way integer values are stored, it is very
>  likely to use more space.
>

Jay, In most cases yes, but there are ones with several integers that should
be used together in ordering, the space is wasted since sqlite saves the
table b-tree with the rowid + these integers and also index b-tree with the
integers and rowid reference. When such tables contains thousands or
millions records, it starts making sense. Using rowid in this case as a
packed value should help.

Ironically sqlite being db right before you with all the statistics
available encourages experimenting opposite to for example mysql looking
like a mountain far away )

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

Re: [sqlite] suggestion: bitwise shift right optimization

[Jay A. Kreibich]

On Tue, Jul 20, 2010 at 04:43:26PM +0400, Max Vlasov scratched on the wall:
> Hi,
> as long as I see currently bitwise right does not use index

  Doing this requires recognizing when an inverse expression exists,
  and then computing it.  It is extremely difficult in the general
  case.  If you want to use an index, you need to refer to a direct value.

> But the first syntax is more straightforward.

  Having a proper column is even more straightforward.  It also makes
  this whole issue go away and makes your indexes work correctly.

> Btw, actually, sometimes when several small fields exists and they should be
> indexed, one can pack them into id(rowid) to save space and the first syntax
> will allow querying more naturally

  This breaks First Normal Form and is very un-relational.  If you want
  the database to do what it does best, use it properly.  Doing stuff
  like this is thinking like a C programmer, not a database programmer.

  In the case of SQLite, it is also very unlikely to save space.  In
  fact, because of the way integer values are stored, it is very
  likely to use more space.

  It also screams of premature optimization.  In most cases it won't
  save you much, if anything, and will cause all kinds of problems
  (like this!).  You also loose the ability to index anything other
  than the left-most field.  
  
  Finally, bit operations are not part of the SQL standard,
  making this kind of approach very non-portable.  Many databases
  don't even use binary integers to store natural-number values.

   -j

-- 
Jay A. Kreibich < J A Y  @  K R E I B I.C H >

"Intelligence is like underwear: it is important that you have it,
 but showing it to the wrong people has the tendency to make them
 feel uncomfortable." -- Angela Johnson
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] suggestion: bitwise shift right optimization

[Max Vlasov]

On Tue, Jul 20, 2010 at 5:14 PM, Pavel Ivanov  wrote:

> > Are there reasons not to implement optimization in the first case? Except
> > for this is not most requested one :)
>
> I guess because this case is highly specific and it's behavior should
> depend on particular constants used. Put there for example Id >> 54 =
> 1000 and now we should make optimizer guess right away that query will
> never return any rows.
>
>
Pavel, I thought about this a little more and I can see a little problem

For example, if we have an abstract function F, that we can guarantee:
- if a <=b  F(a)<=F(b)
- if a >=b  F(a)>=F(b)
we actually should perform a kind of range search, but less effective than
general range search. General range search knows what are the limits so
search only for them regardless of the rows to be found, but this query
should find any value and after that move left while F() is true and move
right while F() is true.

On the other size this kind of search will have either the same
effectiveness as a full scan (in worst case) or better. I suppose this
limitation is also why the queries with complex left parts (even WHERE id +
1 =) also does not use optimizer (CMIIW)

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

Re: [sqlite] suggestion: bitwise shift right optimization

[Pavel Ivanov]

> Are there reasons not to implement optimization in the first case? Except
> for this is not most requested one :)

I guess because this case is highly specific and it's behavior should
depend on particular constants used. Put there for example Id >> 54 =
1000 and now we should make optimizer guess right away that query will
never return any rows.

> Btw, actually, sometimes when several small fields exists and they should be
> indexed, one can pack them into id(rowid) to save space and the first syntax
> will allow querying more naturally

Only for the field placed in the highest valued bits. Fields in lower
valued bits will have to use '&' operator which can't use index
anyway.


Pavel

On Tue, Jul 20, 2010 at 8:43 AM, Max Vlasov  wrote:
> Hi,
> as long as I see currently bitwise right does not use index
>
> CREATE TABLE [TestTable] ([Id] INTEGER PRIMARY KEY AUTOINCREMENT);
>
> EXPLAIN QUERY PLAN SELECT * FROM TestTable WHERE Id >> 12 = 1000;
> : TABLE TestTable
>
> Sure I can replace it with the following query
>
> EXPLAIN QUERY PLAN SELECT * FROM TestTable WHERE Id BETWEEN 1000 << 12 AND
> (1001 << 12)-1;
> : TABLE TestTable USING PRIMARY KEY
>
> But the first syntax is more straightforward.
> Are there reasons not to implement optimization in the first case? Except
> for this is not most requested one :)
> Btw, actually, sometimes when several small fields exists and they should be
> indexed, one can pack them into id(rowid) to save space and the first syntax
> will allow querying more naturally
>
> Thanks,
>
> Max Vlasov
> maxerist.net
> ___
> 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

[sqlite] suggestion: bitwise shift right optimization

[Max Vlasov]

Hi,
as long as I see currently bitwise right does not use index

CREATE TABLE [TestTable] ([Id] INTEGER PRIMARY KEY AUTOINCREMENT);

EXPLAIN QUERY PLAN SELECT * FROM TestTable WHERE Id >> 12 = 1000;
: TABLE TestTable

Sure I can replace it with the following query

EXPLAIN QUERY PLAN SELECT * FROM TestTable WHERE Id BETWEEN 1000 << 12 AND
(1001 << 12)-1;
: TABLE TestTable USING PRIMARY KEY

But the first syntax is more straightforward.
Are there reasons not to implement optimization in the first case? Except
for this is not most requested one :)
Btw, actually, sometimes when several small fields exists and they should be
indexed, one can pack them into id(rowid) to save space and the first syntax
will allow querying more naturally

Thanks,

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