Re: SQL query plan question

In article <44b7ce87$0$6033$9a6e19ea@xxxxxxxxxxxxxxxxxxxx>, Chris wrote:
Suppose we have a very large table in a SQL database, and want to
execute this query:

select *
from table
where price > 10.00
order by name

Assume that both price and name are high-cardinality columns, that is,
there is a very large number of unique values in each column.

Suppose that we have an index on price, and an index on name, but we do
*not* have an index on price + name.

Is there any query plan that can evaluate this query efficiently? I'm
not seeing one, but I really hope that there is. From what I see, if we
start by traversing the name index, we'll have to do a full table scan.
If we traverse the price index, then we'll have to accumulate all the
names and do a brute-force sort.

Well, sorting with a decent algorithm is only O(n log n), thus not too
bad even for fairly large n.

Here's one other little twist: we do not have to return the entire
result set, only the first 10 records.

I don't know about SQL, but in general, finding the k largest (for a
constant k) elements from a list of n elements can be done in O(n)
without sorting.

Bye,

Stephan

--
-------------------------- It can be done! ---------------------------------
Please email me as schulz@xxxxxxxxxxx (Stephan Schulz)
----------------------------------------------------------------------------
.

Relevant Pages

  • Re: A Question of Tables
    ... Without getting into your specific query, ... > price (which should be in the STOCKPRICES table) with this exchange rate. ... > selected lang and currency, ...
    (microsoft.public.sqlserver.programming)
  • Re: Need help with expression on a query
    ... The code create a form in a webpage and the query is to update the data on ... Part, Description, Price, and Code columns. ... >> In the Form Button Memo I have the following code: ...
    (microsoft.public.access.queries)
  • Re: Adding a new parent key for a new child record on a subform
    ... The above query will make it impossible to display or enter OrderItems ... Private Sub Form_BeforeInsert ... vendor, simple enough. ... latest price and insert it as this order-line-items new price: ...
    (microsoft.public.access.forms)
  • Re: adding a text string to data from one field in one database to another
    ... After running the other create table query, ... I have items with price breaks a various quantity levels each ... Qty price at that qty price for that qty ... In the database the data needs to be entered into a field (not ...
    (comp.databases.ms-access)
  • Re: pricing formulas
    ... Partnumber, Description, and Cost and build some expressions in query design ... You can also compare your current retail price to the "formula price" ...
    (microsoft.public.access.forms)