SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Old Forums
 CLOSED - General SQL Server
 Algorithm
 Forum Locked
 Printer Friendly
Previous Page | Next Page
Author Previous Topic Topic Next Topic
Page: of 4

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 07/05/2006 :  13:48:29  Show Profile
select	A.*
from	YourTable A
	inner join YourTable B on A.Pkey = B.Pkey
	inner join YourTable C on A.PKey = B.Pkey
where	(A.COL1 = @Col1
	or A.COL2 = @Col1
	or A.COL3 = @Col1
	or A.COL4 = @Col1
	or A.COL5 = @Col1
	or A.COL6 = @Col1
	or A.COL7 = @Col1
	or A.COL8 = @Col1)
	and
	(B.COL1 = @Col2
	or B.COL2 = @Col2
	or B.COL3 = @Col2
	or B.COL4 = @Col2
	or B.COL5 = @Col2
	or B.COL6 = @Col2
	or B.COL7 = @Col2
	or B.COL8 = @Col2)
	and
	(C.COL1 = @Col3
	or C.COL2 = @Col3
	or C.COL3 = @Col3
	or C.COL4 = @Col3
	or C.COL5 = @Col3
	or C.COL6 = @Col3
	or C.COL7 = @Col3
	or C.COL8 = @Col3)
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/05/2006 :  14:09:56  Show Profile  Visit SwePeso's Homepage
Sorry Sir, this is not good enough. Even if I change
	inner join YourTable B on A.Pkey = B.Pkey
	inner join YourTable C on A.PKey = B.Pkey
to
	inner join YourTable B on A.Pkey = B.Pkey
	inner join YourTable C on A.PKey = C.Pkey
the code does not work. Consider this test data
select 1, 2, 3 union all
select 2, 1, 3 union all
select 3, 2, 1 union all
select 1, 5, 6 union all
select 6, 6, 4
and these search values
select @col1 = 1, @col2 = 1, @col3 = 2
your code fetches following rows
0	1	2	3
1	2	1	3
2	3	2	1
But your code is elegant though.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/05/2006 14:14:16
Go to Top of Page

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 07/05/2006 :  15:19:34  Show Profile
Sorry sir, but nowhere does the poster indicate whether duplicate search keys can be requested, or what results should be returned under such circumstances. You are making assumptions.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/05/2006 :  15:28:16  Show Profile  Visit SwePeso's Homepage
Well Blindman, actually he did. Consider his original test data
quote:
I have a table with description of some connections.
CON1, CON2, CON3... CON8 (I will assume I have CON1-CON3 in example)
1,2,3
2,1,3
3,2,1
1,5,6
6,6,4
Then he writes about what he is searching for
quote:
If the user search for connection 3, 2, 1 I should return following rows
1,2,3
2,1,3
3,2,1

3,2,1 is the same with combination of all 3
With your assumption that not all search values should be treated uniquelly, he would also have posted that row with
1,5,6
should be fetched since the 1's match with your logic.

But he doesn't.

But hey, I'm Swedish (non-american), so I might be wrong since I don't speak, write and read english natively. Neither does Zurbum (I think), as he is Norwegian.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/05/2006 16:05:08
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 07/05/2006 :  15:35:09  Show Profile  Visit jsmith8858's Homepage
The person asking this question needs to specify the actual schema for the table in question. It is bad enough that it is not normalized, but if the table doesn't contain an actual PK then any solution we give is completely worthless since the data itself is worthless.

So -- Is there an actual PK to this table? If so, what is it? If *not*, then come back to us once you add one in. Even an identity at least!

Once the PK is in place, a simple query that "fake" normalizes the data (I believe Corey gave one earlier) and then does the simple GROUP BY/ COUNT(*) is the way to go.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/05/2006 :  15:52:32  Show Profile  Visit SwePeso's Homepage
Yes, the query Corey wrote is elegant and easy to maintain, in spite of the fact that the table is not normalized.

I speak of self-interest here since the code I copied and pasted is used in one of my solutions from a customer I have. Now I intend to replace my old ugly hack with the query Corey presented, as it is 3 times faster too, tested on a production environment with 1.7 million rows. Before 1.5 seconds and now 0.5 seconds.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/05/2006 15:56:11
Go to Top of Page

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 07/05/2006 :  16:27:03  Show Profile
Actually, he didn't. And you are assuming that if duplicate search terms are entered he only wants records where the search term appears twice, not once. We know nothing about his data, and whether values are unique within a record. You are making assumptions which may or may not be correct, but they are still assumptions.
As jsmith8858 said, we would need more details before coming up with any solution, let alone the optimal solution.
Go to Top of Page

DustinMichaels
Constraint Violating Yak Guru

464 Posts

Posted - 07/05/2006 :  16:59:25  Show Profile
Are 1,2,3 and 2,1,3 and 3,2,1 all equivalent pieces of information?

If it is maybe you could update your table storing the lowest value of each row in CON1, the second lowest in CON2, and the highest value in CON3.

Then when the user searches for a connection you could order the connection string in ascending order (so if they typed in 3, 2, 1 you sort it and it becomes 1, 2, 3) and then your where clause can be.

WHERE Lowest Input Value = CON1 AND 2nd Lowest Input Value = CON2 AND Highest Input Value = CON3.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/05/2006 :  17:24:05  Show Profile  Visit SwePeso's Homepage
quote:
Originally posted by DustinMichaels

Are 1,2,3 and 2,1,3 and 3,2,1 all equivalent pieces of information?
No, I don't think so. In the system I made some coding, the columns are the "ranks". User 1 has option 3 at column 1 (highest rank), option 1 at column 2 (second highest rank) and so on. But the task I was given, were to find all users having the same options regardless of rank, in a report.
I don't know the purpose of having the DDL as Zurbum has.

I will be the first to apologize if I have made the wrong assumption about the original intent. I am not afraid to do so.

Some times I learn a new way of thinking when I participate in the SQL Team forums, as in this case.

But I still think I am right about this topic. Why?

Because Zurbum's own attempt to a solution were
SELECT COL1,COL2,COL3 FROM
(SELECT COL1, COL2,COL3, COL1+COL2+COL3 AS COL_SUM, COL1*COL2*COL3 AS COL_MUL FROM TABLE_X) AS TEMP
WHERE TEMP.COL_SUM=INPUT1+INPUT2+INPUT3 AND TEMP.COL_MUL=INPUT1*INPUT2*INPUT3
In his scenario (he wrote Yees, there must be always 3 search numbers. Also the numbers are >0.), the three values matching the three search terms have to be unique.
He missed only a few combinations as I pointed out with simple statistics.

A table row of 1, 2, 4 does not meet the criteria he self made with search terms 1, 1, 7.
And also a table row of 1, 3, 3 does not meet his own critera with search terms 1, 3, 1.
My hack and Corey's query both filters out the same rows and the special cases (pointed out by me) derived from Zurbum's logic. Blindman's algorithm doesn't.

Do you still call my opinion for assumptions, Blindman?


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/05/2006 19:12:20
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

USA
7020 Posts

Posted - 07/05/2006 :  18:52:45  Show Profile
There seems to be lots of opinions about what the original poster actually wanted. I don't think he really explained it that well, but I just can't resist adding to the confusion.

My guess at what he wants is: he wants rows that contain all of the three search values, anywhere in columns COL1 to COL8 in any order. Feel free to flame away.

The code below does the search of 1,000,000 rows in about 1 second.

-- Search params
declare @c1 int
declare @c2 int
declare @c3 int

-- Set Search params
select @c1 = 1 , @c2 = 4, @c3 = 7

declare @test table (
id int not null  primary key clustered,
con1 int,
con2 int,
con3 int,
con4 int,
con5 int,
con6 int,
con7 int,
con8 int)



print 'Load 1000000 rows of test data starting at '+
	convert(varchar(30),getdate(),121)
insert into @test
select
	a.number,
	-- random numbers from 0 to 99
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 ,
	abs(convert(int,convert(varbinary(20),newid())))%100 

from
	F_TABLE_NUMBER_RANGE(1,1000000) a
order by
	a.number

print 'Search for matching rows starting at '+
	convert(varchar(30),getdate(),121)

select
	[Matches]= count(*)
from
	@test a
where
	@c1 in (a.con1,a.con2,a.con3,a.con4,a.con5,a.con6,a.con7,a.con8) and
	@c2 in (a.con1,a.con2,a.con3,a.con4,a.con5,a.con6,a.con7,a.con8) and
	@c3 in (a.con1,a.con2,a.con3,a.con4,a.con5,a.con6,a.con7,a.con8)

print 'Done at '+
	convert(varchar(30),getdate(),121)

Results:

Load 1000000 rows of test data starting at 2006-07-05 18:44:50.743

(1000000 row(s) affected)

Search for matching rows starting at 2006-07-05 18:45:07.070
Matches     
----------- 
286

(1 row(s) affected)

Done at 2006-07-05 18:45:08.040


CODO ERGO SUM
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/05/2006 :  19:06:29  Show Profile  Visit SwePeso's Homepage
Yes, that is speedy! Excellent execution plan. Best this far!

But is does not meet Zurbum's critera when attempting
SELECT COL1,COL2,COL3 FROM
(SELECT COL1, COL2,COL3, COL1+COL2+COL3 AS COL_SUM, COL1*COL2*COL3 AS COL_MUL FROM TABLE_X) AS TEMP
WHERE TEMP.COL_SUM=INPUT1+INPUT2+INPUT3 AND TEMP.COL_MUL=INPUT1*INPUT2*INPUT3
MVJ, your code is excellent and works very well when searching for 1, 4 and 7, because the search terms are all individually unique. But searching for 1, 1, 3 will give any row with at least one 1 and at least one 3. But you also fetch rows with no more than one 1, and that does not meet the critera above, because no other combination of numbers > 0 will give same sum and product.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/05/2006 19:10:24
Go to Top of Page

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 07/05/2006 :  20:59:13  Show Profile
Without more input from the poster, this is just an exercise in maSQLbation.
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 07/05/2006 :  21:18:42  Show Profile  Visit jsmith8858's Homepage
Exactly .... with some detailed and deterministic specs, it could make an interesting SQL challenge, but without clear rules, such a contest is pretty hard to judge !!

- Jeff
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

USA
7020 Posts

Posted - 07/05/2006 :  21:41:59  Show Profile
quote:
Originally posted by Peso

Yes, that is speedy! Excellent execution plan. Best this far!

But is does not meet Zurbum's critera when attempting
SELECT COL1,COL2,COL3 FROM
(SELECT COL1, COL2,COL3, COL1+COL2+COL3 AS COL_SUM, COL1*COL2*COL3 AS COL_MUL FROM TABLE_X) AS TEMP
WHERE TEMP.COL_SUM=INPUT1+INPUT2+INPUT3 AND TEMP.COL_MUL=INPUT1*INPUT2*INPUT3
MVJ, your code is excellent and works very well when searching for 1, 4 and 7, because the search terms are all individually unique. But searching for 1, 1, 3 will give any row with at least one 1 and at least one 3. But you also fetch rows with no more than one 1, and that does not meet the critera above, because no other combination of numbers > 0 will give same sum and product.


Peter Larsson
Helsingborg, Sweden



I don't think that query is a criteria, but just an attempt to solve the problem.

If he actually does want something like 1,1,3, he never said that. The only thing he really said was "Yees, there must be always 3 search numbers"

If he really does want 1,1,3 or 3,3,3, he was fairly clear that the order of occurance within the row did not matter. If that is the case, it will still be fairly fast to use the query I posted as a starting point by inserting the results into another declared table, and then using a UNION ALL/SUM/GROUP BY Primary Key query on COL1 to COL8 columns to find the rows where the counts match exactly. Since the union would be working with a far smaller result set, it should still be very fast.

I'm just not posting that query until I know it's wanted.





CODO ERGO SUM

Edited by - Michael Valentine Jones on 07/05/2006 21:54:44
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

USA
7020 Posts

Posted - 07/05/2006 :  21:53:37  Show Profile
quote:
Originally posted by jsmith8858

Exactly .... with some detailed and deterministic specs, it could make an interesting SQL challenge, but without clear rules, such a contest is pretty hard to judge !!

- Jeff


I think that few people who are capable of writing detailed and deterministic specs are posting questions here, because that requires a level of understanding of the problem that usually means they are capable of solving the problem on their own.




CODO ERGO SUM
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 07/05/2006 :  22:11:56  Show Profile  Visit jsmith8858's Homepage
quote:
Originally posted by Michael Valentine Jones

quote:
Originally posted by jsmith8858

Exactly .... with some detailed and deterministic specs, it could make an interesting SQL challenge, but without clear rules, such a contest is pretty hard to judge !!

- Jeff


I think that few people who are capable of writing detailed and deterministic specs are posting questions here, because that requires a level of understanding of the problem that usually means they are capable of solving the problem on their own.




CODO ERGO SUM



Exactly ! I talk about that here:

http://weblogs.sqlteam.com/jeffs/archive/2005/04/29/4832.aspx



- Jeff
Go to Top of Page

MichaelP
Jedi Yak

USA
2489 Posts

Posted - 07/05/2006 :  22:46:44  Show Profile  Visit MichaelP's Homepage
Jeff / MVJ,
I totally agree! The first step of problem solving is identifing the problem. If you can identify and describe it, you can probably solve it. If not, then you are going to have a real hard time solving the problem, and an even harder time getting others to guess at a solution for you.

Michael

<Yoda>Use the Search page you must. Find the answer you will. Cursors, path to the Dark Side they are. Avoid them, you must. Use Order By NewID() to get a random record you will.</Yoda>

Opinions expressed in this post are not necessarily those of TeleVox Software, inc. All information is provided "AS IS" with no warranties and confers no rights.
Go to Top of Page

zurbum
Yak Posting Veteran

Norway
55 Posts

Posted - 07/06/2006 :  01:25:45  Show Profile
What I wanted is, that if a user enters 3,2,1 the query returns records whitch match one of all permutations of 3,2,1.
Returning 1,1,3 is not valid unless the search was for 1,3,1.

I wrote a simple function which returns a hash string of sorted numbers. It's not very fast, but it works for sure.

function fn_Hash(col1 int, col2 int, col3 int)
returns varchar (64)
begin

declare @mytable table(num int)
declare @mytable_sorted table(item int identity(1,1), num int)
declare @hash varchar(64)

insert into @mytable (num) values (col1)
insert into @mytable (num) values (col2)
insert into @mytable (num) values (col3)

insert into @mytable_sorted
select num from @mytable order by num

SET @hash = str((select top 1 num from @mytable_sorted where item=1 order by num),2)
SET @hash = @hash+str((select top 1 num from @mytable_sorted where item=2 order by num),2)
SET @hash = @hash+str((select top 1 num from @mytable_sorted where item=3 order by num),2)


RETURNS REPLACE(@hash,' ','0')

END
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/06/2006 :  02:36:40  Show Profile  Visit SwePeso's Homepage
Zurbum, this is a quicker way to get the hash you want, the same way as you do today with staging table.
The difference is that there is no table for sorting, and only one select against table.
The drawback is that the algorithm only works for 3 values.
create function fn_Hash(@col1 tinyint, @col2 tinyint, @col3 tinyint)
returns varchar (6)
begin

declare @mytable table(num tinyint)
declare @hash varchar(6)

insert into @mytable (num)
select @col1 union all
select @col2 union all
select @col3

SELECT @hash = str(min(num), 2) + str(sum(num) - min(num) - max(num), 2) + str(max(num), 2) from @mytable

RETURN REPLACE(@hash, ' ', '0')

end

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/06/2006 03:03:51
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29910 Posts

Posted - 07/06/2006 :  02:50:07  Show Profile  Visit SwePeso's Homepage
The quickest way though for building your hash value, must be this
create function fn_Hash(@col1 tinyint, @col2 tinyint, @col3 tinyint)
returns varchar (6)
begin

declare @hash varchar(6)

IF @Col1 <= @Col2 AND @Col1 <= @Col3
	IF @Col2 <= @Col3
		select @hash = str(@col1, 2) +  str(@col2, 2) + str(@col3, 2)
	ELSE
		select @hash = str(@col1, 2) +  str(@col3, 2) + str(@col2, 2)
ELSE
	IF @Col2 <= @Col1 AND @Col2 <= @Col3
		IF @Col1 <= @Col3
			select @hash = str(@col2, 2) +  str(@col1, 2) + str(@col3, 2)
		ELSE
			select @hash = str(@col2, 2) +  str(@col3, 2) + str(@col1, 2)
	ELSE
		IF @Col1 <= @Col2
			select @hash = str(@col3, 2) +  str(@col1, 2) + str(@col2, 2)
		ELSE
			select @hash = str(@col3, 2) +  str(@col2, 2) + str(@col1, 2)

RETURN REPLACE(@hash, ' ', '0')

end

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 07/06/2006 02:50:48
Go to Top of Page
Page: of 4 Previous Topic Topic Next Topic  
Previous Page | Next Page
 Forum Locked
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.19 seconds. Powered By: Snitz Forums 2000