Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Steven E. Harris]

Igor Tandetnik  writes:

> It doesn't matter. The whole point is that the key is constructed in
> such a way that both procedures would arrive at the same result.

That's really what was at the heart of my question: If separate
value-by-value was necessary, then I would conclude that the
concatenated key would /not/ yield the corrected result by comparing the
whole thing in one operation.

I was having trouble convincing myself that the single comparison would
always work. I was looking for a counterexample, where a shorter value's
end and the beginning the following value could be mistakenly compared
against a single longer value. The language used in the referenced Wiki
page added further to my confusion, so I thought it best to ask for
clarification. Studying the encoding more carefully, I see that the end
of one value will always sort earlier than any intermediate byte in
another value. That numbers can never contain a zero byte is an
easy-to-miss detail.


A couple more nits on that page: In the second paragraph, we find:

,
| until a difference if found
` ^
  |
   +--+
   |
s/if/is/


The seventh paragraph reads as follows:

,
| The first byte of a key past the table number will be in the range of
| 0x05..0x0f if ascending or 0xf0..0xfa if descending. This leaves large
| chunks of key space available for other uses. For example, the
| three-byte key 0x00 0x00 0x01 stores the schema cookie for the database
| as a 64-bit big-endian integer.
`

The part that says the first byte will be valued between 5 and 15
(decimal) for ascending values doesn't agree with the table at the end,
where we see leading bytes in the range 0x05 to 0x25, or 5 to 37
decimal. Am I comparing different things here?


Finally, to restate an inquiry from my earlier message, which I had some
trouble sending properly:

I don't understand why the example entries for values 99.0, 99.01, and
99.0001 have first bytes of 0xb4 and 0xb5, respectively.

If we take 99 and use it as "X" in the "2*X+0" formula, shouldn't we
wind up with 198, or 0xC6? Likewise, for the second two examples, I'd
expect 2*99+1 to yield 199, or 0xC7. (The later entry for  has bytes
0xC7 and 0xC6, which match my expectation.)


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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Richard Hipp]

On Tue, Jul 3, 2012 at 3:59 PM, Igor Tandetnik  wrote:

> On 7/3/2012 3:50 PM, Steven E. Harris wrote:
>
>> The first paragraph mentions that the encoding allows comparison of keys
>> with memcmp(), which makes it sound like an entire key -- meaning the
>> concatenation of several values -- can be be compared in one operation
>> against another key.
>>
>> The second paragraph notes:
>>
>> ,
>> | Keys are compared value by value, from left to right, until a difference
>> | if found. The first difference determines the key order.
>> `
>>
>> Does "value by value" here mean that before comparison takes place, the
>> key must be split apart into values, and then each pairwise value from
>> each of the two keys can be compared with one call to memcmp() for each
>> pair of values, or does "value by value" mean simply that the
>> concatenated values' bytes will be compared from left to right, with one
>> call to memcmp() for the entire key?
>>
>
> It doesn't matter. The whole point is that the key is constructed in such
> a way that both procedures would arrive at the same result.
>

Exactly.

"Value by value" means conceptually what happens.  The actual
implementation is a single memcmp() since that is so much faster.


>  --
> Igor Tandetnik
>
>
> __**_
> 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] Consequences of lexicographic sorting of keys in SQLite4?

[Igor Tandetnik]

On 7/3/2012 3:50 PM, Steven E. Harris wrote:

The first paragraph mentions that the encoding allows comparison of keys
with memcmp(), which makes it sound like an entire key -- meaning the
concatenation of several values -- can be be compared in one operation
against another key.

The second paragraph notes:

,
| Keys are compared value by value, from left to right, until a difference
| if found. The first difference determines the key order.
`

Does "value by value" here mean that before comparison takes place, the
key must be split apart into values, and then each pairwise value from
each of the two keys can be compared with one call to memcmp() for each
pair of values, or does "value by value" mean simply that the
concatenated values' bytes will be compared from left to right, with one
call to memcmp() for the entire key?


It doesn't matter. The whole point is that the key is constructed in 
such a way that both procedures would arrive at the same result.

--
Igor Tandetnik

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Steven E. Harris]

Richard Hipp  writes:

> The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way
> that causes a lexicographical ordering of the keys to correspond to
> what the user wants out of ORDER BY.

The first paragraph mentions that the encoding allows comparison of keys
with memcmp(), which makes it sound like an entire key -- meaning the
concatenation of several values -- can be be compared in one operation
against another key.

The second paragraph notes:

,
| Keys are compared value by value, from left to right, until a difference
| if found. The first difference determines the key order.
`

Does "value by value" here mean that before comparison takes place, the
key must be split apart into values, and then each pairwise value from
each of the two keys can be compared with one call to memcmp() for each
pair of values, or does "value by value" mean simply that the
concatenated values' bytes will be compared from left to right, with one
call to memcmp() for the entire key?

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Steven E. Harris]

Richard Hipp  writes:

> The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way
> that causes a lexicographical ordering of the keys to correspond to
> what the user wants out of ORDER BY.

I don't understand why the example entries for values 99.0, 99.01, and
99.0001 have first bytes of 0xb4 and 0xb5, respectively.

If we take 99 and use it as "X" in the "2*X+0" formula, shouldn't we
wind up with 198, or 0xC6? Likewise, for the second two examples, I'd
expect 2*99+1 to yield 199, or 0xC7. (The later entry for  has bytes
0xC7 and 0xC6, which match my expectation.)

One more nit: In the paragraph beginning with "If the numeric value is
exactly zero," there's an extra "then" which should have been "the"
instead:

  s/then then/then the/

Thank you for documenting all of this. It's ugly for a good reason,
which makes it beautiful at the same time.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Steven E. Harris]

Richard Hipp  writes:

> The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way
> that causes a lexicographical ordering of the keys to correspond to
> what the user wants out of ORDER BY.

I don't understand why the example entries for values 99.0, 99.01, and
99.0001 have first bytes of 0xb4 and 0xb5, respectively.

If we take 99 and use it as "X" in the "2*X+0" formula, shouldn't we
wind up with 198, or 0xC6? Likewise, for the second two examples, I'd
expect 2*99+1 to yield 199, or 0xC7. (The later entry for  has bytes
0xC7 and 0xC6, which match my expectation.)

One more nit: In the paragraph beginning with "If the numeric value is
exactly zero," there's an extra "then" which should have been "the"
instead:

  s/then then/then the/

Thank you for documenting all of this. It's ugly for a good reason,
which makes it beautiful at the same time.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Steven E. Harris]

Richard Hipp  writes:

> The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way
> that causes a lexicographical ordering of the keys to correspond to
> what the user wants out of ORDER BY.

I don't understand why the example entries for values 99.0, 99.01, and
99.0001 have first bytes of 0xb4 and 0xb5, respectively.

If we take 99 and use it as "X" in the "2*X+0" formula, shouldn't we
wind up with 198, or 0xC6? Likewise, for the second two examples, I'd
expect 2*99+1 to yield 199, or 0xC7. (The later entry for  has bytes
0xC7 and 0xC6, which match my expectation.)

One more nit: In the paragraph beginning with "If the numeric value is
exactly zero," there's an extra "then" which should have been "the"
instead:

  s/then then/then the/

Thank you for documenting all of this. It's ugly for a good reason,
which makes it beautiful at the same time.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Cory Nelson]

On Fri, Jun 29, 2012 at 5:58 PM, Richard Hipp  wrote:
>
> On Fri, Jun 29, 2012 at 6:40 PM, Nico Williams wrote:
>
> > On Fri, Jun 29, 2012 at 5:24 PM, Richard Hipp  wrote:
> > > varint+value does not sort BLOBs in lexicographical order.
> > >
> > > Not having a distinct terminator for the BLOB means that two BLOBs where
> > > one is a prefix of the other might not compare correctly.
> >
> > Would 31-bit encoding help?
> >
>
> Maybe.
>
> But you know:  How often do people use BLOBs as keys?  What other SQL
> engines other than SQLite even allow BLOBs as keys?  Are we trying to
> optimize something that is never actually used?
>

128-bit GUIDs as a primary key are very common in cases where records
are to be synced between two (often disconnected) databases.
Admittedly 3 bytes of overhead in this case is probably not going to
be a huge deal, but if a 19% overhead can be avoided early in the
design, why not?

Okay. I'm done bike shedding ;)

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Niall O'Reilly]

On 2 Jul 2012, at 18:20, Jay A. Kreibich wrote:

>  The idea of using a plugin system to expand database functionality
>  seems to fit well with the SQLite way of getting things done.
>  Functions, collations, and virtual tables are already done in a
>  similar way.  Extending that to types seems like a natural thing.

Indeed.

>  You can, of course, use a user-defined function that just converts a
>  string to a BLOB of some type.  As long as you use the encoder function
>  for inputs and the decoder for all outputs, you should be good.

Functionally, although involving more overhead, a collation
is enough.  The combination of encoder and decoder obviates
repeated references to the collation function for ORDER BY,
BETWEEN, and so on.

>  That
>  starts to get deep into your SQL, however.  The ability to define
>  native types is similar in complexity to adding user-defined
>  functions.
> 
>  Just a thought.  Any opinions?

/Niall

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Jay A. Kreibich]

On Mon, Jul 02, 2012 at 10:13:13AM -0500, Nico Williams scratched on the wall:

> That reminds me: it'd be nice to have a bit string type, since the
> correct way to sort IPv4 CIDR blocks is as bit strings.  This is also
> a proper way to sort IPv6 blocks.  Alternatively, it'd be nice to have
> native IP address types in SQLite4, as otherwise one has to jump
> through hoops to handle IP addresses properly.


  I'd suggest something bigger, as long as we're putting a lot of
  options on the table.

  Postgres supports user-defined types on the server side.  This is now
  most of their slightly esoteric types (such as CIDR addresses) are
  supported internally.  To define a type, the server developer writes a
  server-side plugin that provides a few functions to the server.
  Required functions convert the in-memory representation of the type
  to/from strings (for SQL input/output) and also convert the in-memory
  representation to/from a bit stream for storing on disk.  I think you
  can also provide a sort function.

http://www.postgresql.org/docs/9.0/static/xtypes.html

  The idea of using a plugin system to expand database functionality
  seems to fit well with the SQLite way of getting things done.
  Functions, collations, and virtual tables are already done in a
  similar way.  Extending that to types seems like a natural thing.

  You can, of course, use a user-defined function that just converts a
  string to a BLOB of some type.  As long as you use the encoder function
  for inputs and the decoder for all outputs, you should be good.  That
  starts to get deep into your SQL, however.  The ability to define
  native types is similar in complexity to adding user-defined
  functions.

  Just a thought.  Any opinions?

   -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] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

On Mon, Jul 2, 2012 at 4:29 AM, Niall O'Reilly  wrote:
>
> On 29 Jun 2012, at 23:58, Richard Hipp wrote:
>
>> But you know:  How often do people use BLOBs as keys?  What other SQL
>> engines other than SQLite even allow BLOBs as keys?  Are we trying to
>> optimize something that is never actually used?
>
> For an IPAM application I have on my back burner, BLOB seems
> a natural way to express IPv[46] addresses, ranges, and prefixes.
> A bulkier alternative would be hexadecimal encoding as text.

That reminds me: it'd be nice to have a bit string type, since the
correct way to sort IPv4 CIDR blocks is as bit strings.  This is also
a proper way to sort IPv6 blocks.  Alternatively, it'd be nice to have
native IP address types in SQLite4, as otherwise one has to jump
through hoops to handle IP addresses properly.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Simon Slavin]

On 2 Jul 2012, at 10:29am, Niall O'Reilly  wrote:

> On 29 Jun 2012, at 23:58, Richard Hipp wrote:
> 
>> But you know:  How often do people use BLOBs as keys?  What other SQL
>> engines other than SQLite even allow BLOBs as keys?  Are we trying to
>> optimize something that is never actually used?
> 
>   For an IPAM application I have on my back burner, BLOB seems
>   a natural way to express IPv[46] addresses, ranges, and prefixes.
>   A bulkier alternative would be hexadecimal encoding as text.

Strikes me as premature optimisation.  Storing them as strings of decimal or 
hex (with, of course, leading zeros) would allow you to sort them meaningfully, 
take substrings meaningfully, and to understand the contents of your file when 
displayed using debugging tools.  If you do that, and the results turn out to 
be too slow for your user(s), /then/ revisit ideas of making things faster or 
more compact.

Worth remembering that BLOBs don't have a well-ordering function.  You can 
compare two BLOBs and tell whether they're the same (usually, but lossless 
encoding defeats this), but if they're not the same you can't put one 'before' 
the other.

This is because BLOBs are essentially black boxes.  You have no idea what the 
data represents.  If you know what it represented, you'd probably be storing it 
as text or a number.  Think of storing images as BLOBs.  How do you compare two 
images ?  Is one before another because it is smaller ?  Or because it contains 
darker pixels (lower brightness) ?  Or because the EXIF information says it was 
taken on an earlier date ?  Or because it's an earlier frame in the animation 
you're making ?

So if a function like building an index requires an ordering function, you 
can't use it on a BLOB.  Now, as it happens, BLOBs are stored as octets, and if 
the functionality is presented there's no harm in sorting them as if they're 
octet-streams.  But it doesn't really mean anything.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Niall O'Reilly]

On 2 Jul 2012, at 10:51, Dan Kennedy wrote:

> That would be a reasonable use. But the blob in this case will be what,
> eight bytes (or 10 in its encoded form)?

10, 18, 34, or 66, depending on which of six classes [*] of object
is involved, using the encoding I have in mind at the moment.
Still small.

* 2x address families, 3x kinds of object (address, prefix, range).

/Niall

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Dan Kennedy]

On 07/02/2012 04:29 PM, Niall O'Reilly wrote:


On 29 Jun 2012, at 23:58, Richard Hipp wrote:


But you know:  How often do people use BLOBs as keys?  What other SQL
engines other than SQLite even allow BLOBs as keys?  Are we trying to
optimize something that is never actually used?


For an IPAM application I have on my back burner, BLOB seems
a natural way to express IPv[46] addresses, ranges, and prefixes.
A bulkier alternative would be hexadecimal encoding as text.


That would be a reasonable use. But the blob in this case will be what,
eight bytes (or 10 in its encoded form)? So the encoding and decoding
(it's actually not clear we will ever want to decode, but anyhow) isn't
going to cost much in the way of CPU. And making the keys memcmp()
compatible allows some other optimizations - prefix compression and so
on. Plus I think memcmp() will be generally faster than any other
type of comparison.

Creating and using an index on larger blobs might be different of
course.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Niall O'Reilly]

On 29 Jun 2012, at 23:58, Richard Hipp wrote:

> But you know:  How often do people use BLOBs as keys?  What other SQL
> engines other than SQLite even allow BLOBs as keys?  Are we trying to
> optimize something that is never actually used?

For an IPAM application I have on my back burner, BLOB seems
a natural way to express IPv[46] addresses, ranges, and prefixes.
A bulkier alternative would be hexadecimal encoding as text.

/Niall

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

OK, I give :)
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Richard Hipp]

On Fri, Jun 29, 2012 at 6:40 PM, Nico Williams wrote:

> On Fri, Jun 29, 2012 at 5:24 PM, Richard Hipp  wrote:
> > varint+value does not sort BLOBs in lexicographical order.
> >
> > Not having a distinct terminator for the BLOB means that two BLOBs where
> > one is a prefix of the other might not compare correctly.
>
> Would 31-bit encoding help?
>

Maybe.

But you know:  How often do people use BLOBs as keys?  What other SQL
engines other than SQLite even allow BLOBs as keys?  Are we trying to
optimize something that is never actually used?

Note that the data
encodingfor
BLOBs (used in the overwhelmingly common case of when the BLOB is not
the key) does have a simple size+content format.


> ___
> 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] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

On Fri, Jun 29, 2012 at 5:24 PM, Richard Hipp  wrote:
> varint+value does not sort BLOBs in lexicographical order.
>
> Not having a distinct terminator for the BLOB means that two BLOBs where
> one is a prefix of the other might not compare correctly.

Would 31-bit encoding help?
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Richard Hipp]

On Fri, Jun 29, 2012 at 6:09 PM, Nico Williams wrote:

> On Fri, Jun 29, 2012 at 4:39 PM, Cory Nelson  wrote:
> > On Fri, Jun 29, 2012 at 2:48 PM, Richard Hipp  wrote:
> > What is the rationale for the 7-bit BINARY encoding? The performance
> impact
> > will surely outweigh any convenience of being able to treat blobs as
> > 0-terminated strings.
>
> I tend to agree.  Varint length + value should be faster,


varint+value does not sort BLOBs in lexicographical order.

Not having a distinct terminator for the BLOB means that two BLOBs where
one is a prefix of the other might not compare correctly.




> though this
> just needs to be measured, and it's likely that the 7-bit approach
> will be faster for very short blobs.  Another possibility would be to
> use 31-bit encoding ;)  or escape zero-bytes, and so on.
>
> Nico
> --
> ___
> 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] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

On Fri, Jun 29, 2012 at 4:39 PM, Cory Nelson  wrote:
> On Fri, Jun 29, 2012 at 2:48 PM, Richard Hipp  wrote:
> What is the rationale for the 7-bit BINARY encoding? The performance impact
> will surely outweigh any convenience of being able to treat blobs as
> 0-terminated strings.

I tend to agree.  Varint length + value should be faster, though this
just needs to be measured, and it's likely that the 7-bit approach
will be faster for very short blobs.  Another possibility would be to
use 31-bit encoding ;)  or escape zero-bytes, and so on.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Cory Nelson]

On Fri, Jun 29, 2012 at 2:48 PM, Richard Hipp  wrote:

> On Fri, Jun 29, 2012 at 3:40 PM, Nico Williams  >wrote:
>
> > So, if I understand section 3.2 of the SQLite4 design page then it
> > will often be the case that lookup keys will not be stored in an order
> > that will be useful for optimizing common ORDER BY expressions.  Is
> > this correct?
>
>
> Not correct.  The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way that
> causes a lexicographical ordering of the keys to correspond to what the
> user wants out of ORDER BY.  So indices can still be used for fulfilling
> ORDER BY.
>

What is the rationale for the 7-bit BINARY encoding? The performance impact
will surely outweigh any convenience of being able to treat blobs as
0-terminated strings.

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

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

On Fri, Jun 29, 2012 at 2:48 PM, Richard Hipp  wrote:
> On Fri, Jun 29, 2012 at 3:40 PM, Nico Williams wrote:
>> So, if I understand section 3.2 of the SQLite4 design page then it
>> will often be the case that lookup keys will not be stored in an order
>> that will be useful for optimizing common ORDER BY expressions.  Is
>> this correct?
>
>
> Not correct.  The keys are encoded (see
> http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way that
> causes a lexicographical ordering of the keys to correspond to what the
> user wants out of ORDER BY.  So indices can still be used for fulfilling
> ORDER BY.

Ah, I hadn't seen that.  That's very clever.

>>  If so, is this worth the trade-off for the single
>> key/value storage complexity?  Or is this wrong because the key
>> comparison function to be used will be aware of of data typing in the
>> encoding of the keys?
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Consequences of lexicographic sorting of keys in SQLite4?

[Richard Hipp]

On Fri, Jun 29, 2012 at 3:40 PM, Nico Williams wrote:

> So, if I understand section 3.2 of the SQLite4 design page then it
> will often be the case that lookup keys will not be stored in an order
> that will be useful for optimizing common ORDER BY expressions.  Is
> this correct?


Not correct.  The keys are encoded (see
http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki) in a way that
causes a lexicographical ordering of the keys to correspond to what the
user wants out of ORDER BY.  So indices can still be used for fulfilling
ORDER BY.



>  If so, is this worth the trade-off for the single
> key/value storage complexity?  Or is this wrong because the key
> comparison function to be used will be aware of of data typing in the
> encoding of the keys?
>
> Nico
> --
> ___
> 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] Consequences of lexicographic sorting of keys in SQLite4?

[Nico Williams]

So, if I understand section 3.2 of the SQLite4 design page then it
will often be the case that lookup keys will not be stored in an order
that will be useful for optimizing common ORDER BY expressions.  Is
this correct?  If so, is this worth the trade-off for the single
key/value storage complexity?  Or is this wrong because the key
comparison function to be used will be aware of of data typing in the
encoding of the keys?

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