SQL Server - Stored Procedure - Binary search algorithm
I've looking for how to create binary search procedure in sql, but i cant find it. Do you have any idea how can i do it?
Im using this test table:
declare @MyTable table (
id int identity (1,1),
UserName varchar(50),
DNI int,
Country varchar(50)
)
Suppose you have indexed the DNI field, which is the field we use to search the records. And therefore, they are ordered from highest to lowest. How can I obtain the data regarding a DNI, using the binary search?
sql
sql-server tsql asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
|
show 3 more comments
I've looking for how to create binary search procedure in sql, but i cant find it. Do you have any idea how can i do it?
Im using this test table:
declare @MyTable table (
id int identity (1,1),
UserName varchar(50),
DNI int,
Country varchar(50)
)
Suppose you have indexed the DNI field, which is the field we use to search the records. And therefore, they are ordered from highest to lowest. How can I obtain the data regarding a DNI, using the binary search?
sql
sql-server tsql asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
1
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
3
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
4
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
1
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48
|
show 3 more comments
I've looking for how to create binary search procedure in sql, but i cant find it. Do you have any idea how can i do it?
Im using this test table:
declare @MyTable table (
id int identity (1,1),
UserName varchar(50),
DNI int,
Country varchar(50)
)
Suppose you have indexed the DNI field, which is the field we use to search the records. And therefore, they are ordered from highest to lowest. How can I obtain the data regarding a DNI, using the binary search?
sql
sql-server tsql asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
I've looking for how to create binary search procedure in sql, but i cant find it. Do you have any idea how can i do it?
Im using this test table:
declare @MyTable table (
id int identity (1,1),
UserName varchar(50),
DNI int,
Country varchar(50)
)
Suppose you have indexed the DNI field, which is the field we use to search the records. And therefore, they are ordered from highest to lowest. How can I obtain the data regarding a DNI, using the binary search?
sql
sql-server tsql sql
sql-server tsql asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
asked Nov 14 '18 at 12:59
Raul EscalonaRaul Escalona
456
456
1
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
3
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
4
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
1
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48
|
show 3 more comments
1
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
3
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
4
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
1
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48
1
1
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
3
3
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
4
4
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
1
1
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48
|
show 3 more comments
2 Answers
2
active
oldest
votes
If we use the logic of the binary search along with the effect of the
indexes, I think you could have a query much faster and without
consuming so many resources. What you think?
I don't think so. Even starting with a list of pages for a table, ordered by the key value (which SQL Server doesn't maintain) a BTree traversal would outperform a Binary Search.
A Binary Search of a sorted list eliminates half the target pages with each read. If the rows are not distributed evenly, you could eliminate less than half the remaining rows with a read.
As you traverse a BTree you eliminate (N-1)/N of the rows, where N is the number of (index key, page pointer) tuples on a non-leaf page, typically in the 100s. And since the tree is "balanced" you can consistently traverse to a the target page with 3 or 4 reads for any size table.
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
add a comment |
You cannot implement a binary search algorithm in TSQL (user level) faster that one implemented at the core level. However, you can create a clustered key (or clustered index for temporary table) on DNI column that physically reorganize the table data in memory in strict order. Hence, the search will be fastest.
answered Nov 14 '18 at 14:50
sergeserge
60047
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53300844%2fsql-server-stored-procedure-binary-search-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
If we use the logic of the binary search along with the effect of the
indexes, I think you could have a query much faster and without
consuming so many resources. What you think?
I don't think so. Even starting with a list of pages for a table, ordered by the key value (which SQL Server doesn't maintain) a BTree traversal would outperform a Binary Search.
A Binary Search of a sorted list eliminates half the target pages with each read. If the rows are not distributed evenly, you could eliminate less than half the remaining rows with a read.
As you traverse a BTree you eliminate (N-1)/N of the rows, where N is the number of (index key, page pointer) tuples on a non-leaf page, typically in the 100s. And since the tree is "balanced" you can consistently traverse to a the target page with 3 or 4 reads for any size table.
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
add a comment |
If we use the logic of the binary search along with the effect of the
indexes, I think you could have a query much faster and without
consuming so many resources. What you think?
I don't think so. Even starting with a list of pages for a table, ordered by the key value (which SQL Server doesn't maintain) a BTree traversal would outperform a Binary Search.
A Binary Search of a sorted list eliminates half the target pages with each read. If the rows are not distributed evenly, you could eliminate less than half the remaining rows with a read.
As you traverse a BTree you eliminate (N-1)/N of the rows, where N is the number of (index key, page pointer) tuples on a non-leaf page, typically in the 100s. And since the tree is "balanced" you can consistently traverse to a the target page with 3 or 4 reads for any size table.
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
add a comment |
If we use the logic of the binary search along with the effect of the
indexes, I think you could have a query much faster and without
consuming so many resources. What you think?
I don't think so. Even starting with a list of pages for a table, ordered by the key value (which SQL Server doesn't maintain) a BTree traversal would outperform a Binary Search.
A Binary Search of a sorted list eliminates half the target pages with each read. If the rows are not distributed evenly, you could eliminate less than half the remaining rows with a read.
As you traverse a BTree you eliminate (N-1)/N of the rows, where N is the number of (index key, page pointer) tuples on a non-leaf page, typically in the 100s. And since the tree is "balanced" you can consistently traverse to a the target page with 3 or 4 reads for any size table.
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
If we use the logic of the binary search along with the effect of the
indexes, I think you could have a query much faster and without
consuming so many resources. What you think?
I don't think so. Even starting with a list of pages for a table, ordered by the key value (which SQL Server doesn't maintain) a BTree traversal would outperform a Binary Search.
A Binary Search of a sorted list eliminates half the target pages with each read. If the rows are not distributed evenly, you could eliminate less than half the remaining rows with a read.
As you traverse a BTree you eliminate (N-1)/N of the rows, where N is the number of (index key, page pointer) tuples on a non-leaf page, typically in the 100s. And since the tree is "balanced" you can consistently traverse to a the target page with 3 or 4 reads for any size table.
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
answered Nov 14 '18 at 19:23
David Browne - MicrosoftDavid Browne - Microsoft
15.5k2626
15.5k2626
add a comment |
add a comment |
You cannot implement a binary search algorithm in TSQL (user level) faster that one implemented at the core level. However, you can create a clustered key (or clustered index for temporary table) on DNI column that physically reorganize the table data in memory in strict order. Hence, the search will be fastest.
answered Nov 14 '18 at 14:50
sergeserge
60047
add a comment |
You cannot implement a binary search algorithm in TSQL (user level) faster that one implemented at the core level. However, you can create a clustered key (or clustered index for temporary table) on DNI column that physically reorganize the table data in memory in strict order. Hence, the search will be fastest.
answered Nov 14 '18 at 14:50
sergeserge
60047
add a comment |
You cannot implement a binary search algorithm in TSQL (user level) faster that one implemented at the core level. However, you can create a clustered key (or clustered index for temporary table) on DNI column that physically reorganize the table data in memory in strict order. Hence, the search will be fastest.
answered Nov 14 '18 at 14:50
sergeserge
60047
You cannot implement a binary search algorithm in TSQL (user level) faster that one implemented at the core level. However, you can create a clustered key (or clustered index for temporary table) on DNI column that physically reorganize the table data in memory in strict order. Hence, the search will be fastest.
answered Nov 14 '18 at 14:50
sergeserge
60047
edited Nov 14 '18 at 19:05
answered Nov 14 '18 at 14:50
sergeserge
60047
answered Nov 14 '18 at 14:50
sergeserge
60047
answered Nov 14 '18 at 14:50
sergeserge
60047
60047
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53300844%2fsql-server-stored-procedure-binary-search-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Just use an index.
– Gordon Linoff
Nov 14 '18 at 13:00
@GordonLinoff I know that the indexes increase the speed of the query in an incredible way, but I have a table with millions of data and I want to do faster searches with fewer iterations. If we use the logic of the binary search along with the effect of the indexes, I think you could have a query much faster and without consuming so many resources. What you think?
– Raul Escalona
Nov 14 '18 at 13:03
3
You don't have direct access to the data structures used to implement the tables so you can't. Most likely this is an XY problem
– SMor
Nov 14 '18 at 13:05
4
The idea that any code written in T-SQL could outspeed the built-in algorithms for traversing B-tree indexes is just wrong. You don't really think the engineers at Microsoft would be unfamiliar with binary search as an algorithm, do you? Searching rows based on an index value is already an O(log n) operation. If your queries aren't fast enough, there's things you can do about it, but writing your own index search algorithm isn't one of them.
– Jeroen Mostert
Nov 14 '18 at 13:48
1
Certainly with using indexes for your search and not handcrafting search implementations for speed. SQL is a declarative language, you are free to say what data you require, you shouldnt need to/specify the path it should take. Let the optimizer do its work, to help the optimizer, keep the statistics up-date, constraints intact,store the correct data-type and you should be good.
– George Joseph
Nov 14 '18 at 14:48