Facebook's new Graph Search is a big deal, but Google-killer it is not, even if it works exactly as Facebook promised, of which there's no guarantee. Facebook's not positioning it as such in any case, in fact, it says it wanted to work with Google but they couldn't reach an agreement.
Facebook Graph Search works with Facebook data, and it's designed to help you find stuff that's relevant to you and your friends.
But when it can't do that, it offloads your query to Bing which does a regular web search. Microsoft invested in Facebook several years back and the two have been pretty close up till now, though Microsoft's been giving more than it's taking.
Bing already powers web search on Facebook, continuing to do so isn't much of a surprise. But Zuckerberg, at the event showcasing the new search engine, actually addressed whether Facebook would work with Google.
"I think that the main thing is that when people share something on Facebook we want to give them the ability to broadcast something out and then take it down or set privacy settings," TechCrunch paraphrased
Zucker's answer to a question about partnering up with Google.
"That requires quick updating, removing photos. We also need that content to be gone if something changes their privacy settings," he added.
"You need infrastructure that can support that. Microsoft was more willing to do things that fit with Facebook. People want flexibility, and that was the stumbling block with Google in our last round of talks. I’m not sure if that was detail in the negotiation or rift between Facebook’s and Google’s strategies," he said.
While it's nice that he answered, he doesn't really say much. He tries to not come out as the bad guy, he tries to drum up Bing and put down Google, all without being too obvious.
The thing to take away though is that it does look like there have been , at least, some talks between Google and Facebook. That alone doesn't mean much though, either could have come with unreasonable demands so the talks wouldn't go anywhere.
Given Facebook's past record, it wasn't willing to give Google much data in return for the service, meaning Facebook search would be better but Google would not get anything out of it, except more searches and maybe a cut of the potential revenue from Graph Search.
This is what Facebook means by privacy here, it wanted to provide Google with a query and no user data at all.