You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-user@db.apache.org by Daniel Noll <da...@nuix.com> on 2009/08/04 08:30:03 UTC
Filtering using the sort order on two columns
Hi all.
I have a table and index like this:
CREATE TABLE Terms (
id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY NOT NULL,
field VARCHAR(255) NOT NULL,
text VARCHAR(255) NOT NULL,
docfreq INTEGER NOT NULL
)
CREATE INDEX TermsFieldAndText ON Terms (field, text)
Here's some example data. Table is shown in sorted order as it would
be listed in the index above:
| field | text | docfreq |
----------------------------------------
| body | hello | 10 |
| tag | home | 100 |
| tag | work | 80 |
For a given input term (let's say tag:home) I want to find the _next_
entry in the table (so it should return tag:work). My naive
implementation does this:
SELECT field, text, docfreq
FROM Terms
WHERE (field = ? AND text > ?) OR field > ?
ORDER BY field ASC, text ASC
This does the right thing as far as the output is concerned, but Derby
does a table scan. Looking at the query, my impression would be that
in the worse case scenario, Derby should do two index scans. Or, if
it's smart, one index scan.
I'm aware that I might be able to work around this by having instead a
field with the concatenation of both fields with
CONCAT(field,'\0',text). But I wanted to check first whether there is
a way I can maintain my relatively understandable table structure
before resorting to hacks. Basically I just need the data in index
order, starting from a given point... so I figure there is a simple
solution.
Daniel
--
Daniel Noll Forensic and eDiscovery Software
Senior Developer The world's most advanced
Nuix email data analysis
http://nuix.com/ and eDiscovery software
Re: Filtering using the sort order on two columns
Posted by Daniel Noll <da...@nuix.com>.
On Wed, Aug 5, 2009 at 14:54, Bryan Pendleton<bp...@amberpoint.com> wrote:
> Great!
>
> Can you construct a UNION of the two queries, and then ORDER BY the UNION?
>
> And, in that case, does it use the index for both the union-ed subqueries?
This is the first time I've used UNION, but I tried this:
SELECT id, field, text, docfreq FROM Terms
WHERE field = ? AND text > ?
UNION ALL
SELECT id, field, text, docfreq FROM Terms
WHERE field > ?
ORDER BY field ASC, text ASC
And yes, it is still doing two separate index scans in this situation,
but code-wise it's far superior to doing each query separately as I
don't need to keep track of how many items I got from the first query.
The performance is basically identical.
Daniel
--
Daniel Noll Forensic and eDiscovery Software
Senior Developer The world's most advanced
Nuix email data analysis
http://nuix.com/ and eDiscovery software
Re: Filtering using the sort order on two columns
Posted by Bryan Pendleton <bp...@amberpoint.com>.
>> SELECT field, text, docfreq FROM Terms
>> WHERE field > ?
>> ORDER BY field ASC, text ASC
>>
>> SELECT field, text, docfreq FROM Terms
>> WHERE (field = ? AND text > ?)
>> ORDER BY field ASC, text ASC
>>
>> Does each query, separately, use the index as you expect?
>
> Indeed, both of these queries (even the one with only >) do an index
> scan instead of a table scan.
Great!
Can you construct a UNION of the two queries, and then ORDER BY the UNION?
And, in that case, does it use the index for both the union-ed subqueries?
thanks,
bryan
Re: Filtering using the sort order on two columns
Posted by Daniel Noll <da...@nuix.com>.
On Wed, Aug 5, 2009 at 00:16, Bryan Pendleton<bp...@amberpoint.com> wrote:
>
> What happens if you do two separate queries:
>
> SELECT field, text, docfreq FROM Terms
> WHERE field > ?
> ORDER BY field ASC, text ASC
>
> SELECT field, text, docfreq FROM Terms
> WHERE (field = ? AND text > ?)
> ORDER BY field ASC, text ASC
>
> Sometimes the "OR" will really throw off the optimizer.
>
> Does each query, separately, use the index as you expect?
Indeed, both of these queries (even the one with only >) do an index
scan instead of a table scan. I think you're right; the optimiser
sees the OR and goes "oops, this condition is too hard", because it
doesn't know that the two ranges are adjacent (which would be hard to
detect, I'm guessing) and then proceeds to use the table scan instead.
I am considering using two separate queries as a workaround. I can
look in the same field and then if that returns nothing, look for the
next field. As far as caching goes, yes... I want to do that, but I
aimed for correctness first. I can't cache *all* entries because
there might be an extremely large number, but I can at least cache
some 100 or 1,000 and then avoid the next 99 queries.
The generated column idea offered by Rick isn't bad either, but it
will double storage requirements versus doing the concatenation
manually, or versus this trick.
Daniel
--
Daniel Noll Forensic and eDiscovery Software
Senior Developer The world's most advanced
Nuix email data analysis
http://nuix.com/ and eDiscovery software
Re: Filtering using the sort order on two columns
Posted by Bryan Pendleton <bp...@amberpoint.com>.
Daniel Noll wrote:
> SELECT field, text, docfreq
> FROM Terms
> WHERE (field = ? AND text > ?) OR field > ?
> ORDER BY field ASC, text ASC
>
> This does the right thing as far as the output is concerned, but Derby
> does a table scan.
What happens if you do two separate queries:
SELECT field, text, docfreq FROM Terms
WHERE field > ?
ORDER BY field ASC, text ASC
SELECT field, text, docfreq FROM Terms
WHERE (field = ? AND text > ?)
ORDER BY field ASC, text ASC
Sometimes the "OR" will really throw off the optimizer.
Does each query, separately, use the index as you expect?
thanks,
bryan
Re: Filtering using the sort order on two columns
Posted by Rick Hillegas <Ri...@Sun.COM>.
Hi Daniel,
Here are two issues which might drive the optimizer to select a table scan:
1) The optimizer may see the OR as an unoptimizable condition. I think
Bryan referred to this.
2) The index does not cover the query, that is, it does not contain all
columns needed to evaluate the query.
A variation of your concatenation solution could involve a generated
column and a covering index involving that column. This would at least
let you preserve the more readable structure of your table for other
queries. Something like the following might work:
connect 'jdbc:derby:memory:temp;create=true';
CREATE TABLE Terms (
id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY NOT NULL,
field VARCHAR(255) NOT NULL,
text VARCHAR(255) NOT NULL,
docfreq INTEGER NOT NULL,
fieldtext generated always as ( field || ':' || text )
);
CREATE INDEX TermsFieldAndText ON Terms (fieldtext, docfreq);
-- just for show. this does not create enough data to justify
-- using an index
insert into Terms ( field, text, docfreq )
values ( 'body', 'hello', 3 ), ( 'tag', 'home', 2 ), ( 'tag', 'work', 4
), ( 'zzz', 'abc', 1 );
select substr( fieldtext, 1, locate( ':', fieldtext ) - 1 ), substr(
fieldtext, locate( ':', fieldtext ) + 1 ), docfreq
from Terms
where fieldtext > 'tag:home'
fetch first row only;
Hope this helps,
-Rick
Daniel Noll wrote:
> Hi all.
>
> I have a table and index like this:
>
> CREATE TABLE Terms (
> id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY NOT NULL,
> field VARCHAR(255) NOT NULL,
> text VARCHAR(255) NOT NULL,
> docfreq INTEGER NOT NULL
> )
>
> CREATE INDEX TermsFieldAndText ON Terms (field, text)
>
> Here's some example data. Table is shown in sorted order as it would
> be listed in the index above:
>
> | field | text | docfreq |
> ----------------------------------------
> | body | hello | 10 |
> | tag | home | 100 |
> | tag | work | 80 |
>
> For a given input term (let's say tag:home) I want to find the _next_
> entry in the table (so it should return tag:work). My naive
> implementation does this:
>
> SELECT field, text, docfreq
> FROM Terms
> WHERE (field = ? AND text > ?) OR field > ?
> ORDER BY field ASC, text ASC
>
> This does the right thing as far as the output is concerned, but Derby
> does a table scan. Looking at the query, my impression would be that
> in the worse case scenario, Derby should do two index scans. Or, if
> it's smart, one index scan.
>
> I'm aware that I might be able to work around this by having instead a
> field with the concatenation of both fields with
> CONCAT(field,'\0',text). But I wanted to check first whether there is
> a way I can maintain my relatively understandable table structure
> before resorting to hacks. Basically I just need the data in index
> order, starting from a given point... so I figure there is a simple
> solution.
>
> Daniel
>
>
> --
> Daniel Noll Forensic and eDiscovery Software
> Senior Developer The world's most advanced
> Nuix email data analysis
> http://nuix.com/ and eDiscovery software
>
Re: Filtering using the sort order on two columns
Posted by Brett Wooldridge <br...@gmail.com>.
Educated guess, but I think an index scan will not be used because the
predicate provides no "stop condition". See "What's Optimizable?" here:
http://db.apache.org/derby/docs/10.0/manuals/tuning/perf43.html
*Possibly* can you force the use of an index by overriding the optimizer:
http://db.apache.org/derby/docs/10.5/tuning/ctunoptimzoverride.html
>From the first document:
"Sometimes a table scan is the most efficient way to access data, even if a
potentially useful index is available. For example, if the statement returns
virtually all the data in the table, it is more efficient to go straight to
the table instead of looking values up in an index, because then Derby is
able to avoid the intermediate step of retrieving the rows from the index
lookup values."
The trouble is, because your query is open-ended (using > with no <), Derby
doesn't know how many rows will be returned ... maybe it's the entire table
... in which case a table-scan is more efficient. You *might* also try
using ROW_NUMBER() to limit the query and maybe trick the optimizer (search
the FAQ for LIMIT), but somehow I don't think the optimizer is that smart.
Any reason not to cache the result of the first query, and manually step
through the results rather than constantly re-running a query to get the
"next" row?
-Brett
On Tue, Aug 4, 2009 at 3:30 PM, Daniel Noll <da...@nuix.com> wrote:
> Hi all.
>
> I have a table and index like this:
>
> CREATE TABLE Terms (
> id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY NOT NULL,
> field VARCHAR(255) NOT NULL,
> text VARCHAR(255) NOT NULL,
> docfreq INTEGER NOT NULL
> )
>
> CREATE INDEX TermsFieldAndText ON Terms (field, text)
>
> Here's some example data. Table is shown in sorted order as it would
> be listed in the index above:
>
> | field | text | docfreq |
> ----------------------------------------
> | body | hello | 10 |
> | tag | home | 100 |
> | tag | work | 80 |
>
> For a given input term (let's say tag:home) I want to find the _next_
> entry in the table (so it should return tag:work). My naive
> implementation does this:
>
> SELECT field, text, docfreq
> FROM Terms
> WHERE (field = ? AND text > ?) OR field > ?
> ORDER BY field ASC, text ASC
>
> This does the right thing as far as the output is concerned, but Derby
> does a table scan. Looking at the query, my impression would be that
> in the worse case scenario, Derby should do two index scans. Or, if
> it's smart, one index scan.
>
> I'm aware that I might be able to work around this by having instead a
> field with the concatenation of both fields with
> CONCAT(field,'\0',text). But I wanted to check first whether there is
> a way I can maintain my relatively understandable table structure
> before resorting to hacks. Basically I just need the data in index
> order, starting from a given point... so I figure there is a simple
> solution.
>
> Daniel
>
>
> --
> Daniel Noll Forensic and eDiscovery Software
> Senior Developer The world's most advanced
> Nuix email data analysis
> http://nuix.com/ and eDiscovery software
>